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.
Type: | Proceedings paper |
---|---|
Title: | Two philosophies for solving non-linear equations in algebraic cryptanalysis |
Event: | International Conference on Cryptology in Malaysia - Mycrypt 2016: Paradigms in Cryptology – Mycrypt 2016. Malicious and Exploratory Cryptology pp |
ISBN-13: | 9783319612720 |
Open access status: | An open access version is available from UCL Discovery |
DOI: | 10.1007/978-3-319-61273-7_27 |
Publisher version: | https://doi.org/10.1007/978-3-319-61273-7_27 |
Language: | English |
Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
Keywords: | algebraic cryptanalysis, finite fields, overdefined systems of equations, NP-hard problems, phase transitions, XL algorithm, Gr¨obner bases, XSL algorithm, degree falls, mutants, ElimLin, error correcting codes, algebraic codes, elliptic curves, ECDL problem, Semaev polynomials, block ciphers, Simon cipher |
UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
URI: | https://discovery.ucl.ac.uk/id/eprint/10133810 |
Archive Staff Only
View Item |