Informatics and Applications
2019, Volume 13, Issue 1, pp 67-74
POLYNOMIAL ALGORITHMS FOR CONSTRUCTING LOCAL AFFINITIES OF QUADRATIC BOOLEAN FUNCTIONS
- O. A. Logachev
- A. A. Sukayev
- S.N. Fedorov
Abstract
Due to the affine normal form, one can consider a Boolean function as affine on certain flats in its domain - so-called local affinities. This Boolean function representation - affine approximation - could be useful for solving systems of nonlinear equations over two-element field. The problem of solving these systems (of a special sort) arises, in particular, in some methods of the information security tools design and analysis. The paper describes an approach to finding local affinities for quadratic Boolean functions which is based on Dickson's theorem. By this, one obtains affine normal forms for such functions. Besides, the paper concerns the efficiency of corresponding algorithms. This approach can be profitable for constructing efficient methods of solving systems of quadratic Boolean equations via "approximation" of corresponding Boolean functions by their affine normal forms.
[+] References (10)
- Garey, M. R., and D. S. Johnson. 1979. Computers and intractability: A guide to the theory of NP-completeness. San Francisco, CA: W H. Freeman and Co. 348 p.
- Gorshkov, S. P., and A. V. Tarasov 2017. Slozhnost' resheniya sistem bulevykh uravneniy [Complexity of solving the systems of Boolean equations]. Moscow: Kurs. 192 p.
- Smirnov, V. G. 2000. Nekotorye klassy effektivno reshaemykh sistem bulevykh uravneniy [Some classes of Boolean equation systems permitting effective solution]. Trudy po diskretnoy matematike [Proceedings on Discrete Mathematics] 3:269-282.
- Bard, G. V. 2009. Algebraic cryptanalysis. Springer. 389 p.
- Bard, G., N. Courtois, and C. Jefferson. 2007. Efficient methods for conversion and solution of sparse systems of low-degree multivariate polynomials over GF(2) via SAT- solvers. Cryptology ePrintArchive. Report 2007/024. Available at: http://eprint.iacr.org/2007/024.pdf (accessed August 30, 2018).
- Logachev, O.A., A. A. Sal'nikov, S.V. Smyshlyaev, and V. V. Yashchenko .2015. Bulevyfunktsii v teorii kodirovan iya
i kriptologii [Boolean functions in coding theory and cryp-tology]. Moscow: LENAND. 576 p.
- MacWilliams, FJ., and N.J. A. Sloane. 1977. The theory of error-correcting codes. North-Holland mathematical library ser. North-Holland Publishing Co. 774 p.
- Logachev, O. A., V. V. Yashchenko, and M. P. Denisenko. 2008. Local affinity of Boolean mappings. Boolean functions in cryptology and information security: Proceedings of the NATO Advanced Study Institute. IOS Press. 148-172.
- Gorshkov, S. P. 1995. Primenenie teorii NP-polnykh zadach dlya otsenki slozhnosti resheniya sistem bulevykh uravneniy [Application of the NP-complete problem theory to assessment of complexity of solving the systems of Boolean equations]. Obozrenieprikladnoy ipromyshlennoy matematiki [Applied and Industrial Mathematics Review] 2(3):325-398.
- Dickson, L. E. 1901. Linear groups: With an exposition of the Galois field theory. Leipzig: B. G. Teubner. 322 p.
[+] About this article
Title
POLYNOMIAL ALGORITHMS FOR CONSTRUCTING LOCAL AFFINITIES OF QUADRATIC BOOLEAN FUNCTIONS
Journal
Informatics and Applications
2019, Volume 13, Issue 1, pp 67-74
Cover Date
2019-04-30
DOI
10.14357/19922264190110
Print ISSN
1992-2264
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
Boolean function; system of quadratic Boolean equations; vector space partition; flat; local affinity; Dickson's theorem; affine normal form (ANF) of Boolean function; algebraic cryptanalysis
Authors
O. A. Logachev  ,  , A. A. Sukayev , and S.N. Fedorov
Author Affiliations
Information Security Institute, M. V. Lomonosov Moscow State University, 1 Michurinskiy Prosp., Moscow 119192, Russian Federation
Institute of Informatics Problems, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation
|