On July 6, 2021 our SP2 doctoral candidate Luca Notarnicola successfully defended his thesis titled:
“Topics in Computational Number Theory and Cryptanalysis – On Euclidean Lattices, Edwards Curves and Cryptographic Multilinear Maps“
Members of the defense committee:
Prof Dr. Antonella Perucca, Université du Luxembourg, Chairman
Prof. Dr. Jean-Sébastien Coron, Université du Luxembourg, Vice-Chairman
Prof. Dr. Gabor Wiese, Université Du Luxembourg, Supervisor
Prof. Dr. Frederik Vercautern, KU Leuven, Member
Prof Dr. Phong Q. Nguyen, Inria and DIENS PSL Paris, Member
Abstract:
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 Subset 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 celebrated Nguyen-Stern orthogonal lattice attack. For both algorithms, we provide practical parameters, based on heuristic and rigorous studies of the geometry of the underlying lattices. 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 contribution 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 particular, 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.
Link to dissertation: