Nathan Keller



I am an Associate 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 (unoficially) 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.keller27 At gmail.com

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


Students:

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

  1. Rani Hod (Post-doc fellow, started in 2016).
  2. Achiya Bar-On (Ph.D. student, started in 2015).
  3. Noam Lifshitz (finished M.Sc. in 2016).
  4. Aviya Vaidberg (M.Sc. student, started in 2015).
  5. Ariel Weizmann (M.Sc. student, started in 2015).
  6. Ohad Klein (M.Sc. student, started in 2015).
  7. Omri Marcus (M.Sc. student, started in 2015).

Publications:

Preprints:

  1. D. Ellis, N. Keller, and N. Lifshitz, On the structure of subsets of the discrete cube with small edge boundary, submitted.
  2. N. Keller and N. Lifshitz, On large H-intersecting families, submitted.
  3. E. Friedgut, J. Kahn, G. Kalai, and N. Keller, Chvatal's conjecture and correlation inequalities, submitted.
  4. N. Keller and N. Lifshitz, A tight stability version of the Complete Intersection Theorem, submitted.
  5. D. Ellis, N. Keller, and N. Lifshitz, Stability versions of Erdos-Ko-Rado type theorems, via isoperimetry, submitted.
  6. A. Bar-On, E. Biham, O. Dunkelman, and N. Keller, Efficient slide attacks, submitted.

Journal Papers:

  1. G. Kalai, N. Keller, and E. Mossel, On the correlation of increasing families, Journal of Combinatorial Theory, Series A, 144 (2016), pp. 250-276.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. O. Dunkelman, N. Keller, and A. Shamir, Slidex attacks on the Even-Mansour encryption scheme, Journal of Cryptology, 28(1) (2015), pp. 1-28.
  8. 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.
  9. 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.
  10. O. Dunkelman and N. Keller, Practical-time attacks on reduced-round Misty1, Design, Codes and Cryptography, 76(3) (2015), pp. 601-627.
  11. 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.
  12. 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.
  13. 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.
  14. N. Keller and G. Kindler, Quantitative relation between noise sensitivity and influences, Combinatorica, 33(1) (2013), pp. 45-71.
  15. O. Dunkelman and N. Keller, Cryptanalysis of the stream cipher LEX, Design, Codes, and Cryptography, 67(3) (2013), pp. 357-373.
  16. N. Keller, A tight quantitative version of Arrow's impossibility theorem, Journal of the European Mathematical Society, 14(5) (2012), pp. 1331-1355.
  17. N. Keller, E. Mossel, and A. Sen, Geometric influences, Annals of Probability, 40(3) (2012), pp. 1135-1166.
  18. 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.
  19. N. Keller, E. Mossel, and T. Schlank, A note on the entropy/influence conjecture, Discrete Mathematics, 312(22) (2012), pp. 3364-3372.
  20. 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.
  21. 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.
  22. 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.
  23. 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.
  24. N. Keller, On the influences of variables on Boolean functions in product spaces, Combinatorics, Probability and Computing, 20(1) (2011), pp. 83-102.
  25. 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.
  26. 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.
  27. 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.
  28. N. Keller, On the correlation between monotone families in the average case, Advances in Applied Mathematics, 43(1) (2009), pp. 31-45.
  29. N. Keller and H. Pilpel, Linear transformations of monotone functions on the discrete cube, Discrete Mathematics, 309(12) (2009), pp. 4210-4214.
  30. E. Barkan, E. Biham, and N. Keller, Instant ciphertext-only cryptanalysis of GSM encrypted communication, Journal of Cryptology, 21(3) (2008), pp. 392-429.
  31. 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.
  32. O. Dunkelman and N. Keller, A new criterion for nonlinearity of block ciphers, IEEE Transactions on Information Theory, 53(11) (2007), pp. 3944-3957.
  33. D. Hershkowitz and N. Keller, Spectral properties of sign symmetric matrices, Electronic Journal of Linear Algebra, 13 (2005), pp. 90-110.
  34. 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:

The papers below were presented in peer reviewed conferences in Cryptography and published in the series "Lecture Notes of Computer Science" (LNCS) of Springer-Verlag.
  1. A. Bar-On and N. Keller, A 2^70 attack on the full Misty1, Crypto 2016 (1), LNCS 9814, pp. 435-456.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. O. Dunkelman, N. Keller, and A. Shamir, Minimalism in cryptography: the Even-Mansour cryptosystem revisited, Eurocrypt 2012, LNCS 7237, pp. 336-354.
  10. 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.
  11. 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.
  12. 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.
  13. O. Dunkelman and N. Keller, Cryptanalysis of CTC2, CT-RSA 2009, LNCS 5473, pp. 226-239.
  14. O. Dunkelman and N. Keller, An improved impossible differential attack on Misty1, Asiacrypt 2008, LNCS 5350, pp. 441-454.
  15. O. Dunkelman and N. Keller, A new attack on the LEX stream cipher, Asiacrypt 2008, LNCS 5350, pp. 539-556.
  16. J. Lu, O. Dunkelman, N. Keller, and J. Kim, New impossible differential attacks on AES, Indocrypt 2008, LNCS 5365, pp. 279-293.
  17. O. Dunkelman, S. Indesteege, and N. Keller, A differential-linear attack on 12-round Serpent, Indocrypt 2008, LNCS 5365, pp. 308-321.
  18. S. Indesteege, N. Keller, O. Dunkelman, E. Biham, and B. Preneel, A practical attack on KeeLoq, Eurocrypt 2008, LNCS 4965, pp. 1-18.
  19. E. Biham, O. Dunkelman, and N. Keller, A unified approach to related key attacks, FSE 2008, LNCS 5086, pp. 73-96.
  20. J. Lu, J. Kim, N. Keller, and O. Dunkelman, Improving the efficiency of impossible differential cryptanalysis of reduced Camellia and Misty1
  21. , CT-RSA 2008, LNCS 4964, pp. 370-386.
  22. G. Wang, N. Keller, and O. Dunkelman, The delicate issues of addition with respect to XOR differences, SAC 2007, LNCS 4876, pp. 212-231.
  23. 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.
  24. E. Biham, O. Dunkelman, and N. Keller, Improved slide attacks, FSE 2007, LNCS 4593, pp. 153-166.
  25. E. Biham, O. Dunkelman, and N. Keller, A new attack on 6-Round IDEA, FSE 2007, LNCS 4593, pp. 211-224.
  26. 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.
  27. E. Biham, O. Dunkelman, and N. Keller, New cryptanalytic results on IDEA, Asiacrypt 2006, LNCS 4284, pp. 412-427.
  28. 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.
  29. O. Dunkelman, N. Keller, and J. Kim, Related-key rectangle attack on the full SHACAL-1, SAC 2006, LNCS 4356, pp. 28-44.
  30. 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.
  31. 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.
  32. O. Dunkelman and N. Keller, A new criterion for nonlinearity of block ciphers, CT-RSA 2006, LNCS 3860, pp. 295-312.
  33. E. Biham, O. Dunkelman and N. Keller, Related-key rectangle attack on the full KASUMI, Asiacrypt 2005, LNCS 3788, pp. 443-461.
  34. E. Biham, O. Dunkelman, and N. Keller, Related-key boomerang and rectangle attacks, Eurocrypt 2005, LNCS 3494, pp. 507-525.
  35. E. Biham, O. Dunkelman, and N. Keller, New combined attacks on block ciphers, FSE 2005, LNCS 3557, pp. 126-144.
  36. E. Barkan, E. Biham, and N. Keller, Instant ciphertext-only cryptanalysis of GSM encrypted communication, Crypto 2003, LNCS 2729, pp. 600-616.
  37. E. Biham, O. Dunkelman, and N. Keller, Rectangle attacks on 49-round SHACAL-1, FSE 2003, LNCS 2883, pp. 22-35.
  38. E. Biham, O. Dunkelman, and N. Keller, Differential-linear cryptanalysis of Serpent, FSE 2003, LNCS 2883, pp. 9-21.
  39. E. Biham, O. Dunkelman, and N. Keller, Enhancing differential-linear cryptanalysis, Asiacrypt 2002, LNCS 2501, pp. 254-266.
  40. E. Biham, O. Dunkelman and N. Keller, New results on boomerang and rectangle attacks, FSE 2002, LNCS 2365, pp. 1-16.
  41. E. Biham, O. Dunkelman and N. Keller, The rectangle attack -- rectangling the Serpent, Eurocrypt 2001, LNCS 2045, pp. 340-357.
  42. E. Biham, O. Dunkelman and N. Keller, Linear cryptanalysis of reduced-round Serpent, FSE 2001, LNCS 2355, pp. 16-27.


Last updated: 22.1.2017