Welcome to the resource topic for 2013/633
Title:
Four Measures of Nonlinearity
Authors: J. Boyar, M. G. Find, R. Peralta
Abstract:Cryptographic applications, such as hashing, block ciphers and stream ciphers, make use of functions which are simple by some criteria (such as circuit implementations), yet hard to invert almost everywhere. A necessary condition for the latter property is to be ``sufficiently distant’’ from linear, and cryptographers have proposed several measures for this distance. In this paper, we show that four common measures, {\em nonlinearity, algebraic degree, annihilator immunity}, and {\em multiplicative complexity}, are incomparable in the sense that for each pair of measures, \mu_1,\mu_2, there exist functions f_1,f_2 with \mu_1(f_1)> \mu_1(f_2) but \mu_2(f_1)< \mu_2(f_2). We also present new connections between two of these measures. Additionally, we give a lower bound on the multiplicative complexity of collision-free functions.
ePrint: https://eprint.iacr.org/2013/633
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .