Jean-François Biasse
Research Subjects
Research Interests
Jean-François Biasse has a total of 5 co-authors. Here are the top co-authors by number of shared publications:
- Michael John Jacobson
University of Calgary
3 shared publications - Claus Fieker
RPTU Kaiserslautern-Landau
2 shared publications - Guillaume Quintin
LIX École polytechnique 91128 Palaiseau France
2 shared publications Luis Ruiz
University of Waterloo
1 shared publication- Silverster K. Alan1 shared publication
Latest Publications
- Open AccessA fast algorithm for finding a short generator of a principal ideal of $\mathbb{Q}(ζ_{p^s})$We present a heuristic algorithm to compute the ideal class group, and a generator of a principal ideal in $\mathbb{Q}(\zeta_{p^s})$ in time $2^{O(n^{1/2+\varepsilon})}$ for $n:= deg(K)$ and arbitrarily small $\varepsilon$. This yields an attack on the schemes relying on the hardness of finding a short generator of a principal ideal such as such as the homomorphic encryption scheme of Vercauteren and Smart, and the multilinear maps of Garg, Gentry and Halevi. We rely on the work from Cramer, Ducas, Peikert and Regev. They proved that finding a short generator polynomially reduces to finding an arbitrary one. The complexity is better than when we rely on the work of Biasse and Fieker on the PIP, which yields an attack in time $2^{n^{2/3+\varepsilon}}$ for arbitrarily small $\varepsilon >0$. $\textbf{Since Sep. 30 2016}$ We present practical improvements to our methods. Moreover, we describe a variant that solves the PIP on input ideal $I$ of norm less than $2^{n^b}$ in time $2^{O\left(n^{c+o(1)}\right)}$ for $2/5 < c < 1/2$ and $b\leq 7c -2$ given a one time precomputation of cost $2^{O(n^{2-3c+\varepsilon})}$ for an arbitrarily small $\varepsilon$. This also solves $\gamma$-SVP in principal ideals of $\mathbb{Q}(\zeta_{p^s})$ for $\gamma\in e^{\tilde{O}(\sqrt{n})}$. On principal ideals of norm less than $2^{n^b}$, we can leverage the precomputation to achieve a better asymptotic run time than the BKZ algorithm.Open AccessA fast algorithm for finding a short generator of a principal ideal of $\mathbb{Q}(ζ_{p^s})$We present a heuristic algorithm to compute the ideal class group, and a generator of a principal ideal in $\mathbb{Q}(\zeta_{p^s})$ in time $2^{O(n^{1/2+\varepsilon})}$ for $n:= deg(K)$ and arbitrarily small $\varepsilon$. This yields an attack on the schemes relying on the hardness of finding a short generator of a principal ideal such as such as the homomorphic encryption scheme of Vercauteren and Smart, and the multilinear maps of Garg, Gentry and Halevi. We rely on the work from Cramer, Ducas, Peikert and Regev. They proved that finding a short generator polynomially reduces to finding an arbitrary one. The complexity is better than when we rely on the work of Biasse and Fieker on the PIP, which yields an attack in time $2^{n^{2/3+\varepsilon}}$ for arbitrarily small $\varepsilon >0$. $\textbf{Since Sep. 30 2016}$ We present practical improvements to our methods. Moreover, we describe a variant that solves the PIP on input ideal $I$ of norm less than $2^{n^b}$ in time $2^{O\left(n^{c+o(1)}\right)}$ for $2/5 < c < 1/2$ and $b\leq 7c -2$ given a one time precomputation of cost $2^{O(n^{2-3c+\varepsilon})}$ for an arbitrarily small $\varepsilon$. This also solves $\gamma$-SVP in principal ideals of $\mathbb{Q}(\zeta_{p^s})$ for $\gamma\in e^{\tilde{O}(\sqrt{n})}$. On principal ideals of norm less than $2^{n^b}$, we can leverage the precomputation to achieve a better asymptotic run time than the BKZ algorithm.
- Open Access
- 1 August 2014
- Published by Wiley in LMS Journal of Computation and Mathematics
- Vol. 17 (A) , 385-403
Subexponential class group and unit group computation in large degree number fields
We describe how to compute the ideal class group and the unit group of an order in a number field in subexponential time. Our method relies on the generalized Riemann hypothesis and other usual heuristics concerning the smoothness of ideals. It applies to arbitrary classes of number fields, including those for which the degree goes to infinity.
- 1 August 2014
- Published by Wiley in LMS Journal of Computation and Mathematics
- Vol. 17 (A) , 385-403
Open AccessSubexponential class group and unit group computation in large degree number fields
We describe how to compute the ideal class group and the unit group of an order in a number field in subexponential time. Our method relies on the generalized Riemann hypothesis and other usual heuristics concerning the smoothness of ideals. It applies to arbitrary classes of number fields, including those for which the degree goes to infinity.
- 17 January 2014
- Published by American Mathematical Society (AMS) in Mathematics of Computation
- Vol. 83 (288) , 2005-2031
An 𝐿(1/3) algorithm for ideal class group and regulator computation in certain number fields
We analyze the complexity of the computation of the class group structure, regulator, and a system of fundamental units of an order in a certain class of number fields. Our approach differs from Buchmann’s, who proved a complexity bound under the generalized Riemann hypothesis of L ( 1 / 2 , O ( 1 ) ) L(1/2,O(1)) when the discriminant tends to infinity with fixed degree. We achieve a heuristic subexponential complexity in O ( L ( 1 / 3 , O ( 1 ) ) ) O(L(1/3,O(1))) under the generalized Riemann hypothesis when both the discriminant and the degree of the extension tend to infinity by using techniques due to Enge, Gaudry and Thomé in the context of algebraic curves over finite fields. We also address rigorously the problem of the precision of the computation of the regulator.
- 17 January 2014
- Published by American Mathematical Society (AMS) in Mathematics of Computation
- Vol. 83 (288) , 2005-2031
An 𝐿(1/3) algorithm for ideal class group and regulator computation in certain number fields
We analyze the complexity of the computation of the class group structure, regulator, and a system of fundamental units of an order in a certain class of number fields. Our approach differs from Buchmann’s, who proved a complexity bound under the generalized Riemann hypothesis of L ( 1 / 2 , O ( 1 ) ) L(1/2,O(1)) when the discriminant tends to infinity with fixed degree. We achieve a heuristic subexponential complexity in O ( L ( 1 / 3 , O ( 1 ) ) ) O(L(1/3,O(1))) under the generalized Riemann hypothesis when both the discriminant and the degree of the extension tend to infinity by using techniques due to Enge, Gaudry and Thomé in the context of algebraic curves over finite fields. We also address rigorously the problem of the precision of the computation of the regulator.
- 1 January 2014
- Published by American Institute of Mathematical Sciences (AIMS) in Advances in Mathematics of Communications
- Vol. 8 (4) , 459-477
Smoothness testing of polynomials over finite fields
We present an analysis of Bernstein's batch integer smoothness test when applied to the case of polynomials over a finite field $\mathbb{F}_q.$ We compare the performance of our algorithm with the standard method based on distinct degree factorization from both an analytical and a practical point of view. Our results show that although the batch test is asymptotically better as a function of the degree of the polynomials to test for smoothness, it is unlikely to offer significant practical improvements for cases of practical interest.- 1 January 2014
- Published by American Institute of Mathematical Sciences (AIMS) in Advances in Mathematics of Communications
- Vol. 8 (4) , 459-477
Smoothness testing of polynomials over finite fields
We present an analysis of Bernstein's batch integer smoothness test when applied to the case of polynomials over a finite field $\mathbb{F}_q.$ We compare the performance of our algorithm with the standard method based on distinct degree factorization from both an analytical and a practical point of view. Our results show that although the batch test is asymptotically better as a function of the degree of the polynomials to test for smoothness, it is unlikely to offer significant practical improvements for cases of practical interest.- Open Access
- 1 January 2014
- Published by American Institute of Mathematical Sciences (AIMS) in Advances in Mathematics of Communications
- Vol. 8 (4) , 407-425
Subexponential time relations in the class group of large degree number fields
Hafner and McCurley described a subexponential time algorithm to compute the ideal class group of a quadratic field, which was generalized to families of fixed degree number fields by Buchman. The main ingredient of this method is a subexponential time algorithm to derive relations between primes of norm bounded by a subexponential value. Besides ideal class group computation, this was successfully used to evaluate isogenies, compute endomorphism rings, solve the discrete logarithm problem in the class group and find a generator of a principal ideal. In this paper, we present a generalization of the relation search to classes of number fields with degree growing to infinity.
- 1 January 2014
- Published by American Institute of Mathematical Sciences (AIMS) in Advances in Mathematics of Communications
- Vol. 8 (4) , 407-425
Open AccessSubexponential time relations in the class group of large degree number fields
Hafner and McCurley described a subexponential time algorithm to compute the ideal class group of a quadratic field, which was generalized to families of fixed degree number fields by Buchman. The main ingredient of this method is a subexponential time algorithm to derive relations between primes of norm bounded by a subexponential value. Besides ideal class group computation, this was successfully used to evaluate isogenies, compute endomorphism rings, solve the discrete logarithm problem in the class group and find a generator of a principal ideal. In this paper, we present a generalization of the relation search to classes of number fields with degree growing to infinity.
- Open Access
An algorithm for list decoding number field codes
We present an algorithm for list decoding codewords of algebraic number field codes in polynomial time. This is the first explicit procedure for decoding number field codes whose construction were previously described by Lenstra [12] and Guruswami [8]. We rely on a new algorithm for computing the Hermite normal form of the basis of an OK -module due to Biasse and Fieker [2] where OK is the ring of integers of a number field K.
Open AccessAn algorithm for list decoding number field codes
We present an algorithm for list decoding codewords of algebraic number field codes in polynomial time. This is the first explicit procedure for decoding number field codes whose construction were previously described by Lenstra [12] and Guruswami [8]. We rely on a new algorithm for computing the Hermite normal form of the basis of an OK -module due to Biasse and Fieker [2] where OK is the ring of integers of a number field K.
- Open Access
New techniques for computing the ideal class group and a system of fundamental units in number fields
We describe a new algorithm for computing the ideal class group, the regulator and a system of fundamental units in number fields under the generalized Riemann hypothesis. We use sieving techniques adapted from the number field sieve algorithm to derive relations between elements of the ideal class group, and $p$-adic approximations to manage the loss of precision during the computation of units. This new algorithm is particularily efficient for number fields of small degree for which a speed-up of an order of magnitude is achieved with respect to the standard methods.
Open AccessNew techniques for computing the ideal class group and a system of fundamental units in number fields
We describe a new algorithm for computing the ideal class group, the regulator and a system of fundamental units in number fields under the generalized Riemann hypothesis. We use sieving techniques adapted from the number field sieve algorithm to derive relations between elements of the ideal class group, and $p$-adic approximations to manage the loss of precision during the computation of units. This new algorithm is particularily efficient for number fields of small degree for which a speed-up of an order of magnitude is achieved with respect to the standard methods.
- Open Access
An L(1/3) algorithm for discrete logarithm computation and principality testing in certain number fields
We analyse the complexity of solving the discrete logarithm problem and of testing the principality of ideals in a certain class of number fields. We achieve the subexponential complexity in $O(L(1/3,O(1)))$ when both the discriminant and the degree of the extension tend to infinity by using techniques due to Enge, Gaudry and Thom\'{e} in the context of algebraic curves over finite fields.Open AccessAn L(1/3) algorithm for discrete logarithm computation and principality testing in certain number fields
We analyse the complexity of solving the discrete logarithm problem and of testing the principality of ideals in a certain class of number fields. We achieve the subexponential complexity in $O(L(1/3,O(1)))$ when both the discriminant and the degree of the extension tend to infinity by using techniques due to Enge, Gaudry and Thom\'{e} in the context of algebraic curves over finite fields. - Open Access
An algorithm for list decoding number field codes
We present an algorithm for list decoding codewords of algebraic number field codes in polynomial time. This is the first explicit procedure for decoding number field codes whose construction were previously described by Lenstra and Guruswami. We rely on an equivalent of the LLL reduction algorithm for $\OK$-modules due to Fieker and Stehl\'e and on algorithms due to Cohen for computing the Hermite normal form of matrices representing modules over Dedekind domains.
Open AccessAn algorithm for list decoding number field codes
We present an algorithm for list decoding codewords of algebraic number field codes in polynomial time. This is the first explicit procedure for decoding number field codes whose construction were previously described by Lenstra and Guruswami. We rely on an equivalent of the LLL reduction algorithm for $\OK$-modules due to Fieker and Stehl\'e and on algorithms due to Cohen for computing the Hermite normal form of matrices representing modules over Dedekind domains.