May  2017, 11(2): 373-377. doi: 10.3934/amc.2017031

Fast algebraic immunity of Boolean functions

1. 

Department of Mathematics, University of Paris Ⅷ and Paris ⅩⅢ and Télécom ParisTech, LAGA, UMR 7539, CNRS, Sorbonne Paris Cité

2. 

Télécom ParisTech, department INFRES/MIC2, CNRS, UMR 5441

Received  February 2016 Revised  March 2016 Published  May 2017

Since 1970, Boolean functions have been the focus of a lot of attention in cryptography. An important topic in symmetric ciphers concerns the cryptographic properties of Boolean functions and constructions of Boolean functions with good cryptographic properties, that is, good resistance to known attacks. An important progress in cryptanalysis areas made in 2003 was the introduction by Courtois and Meier of algebraic attacks and fast algebraic attacks which are very powerful analysis concepts and can be applied to almost all cryptographic algorithms. To study the resistance against algebraic attacks, the notion of algebraic immunity has been introduced. In this paper, we use a parameter introduced by Liu and al., called fast algebraic immunity, as a tool to measure the resistance of a cryptosystem (involving Boolean functions) to fast algebraic attacks. We prove an upper bound on the fast algebraic immunity. Using our upper bound, we establish the weakness of trace inverse functions against fast algebraic attacks confirming a recent result of Feng and Gong.

Citation: Sihem Mesnager, Gérard Cohen. Fast algebraic immunity of Boolean functions. Advances in Mathematics of Communications, 2017, 11 (2) : 373-377. doi: 10.3934/amc.2017031
References:
[1]

C. Carlet, Boolean functions for cryptography and error correcting codes, in Boolean Models and Methods in Mathematics, Computer Science, and Engineering (eds. Y. Crama and P. L. Hammer), Cambridge Univ. Press, 2010,257-397. doi: 10.1017/CBO9780511780448. Google Scholar

[2]

C. Carlet and K. Feng, An infinite class of balanced functions with optimal algebraic immunity, good immunity to fast algebraic attacks and good nonlinearity, in Adv. Crypt. -ASIACRYPT 2008, Springer, 2008,425-440. doi: 10.1007/978-3-540-89255-7_26. Google Scholar

[3]

C. Carlet and D. Tang, Enhanced Boolean functions suitable for the filter model of pseudo-random generator, Des. Codes Crypt., 76 (2015), 571-587. doi: 10.1007/s10623-014-9978-9. Google Scholar

[4]

N. Courtois, Fast algebraic attacks on stream ciphers with linear feedback, Advances in Cryptology-CRYPTO 2003, Springer, 2003,177-194. doi: 10.1007/978-3-540-45146-4_11. Google Scholar

[5]

N. Courtois and W. Meier, Algebraic attacks on stream ciphers with linear feedback, in Advances in Cryptology, Springer, 2002,346-359. doi: 10.1007/3-540-39200-9_21. Google Scholar

[6]

Y. Du, F. Zhang and M. Liu, On the resistance of Boolean functions against fast algebraic attacks, in ICISC 2011, Springer, 2012,261-274. doi: 10.1007/978-3-642-31912-9_18. Google Scholar

[7]

X. Feng and G. Gong, On algebraic immunity of trace inverse functions over finite fields with characteristic two, Cryptology ePrint Archive: Report 2013/585.Google Scholar

[8]

M. LiuD. Lin and D. Pei, Fast algebraic attacks and decomposition of symmetric Boolean functions, IEEE Trans. Inf. Theory, 57 (2011), 4817-4821. doi: 10.1109/TIT.2011.2145690. Google Scholar

[9]

W. Meier, E. Pasalic and C. Carlet, Algebraic attacks and decomposition of Boolean functions, in Eurocrypt 2004, Springer, 2004,474-491. doi: 10.1007/978-3-540-24676-3_28. Google Scholar

[10]

Y. Nawaz, G. Gong and K. C. Gupta, Upper bounds on algebraic immunity of Boolean power functions, in 13th Int. Workshop Fast Softw. Encrypt., Springer, 2006,375-389.Google Scholar

[11]

K. Nyberg, Differentially uniform mappings for cryptography, in Eurocrypt 1993, Springer, 1994, 55-64. doi: 10.1007/3-540-48285-7_6. Google Scholar

[12]

E. Pasalic, Almost fully optimized infinite classes of Boolean functions resistant to (fast) algebraic cryptanalysis, in ICISC 2008, Springer, 2008,399-414. doi: 10.1007/978-3-642-00730-9_25. Google Scholar

[13]

C. Shannon, Communication theory of secrecy systems, Bell Syst. Techn. J., 28 (1949), 656-715. doi: 10.1002/j.1538-7305.1949.tb00928.x. Google Scholar

show all references

References:
[1]

C. Carlet, Boolean functions for cryptography and error correcting codes, in Boolean Models and Methods in Mathematics, Computer Science, and Engineering (eds. Y. Crama and P. L. Hammer), Cambridge Univ. Press, 2010,257-397. doi: 10.1017/CBO9780511780448. Google Scholar

[2]

C. Carlet and K. Feng, An infinite class of balanced functions with optimal algebraic immunity, good immunity to fast algebraic attacks and good nonlinearity, in Adv. Crypt. -ASIACRYPT 2008, Springer, 2008,425-440. doi: 10.1007/978-3-540-89255-7_26. Google Scholar

[3]

C. Carlet and D. Tang, Enhanced Boolean functions suitable for the filter model of pseudo-random generator, Des. Codes Crypt., 76 (2015), 571-587. doi: 10.1007/s10623-014-9978-9. Google Scholar

[4]

N. Courtois, Fast algebraic attacks on stream ciphers with linear feedback, Advances in Cryptology-CRYPTO 2003, Springer, 2003,177-194. doi: 10.1007/978-3-540-45146-4_11. Google Scholar

[5]

N. Courtois and W. Meier, Algebraic attacks on stream ciphers with linear feedback, in Advances in Cryptology, Springer, 2002,346-359. doi: 10.1007/3-540-39200-9_21. Google Scholar

[6]

Y. Du, F. Zhang and M. Liu, On the resistance of Boolean functions against fast algebraic attacks, in ICISC 2011, Springer, 2012,261-274. doi: 10.1007/978-3-642-31912-9_18. Google Scholar

[7]

X. Feng and G. Gong, On algebraic immunity of trace inverse functions over finite fields with characteristic two, Cryptology ePrint Archive: Report 2013/585.Google Scholar

[8]

M. LiuD. Lin and D. Pei, Fast algebraic attacks and decomposition of symmetric Boolean functions, IEEE Trans. Inf. Theory, 57 (2011), 4817-4821. doi: 10.1109/TIT.2011.2145690. Google Scholar

[9]

W. Meier, E. Pasalic and C. Carlet, Algebraic attacks and decomposition of Boolean functions, in Eurocrypt 2004, Springer, 2004,474-491. doi: 10.1007/978-3-540-24676-3_28. Google Scholar

[10]

Y. Nawaz, G. Gong and K. C. Gupta, Upper bounds on algebraic immunity of Boolean power functions, in 13th Int. Workshop Fast Softw. Encrypt., Springer, 2006,375-389.Google Scholar

[11]

K. Nyberg, Differentially uniform mappings for cryptography, in Eurocrypt 1993, Springer, 1994, 55-64. doi: 10.1007/3-540-48285-7_6. Google Scholar

[12]

E. Pasalic, Almost fully optimized infinite classes of Boolean functions resistant to (fast) algebraic cryptanalysis, in ICISC 2008, Springer, 2008,399-414. doi: 10.1007/978-3-642-00730-9_25. Google Scholar

[13]

C. Shannon, Communication theory of secrecy systems, Bell Syst. Techn. J., 28 (1949), 656-715. doi: 10.1002/j.1538-7305.1949.tb00928.x. Google Scholar

[1]

Claude Carlet, Brahim Merabet. Asymptotic lower bound on the algebraic immunity of random balanced multi-output Boolean functions. Advances in Mathematics of Communications, 2013, 7 (2) : 197-217. doi: 10.3934/amc.2013.7.197

[2]

Sihong Su. A new construction of rotation symmetric bent functions with maximal algebraic degree. Advances in Mathematics of Communications, 2019, 13 (2) : 253-265. doi: 10.3934/amc.2019017

[3]

Laura Luzzi, Ghaya Rekaya-Ben Othman, Jean-Claude Belfiore. Algebraic reduction for the Golden Code. Advances in Mathematics of Communications, 2012, 6 (1) : 1-26. doi: 10.3934/amc.2012.6.1

[4]

Javier de la Cruz, Michael Kiermaier, Alfred Wassermann, Wolfgang Willems. Algebraic structures of MRD codes. Advances in Mathematics of Communications, 2016, 10 (3) : 499-510. doi: 10.3934/amc.2016021

[5]

Peter Haïssinsky, Kevin M. Pilgrim. An algebraic characterization of expanding Thurston maps. Journal of Modern Dynamics, 2012, 6 (4) : 451-476. doi: 10.3934/jmd.2012.6.451

[6]

Aihua Li. An algebraic approach to building interpolating polynomial. Conference Publications, 2005, 2005 (Special) : 597-604. doi: 10.3934/proc.2005.2005.597

[7]

Elisa Gorla, Felice Manganiello, Joachim Rosenthal. An algebraic approach for decoding spread codes. Advances in Mathematics of Communications, 2012, 6 (4) : 443-466. doi: 10.3934/amc.2012.6.443

[8]

Z. Reichstein and B. Youssin. Parusinski's "Key Lemma" via algebraic geometry. Electronic Research Announcements, 1999, 5: 136-145.

[9]

Vu Hoang Linh, Volker Mehrmann. Spectral analysis for linear differential-algebraic equations. Conference Publications, 2011, 2011 (Special) : 991-1000. doi: 10.3934/proc.2011.2011.991

[10]

L. Yu. Glebsky and E. I. Gordon. On approximation of locally compact groups by finite algebraic systems. Electronic Research Announcements, 2004, 10: 21-28.

[11]

Feng Rong. Non-algebraic attractors on $\mathbf{P}^k$. Discrete & Continuous Dynamical Systems - A, 2012, 32 (3) : 977-989. doi: 10.3934/dcds.2012.32.977

[12]

Marco Calderini. A note on some algebraic trapdoors for block ciphers. Advances in Mathematics of Communications, 2018, 12 (3) : 515-524. doi: 10.3934/amc.2018030

[13]

Heide Gluesing-Luerssen, Uwe Helmke, José Ignacio Iglesias Curto. Algebraic decoding for doubly cyclic convolutional codes. Advances in Mathematics of Communications, 2010, 4 (1) : 83-99. doi: 10.3934/amc.2010.4.83

[14]

B. Harbourne, P. Pokora, H. Tutaj-Gasińska. On integral Zariski decompositions of pseudoeffective divisors on algebraic surfaces. Electronic Research Announcements, 2015, 22: 103-108. doi: 10.3934/era.2015.22.103

[15]

Patrick Foulon, Boris Hasselblatt. Lipschitz continuous invariant forms for algebraic Anosov systems. Journal of Modern Dynamics, 2010, 4 (3) : 571-584. doi: 10.3934/jmd.2010.4.571

[16]

M. D. König, Stefano Battiston, M. Napoletano, F. Schweitzer. On algebraic graph theory and the dynamics of innovation networks. Networks & Heterogeneous Media, 2008, 3 (2) : 201-219. doi: 10.3934/nhm.2008.3.201

[17]

Alex L Castro, Wyatt Howard, Corey Shanbrom. Bridges between subriemannian geometry and algebraic geometry: Now and then. Conference Publications, 2015, 2015 (special) : 239-247. doi: 10.3934/proc.2015.0239

[18]

Sylvain E. Cappell, Anatoly Libgober, Laurentiu Maxim and Julius L. Shaneson. Hodge genera and characteristic classes of complex algebraic varieties. Electronic Research Announcements, 2008, 15: 1-7. doi: 10.3934/era.2008.15.1

[19]

Jianjun Paul Tian. Algebraic model of non-Mendelian inheritance. Discrete & Continuous Dynamical Systems - S, 2011, 4 (6) : 1577-1586. doi: 10.3934/dcdss.2011.4.1577

[20]

Jaume Llibre, Claudia Valls. Algebraic limit cycles for quadratic polynomial differential systems. Discrete & Continuous Dynamical Systems - B, 2018, 23 (6) : 2475-2485. doi: 10.3934/dcdsb.2018070

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (8)
  • HTML views (8)
  • Cited by (0)

Other articles
by authors

[Back to Top]