Abstract
Algebraic attacks have received a lot of attention in studying security of symmetric ciphers. The function used in a symmetric cipher should have high algebraic immunity (\({\cal AI}\)) to resist algebraic attacks. In this paper we are interested in finding \({\cal AI}\) of Boolean power functions. We give an upper bound on the \({\cal AI}\) of any Boolean power function and a formula to find its corresponding low degree multiples. We prove that the upper bound on the \({\cal AI}\) for Boolean power functions with Inverse, Kasami and Niho exponents are \(\lfloor \sqrt{n}\rfloor + \lceil \frac{n}{\lfloor \sqrt{n} \rfloor}\rceil -2\), \(\lfloor \sqrt{n} \rfloor + \lceil \frac{n}{\lfloor \sqrt{n} \rfloor}\rceil\) and \(\lfloor \sqrt{n} \rfloor + \lceil \frac{n}{\lfloor \sqrt{n} \rfloor}\rceil\) respectively. We also generalize this idea to Boolean polynomial functions. All existing algorithms to determine \({\cal AI}\) and corresponding low degree multiples become too complex if the function has more than 25 variables. In our approach no algorithm is required. The \({\cal AI}\) and low degree multiples can be obtained directly from the given formula.
Chapter PDF
Similar content being viewed by others
Keywords
References
Armknecht, F.: On the Existence of Low-degree Equations for Algebraic Attacks, Cryptology ePrint Archive, Report 2004/185 (2004), http://eprint.iacr.org/
Armknecht, F.: Algebraic attacks on combiners with memory. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 162–175. Springer, Heidelberg (2003)
Armknecht, F.: Improving fast algebraic attacks. In: Roy, B., Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 65–82. Springer, Heidelberg (2004)
Braeken, A., Lano, J., Mentens, N., Preneel, B., Verbauwhede, I.: SFINKS: A Synchronous Stream Cipher for Restricted Hardware Environments, eSTREAM Project report 2005/026, Available at, http://www.ecrypt.eu.org/stream/
Braeken, A., Preneel, B.: On the Algebraic Immunity of Symmetric Boolean Functions. In: Maitra, S., Veni Madhavan, C.E., Venkatesan, R. (eds.) INDOCRYPT 2005. LNCS, vol. 3797, pp. 35–48. Springer, Heidelberg (2005)
Cheon, J., Lee, D.: Resistance of S-Boxes Against Algebraic Attacks. In: Roy, B., Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 83–94. Springer, Heidelberg (2004)
Courtois, N.: Fast Algebraic Attacks on Stream Ciphers with Linear Feedback. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 176–194. Springer, Heidelberg (2003)
Courtois, N., Meier, W.: Algebraic Attacks on Stream Ciphers with Linear Feedback. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 346–359. Springer, Heidelberg (2003)
Courtois, N., Meier, W.: Algebraic Attacks on Stream Ciphers with Linear Feedback, Extended version of [8], available at, http://cryptosystem.net/stream
Courtois, N.: Algebraic Attacks on Combiners with Memory and Several Outputs. In: Park, C.-s., Chee, S. (eds.) ICISC 2004. LNCS, vol. 3506, pp. 3–20. Springer, Heidelberg (2005)
Courtois, N., Pieprzyk, J.: Cryptanalysis of Block Ciphers with Overdefined Systems of Equations. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 267–287. Springer, Heidelberg (2002)
Courtois, N., Debraize, B., Garrido, E.: On Exact Algebraic [Non]Immunity of S-boxes Based on Power Functions, Cryptology ePrint Archive, Report 2005/203 (2005), http://eprint.iacr.org/
Daemen, J., Rijmen, V.: The Design of Rijndael. Springer, Heidelberg (2002)
Dalai, D.K., Gupta, K.C., Maitra, S.: Cryptographically Significant Boolean Functions: Construction and Analysis in Terms of Algebraic Immunity. In: Gilbert, H., Handschuh, H. (eds.) FSE 2005. LNCS, vol. 3557, pp. 98–111. Springer, Heidelberg (2005)
Dalai, D.K., Maitra, S., Sarkar, S.: Basic Theory in Construction of Boolean Functions with Maximum Possible Annihilator Immunity. In: Designs, Codes and Cryptography (to appear)
Dobbertin, H.: Almost Perfect Nonlinear Power Functions on GF(2n): The Welch Case. IEEE Transactions on Information Theory 45(4), 1271–1275 (1999)
Dobbertin, H.: Almost Perfect Nonlinear Power Functions on GF(2n): The Niho Case. Information and Computation 151, 57–72 (1998)
Gold, R.: Maximal Recursive Sequences with 3 valued cross-correlation function. IEEE Transactions on Information Theory 14, 154–156 (1968)
Golomb, S.W., Gong, G.: Hyper-Cyclotomic Algebra, Sequences and their Applications. In: SETA 2001, Discrete Mathematics and Theoretical Computer Science, CORR 2001-33, pp. 154–165. Springer, Heidelberg (2001)
Golomb, S.W., Gong, G.: Signal Design for Good Correlation: For Wireless Communication, Cryptography, and Radar. Cambridge University Press, Cambridge (2005), ISBN 0521821045
Hawkes, P., Rose, G.: Rewriting Variables: The Complexity of Fast Algebraic Attacks on Stream Ciphers. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 390–406. Springer, Heidelberg (2004)
Ekdahl, P., Johansson, T.: SNOW-A New Version of the Stream Cipher SNOW. In: Nyberg, K., Heys, H.M. (eds.) SAC 2002. LNCS, vol. 2595, pp. 47–61. Springer, Heidelberg (2003)
Kasami, T.: The Weight Enumerators for Several Classes of Subcodes of the Second Order Binary Reed-Muller Codes. Infor. Contr. 18, 369–394 (1971)
Lidl, R., Niederreiter, H.: Introduction to Finite Fields and their Applications. Cambridge University Press, Cambridge (1994)
MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error Correcting Codes. North Holland, Amsterdam (1986)
Meier, W., Pasalic, E., Carlet, C.: Algebraic Attacks and Decomposition of Boolean Functions. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 474–491. Springer, Heidelberg (2004)
Murphy, S., Robshaw, M.: Essential Algebraic Structure within AES. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 1–16. Springer, Heidelberg (2002)
Murphy, S., Robshaw, M.: Comments on the Security of the AES and the XSL Technique. Electronic Letters 39, 26–38 (2003)
Nawaz, Y., Gong, G., Gupta, K.: Upper Bounds on Algebraic Immunity of Boolean Power Functions (Preprint)
Schaumuller-Bichl, I.: Cryptanalysis of the Data Encryption Standard by the Method of Formal Coding. In: Beth, T. (ed.) EUROCRYPT 1982. LNCS, vol. 149, pp. 235–255. Springer, Heidelberg (1983)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Nawaz, Y., Gong, G., Gupta, K.C. (2006). Upper Bounds on Algebraic Immunity of Boolean Power Functions. In: Robshaw, M. (eds) Fast Software Encryption. FSE 2006. Lecture Notes in Computer Science, vol 4047. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11799313_24
Download citation
DOI: https://doi.org/10.1007/11799313_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-36597-6
Online ISBN: 978-3-540-36598-3
eBook Packages: Computer ScienceComputer Science (R0)