Informatics and Applications
2019, Volume 13, Issue 2, pp 37-46
ON LOCAL AFFINITY BASED METHOD OF SOLVING SYSTEMS OF QUADRATIC BOOLEAN EQUATIONS
- O. A. Logachev
- A. A. Sukayev
- S. N. Fedorov
Abstract
Solving nonlinear systems of Boolean equations is NP-hard. Nevertheless, certain classes of such systems can be solved by efficient algorithms. There are theoretical and applied reasons for studying these classes and designing corresponding efficient algorithms. The paper proposes an approach to solving the systems of quadratic equations over two-element field. The method makes use of the quadratic functions' representation by their affine normal forms, i. e., in a sense, of their piecewise affine approximation. So, the initial nonlinear instance comes to a number of linear equations systems of the same variables. The paper also discusses possible ways to reduce the complexity of the proposed method.
[+] References (11)
- Shannon, C. 1949. Communication theory of secrecy systems. Bell Syst. Tech. J. 28 (4):656-715.
- 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 ePrint Archive. Report 2007/024. Available at: http://eprint.iacr.org/2007/024.pdf (accessed August 30, 2018).
- Logachev, O.A., A.A. Sukayev, and S.N. Fedorov
2019. Polinomial'nye algoritmy vychisleniya lokal'nykh affinnostey kvadratichnykh bulevykh funktsiy [Polynomial algorithms for constructing local affinities of quadratic Boolean functions]. Informatika i ee Primeneniya - Inform. Appl. 13(1):67-74.
- Logachev, O.A. 2009. Ob ispol'zovanii affinnykh nor- mal'nykh form bulevykh funktsiy dlya opredeleniya klyuchey fil'truyushchikh generatorov [On using affine normal forms of Boolean functions for identifying filter generator keys]. 4th Conference (International) on Security and Counteraction to Terrorism Proceedings. Moscow. 2:101-109.
- 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.
- Fraenkel, A. S., and Y. Yesha. 1980. Complexity of solving algebraic equations. Inform. Process. Lett. 10(4-5):178- 179.
- 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' reshe- niya sistem bulevykh uravneniy [Complexity of solving the systems of Boolean equations]. Moscow: Kurs. 192 p.
- Simpson, L. R., E. Dawson, J. Dj. Golic, and W. L. Mil- lan. 2001. LILI keystream generator. Selected areas in cryptography. Eds. D. R. Stinson and S. Tavares. Lecture notes in computer science ser. Springer. 2012:248-261.
- Logachev, O. A., V. V. Yashchenko, and M. P. Denisenko.
2008. Local affinity of Boolean mappings. Boolean Functions in Cryptology and Information Security: Proc. NATO Advanced Study Institute. IOS Press. 148-172.
[+] About this article
Title
ON LOCAL AFFINITY BASED METHOD OF SOLVING SYSTEMS OF QUADRATIC BOOLEAN EQUATIONS
Journal
Informatics and Applications
2019, Volume 13, Issue 2, pp 37-46
Cover Date
2019-06-30
DOI
10.14357/19922264190206
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; affine normal form; algebraic cryptanalysis
Authors
O. A. Logachev  , A. A. Sukayev  , and S. N. Fedorov
Author Affiliations
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
M. V Lomonosov Moscow State University, 1 Michurinskiy Prosp., Moscow 119192, Russian Federation
|