Abstract: Boolean functions are used as one component in the design of symmetric ciphers, e.g. the Sbox in AES, or the filtering function in stream ciphers. If these functions are linear, it opens the way to certain types of attacks (linear and differential cryptanalysis). These attacks also work if the function is not linear but can be approximated well by a linear function. This has led to the notion of nonlinearity, a parameter of the function which measures its distance to the closest linear/affine function. The nonlinearity can be computed by a O(n2^n) algorithm, where n is the number of variables. When n is large, this computation is unfeasible. Therefore, we investigate the possibility of probabilistic estimation of the nonlinearity. To do so, we use the notion of nonhomomorphicity (introduced by Zhang and Zheng), which can be estimated efficiently even for large n. We generalise several techniques developed by Bellare et al, to obtain upper and lower bounds for the honhomomorphicity in terms of the nonlinearity. These bounds then allow us to estimate the nonlinearity once a good estimate of the nonhomomorphicity was obtained. This is joint work with Pante Stanica and was first presented at the SETA 2020 conference.

 

Bio: Ana Salagean is a Senior Lecturer in the Department of Computer Science at Loughborough University. She previously held positions at Nottingham Trent University, University of Bristol and University of Bucharest, Romania, after obtaining her PhD from University of Linz, Austria. Her current research interests are mainly in cryptography. Specifically, she studies the mathematical properties and construction of cryptographic Boolean functions and cryptographic sequences that are used in the design of symmetric ciphers. She also worked in the area of algebraic error-correcting codes.

 

Please feel free to forward to others who might be interested. 

UK-SPS is an inter-university seminar series on cyber security and privacy. Seminar details are also advertised on our website, calendar and Twitter, and recordings will be available on our YouTube channel afterwards.