Abstract
We study a new representation of non-linear multivariate equations for algebraic cryptanalysis. Using a combination of multiple right hand side equations and binary decision diagrams, our new representation allows a very efficient conjunction of a large number of separate equations. We apply our new technique to the stream cipher Trivium and variants of Trivium reduced in size. By merging all equations into one single constraint, manageable in size and processing time, we get a representation of the Trivium cipher as one single equation.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
McDonald, C., Charnes, C., Pieprzyk, J.: Attacking Bivium with MiniSat. eSTREAM, ECRYPT Stream Cipher Project, Report 2007/040 (2007), http://www.ecrypt.eu.org/stream
Raddum, H., Semaev, I.: Solving Multiple Right Hand Sides linear equations. Designs, Codes and Cryptography 49(1), 147–160 (2008)
Faugère, J.: A new efficient algorithm for computing Gröbner bases (F4). Journal of Pure and Applied Algebra 139(1-3), 61–88 (1999)
Courtois, N., Klimov, A., Patarin, J., Shamir, A.: Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 392–407. Springer, Heidelberg (2000)
Raddum, H.: MRHS Equation Systems. In: Adams, C., Miri, A., Wiener, M. (eds.) SAC 2007. LNCS, vol. 4876, pp. 232–245. Springer, Heidelberg (2007)
Semaev, I.: Sparse algebraic equations over finite fields. SIAM Journal on Computing 39(2), 388–409 (2009)
Akers, S.: Binary decision diagrams. IEEE Transactions on Computers 27(6), 509–516 (1978)
Somenzi, F.: Binary decision diagrams. In: Calculational System Design. NATO Science Series F: Computer and Systems Sciences, vol. 173, pp. 303–366. IOS Press (1999)
Knuth, D.: The Art of Computer Programming. vol. 4, Fascicles 0-4, The Art of Computer Programming. Addison Wesley (PEAR) (2009)
Krause, M.: BDD-Based Cryptanalysis of Keystream Generators. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 222–237. Springer, Heidelberg (2002)
Stegemann, D.: Extended BDD-Based Cryptanalysis of Keystream Generators. In: Adams, C., Miri, A., Wiener, M. (eds.) SAC 2007. LNCS, vol. 4876, pp. 17–35. Springer, Heidelberg (2007)
Bryant, R.E.: Graph-based algorithms for boolean function manipulation. IEEE Transactions on Computers 35, 677–691 (1986)
Cannière, C.D., Preneel, B.: Trivium specifications. ECRYPT Stream Cipher Project (2005)
Somenzi, F.: CUDD: CU Decision Diagram Package (2009), http://vlsi.colorado.edu/~fabio/CUDD/
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Schilling, T.E., Raddum, H. (2012). Analysis of Trivium Using Compressed Right Hand Side Equations. In: Kim, H. (eds) Information Security and Cryptology - ICISC 2011. ICISC 2011. Lecture Notes in Computer Science, vol 7259. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31912-9_2
Download citation
DOI: https://doi.org/10.1007/978-3-642-31912-9_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-31911-2
Online ISBN: 978-3-642-31912-9
eBook Packages: Computer ScienceComputer Science (R0)