25 citations · 27 across the 8 of their papers we have counts for
11 papers
Indefiniteness makes lattice reduction easier
Antoine Joux
Since the invention of the famous LLL algorithm, lattice reduction has been an extremely useful tool in computational number theory. By construction, the LLL algorithm deals with l…
The regular multivariate quadratic problem
Antoine Joux, Rocco Mora
In this work, we introduce a novel variant of the multivariate quadratic problem, which is at the core of one of the most promising post-quantum alternatives: multivariate cryptogr…
Polynomial Time Algorithms for Integer Programming and Unbounded Subset Sum in the Total Regime
Divesh Aggarwal, Antoine Joux, Miklos Santha +1
The Unbounded Subset Sum (USS) problem is an NP-hard computational problem where the goal is to decide whether there exist non-negative integers such that $x_1 a…
RYDE: A Digital Signature Scheme based on Rank-Syndrome-Decoding Problem with MPCitH Paradigm
Loïc Bidoux, Jesús-Javier Chi-Domínguez, Thibauld Feneuil +4
We present a signature scheme based on the Syndrome-Decoding problem in rank metric. It is a construction from multi-party computation (MPC), using a MPC protocol which is a slight…
Classical and Quantum Algorithms for Variants of Subset-Sum via Dynamic Programming
Jonathan Allcock, Yassine Hamoudi, Antoine Joux +2
Subset-Sum is an NP-complete problem where one must decide if a multiset of integers contains a subset whose elements sum to a target value . The best-known classical and qu…
Discrete logarithm and Diffie-Hellman problems in identity black-box groups
Gabor Ivanyos, Antoine Joux, Miklos Santha
We investigate the computational complexity of the discrete logarithm, the computational Diffie-Hellman and the decisional Diffie-Hellman problems in some identity black-box groups…
Algorithmic aspects of elliptic bases in finite field discrete logarithm algorithms
Antoine Joux, Cecile Pierrot
Elliptic bases, introduced by Couveignes and Lercier in 2009, give an elegant way of representing finite field extensions. A natural question which seems to have been considered in…
Certified lattice reduction
Thomas Espitau, Antoine Joux
Quadratic form reduction and lattice reduction are fundamental tools in computational number theory and in computer science, especially in cryptography. The celebrated Lenstra-Lens…
Optimal quantum-programmable projective measurement with linear optics
Ulysse Chabaud, Eleni Diamanti, Damian Markham +2
We present a scheme for a universal device which can be programmed by quantum states to approximate a chosen projective measurement to a given precision. Our scheme can be viewed a…
A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic
Razvan Barbulescu, Pierrick Gaudry, Antoine Joux +1
In the present work, we present a new discrete logarithm algorithm, in the same vein as in recent works by Joux, using an asymptotically more efficient descent approach. The main r…
Pairing the Volcano
Sorina Ionica, Antoine Joux
Isogeny volcanoes are graphs whose vertices are elliptic curves and whose edges are -isogenies. Algorithms allowing to travel on these graphs were developed by Kohel in his t…