Upper bounds on the complexity of algebraic cryptanalysis of ciphers with a low multiplicative complexity
Tóm tắt
Lightweight cipher designs try to minimize the implementation complexity of the cipher while maintaining some specified security level. Using only a small number of AND gates lowers the implementation costs, and enables easier protections against side-channel attacks. In our paper we study the connection between the number of AND gates (multiplicative complexity) and the complexity of algebraic attacks. We model the encryption with multiple right-hand sides (MRHS) equations. The resulting equation system is transformed into a syndrome decoding problem. The complexity of the decoding problem depends on the number of AND gates, and on the relative number of known output bits with respect to the number of unknown key bits. This allows us to apply results from coding theory, and to explicitly connect the complexity of the algebraic cryptanalysis to the multiplicative complexity of the cipher. This means that we can provide asymptotic upper bounds on the complexity of algebraic attacks on selected families of ciphers based on the hardness of the decoding problem.
Tài liệu tham khảo
Albrecht M.R., Rechberger C., Schneider T., Tiessen T., Zohner M.: Ciphers for MPC and FHE. In: Advances in Cryptology—EUROCRYPT 2015, pp. 430–454. Springer, Berlin (2015).
Bard G.V., Courtois N.T., Jefferson C.: 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 (2007). http://eprint.iacr.org/.
Beaulieu R., Shors D., Smith J., Treatman-Clark S., Weeks B., Wingers L.: The SIMON and SPECK families of lightweight block ciphers. IACR Cryptology ePrint Archive (2013).
Becker A., Joux A., May A., Meurer A.: Decoding random binary linear codes in \(2^{n/20}\): How \(1+ 1= 0\) improves information set decoding. In: Advances in Cryptology—EUROCRYPT 2012, pp. 520–536. Springer, Berlin (2012).
Bogdanov A., Knudsen L.R., Leander G., Paar C., Poschmann A., Robshaw M.J., Seurin Y., Vikkelsoe C.: PRESENT: An Ultra-lightweight Block Cipher. Springer, Berlin (2007).
Boyar J., Peralta R., Pochuev D.: On the multiplicative complexity of boolean functions over the basis \((\wedge ,\oplus , 1)\). Theor. Comput. Sci. 235(1), 43–57 (2000).
Courtois N., Hulme D., Mourouzis T.: Solving circuit optimisation problems in cryptography and cryptanalysis. Cryptology ePrint Archive, Report 2011/475 (2011).
De Cannière C.: Trivium: A stream cipher construction inspired by block cipher design principles. In: Information Security, pp. 171–186. Springer, Berlin (2006).
Faugère J.C.: A new efficient algorithm for computing Gröbner bases without reduction to zero (F5). In: Workshop on Applications of Commutative Algebra, Catania, Italy, 3–6 Apr 2002. ACM Press, New York (2002).
Lee P.J., Brickell E.F.: An observation on the security of McEliece’s public-key cryptosystem. In: Workshop on the Theory and Application of of Cryptographic Techniques, pp. 275–280. Springer, Berlin (1988).
Magliveras S.S., Stinson D.R., van Trung T.: New approaches to designing public key cryptosystems using one-way functions and trapdoors in finite groups. J. Cryptol. 15(4), 285–297 (2002).
Raddum H.: MRHS equation systems. In: Selected Areas in Cryptography. Lecture Notes in Computer Science, pp. 232–245. Springer, Berlin (2007).
Raddum H., Semaev I.: Solving multiple right hand sides linear equations. Des. Codes Cryptogr. 49(1–3), 147–160 (2008).
Schilling T., Raddum H.: Solving equation systems by agreeing and learning. In: Hasan M., Helleseth T. (eds.) Arithmetic of Finite Fields. Lecture Notes in Computer Science, vol. 6087, pp. 151–165. Springer, Berlin (2010). doi:10.1007/978-3-642-13797-6_11.
Schilling T.E., Raddum H.: Analysis of Trivium using compressed right hand side equations. In: Information Security and Cryptology-ICISC 2011, pp. 18–32. Springer, Berlin (2012).
Schilling T.E., Raddum H.: Solving compressed right hand side equation systems with linear absorption. In: Sequences and Their Applications—SETA 2012, pp. 291–302. Springer, Berlin (2012).
Semaev I.: On solving sparse algebraic equations over finite fields. Department of Informatics, University of Bergen, Tech. Rep. (2005).
Semaev I.: On solving sparse algebraic equations over finite fields. Des. Codes Cryptogr. 49(1–3), 47–60 (2008).
Semaev I., Mikuš M.: Methods to solve algebraic equations in cryptanalysis. Tatra Mountains Math. Publ. 45, 107–136 (2010).
Sendrier N.: Decoding one out of many. In: Post-Quantum Cryptography, pp. 51–67. Springer, Berlin (2011).
Sönmez M.T., Peralta R.: The multiplicative complexity of boolean functions on four and five variables. In: Lightweight Cryptography for Security and Privacy, pp. 21–33. Springer, Berlin (2015).
The Sage Developers: SageMath, the Sage Mathematics Software System (Version 7.2) (2016). http://www.sagemath.org.
Zajac P.: A new method to solve MRHS equation systems and its connection to group factorization. J. Math. Cryptol. 7(4), 367–381 (2013).
Zajac P.: GitHub - zajacpa/DecodingAttack: demonstration of the decoding attack on SIMON-32. https://github.com/zajacpa/DecodingAttack (2016).
Zajac P., Jókay, M.: Multiplicative complexity of bijective \(4 \times 4\) S-boxes. Cryptogr. Commun. 6(3), 255–277 (2014).
Zhu B.: GitHub - bozhu/NSA-ciphers: SIMON and SPECK, the two lightweight block ciphers dedesign by the researchers from NSA. https://github.com/bozhu/NSA-ciphers (2016).