nach oben

Designs, Codes and Cryptography

Erschienen in:

26.07.2016

Upper bounds on the complexity of algebraic cryptanalysis of ciphers with a low multiplicative complexity

verfasst von: Pavol Zajac

Erschienen in: Designs, Codes and Cryptography | Ausgabe 1-2/2017

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

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.

Vorheriger Artikel Improving algebraic attacks on stream ciphers based on linear feedback shift register over

Nächster Artikel MacWilliams Extension Theorem for MDS codes over a vector space alphabet

Nur mit Berechtigung zugänglich

Which in hindsight is similar to an informal proposal from [12, Sect. 5], but based on different premises.

The bits of a possible initialization vector from the introduction part become affine constants in this model.

Cipher design where only operations modular Addition, bit Rotation, and XOR are used.

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).

10.

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).

11.

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).

12.

Raddum H.: MRHS equation systems. In: Selected Areas in Cryptography. Lecture Notes in Computer Science, pp. 232–245. Springer, Berlin (2007).

13.

Raddum H., Semaev I.: Solving multiple right hand sides linear equations. Des. Codes Cryptogr. 49(1–3), 147–160 (2008).

14.

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.

15.

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).

16.

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).

17.

Semaev I.: On solving sparse algebraic equations over finite fields. Department of Informatics, University of Bergen, Tech. Rep. (2005).

18.

Semaev I.: On solving sparse algebraic equations over finite fields. Des. Codes Cryptogr. 49(1–3), 47–60 (2008).

19.

Semaev I., Mikuš M.: Methods to solve algebraic equations in cryptanalysis. Tatra Mountains Math. Publ. 45, 107–136 (2010).

20.

Sendrier N.: Decoding one out of many. In: Post-Quantum Cryptography, pp. 51–67. Springer, Berlin (2011).

21.

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).

22.

The Sage Developers: SageMath, the Sage Mathematics Software System (Version 7.2) (2016). http://www.sagemath.org.

23.

Zajac P.: A new method to solve MRHS equation systems and its connection to group factorization. J. Math. Cryptol. 7(4), 367–381 (2013).CrossRefMATHMathSciNet

24.

Zajac P.: GitHub - zajacpa/DecodingAttack: demonstration of the decoding attack on SIMON-32. https://github.com/zajacpa/DecodingAttack (2016).

25.

Zajac P., Jókay, M.: Multiplicative complexity of bijective \(4 \times 4\) S-boxes. Cryptogr. Commun. 6(3), 255–277 (2014).

26.

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).

Titel: Upper bounds on the complexity of algebraic cryptanalysis of ciphers with a low multiplicative complexity
verfasst von: Pavol Zajac
Publikationsdatum: 26.07.2016
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 1-2/2017
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-016-0256-x

Springer Professional

Upper bounds on the complexity of algebraic cryptanalysis of ciphers with a low multiplicative complexity

Abstract

Premium Partner

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 1-2/2017

Redefining the transparency order

Symmetric disjunctive list-decoding codes

Revisiting (nested) Roos bias in RC4 key scheduling algorithm

Almost cover-free codes and designs

Joint data and key distribution of simple, multiple, and multidimensional linear cryptanalysis test statistic and its impact to data complexity

Row reduction applied to decoding of rank-metric and subspace codes

Premium Partner