The recent algebraic attacks have received a lot of attention in cryptographic literature. The algebraic immunity of a Boolean function quantifies its resistance to the standard algebraic attacks of the pseudo-random generators using it as a nonlinear filtering or combining function. This survey contains brief description of algebraic attacks and results have been found concerning the algebraic immunity and its relations with the other cryptographic parameters.
Download file
Counter downloads: 126
- Title THE ALGEBRAIC IMMUNITY OF BOOLEAN FUNCTIONS
- Headline THE ALGEBRAIC IMMUNITY OF BOOLEAN FUNCTIONS
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 2(2)
- Date:
- DOI
Keywords
криптография , алгебраическая атака , булевы функции , алгебраический иммунитет Authors
References
Lobanov M. Tight bounds between algebraic immunity and nonlinearities of high orders // Cryptology ePrint Archive 2007/444.
Mesnager S. Improving the lower bound on the higher order nonlinearity of Boolean functions with prescribed algebraic immunity // Cryptology ePrint Archive 2007/117.
Carlet С. On the higher order nonlinearities of algebraic immune Boolean functions // Proceedings of Crypto 2006, Lecture Notes in Computer Science. 2006. V. 4117. P. 584 - 601.
Ars G.,Faugere J. Algebraic Immunities of functions over finite fields // INRIA, Rapport de recherchй №5532. 2005.
Dalai D., Maitra S. Balanced Boolean Functions with (more than) Maximum Algebraic Immunity // Proceedings of WCC. 2007. P. 99-108.
Nawaz Y., Gupta К., Gong G. Efficient Techniques to Find Algebraic Immunity of S-boxes Based on Power Mappings // Proceedings of WCC. 2007. P. 237 - 246.
Canteaut A. Open problems related to algebraic attacks on stream ciphers // Proceedings of WCC 2005, Lecture Notes in Computer Science. 2006. V. 3969. P. 120 - 134.
Баев В.В. Эффективные алгоритмы получения оценок алгебраической иммунности булевых функций // Дис. ... канд. физ.-мат. наук. М.: МГУ им. М.В.Ломоносова, 2007.
Wang Y., Fan S., Han W. New construction of Boolean function with optimum algebraic immunity // Cryptology ePrint Archive 2008/176.
Liu F., Feng K. On the 2m-variable Symmetric Boolean Functions with Maximum Algebraic Immunity 2m 1 // Proceedings of WCC. 2007. P. 225-232.
Carlet С. A method of construction of balanced functions with optimum algebraic immunity // Cryptology ePrint Archive 2006/149.
Li N., Qi W. Construction and analysis of Boolean functions of 2t+1 variables with maximum algebraic immunity // Proceedings of Asiacrypt 2006, Lecture Notes in Computer Sciences. 2006. V. 4284. P. 84-98.
Dalai D., Gupta K., Maitra S. Results on algebraic immunity for cryptographically significant Boolean functions // Proceedings of Indocrypt 2004, Lecture Notes in Computer Sciences. 2004. V. 3348. P. 92 - 106.
Braeken A., Preneel B. On the algebraic immunity of symmetric Boolean functions // Proceedings of Indocrypt 2005, Lecture Notes in Computer Sciences. 2005. V. 3797. P. 35 - 48.
Armknecht F., Krause M. Constracting Single- and Multi-output Boolean Functions with Maximal Algebraic Immunity // Proceedings of ICALP 2006, Lecture Notes in Computer Sciences. 2006. V. 4052. P. 180 - 191.
Carlet C., Dalai D., Gupta K., Maitra S. Algebraic immunity for cryptographically significant Boolean functions: analysis and construction//IEEE Transactions on Information Theory. 2006. V. 52. No. 7. P. 3105-3121.
Dalai D., Gupta K., Maitra S. Cryptographically significant Boolean functions: construction and analysis in terms of algebraic immunity // Proceedings of FSE 2005, Lecture Notes in Computer Sciences. 2005. V. 3557. P. 98 - 111.
Carlet С., Zeng X., Li С., Ни L. Further properties of several classes of Boolean functions with optimal algebraic immunity // Cryptology ePrint Archive 2007/370.
Dalai D., Maitra S., Sarkar S. Basic theory in construction of Boolean functions with maximum possible annihilator immunity // Designs, Codes and Cryptography. 2006. V. 40. No 1. P. 41 - 58.
Lobanov M. Tight bound between nonlinearity and algebraic immunity // Cryptology ePrint Archive 2005/441.
Tu Z., Yingpu Deng Y. Algebraic Immunity Hierarchy of Boolean Functions // Cryptology ePrint Archive 2007/259.
Didier F. A new upper bound of the block error probability after decoding over the erasure channel // IEEE Transactions On Information Theory. 2006. V. 52. No. 10. P. 4496 - 4503.
Courtois N. Cryptanalysis of SFINKS // Proceedings of ISICS 2005, Lecture Notes in Computer Sciences. 2005. V. 3935. P. 261-269.
Meier W., Pasalic E., Carlet С. Algebraic Attacks and Decomposition of Boolean Functions // Proceedings of Eurocrypt 2004, Lecture Notes in Computer Sciences. 2004. V. 3027. P. 474 - 491.
Armknecht F. Improving Fast Algebraic Attacks // Proceedings of FSE 2004, Lecture Notes in Computer Sciences. 2004 V. 3017. P. 65-82.
Hawkes P., Rose G. Rewriting Variables: the Complexity of Fast Algebraic Attacks on Stream Ciphers // Proceedings of Crypto 2004, Lecture Notes in Computer Sciences. 2004. V. 3152. P. 390 - 406.
Courtois N. Fast Algebraic Attacks on Stream Ciphers with Linear Feedback // Proceedings of Crypto 2003, Lecture Notes in Computer Sciences. 2003. V. 2729. P. 176 - 194.
Courtois N., Meier W. Algebraic Attacks on Stream Ciphers with Linear Feedback // Proceedings of Eurocrypt 2003, Lecture Notes in Computer Sciences. 2003. V. 2656. P. 345 - 359.
THE ALGEBRAIC IMMUNITY OF BOOLEAN FUNCTIONS | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2008. № 2(2).
Download full-text version
Download fileCounter downloads: 410