Description
This lecture presents the preliminary notions to understand how AI techniques are used nowadays to design sound cryptographic primitives. We start by first introducing Boolean functions, which are used as low-level building blocks in symmetric ciphers. To withstand specific attacks, such functions need to satisfy a number of cryptographic properties. These properties however cannot be satisfied simultaneously, and moreover it is not possible to explore exhaustively the set of all Boolean functions to search for the best one, since it would take a super-exponential time in the number of input variables. This motivates the formulation of searching for a good Boolean function as a combinatorial optimization problem. To solve this optimization problem, we introduce evolutionary algorithms, focusing in particular on genetic algorithms and genetic programming.
Topics covered:
- Pseudorandom generators in practice: Linear Feedback Shift Registers and combiner functions
- Basic representations of Boolean functions: truth tables, algebraic normal form, Walsh transform
- Cryptographic properties of Boolean functions: balancedness, algebraic degree, nonlinearity, resiliency
- S-boxes as vectorial Boolean functions for block ciphers
- Cryptographic properties of S-boxes: nonlinearity and differential uniformity
- Trade-offs for cryptographic properties
- Combinatorial optimization problems
- Evolutionary algorithms: genetic algorithms (GA) and genetic programming (GP)
Reading Material
Reference book on Boolean functions:
- C. Carlet. Boolean Functions for Cryptography and Coding Theory. Cambridge University Press, 2021
Surveys on AI methods in symmetric cryptography:
- M. Đurasevic, D. Jakobovic, L. Mariot, S. Picek: A Survey of Metaheuristic Algorithms for the Design of Cryptographic Boolean Functions. Cryptography and Communications, 2023 (in press)
- L. Mariot, D. Jakobovic, T. Bäck, J. Hernandez-Castro: Artificial Intelligence for the Design of Symmetric Cryptographic Primitives. Security and Artificial Intelligence 2022: 3-24 (2022)
See also the references on the last slide.