Dear all,
Next week, we have the pleasure of having Prof. Orr Dunkelman give a talk in the colloquium.
The seminar will be held on Monday, June 3rd at 14:00. Location: C221.
The title, abstract and bio appear below.
Looking forward to seeing you, Sagie and Liat
*Title:* The Hunt for High Probability Statistical Impurities in Cryptographic Primitives
*Abstract:* Computer security relies on cryptographic primitives such as block ciphers and hash functions. The security of these primitives is usually not proved in a reduction-style proof, but rather argued based on claims of the form - this block cipher has no statistical property of some type (e.g., differential) with high enough probability. However, how do we know that there are no such statistical properties in a given n-bit cryptographic primitive?
When *n* is small (e.g., an 8-bit S-box), this is easy to do. However, for large values of *n*, the only practical way to find such statistical properties was to exploit the internal structure of the primitive and to speed up the search with a variety of heuristic rules of thumb. However, such bottom-up techniques can miss many properties, especially in cryptosystems which are designed to have hidden trapdoors.
In this work we consider the top-down version of the problem in which the cryptographic primitive is given as a structureless black box, and reduce the complexity of the best known techniques for finding all its significant differential and linear properties by a large factor of 2^{n/2}. Our main new tool is the idea of using *surrogate differentiation*. In the context of finding differential properties, it enables us to simultaneously find information about all the differentials of the form f(x) \oplus f(x \oplus \alpha) in all possible directions by differentiating *f* in a single randomly chosen direction \gamma (which is unrelated to the \alpha’s). In the context of finding linear properties, surrogate differentiation can be combined in a highly effective way with the Fast Fourier Transform. For 64-bit cryptographic primitives, this technique makes it possible to automatically find in about 2^64 time all their differentials with probability larger than 2^{-32} and all their linear approximations with bias larger than 2^{-16}; previous algorithms for these problems required at least 2^{96} time.
This is a joint work with Itai Dinur, Nathan Keller, Eyal Ronen, and Adi Shamir. *Bio*:
Orr Dunkelman is a full professor in the Computer Science Department at the University of Haifa. He has held post-doctoral research positions at the Weizmann Institute of Science, Ecole Normale Superieure, and Katholieke Universiteit Leuven. He earned his Ph.D. from the Technion under the supervision of Prof. Eli Biham.