Circuit Complexity of Cryptographic Algorithms

Dr. Çağdaş Çalık

National Institute of Standards and Technology, NIST, USA

Invited by: Sevtap Kestel

Zoom Meeting ID: 984 0800 6920
Passcode:  724032
Date/Time: 22.06.2021, 15:30-16:30 

Abstract: Algorithms are expressed as circuits consisting of logic gates (including other components) when they are implemented in hardware. Various characteristics of circuits can be used as metrics for optimization, which are defined by the requirements of specific applications; such as minimizing the total number of gates for low chip area, or minimizing the depth of the circuit for low latency. One particular metric of interest for cryptographic applications is the multiplicative complexity of functions, which is defined as the minimum number of 2-input AND gates that is necessary and sufficient to implement it over the basis of XOR, AND, and NOT gates. Multiplicative complexity is not only an indicator of the complexity of a function but it is also related to the cost of protecting an implementation against side-channel attacks as nonlinear gates are more expensive to protect than linear gates. This talk will highlight circuit complexity results from the literature within the context of cryptographic algorithms and protocols, and demonstrate the implications of constructing better circuits for real world applications.

Last Updated:
11/06/2021 - 16:06