Nathan Keller

 

 

 

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

 

Before coming to the Bar Ilan University, I was a Koshland Postdoctoral Fellow at the Mathematics Department of the Weizmann Institute of Science, hosted by Prof. Elchanan Mossel. I continue my affiliation with the Weizmann Institute, as a consultant at the Department of Computer Science and Applied Mathematics, hosted by Prof. Adi Shamir.

 

I completed my Ph.D. at the Einstein Institute of Mathematics  in the Hebrew University of Jerusalem, under the supervision of Prof. Gil Kalai.

 

 

My first field of research is Combinatorics. I'm interested in application of analytic tools (such as discrete harmonic analysis) to Combinatorics, and especially in the influences of variables on functions in product spaces.

 

My second field of research is Cryptography, and especially Cryptanalysis (i.e., design and security of various cryptosystems).

 

My CV can be found here.

 

Email address: nathan.keller27 At gmail.com

 

 

 

 

 

 

Publications:

 

Published Papers in Combinatorics:

 

1)      N. Keller, E. Mossel, and A. Sen, Geometric influences II: Correlation inequalities and noise sensitivity, Annales de l'Institut Henri Poincare, to appear.

 

2)      N. Keller and G. Kindler, Quantitative relation between noise sensitivity and influences, Combinatorica, 33(1) (2013), pp. 45-71.

 

3)      N. Keller, A tight quantitative version of Arrow's impossibility theorem, Journal of the European Mathematical Society, 14(5) (2012), pp. 1331-1355.

4)      N. Keller, E. Mossel, and A. Sen, Geometric influences, Annals of Probability, 40(3) (2012), pp. 1135-1166.

 

5)      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.

 

6)      N. Keller, E. Mossel, and T. Schlank, A note on the entropy/influence conjecture, Discrete Mathematics, 312(22) (2012), pp. 3364-3372.

 

7)      E. Friedgut, G. Kalai, N. Keller, and N. Nisan, A Quantitative version of the Gibbard-Satterthwaite theorem for three alternatives, SIAM journal of  Computing, 40(3) (2011), pp. 934-952.

 

8)      N. Keller, On the influences of variables on Boolean functions in product spaces, Combinatorics, Probability and Computing, 20(1) (2011), pp. 83-102.

 

9)      N. Keller, On the probability of a rational outcome for generalized social welfare functions on three alternatives, Journal of Combinatorial Theory Ser. A, 117(4) (2010), pp. 389-410.

 

10)  N. Keller, On the correlation between monotone families in the average case, Advances in Applied Mathematics, 43(1) (2009), pp. 31-45.

 

11)  N. Keller and H. Pilpel, Linear transformations of monotone functions on the discrete cube, Discrete Mathematics, 309(12) (2009), pp. 4210-4214.

 

 

 

Published Papers in Cryptography:

 

1)      I. Dinur, O. Dunkelman, N. Keller, and A.Shamir, Dissection: A new paradigm for solving bicomposite search problems, Communications of the ACM, to appear. (Invited and accepted to the “Research highlights” section).

 

2)      O. Dunkelman, N. Keller, and A. Shamir, Slidex attacks on the Even-Mansour encryption scheme, Journal of Cryptology, to appear.

 

3)      E. Biham, O. Dunkelman, N. Keller, and A. Shamir, New data-efficient attacks on reduced-round IDEA, Journal of Cryptology, to appear. 

 

4)      O. Dunkelman, N. Keller, and A. Shamir, Improved single-key attacks on 8-round AES-192 and AES-256, Journal of Cryptology, to appear.

 

5)      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, to appear.

 

6)      O. Dunkelman and N. Keller, Cryptanalysis of the stream cipher LEX, Design, Codes, and Cryptography, 67(3) (2013), pp. 357-373.

 

7)      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.

 

8)      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.

 

9)      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.

 

10)  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.

 

11)  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.

 

12)  E. Barkan, E. Biham, and N. Keller, Instant ciphertext-only cryptanalysis of GSM encrypted communication, Journal of Cryptology 21 (2008), no. 3, pp. 392-429.

 

13)  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.

 

14)  O. Dunkelman and N. Keller, A new criterion for nonlinearity of block ciphers, IEEE Transactions on Information Theory 53 (2007), no. 11, pp. 3944-3957.

 

 

Preprints in Cryptography:

 

 

1)      I. Dinur, O. Dunkelman, N. Keller, and A. Shamir, Efficient dissection of composite problems, with applications to Cryptanalysis, Knapsacks and Combinatorial search problems, submitted.

 

2)      O. Dunkelman, N. Keller, and A. Shamir, Almost universal forgery attacks on AES-based MACs, submitted.

 

3)      O. Dunkelman and N. Keller, Practical-time attacks against reduced variants of MISTY1, submitted.

 

 

Published Papers in Matrix Theory:

 

1)      D. Hershkowitz and N. Keller, Spectral Properties of Sign Symmetric Matrices, Electronic Journal of Linear Algebra 13 (2005), pp. 90-110.

 

2)      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 in Cryptography:

 

All the papers below were presented in conferences in Cryptography and published in the series “Lecture Notes of Computer Science” (LNCS) of Springer-Verlag.

 

 

1)      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, to appear in LNCS. (Solicited for publication in Journal of Cryptology as one of the three best papers).

 

2)      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. (Best Paper Award).

 

3)      O. Dunkelman, N. Keller, and A. Shamir, Minimalism in cryptography: the Even-Mansour cryptosystem revisited, Eurocrypt 2012, LNCS 7237, pp. 336-354.

 

4)      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. (Solicited for publication in Journal of Cryptology as one of the three best papers).  

 

5)      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.

 

6)      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.

 

7)      O. Dunkelman and N. Keller, Cryptanalysis of CTC2, CT-RSA 2009, LNCS 5473, pp. 226-239.

 

8)      O. Dunkelman and N. Keller, An improved impossible differential attack on Misty1, Asiacrypt 2008, LNCS 5350, pp. 441-454. 

 

9)      O. Dunkelman and N. Keller, A new attack on the LEX stream cipher, Asiacrypt 2008, LNCS 5350, pp. 539-556.

 

10)  J. Lu, O. Dunkelman, N. Keller, and J. Kim, New impossible differential attacks on AES, Indocrypt 2008, LNCS 5365, pp. 279-293.

 

11)  O. Dunkelman, S. Indesteege, and N. Keller, A differential-linear attack on 12-round Serpent, Indocrypt 2008, LNCS 5365, pp. 308-321.

 

12)  S. Indesteege, N. Keller, O. Dunkelman, E. Biham, and B. Preneel, A practical attack on KeeLoq, Eurocrypt 2008, LNCS 4965, pp. 1-18.

 

13)  E. Biham, O. Dunkelman, and N. Keller, A unified approach to related key attacks, FSE 2008, LNCS 5086, pp. 73-96.

 

14)  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.

 

15)  G. Wang, N. Keller, and O. Dunkelman, The delicate issues of addition with respect to XOR differences, SAC 2007, LNCS 4876, pp. 212-231.  

 

16)  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.

 

17)  E. Biham, O. Dunkelman, and N. Keller, Improved Slide Attacks, FSE 2007, LNCS 4593, pp. 153-166.

 

18)  E. Biham, O. Dunkelman, and N. Keller, A New Attack on 6-Round IDEA, FSE 2007, LNCS 4593, pp. 211-224.

 

19)  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.

 

20)  E. Biham, O. Dunkelman, and N. Keller, New Cryptanalytic Results on IDEA, Asiacrypt 2006, LNCS 4284, pp. 412-427.

 

21)  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.

 

22)  O. Dunkelman, N. Keller, and J. Kim, Related-Key Rectangle Attack on the Full SHACAL-1, SAC 2006, LNCS 4356, pp. 28-44.

 

23)  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.

 

24)  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.

 

25)  O. Dunkelman and N. Keller, A New Criterion for Nonlinearity of Block Ciphers, CT-RSA 2006, LNCS 3860, pp. 295-312.

 

26)  E. Biham, O. Dunkelman and N. Keller, Related-Key Rectangle Attack on the Full KASUMI, Asiacrypt 2005, LNCS 3788, pp. 443-461.

 

27)  E. Biham, O. Dunkelman, and N. Keller, Related-Key Boomerang and Rectangle Attacks, Eurocrypt 2005, LNCS 3494, pp. 507-525.

28)  E. Biham, O. Dunkelman, and N. Keller, New Combined Attacks on Block Ciphers, FSE 2005, LNCS 3557, pp. 126-144.

 

29)  E. Barkan, E. Biham, and N. Keller: Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication, Crypto 2003, LNCS 2729, pp. 600-616.

 

30)  E. Biham, O. Dunkelman, and N. Keller: Rectangle Attacks on 49-Round SHACAL-1, FSE 2003, LNCS 2883, pp. 22-35.

 

31)  E. Biham, O. Dunkelman, and N. Keller, Differential-Linear Cryptanalysis of Serpent, FSE 2003, LNCS 2883, pp. 9-21.

 

32)  E. Biham, O. Dunkelman, and N. Keller, Enhancing Differential-Linear Cryptanalysis, Asiacrypt 2002, LNCS 2501, pp. 254-266.

 

33)  E. Biham, O. Dunkelman and N. Keller, New Results on Boomerang and Rectangle Attacks, FSE 2002, LNCS 2365, pp. 1-16.

 

34)  E. Biham, O. Dunkelman and N. Keller, The Rectangle Attack – Rectangling the Serpent, Eurocrypt 2001, LNCS 2045, pp. 340-357.

 

35)  E. Biham, O. Dunkelman and N. Keller, Linear Cryptanalysis of Reduced-Round Serpent, FSE 2001, LNCS 2355, pp. 16-27.

 

 

 

 

 

 

 

 

 

 

 

 

For Hebrew version click here.

 

Last updated: 5.3.2013