Solving Trivium-based Boolean Equations Using the Method of Syllogisms

• Autorzy: Zajac P.
• Języki publikacji: EN

Abstrakty

EN

The article examines a practical application of the method of syllogisms to solve a system of Boolean equations arising in the cryptanalysis of the stream cipher Trivium. Experimental results show that different guessing strategies lead to significantly different complexities of generic attacks. A new experimental approach is presented that can be used to estimate lower bounds on the complexity of such attacks.

Słowa kluczowe

EN

Boolean equations; algebraic cryptanalysis; method of syllogisms; trivium

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 114, nr 3/4
• Strony: 359--373
• Opis fizyczny: Bibliogr. 11 poz., tab., wykr.

Twórcy

autor

Zajac P.

• Department of Applied Informatics and IT Slovak University of Technology Bratislava, Slovakia,

Bibliografia

• [1] Bard, G.: Algebraic Cryptanalysis, Springer, 2009, ISBN 978-0-387-88756-2.
• [2] Cannière, C. D., Preneel, B.: Trivium - A Stream Cipher Construction Inspired by Block Cipher Design Principles., Technical report, eSTREAM, ECRYPT Stream Cipher, 2005.
• [3] Maximov, A., Biryukov, A.: Two Trivial Attacks on Trivium, Selected Areas in Cryptography (C. M. Adams, A. Miri, M. J. Wiener, Eds.), 4876, Springer, 2007, ISBN 978-3-540-77359-7.
• [4] Pieprzyk, J., McDonald, C., Charnes, C.: An algebraic analysis of Trivium ciphers based on the Boolean satisfiability problem, Cryptology ePrint Archive: Report 129/2007, http://eprint.iacr.org/2007/129, 2007.
• [5] Raddum, H.: Cryptanalytic results on TRIVIUM., Technical Report 2006/039, eSTREAM, ECRYPT Stream Cipher Project, 2006.
• [6] Raddum, H., Semaev, I.: New technique for solving sparse equation systems, Cryptology ePrint Archive: Report 475/2006, http://eprint.iacr.org/2006/475, 2006.
• [7] Schilling, T., Zajac, P.: Phase transition in a system of random sparse Boolean equations, Tatra Mt. Math. Publs., 45, 2010, 93-105.
• [8] Wong, K. K.-H., Bard, G. V.: Improved Algebraic Cryptanalysis of QUAD, Bivium and Trivium via Graph Partitioning on Equation Systems, Cryptology ePrint Archive: Report 349/2010, http://eprint.iacr.
• [9] Zajac, P.: On the use of the method of syllogisms in algebraic cryptanalysis, Proceedings of the 1st Plenary Conference of the NIL-I-004, University of Bergen, 2009.
• [10] Zajac, P.: Implementation of the method of syllogisms, 2010, Preprint.
• [11] Zakrevskij, A., Vasilkova, I.: Reducing Large Systems of Boolean Equations, 4th International Workshop on Boolean Problems, Freiberg University, 2000.