Time: Thursday, 23.06.22, 12:30

Place: Taub 1

Title: Efficient Detection of High Probability Cryptographic Properties of Large Boolean Functions via Surrogate Differentiation

Abstract: A central problem in cryptanalysis is to find all the significant deviations from randomness in a given $n$-bit cryptographic primitive. When $n$ is large, 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 talk I will consider the top-down version of the problem in which the cryptographic primitive is given as a structureless black box which implements an arbitrary Boolean function from $n$ bits to $n$ bits. I will then show how to 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}$. The main new idea is to use {\it surrogate differentiation}, which is a new way to analyze the properties of large Boolean functions. 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 $\alpha$ by differentiating $f$ in a single arbitrarily 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.

This is joint work with Itai Dinur, Orr Dunkelman, Nathan Keller, and Eyal Ronen.