Advancing Nonlinear Cryptanalysis of Symmetric-key Cryptographic Primitives

• Applicant: Dr. Eik List
• Subject Area: Security and Dependability, Operating-, Communication- and Distributed Systems ; Theoretical Computer Science
• Term: since 2022
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 509754807

Modern cryptography is ubiquitous but essential for securing our digital communication. In the usual layered view, cryptographic primitives represent the building blocks for constructing higher-level cryptographic schemes and protocols upon them. Symmetric-key primitives, such as block ciphers or permutations, are particularly relevant for their high efficiency. While one can often prove the security of schemes and protocols, symmetric-key primitives have to be evaluated systematically in terms of resistance against the known attack techniques. The refinement and extension of those techniques is a foundational research task that benefits us who depend on the security of those primitives in the long run.This project aims at advancing the state-of-the-art of cryptanalysis of symmetric-key cryptographic primitives by studying three less explored paths: (WP1) Nonlinear cryptanalysis, (WP2) invariant cryptanalysis, and the application of (WP3) cryptanalysis for neural-network model extraction. Those directions obtained more attention in the recent decade but are not sufficiently understood yet.Linear cryptanalysis is one of the core attack techniques, trying to approximate a primitive by linear functions. Nonlinear cryptanalysis is a generalization that considers more complex approximations. While known for long and potentially more effective than linear cryptanalysis, it has received attention only recently since the search space of nonlinear approximations is considerably larger than that of linear ones. This project shall develop a framework for their efficient search and reinvestigate their applicability to widespread primitives.Invariants are a particular case of approximations that always hold. In the past decade, they could show their potential with breaks of various lightweight ciphers. However, finding a good search strategy for higher-degree invariants is not investigated in full detail yet. This project shall develop a framework for their efficient search and study their effect on widespread primitives.Third, neural networks are a core primitive in artificial intelligence for their high efficiency on computationally intensive tasks such as autonomous driving. Prior, one must train their parameters by evaluating potentially large amounts of data, rendering the resulting parameters (the model) precious secrets. Neural networks are structurally similar to symmetric-key primitives, although the former usually operate on real numbers and the latter on finite fields. This similarity motivated recent works to view parameter extraction as a cryptographic task. While those works used differentials successfully, the question has remained open if one can apply more techniques from the cryptanalyst's toolbox for more efficient model extraction. This project shall investigate the applicability of cryptanalysis techniques other than differentials for model extraction and prove or dismiss the effectiveness of early existing defense strategies.

• DFG Programme: WBP Fellowship
• International Connection: Singapore
• Host: Professor Dr. Jian Guo