This article is cited in 7 papers

Mathematical Methods of Cryptography

From cryptanalysis to cryptographic property of a Boolean function

A. A. Gorodilova

Sobolev Institute of Mathematics, Novosibirsk, Russia

Abstract: The survey is devoted to description of basic, but not all, cryptographic properties of Boolean functions: algebraic degree, balancedness and perfect balancedness, avalanche characteristics, non-existence of linear structures, correlation immunity and resiliency, high nonlinearity, statistical independence, algebraic immunity, affinity level and $k$-normality, differential uniformity, threshold implementation, multiplicative complexity, high cardinality of linearization sets. The questions about these properties formation are studied based on the attacks on stream and block ciphers that exploit the vulnerabilities of Boolean functions used in ciphers as components. The ideas of such attacks are given. We briefly describe the basic theoretical results obtained for each of the properties and formulate open problems in this area.

Keywords: Boolean function, stream cipher, block cipher, algebraic degree, balancedness, perfect balancedness, avalanche characteristics, linear structure, correlation immunity, resiliency, nonlinearity, statistical independence, algebraic immunity, affinity level, $k$-normality, differential uniformity, threshold implementation, multiplicative complexity, linearization set, linear complexity, correlation attack, fast correlation attack, linear cryptanalysis, statistical analogue, differential cryptanalysis, side-channel attacks, linearization attack.

UDC: 519.7

DOI: 10.17223/20710410/33/2

Bibliographic databases:

•