Search

International audience; The security of essentially all public-key cryptography currently in common use today is based on the presumed computational hardness of three number-theoretic problems: integer factoring (required for the security of RSA encryption and digital signatures), discrete logarithms in finite fields (required for Diffie-Hellman key exchange and the DSA digital signature algorithm), and discrete logarithms over elliptic curves (required for elliptic curve Diffie-Hellman and ECDSA, Ed25519, and other elliptic curve digital signature algorithms).In this column, we will review the current state of the art of cryptanalysis for these problems using classical (non-quantum) computers, including in particular our most recent computational records for integer factoring and prime field discrete logarithms.

The block Lanczos algorithm proposed by Peter Montgomery is an efficient means to tackle the sparse linear algebra problem which arises in the context of the number field sieve factoring algorithm and its predecessors. We present here a modified version of the algorithm, which incorporates several improvements: we discuss how to efficiently handle homogeneous systems and how to reduce the number of vectors stored in the course of the computation. We also provide heuristic justification for the success probability of our modified algorithm. While the overall complexity and expected number of steps of the block Lanczos is not changed by the modifications presented in this article, we expect these to be useful for implementations of the block Lanczos algorithm where the storage of auxiliary vectors sometimes has a non-negligible cost. 1 Linear systems for integer factoring For factoring a composite integer N, algorithms based on the technique of combination of congruences look for several pairs of integers (x, y) such that x 2 $\not\equiv$ y 2 mod N. This equality is hoped to be non trivial for at least one of the obtained pairs, letting gcd(x -- y, N) unveil a factor of the integer N. Several algorithms use this strategy: the CFRAC algorithm, the quadratic sieve and its variants, and the number field sieve. Pairs (x, y) as above are obtained by combining relations which have been collected as a step of these algorithms. Relations are written multiplicatively as a set of valuations. All the algorithms considered seek a multiplicative combination of these relations which can be rewritten as an equality of squares. This is achieved by solving a system of linear equations defined over F 2, where equations are parity constraints on, Comment: Topics in Computational Number Theory inspired by Peter L. Montgomery, Cambridge University Press, 2016

Nicolas Anciaux, Xavier Bonnetain, Anne Canteaut, Véronique Cortier, Pierrick Gaudry, Lucca Hirschi, Steve Kremer, Stéphanie Lacour, Gaëtan Leurent, Matthieu Lequesne, Léo Perrin, André Schrottenloher, Emmanuel Thomé, Serge Vaudenay, Christophe Vuillot Dans le but affiché de ralentir la progression de l'épidémie COVID-19, la France envisage de mettre en place un système de traçage des contacts des malades à l'aide d'une application mobile. Les concepteurs de ce type d'applications assurent qu'elles sont respectueuses de la vie privée. Cependant cette notion reste vague. Nous souhaitons donc contribuer au débat public en apportant un éclairage sur ce que pourrait et ne pourrait pas garantir une application de traçage, afin que chacun puisse se forger une opinion sur l'opportunité de son déploiement.