Nathan Keller



I am a Professor at the Mathematics Department of the Bar Ilan University.


Before coming to the Bar Ilan University, I completed my Ph.D. at the Einstein Institute of Mathematics  in the Hebrew University of Jerusalem, under the supervision of Prof. Gil Kalai, and was a Post-Doc at the Weizmann Institute of Science, hosted by Prof. Elchanan Mossel. In addition, I was fortunate to work under the supervision of Prof. Daniel Hershkowitz (my M.Sc. advisor), and (unofficially) Prof. Eli Biham and Prof. Adi Shamir.


My fields of research are Combinatorics (mainly probabilistic combinatorics and discrete Fourier analysis) and Cryptography (mainly cryptanalysis of symmetric-key cryptosystems).

My CV can be found here. My e-mail address is Nathan.Keller At biu.ac.il

My wife, Chaya, is also a mathematician. Her website can be found here.


Students and Post-Docs:

I have the opportunity to supervise a group of great students, which includes:

  1. Eran Lambooij (Post-doc, started in 2023).
  2. Omri Marcus (M.Sc. student, expected graduation: 2024).
  3. Ohad Sheinfeld (M.Sc. student, expected graduation: 2024).
  4. Asaf Rosemarin (M.Sc. student, expected graduation: 2024).
  5. David Ross (M.Sc. student, expected graduation: 2025).
  6. Nitay Reiter (M.Sc. student, expected graduation: 2026).

The former students and post-docs I was very fortunate to supervise are: Rani Hod (Post-doctoral fellow, 2016-2019), Ariel Weizmann (Ph.D., 2023; M.Sc., 2017, both joint with Prof. Orr Dunkelman), Ohad Klein (Ph.D., 2022; M.Sc., 2017), Achiya Bar On (Ph.D., 2019; M.Sc., 2015. The M.Sc. was joint with Prof. Boaz Tsaban), Yuval Beker (M.Sc., 2020, joint with Prof. Boaz Tsaban), Aviya Vaidberg (M.Sc., 2017), and Noam Lifshitz (M.Sc., 2016).

Publications:

Journal Papers:

  1. N. Keller, N. Lifshitz, and O. Sheinfeld Improved covering results for conjugacy classes of symmetric groups via hypercontractivity, Forum of Mathematics, Sigma, to appear.
  2. D. Ellis, N. Keller, and N. Lifshitz, Stability for the Complete Intersection Theorem, and the Forbidden Intersection Problem of Erdos and Sos, Journal of the European Mathematical Society, 26(5) (2024), pp. 1611-1654.
  3. I. Dinur, N. Keller, and O. Klein, Fine-grained cryptanalysis: Tight conditional bounds for dense k-SUM and k-XOR , Journal of the ACM, 71(3) (2024), 23, pp. 1-41.
  4. N. Keller, N. Lifshitz, D. Minzer, and O. Sheinfeld, On t-intersecting families of permutations, Advances in Mathematics, 445 (2024), 109650, pp. 1-28.
  5. O. Dunkelman, N. Keller, E. Ronen, and A. Shamir, The retracing boomerang attack, with application to reduced-round AES, Journal of Cryptology, 37 (2024), 32, pp. 1-42.
  6. O. Dunkelman, N. Keller, E. Ronen, and A. Shamir, Quantum time/memory/data tradeoff attacks, Design, Codes, and Cryptography, 92(1) (2024), pp. 159-177.
  7. N. Keller and O. Klein, Proof of Tomaszewski's conjecture on randomly signed sums, Advances in Mathematics, 407 (2022), 108558, pp. 1-39.
  8. O. Dunkelman, M. Eichlseder, D. Kales, N. Keller, G. Leurent, and M. Schofnegger, Practical key-recovery attacks on FLEX-AEAD, Design, Codes, and Cryptography, 90 (2022), pp. 983-1007.
  9. N. Keller and N. Lifshitz, The junta method for hypergraphs and the Erdos-Chvatal simplex conjecture, Advances in Mathematics, 392 (2021), 107991, pp. 1-95.
  10. N. Keller and O. Klein, A structure theorem for almost low-degree functions on the slice, Israel Journal of Mathematics, 240 (2020), pp. 179-221.
  11. A. Bar-On, O. Dunkelman, N. Keller, E. Ronen, and A. Shamir, Improved key recovery attacks on AES with practical data and memory complexities, Journal of Cryptology, 33(3) (2020), pp. 1003-1043.
  12. I. Dinur, N. Keller, and O. Klein, An optimal distributed discrete log protocol with applications to homomorphic secret sharing, Journal of Cryptology, 33(3) (2020), pp. 824-873.
  13. O. Dunkelman, N. Keller, E. Lambooij, and Y. Sasaki, A practical forgery attack on Lilliput-AE, Journal of Cryptology, 33(3) (2020), pp. 910-916.
  14. A. Bar-On, I. Dinur, O. Dunkelman, R. Hod, N. Keller, E. Ronen, and A. Shamir, Tight bounds on online checkpointing algorithms, ACM Transactions on Algorithms, 16(3) (2020), pp. 31:1-31:22.
  15. D. Ellis, N. Keller, and N. Lifshitz, Stability versions of Erdos-Ko-Rado type theorems, via isoperimetry, Journal of the European Mathematical Society, 21(12) (2019), pp. 3857-3902.
  16. N. Keller and O. Klein, Biased halfspaces, noise sensitivity, and relative Chernoff inequalities, Discrete Analysis, 2019:13 (2019), pp. 1-50.
  17. I. Dinur, O. Dunkelman, N. Keller, and A. Shamir, Efficient dissection of bicomposite problems with cryptanalytic applications, Journal of Cryptology, 32(4) (2019), pp. 1448-1490.
  18. N. Keller and N. Lifshitz, A note on large H-intersecting families, SIAM Journal on Discrete Mathematics, 33(1) (2019), pp. 398-401.
  19. D. Ellis, N. Keller, and N. Lifshitz, On a biased edge isoperimetric inequality for the discrete cube, Journal of Combinatorial Theory, Series A, 163 (2019), pp. 118-162.
  20. N. Keller and N. Lifshitz, Approximation of biased Boolean functions of small total influence by DNF's, Bulletin of the London Mathematical Society, 50(4) (2018), pp. 667-679.
  21. D. Ellis, N. Keller, and N. Lifshitz, On the structure of subsets of the discrete cube with small edge boundary, Discrete Analysis, 2018:9 (2018), pp. 1-29.
  22. A. Bar-On, E. Biham, O. Dunkelman, and N. Keller, Efficient slide attacks, Journal of Cryptology, 31(3) (2018), pp. 641-670.
  23. E. Friedgut, J. Kahn, G. Kalai, and N. Keller, Chvatal's conjecture and correlation inequalities, Journal of Combinatorial Theory, Series A, 156 (2018), pp. 22-43.
  24. G. Kalai, N. Keller, and E. Mossel, On the correlation of increasing families, Journal of Combinatorial Theory, Series A, 144 (2016), pp. 250-276.
  25. I. Benjamini, D. Ellis, E. Friedgut, N. Keller, and A. Sen, Juntas in the ell_1-grid and Lipschitz maps between discrete tori, Random Structures and Algorithms 49(2) (2016), pp. 253-279.
  26. Y. Filmus, H. Hatami, N. Keller, and N. Lifshitz, Bounds on the sum of L1 influences, Israel Journal of Mathematics, 214(1) (2016), pp. 167-192.
  27. I. Dinur, O. Dunkelman, N. Keller, and A. Shamir, Key-recovery attacks on iterated Even-Mansour encryption schemes, Journal of Cryptology, 29(4) (2016), pp. 697-728.
  28. O. Dunkelman, N. Keller, and A. Shamir, Improved single-key attacks on 8-round AES-192 and AES-256, Journal of Cryptology, 28(3) (2015), pp. 397-422.
  29. E. Biham, O. Dunkelman, N. Keller, and A. Shamir, New data-efficient attacks on reduced-round variants of IDEA, Journal of Cryptology, 28(2) (2015), pp. 209-239.
  30. O. Dunkelman, N. Keller, and A. Shamir, Slidex attacks on the Even-Mansour encryption scheme, Journal of Cryptology, 28(1) (2015), pp. 1-28.
  31. I. Dinur, O. Dunkelman, N. Keller, and A. Shamir, Reflections on slide with a twist attacks, Design, Codes, and Cryptography, 77(2-3) (2015), pp. 633-651.
  32. O. Dunkelman, N. Keller, and A. Shamir, Almost universal forgery attacks on AES-based MACs, Design, Codes and Cryptography, 76(3) (2015), pp. 431-449.
  33. O. Dunkelman and N. Keller, Practical-time attacks on reduced-round Misty1, Design, Codes and Cryptography, 76(3) (2015), pp. 601-627.
  34. N. Keller, E. Mossel, and A. Sen, Geometric influences II: Correlation inequalities and noise sensitivity, Annales de l'Institut Henri Poincare, 50(4) (2014), pp. 1121–1139.
  35. I. Dinur, O. Dunkelman, N. Keller, and A. Shamir, Dissection: A new paradigm for solving bicomposite search problems, Communications of the ACM, 57(10) (2014), pp. 98-105.
  36. O. Dunkelman, N. Keller, and A. Shamir, A practical-time related-key attack on the KASUMI cryptosystem used in GSM and 3G telephony, Journal of Cryptology, 27(4) (2014), pp. 824-849.
  37. N. Keller and G. Kindler, Quantitative relation between noise sensitivity and influences, Combinatorica, 33(1) (2013), pp. 45-71.
  38. O. Dunkelman and N. Keller, Cryptanalysis of the stream cipher LEX, Design, Codes, and Cryptography, 67(3) (2013), pp. 357-373.
  39. N. Keller, A tight quantitative version of Arrow's impossibility theorem, Journal of the European Mathematical Society, 14(5) (2012), pp. 1331-1355.
  40. N. Keller, E. Mossel, and A. Sen, Geometric influences, Annals of Probability, 40(3) (2012), pp. 1135-1166.
  41. N. Keller, A simple reduction from a biased measure on the discrete cube to the uniform measure, European Journal of Combinatorics, 33(8) (2012), pp. 1943-1957.
  42. N. Keller, E. Mossel, and T. Schlank, A note on the entropy/influence conjecture, Discrete Mathematics, 312(22) (2012), pp. 3364-3372.
  43. C. Bouillaguet, O. Dunkelman, P.A. Fouque, N. Keller, and V. Rijmen, Low data complexity attacks on AES, IEEE Transactions on Information Theory, 58(11) (2012), pp. 7002-7017.
  44. J. Kim, S. Hong, B. Preneel, E. Biham, O. Dunkelman, and N. Keller, Related-key boomerang and rectangle attacks: Theory and experimental verification, IEEE Transactions on Information Theory, 58(7) (2012), pp. 4948-4966.
  45. W. Aerts, E. Biham, D. de Moitie, E. de Mulder, O. Dunkelman, S. Indesteege, N. Keller, B. Preneel, G. Vandenbosch, and I. Verbauwhede, A practical attack on KeeLoq, Journal of Cryptology, 25(1) (2012), pp. 136-157.
  46. E. Friedgut, G. Kalai, N. Keller, and N. Nisan, A quantitative version of the Gibbard-Satterthwaite theorem for three alternatives, SIAM Journal on Computing, 40(3) (2011), pp. 934-952.
  47. N. Keller, On the influences of variables on Boolean functions in product spaces, Combinatorics, Probability and Computing, 20(1) (2011), pp. 83-102.
  48. N. Keller, On the probability of a rational outcome for generalized social welfare functions on three alternatives, Journal of Combinatorial Theory Series A, 117(4) (2010), pp. 389-410.
  49. O. Dunkelman and N. Keller, The effects of the omission of last round's MixColumns on AES, Information Processing Letters 110 (2010), pp. 304-308.
  50. N. Keller and S. D. Miller, Distinguishing attacks on stream ciphers based on arrays of pseudo-random words, Information Processing Letters 110 (2010), pp. 129-132.
  51. N. Keller, On the correlation between monotone families in the average case, Advances in Applied Mathematics, 43(1) (2009), pp. 31-45.
  52. N. Keller and H. Pilpel, Linear transformations of monotone functions on the discrete cube, Discrete Mathematics, 309(12) (2009), pp. 4210-4214.
  53. E. Barkan, E. Biham, and N. Keller, Instant ciphertext-only cryptanalysis of GSM encrypted communication, Journal of Cryptology, 21(3) (2008), pp. 392-429.
  54. O. Dunkelman and N. Keller, Treatment of the initial value in time-memory-data tradeoff attacks on stream ciphers, Information Processing Letters 107 (2008), pp. 133-137.
  55. O. Dunkelman and N. Keller, A new criterion for nonlinearity of block ciphers, IEEE Transactions on Information Theory, 53(11) (2007), pp. 3944-3957.
  56. D. Hershkowitz and N. Keller, Spectral properties of sign symmetric matrices, Electronic Journal of Linear Algebra, 13 (2005), pp. 90-110.
  57. D. Hershkowitz and N. Keller, Positivity of principal minors, sign symmetry and stability, Linear Algebra and its Applications, 364 (2003), pp. 105-124.

Conference Papers:

Most of the papers below were presented in peer reviewed conferences in Cryptography and published in the series "Lecture Notes in Computer Science" (LNCS) of Springer-Verlag.
  1. O. Dunkelman, S. Ghosh, N. Keller, G. Leurent, A. Marmor, and V. Mollimard, Partial sums meet FFT: Improved attack on 6-round AES, Eurocrypt 2024 (1), LNCS 14651, pp. 128-157.
  2. O. Dunkelman, N. Keller, and A. Weizman, Practical-time related-key attack on GOST with secret S-boxes, Crypto 2023 (3), LNCS 14083, pp. 177-208.
  3. I. Dinur, O. Dunkelman, N. Keller, E. Ronen, and A. Shamir, Efficient detection of high probability statistical properties of cryptosystems via surrogate differentiation, Eurocrypt 2023 (4), LNCS 14007, pp. 98-127.
  4. E. Boyle, I. Dinur, N. Gilboa, Y. Ishai, N. Keller, and O. Klein, Locality-preserving hashing for shifts, with connections to cryptography, ITCS 2022, pp. 21:1-27:24.
  5. I. Dinur, N. Keller, and O. Klein, Fine-grained cryptanalysis: Tight conditional bounds for dense k-SUM and k-XOR, FOCS 2021, pp.80-91.
  6. N. Keller and O. Klein, Local concentration inequalities and Tomaszewski's conjecture, STOC 2021, pp. 1656-1669.
  7. O. Amon, O. Dunkelman, N. Keller, E. Ronen, and A. Shamir, Three third generation attacks on the Format Preserving Encryption scheme FF3, Eurocrypt 2021 (2), LNCS 12697, pp. 127-154.
  8. N. Keller and A. Rosemarin, Mind the Middle Layer: The HADES Design Strategy Revisited, Eurocrypt 2021 (2), LNCS 12697, pp. 35-63.
  9. O. Dunkelman, Z. Geyzel, C. Keller, N. Keller, E. Ronen, A. Shamir, and R. Tessler, Error-resilient space partitioning, ICALP 2021, LIPIcs 198, pp. 4:1-4:22.
  10. O. Dunkelman, N. Keller, N. Lasry, and A. Shamir, New slide attacks on almost self similar ciphers, Eurocrypt 2020 (1), LNCS 12105, pp. 250-279.
  11. O. Dunkelman, N. Keller, E. Ronen, and A. Shamir, The retracing boomerang attack, Eurocrypt 2020 (1), LNCS 12105, pp. 280-309.
  12. A. Bar-On, O. Dunkelman, N. Keller, and A. Weizmann, DLCT: A new tool for differential-linear cryptanalysis, Eurocrypt 2019 (1), LNCS 11476, pp. 313-342.
  13. A. Bar-On, O. Dunkelman, N. Keller, E. Ronen, and A. Shamir, Improved key recovery attacks on AES with practical data and memory complexities, Crypto 2018 (2), LNCS 10992, pp. 185-212.
  14. I. Dinur, N. Keller, and O. Klein, An optimal distributed discrete log protocol with applications to homomorphic secret sharing, Crypto 2018 (3), LNCS 10993, pp. 213-242.
  15. A. Bar-On, I. Dinur, O. Dunkelman, R. Hod, N. Keller, E. Ronen, and A. Shamir, Tight bounds on online checkpointing algorithms, ICALP 2018, LIPICS 107, pp. 13:1-13:13.
  16. N. Keller and N. Lifshitz, The junta method in extremal hypergraph theory and Chvatal's conjecture, Eurocomb 2017, Electronic Notes in Discrete Mathematics, 61 (2017), pp. 711-717.
  17. J. Cho, K.-Y. Choi, I. Dinur, O. Dunkelman, N. Keller, D. Moon, and A. Vaidberg, WEM: A new family of white-box block ciphers based on the Even-Mansour construction, CT-RSA 2017, LNCS 10159, pp. 293-308.
  18. J. Cho, K.-Y. Choi, O. Dunkelman, N. Keller, D. Moon, and A. Vaidberg, Hybrid WBC: Secure and efficient white-box encryption schemes, CANS 2016, LNCS 10052, pp. 749-754.
  19. A. Bar-On and N. Keller, A 2^70 attack on the full Misty1, Crypto 2016 (1), LNCS 9814, pp. 435-456.
  20. I. Dinur, O. Dunkelman, N. Keller, and A. Shamir, Memory-efficient algorithms for finding needles in haystacks, Crypto 2016 (2), LNCS 9815, pp. 185-206.
  21. I. Dinur, O. Dunkelman, N. Keller, and A. Shamir, New attacks on Feistel structures with improved memory complexities, Crypto 2015, LNCS 9215, pp. 433-454.
  22. A. Bar-On, I. Dinur, O. Dunkelman, N. Keller, V. Lallemand, and B. Tsaban, Cryptanalysis of SP networks with partial non-linear layers, Eurocrypt 2015, LNCS 9056, pp. 315-342.
  23. I. Dinur, O. Dunkelman, N. Keller, and A. Shamir, Cryptanalysis of iterated Even-Mansour schemes with two keys, Asiacrypt 2014, LNCS 8873, pp. 439-457.
  24. I. Dinur, O. Dunkelman, N. Keller, and A. Shamir, Improved linear sieving techniques, with applications to step-reduced LED-64, FSE 2014, LNCS 8540, pp. 390-410.
  25. I. Dinur, O. Dunkelman, N. Keller, and A. Shamir, Key-recovery attacks on 3-round Even-Mansour, 8-step LED-128, and full AES^2, Asiacrypt 2013, LNCS 8269, pp. 337-356.
  26. I. Dinur, O. Dunkelman, N. Keller, and A. Shamir, Efficient dissection of composite problems, with applications to Cryptanalysis, Knapsacks and Combinatorial search problems, Crypto 2012, LNCS 7417, pp. 719-740.
  27. O. Dunkelman, N. Keller, and A. Shamir, Minimalism in cryptography: the Even-Mansour cryptosystem revisited, Eurocrypt 2012, LNCS 7237, pp. 336-354.
  28. O. Dunkelman, N. Keller, and A. Shamir, Improved single key attacks on 8-round AES-192 and AES-256, Asiacrypt 2010, LNCS 6477, pp. 158-176.
  29. O. Dunkelman, N. Keller, and A. Shamir, A practical-time attack on the KASUMI cryptosystem used in GSM and 3G telephony, Crypto 2010, LNCS 6223, pp. 393-410.
  30. A. Biryukov, O. Dunkelman, N. Keller, D. Khovratovich, and A. Shamir, Key recovery attacks of practical complexity on AES-256 variants with up to 10 rounds, Eurocrypt 2010, LNCS 6110, pp. 299-319.
  31. O. Dunkelman and N. Keller, Cryptanalysis of CTC2, CT-RSA 2009, LNCS 5473, pp. 226-239.
  32. O. Dunkelman and N. Keller, An improved impossible differential attack on Misty1, Asiacrypt 2008, LNCS 5350, pp. 441-454.
  33. O. Dunkelman and N. Keller, A new attack on the LEX stream cipher, Asiacrypt 2008, LNCS 5350, pp. 539-556.
  34. J. Lu, O. Dunkelman, N. Keller, and J. Kim, New impossible differential attacks on AES, Indocrypt 2008, LNCS 5365, pp. 279-293.
  35. O. Dunkelman, S. Indesteege, and N. Keller, A differential-linear attack on 12-round Serpent, Indocrypt 2008, LNCS 5365, pp. 308-321.
  36. S. Indesteege, N. Keller, O. Dunkelman, E. Biham, and B. Preneel, A practical attack on KeeLoq, Eurocrypt 2008, LNCS 4965, pp. 1-18.
  37. E. Biham, O. Dunkelman, and N. Keller, A unified approach to related key attacks, FSE 2008, LNCS 5086, pp. 73-96.
  38. J. Lu, J. Kim, N. Keller, and O. Dunkelman, Improving the efficiency of impossible differential cryptanalysis of reduced Camellia and Misty1, CT-RSA 2008, LNCS 4964, pp. 370-386.
  39. G. Wang, N. Keller, and O. Dunkelman, The delicate issues of addition with respect to XOR differences, SAC 2007, LNCS 4876, pp. 212-231.
  40. N.Keller, S. Miller, I. Mironov, and R. Venkatesan, MV3: A new stream cipher based on random walks and revolving buffers, CT-RSA 2007, LNCS 4377, pp. 1-19.
  41. E. Biham, O. Dunkelman, and N. Keller, Improved slide attacks, FSE 2007, LNCS 4593, pp. 153-166.
  42. E. Biham, O. Dunkelman, and N. Keller, A new attack on 6-Round IDEA, FSE 2007, LNCS 4593, pp. 211-224.
  43. E. Biham, O. Dunkelman, and N. Keller, A simple related-key attack on the full SHACAL-1, CT-RSA 2007, LNCS 4377, pp. 20-30.
  44. E. Biham, O. Dunkelman, and N. Keller, New cryptanalytic results on IDEA, Asiacrypt 2006, LNCS 4284, pp. 412-427.
  45. J. Lu, J. Kim, N. Keller, and O. Dunkelman, Differential and rectangle attacks on reduced-round SHACAL-1, Indocrypt 2006, LNCS 4329, pp. 17-31.
  46. O. Dunkelman, N. Keller, and J. Kim, Related-key rectangle attack on the full SHACAL-1, SAC 2006, LNCS 4356, pp. 28-44.
  47. J. Lu, J. Kim, N. Keller, and O. Dunkelman, Related-key rectangle attack on 42-round SHACAL-2, ISC 2006, LNCS 4176, pp. 85-100.
  48. E. Biham, O. Dunkelman and N. Keller, Related-key impossible differential attacks on 8-round AES-192, CT-RSA 2006, LNCS 3860, pp. 21-33.
  49. O. Dunkelman and N. Keller, A new criterion for nonlinearity of block ciphers, CT-RSA 2006, LNCS 3860, pp. 295-312.
  50. E. Biham, O. Dunkelman and N. Keller, Related-key rectangle attack on the full KASUMI, Asiacrypt 2005, LNCS 3788, pp. 443-461.
  51. E. Biham, O. Dunkelman, and N. Keller, Related-key boomerang and rectangle attacks, Eurocrypt 2005, LNCS 3494, pp. 507-525.
  52. E. Biham, O. Dunkelman, and N. Keller, New combined attacks on block ciphers, FSE 2005, LNCS 3557, pp. 126-144.
  53. E. Barkan, E. Biham, and N. Keller, Instant ciphertext-only cryptanalysis of GSM encrypted communication, Crypto 2003, LNCS 2729, pp. 600-616.
  54. E. Biham, O. Dunkelman, and N. Keller, Rectangle attacks on 49-round SHACAL-1, FSE 2003, LNCS 2883, pp. 22-35.
  55. E. Biham, O. Dunkelman, and N. Keller, Differential-linear cryptanalysis of Serpent, FSE 2003, LNCS 2883, pp. 9-21.
  56. E. Biham, O. Dunkelman, and N. Keller, Enhancing differential-linear cryptanalysis, Asiacrypt 2002, LNCS 2501, pp. 254-266.
  57. E. Biham, O. Dunkelman and N. Keller, New results on boomerang and rectangle attacks, FSE 2002, LNCS 2365, pp. 1-16.
  58. E. Biham, O. Dunkelman and N. Keller, The rectangle attack -- rectangling the Serpent, Eurocrypt 2001, LNCS 2045, pp. 340-357.
  59. E. Biham, O. Dunkelman and N. Keller, Linear cryptanalysis of reduced-round Serpent, FSE 2001, LNCS 2355, pp. 16-27.


Last updated: 14.9.2024