Topics in Computational Number Theory and Cryptanalysis - On Euclidean Lattices, Edwards Curves and Cryptographic Multilinear Maps

Doctoral thesis (2021)

The content of this thesis is situated between number theory and cryptology. It contributes in several directions of mathematical cryptanalysis and arithmetic geometry, by the use of explicit and ... [more ▼]

The content of this thesis is situated between number theory and cryptology. It contributes in several directions of mathematical cryptanalysis and arithmetic geometry, by the use of explicit and computational methods in number theory. The thesis is divided into four main parts, describing four different works. The first part of this thesis treats cryptographic multilinear maps, introduced in the early 2000s, as extension of bilinear pairings on abelian varieties following a survey by Boneh and Silverberg (Contemp. Math. 2003). The difficulties of constructing efficient cryptographic multilinear maps from algebraic geometry led cryptographers to obtain multilinear maps from the notion of graded encoding systems, following the formalism of Garg, Gentry and Halevi (Eurocrypt 2013), backgrounded from ideas on fully homomorphic encryption. To this date, there are three candidate constructions. Their security however is rather poorly understood and many attacks have flourished over the past years. In this thesis, we consider the CLT13 Scheme, proposed by Coron, Lepoint and Tibouchi (Crypto 2013), constructing multilinear maps over the integers. A vulnerability of this scheme was detected by Gentry, Lewko and Waters (Crypto 2014), by exploiting the composite-ring structure of the plaintext space, enabling a simple two-dimensional lattice attack to reveal secret information. At the same time, the authors suggested a simple countermeasure to prevent this line of attack. By relying on high-dimensional lattice reduction, we design new cryptanalysis against CLT13, overriding the countermeasure of Gentry, Lewko and Waters by several orders of magnitude. Combined with the Cheon et al. attack (Eurocrypt 2015), we reveal all secret parameters of CLT13. By applying our cryptanalysis to concrete instantiations of CLT13-based construc- tions, certain parameter ranges are found unsecure. The second work presented in this thesis isolates the Hidden Lattice Problem as a more general problem appearing in several cryptographic scenarios, among which the Hidden Sub- set Sum Problem, studied by Nguyen and Stern (Crypto 1999). The Nguyen-Stern algorithm for the Hidden Subset Sum Problem builds on the use of orthogonal lattices, which have shown powerful in public-key cryptanalysis. After extending their algorithm to our more general setting, our main contribution is to present, based on duality in lattice theory, a new algorithm for the Hidden Lattice Problem, providing a competitive alternative to the cel- ebrated Nguyen-Stern orthogonal lattice attack. For both algorithms, we provide practical parameters, based on heuristic and rigorous studies of the geometry of the underlying lat- tices. The generality of our definition for the Hidden Lattice Problem allows encompassing multiple number-theoretic problems of cryptographic interest. For these problems, our new algorithm leads to a valuable alternative to the state-of-the-art algorithms. The third work presented in this thesis aims at extending the powerful cryptanalysis by Cheon et al. (Eurocrypt 2015) against the multiparty Diffie-Hellman protocol instantiated un- der the aforementioned CLT13 Scheme. To do so, we formulate, independently of the CLT- framework, a general problem on simultaneous diagonalization of special matrices of low- rank, which we call “incomplete”. Based on techniques from linear algebra, our major contri- bution is the design of efficient algorithms for this problem, providing explicit and practical parameters. We recognize that our algorithms also apply to solve the Approximate Common Divisor Problem based on the Chinese Remainder Theorem (CRT-ACD Problem). In partic- ular, our algorithms lead to quadratic improvements in the input length for the CRT-ACD Problem, and some cases of the Cheon et al. attack. The last work included in this thesis studies Edwards curves, a normal form for elliptic curves, first introduced by Edwards (Bull. Amer. Math. Soc. 2007). This model for elliptic curves has been proposed for elliptic-curve cryptography by the work of Bernstein and Lange (Asiacrypt 2007), by exploiting the efficient Edwards point arithmetic. Their work includes a construction of the Edwards model from the Weierstrass model. While not directly oriented towards cryptographic targets, our study of the Edwards model is of arithmetic-geometric nature. Our main contributions include abstract constructions for the Edwards model, an explicit generalization of the Bernstein-Lange construction, as well as general properties of geometric nature. From an analytic perspective, we complement our study with extensive computer calculations related to the ranks of rational elliptic curves in a family related to Ed- wards curves. Part of our statistical data is based on our extension of an algorithm involving L-functions and relying on the well-known Birch and Swinnerton-Dyer Conjecture for elliptic curves. [less ▲]

Simultaneous Diagonalization of Incomplete Matrices and Applications

in Proceedings of the Fourteenth Algorithmic Number Theory Symposium (ANTS-XIV), edited by Steven Galbraith, Open Book Series 4, Mathematical Sciences Publishers, Berkeley, 2020 (2020, December)

We consider the problem of recovering the entries of diagonal matrices {U_a}_a for a = 1, . . . , t from multiple “incomplete” samples {W_a}_a of the form W_a = P U_a Q, where P and Q are unknown matrices ... [more ▼]

We consider the problem of recovering the entries of diagonal matrices {U_a}_a for a = 1, . . . , t from multiple “incomplete” samples {W_a}_a of the form W_a = P U_a Q, where P and Q are unknown matrices of low rank. We devise practical algorithms for this problem depending on the ranks of P and Q. This problem finds its motivation in cryptanalysis: we show how to significantly improve previous algorithms for solving the approximate common divisor problem and breaking CLT13 cryptographic multilinear maps. [less ▲]

Cryptanalysis of CLT13 Multilinear Maps with Independent Slots

Speeches/Talks (2019)

MATHEMATICAL CAREERS In Luxembourg and beyond

Diverse speeches and writings (2019)