Multiplicative Complexity of Boolean Functions
The multiplicative complexity (MC) of a Boolean function is the minimum number of two-input AND gates that are necessary and sufficient to implement the function over the basis (AND, XOR, NOT). Finding the MC of a given function is computationally intractable, even for functions with small number of inputs. The talk highlights the importance of MC for cryptographic applications and the design of symmetric-key cryptography algorithms. The MC distribution of Boolean functions with up to 6 variables, the characterization of Boolean functions with MC up to 4 and some results on symmetric Boolean functions are presented. Finally, the talk proposes some research directions and challenges.
Dr. Meltem Sonmez Turan
Cryptographer, Computer Security Division, National Institute of Standards and Technology (NIST)
Meltem Sonmez Turan is a mathematician in the Computer Security Division of National Institute of Standards and Technology. Dr. Sonmez Turan’s research interests include symmetric cryptography, random number generation and circuit complexity. She has contributed to several cryptography standardization efforts, including SHA-3 and Password Hashing Competition. She is currently co-leading the NIST Lightweight Cryptography Standardization process.
Host: Professor Patrick Schaumont