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, nonlinearity, algebraic degree, annihilator immunity, and multiplicative complexity, are incomparable in the sense that for each pair of measures, μ 1,μ 2, there exist functions f 1,f 2 with μ 1(f 1) > μ 1(f 2) but μ 2(f 1) < μ 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.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Boyar, J., Damgaard, I., Peralta, R.: Short non-interactive cryptographic proofs. Journal of Cryptology 13, 449–472 (2000)
Boyar, J., Peralta, R.: Tight bounds for the multiplicative complexity of symmetric functions. Theor. Comput. Sci. 396(1-3), 223–246 (2008)
Boyar, J., Peralta, R., Pochuev, D.: On the multiplicative complexity of Boolean functions over the basis ( ∧ , ⊕ , 1). Theor. Comput. Sci. 235(1), 43–57 (2000)
Canteaut, A., Videau, M.: Symmetric Boolean functions. IEEE Transactions on Information Theory 51(8), 2791–2811 (2005)
Carlet, C.: On the degree, nonlinearity, algebraic thickness, and nonnormality of Boolean functions, with developments on symmetric functions. IEEE Transactions on Information Theory 50(9), 2178–2185 (2004)
Carlet, C.: Boolean functions for cryptography and error correcting codes. In: Crama, Y., Hammer, P.L. (eds.) Boolean Models and Methods in Mathematics, Computer Science, and Engineering, ch. 8, pp. 257–397. Cambridge Univ. Press, Cambridge (2010)
Carlet, C., Dalai, D.K., Gupta, K.C., Maitra, S.: Algebraic immunity for cryptographically significant Boolean functions: Analysis and construction. IEEE Transactions on Information Theory 52(7), 3105–3121 (2006)
Courtois, N., Meier, W.: Algebraic attacks on stream ciphers with linear feedback. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 345–359. Springer, Heidelberg (2003)
Courtois, N., Hulme, D., Mourouzis, T.: Solving circuit optimisation problems in cryptography and cryptanalysis, e-print can be found at http://eprint.iacr.org/2011/475.pdf
Dalai, D.K., Gupta, K.C., Maitra, S.: Results on algebraic immunity for cryptographically significant Boolean functions. In: Canteaut, A., Viswanathan, K. (eds.) INDOCRYPT 2004. LNCS, vol. 3348, pp. 92–106. Springer, Heidelberg (2004)
Dalai, D.K., Maitra, S., Sarkar, S.: Basic theory in construction of Boolean functions with maximum possible annihilator immunity. Des. Codes Cryptography 40(1), 41–58 (2006)
Demenkov, E., Kulikov, A.S.: An elementary proof of a 3n − o(n) lower bound on the circuit complexity of affine dispersers. In: Murlak, F., Sankowski, P. (eds.) MFCS 2011. LNCS, vol. 6907, pp. 256–265. Springer, Heidelberg (2011)
Didier, F.: A new upper bound on the block error probability after decoding over the erasure channel. IEEE Transactions on Information Theory 52(10), 4496–4503 (2006)
Dobbertin, H.: Construction of bent functions and balanced Boolean functions with high nonlinearity. In: Preneel, B. (ed.) FSE 1994. LNCS, vol. 1008, pp. 61–74. Springer, Heidelberg (1995)
Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game. In: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC 1987, pp. 218–229. ACM, New York (1987), http://doi.acm.org/10.1145/28395.28420
Jukna, S.: Boolean Function Complexity: Advances and Frontiers. Springer, Heidelberg (2012)
Kavut, S., Maitra, S., Yücel, M.D.: There exist Boolean functions on n (odd) variables having nonlinearity > 2n − 1 - 2(n − 1)/2 if and only if n>7. IACR Cryptology ePrint Archive 2006, 181 (2006)
Kolesnikov, V., Schneider, T.: Improved garbled circuit: Free XOR gates and applications. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part II. LNCS, vol. 5126, pp. 486–498. Springer, Heidelberg (2008)
Lupanov, O.: On rectifier and switching-and-rectifier schemes. Dokl. Akad. 30 Nauk SSSR 111, 1171-1174 (1965)
Maitra, S., Sarkar, P.: Maximum nonlinearity of symmetric Boolean functions on odd number of variables. IEEE Transactions on Information Theory 48(9), 2626–2630 (2002)
McFarland, R.L.: Sub-difference sets of Hadamard difference sets. J. Comb. Theory, Ser. A 54(1), 112–122 (1990)
Nechiporuk, E.I.: On the complexity of schemes in some bases containing nontrivial elements with zero weights (in Russian). Problemy Kibernetiki 8, 123–160 (1962)
Nielsen, J.B., Nordholt, P.S., Orlandi, C., Burra, S.S.: A new approach to practical active-secure two-party computation. In: Safavi-Naini, R. (ed.) CRYPTO 2012. LNCS, vol. 7417, pp. 681–700. Springer, Heidelberg (2012)
O’Donnell, R.: Analysis of Boolean Functions. Book Draft (2012), http://www.analysisofbooleanfunctions.org
Rodier, F.: Asymptotic nonlinearity of Boolean functions. Des. Codes Cryptography 40(1), 59–70 (2006)
Rothaus, O.S.: On “bent” functions. J. Comb. Theory, Ser. A 20(3), 300–305 (1976)
Savický, P.: On the bent Boolean functions that are symmetric. Eur. J. Comb. 15(4), 407–410 (1994)
Schnorr, C.-P.: The multiplicative complexity of Boolean functions. In: Mora, T. (ed.) AAECC 1988. LNCS, vol. 357, pp. 45–58. Springer, Heidelberg (1989)
Zhang, X.-M., Pieprzyk, J., Zheng, Y.: On algebraic immunity and annihilators. In: Rhee, M.S., Lee, B. (eds.) ICISC 2006. LNCS, vol. 4296, pp. 65–80. Springer, Heidelberg (2006)
Zhegalkin, I.I.: On the technique of calculating propositions in symbolic logic. Matematicheskii Sbornik 43, 9–28 (1927)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Boyar, J., Find, M., Peralta, R. (2013). Four Measures of Nonlinearity. In: Spirakis, P.G., Serna, M. (eds) Algorithms and Complexity. CIAC 2013. Lecture Notes in Computer Science, vol 7878. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38233-8_6
Download citation
DOI: https://doi.org/10.1007/978-3-642-38233-8_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38232-1
Online ISBN: 978-3-642-38233-8
eBook Packages: Computer ScienceComputer Science (R0)