Skip to Main content Skip to Navigation
Conference papers

On algebraic cryptanalysis of ciphers with low multiplicative complexity

Abstract : In this article we study the application of multiple righthand sides (MRHS) equations in algebraic attacks against ciphers with low multiplicative complexity. Each AND gate in the circuit description is converted to a corresponding MRHS equation. The resulting system is transformed into a syndrome decoding problem. The complexity of the decoding problem then 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 explicitly connect the complexity of algebraic cryptanalysis to the multiplicative complexity of the cipher.
Document type :
Conference papers
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download
Contributor : Jean-Pierre Tillich Connect in order to contact the contributor
Submitted on : Friday, February 19, 2016 - 2:48:55 PM
Last modification on : Monday, February 22, 2016 - 11:15:52 AM
Long-term archiving on: : Saturday, November 12, 2016 - 11:41:44 PM


Files produced by the author(s)


  • HAL Id : hal-01276499, version 1



Pavol Zajac. On algebraic cryptanalysis of ciphers with low multiplicative complexity. The 9th International Workshop on Coding and Cryptography 2015 WCC2015, Anne Canteaut, Gaëtan Leurent, Maria Naya-Plasencia, Apr 2015, Paris, France. ⟨hal-01276499⟩



Record views


Files downloads