Courtois, NT; (2017) Two philosophies for solving non-linear equations in algebraic cryptanalysis. In: Proceedings of the International Conference on Cryptology in Malaysia - Mycrypt 2016: Paradigms in Cryptology – Mycrypt 2016. Malicious and Exploratory Cryptology pp. (pp. pp. 506-520). Springer: Kuala Lumpur, Malaysia,.

Preview

Text Igamma-Mycrypt2016.pdf - Accepted Version Download (283kB) | Preview

Abstract

Algebraic Cryptanalysis [45] is concerned with solving of particular systems of multivariate non-linear equations which occur in cryptanalysis. Many different methods for solving such problems have been proposed in cryptanalytic literature: XL and XSL method, Gröbner bases, SAT solvers, as well as many other. In this paper we survey these methods and point out that the main working principle in all of them is essentially the same. One quantity grows faster than another quantity which leads to a “phase transition” and the problem becomes efficiently solvable. We illustrate this with examples from both symmetric and asymmetric cryptanalysis. In this paper we point out that there exists a second (more) general way of formulating algebraic attacks through dedicated coding techniques which involve redundancy with addition of new variables. This opens numerous new possibilities for the attackers and leads to interesting optimization problems where the existence of interesting equations may be somewhat deliberately engineered by the attacker.

Download activity - last month

Export as JSONCSVXML

Download activity - last 12 months

Export as CSVXMLJSON

Downloads by country - last 12 months

Export as JSONXMLCSV

Archive Staff Only

View Item