Ludovic Perret
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Ludovic Perret has a total of 24 co-authors. Here are the top co-authors by number of shared publications:
- Jean-Charles Faugère
Laboratoire d'Informatique de Paris 6 LIP6 Sorbonne Université CNRS INRIA Équipe PolSys 4 place Jussieu F-75005 Paris France
12 shared publications - Carlos Cid
Royal Holloway, University of London
3 shared publications - Ayoub Otmani
University of Rouen
2 shared publications Jean-Charles Faugère
Inria, Paris Center, Sorbonne Universités, UPMC Univ Paris 06, Équipe PolSys, LIP6
2 shared publications- Jean-Pierre Tillich
INRIA, Paris, France
2 shared publications - Robert Fitzpatrick
University of London
2 shared publications
Latest Publications
- 3 July 2024
- Published by Springer Nature
- p. 222-235
Polynomial-Time Key-Recovery Attack on the NIST Specification of PROV
- 3 July 2024
- Published by Springer Nature
- p. 222-235
Polynomial-Time Key-Recovery Attack on the NIST Specification of PROV
- 18 April 2021
- Published by Springer Nature in Designs, Codes and Cryptography
- Vol. 89 (6) , 1335-1364
Cryptanalysis of the extension field cancellation cryptosystem
- 18 April 2021
- Published by Springer Nature in Designs, Codes and Cryptography
- Vol. 89 (6) , 1335-1364
Cryptanalysis of the extension field cancellation cryptosystem
- Open Access
A nearly optimal algorithm to decompose binary forms
Symmetric tensor decomposition is an important problem with applications in several areas for example signal processing, statistics, data analysis and computational neuroscience. It is equivalent to Waring's problem for homogeneous polynomials, that is to write a homogeneous polynomial in n variables of degree D as a sum of D-th powers of linear forms, using the minimal number of summands. This minimal number is called the rank of the polynomial/tensor. We focus on decomposing binary forms, a problem that corresponds to the decomposition of symmetric tensors of dimension 2 and order D. Under this formulation, the problem finds its roots in invariant theory where the decompositions are known as canonical forms. In this context many different algorithms were proposed. We introduce a superfast algorithm that improves the previous approaches with results from structured linear algebra. It achieves a softly linear arithmetic complexity bound. To the best of our knowledge, the previously known algorithms have at least quadratic complexity bounds. Our algorithm computes a symbolic decomposition in $O(M(D) log(D))$ arithmetic operations, where $M(D)$ is the complexity of multiplying two polynomials of degree D. It is deterministic when the decomposition is unique. When the decomposition is not unique, our algorithm is randomized. We present a Monte Carlo version of it and we show how to modify it to a Las Vegas one, within the same complexity. From the symbolic decomposition, we approximate the terms of the decomposition with an error of $2^{--$\epsilon$}$ , in $O(D log^2(D) (log^2(D) + log($\epsilon$)))$ arithmetic operations. We use results from Kaltofen and Yagati (1989) to bound the size of the representation of the coefficients involved in the decomposition and we bound the algebraic degree of the problem by min(rank, D -- rank + 1). We show that this bound can be tight. When the input polynomial has integer coefficients, our algorithm performs, up to poly-logarithmic factors, $O\_{bit} (D{\ell} + D^4 + D^3 $\tau$)$ bit operations, where $$\tau$$ is the maximum bitsize of the coefficients and $2^{--{\ell}}$ is the relative error of the terms in the decomposition.Open AccessA nearly optimal algorithm to decompose binary forms
Symmetric tensor decomposition is an important problem with applications in several areas for example signal processing, statistics, data analysis and computational neuroscience. It is equivalent to Waring's problem for homogeneous polynomials, that is to write a homogeneous polynomial in n variables of degree D as a sum of D-th powers of linear forms, using the minimal number of summands. This minimal number is called the rank of the polynomial/tensor. We focus on decomposing binary forms, a problem that corresponds to the decomposition of symmetric tensors of dimension 2 and order D. Under this formulation, the problem finds its roots in invariant theory where the decompositions are known as canonical forms. In this context many different algorithms were proposed. We introduce a superfast algorithm that improves the previous approaches with results from structured linear algebra. It achieves a softly linear arithmetic complexity bound. To the best of our knowledge, the previously known algorithms have at least quadratic complexity bounds. Our algorithm computes a symbolic decomposition in $O(M(D) log(D))$ arithmetic operations, where $M(D)$ is the complexity of multiplying two polynomials of degree D. It is deterministic when the decomposition is unique. When the decomposition is not unique, our algorithm is randomized. We present a Monte Carlo version of it and we show how to modify it to a Las Vegas one, within the same complexity. From the symbolic decomposition, we approximate the terms of the decomposition with an error of $2^{--$\epsilon$}$ , in $O(D log^2(D) (log^2(D) + log($\epsilon$)))$ arithmetic operations. We use results from Kaltofen and Yagati (1989) to bound the size of the representation of the coefficients involved in the decomposition and we bound the algebraic degree of the problem by min(rank, D -- rank + 1). We show that this bound can be tight. When the input polynomial has integer coefficients, our algorithm performs, up to poly-logarithmic factors, $O\_{bit} (D{\ell} + D^4 + D^3 $\tau$)$ bit operations, where $$\tau$$ is the maximum bitsize of the coefficients and $2^{--{\ell}}$ is the relative error of the terms in the decomposition. - 30 March 2017
- Published by Springer Nature
- p. 258-266
The Quantum-Safe Revolution
- Open Access
Polynomial-Time Algorithms for Quadratic Isomorphism of Polynomials: The Regular Case
Let $\mathbf{f}=(f\_1,\ldots,f\_m)$ and $\mathbf{g}=(g\_1,\ldots,g\_m)$ be two sets of $m\geq 1$ nonlinear polynomials over $\mathbb{K}[x\_1,\ldots,x\_n]$ ($\mathbb{K}$ being a field). We consider the computational problem of finding -- if any -- an invertible transformation on the variables mapping $\mathbf{f}$ to $\mathbf{g}$. The corresponding equivalence problem is known as {\tt Isomorphism of Polynomials with one Secret} ({\tt IP1S}) and is a fundamental problem in multivariate cryptography. The main result is a randomized polynomial-time algorithm for solving {\tt IP1S} for quadratic instances, a particular case of importance in cryptography and somewhat justifying {\it a posteriori} the fact that {\it Graph Isomorphism} reduces to only cubic instances of {\tt IP1S} (Agrawal and Saxena). To this end, we show that {\tt IP1S} for quadratic polynomials can be reduced to a variant of the classical module isomorphism problem in representation theory, which involves to test the orthogonal simultaneous conjugacy of symmetric matrices. We show that we can essentially {\it linearize} the problem by reducing quadratic-{\tt IP1S} to test the orthogonal simultaneous similarity of symmetric matrices; this latter problem was shown by Chistov, Ivanyos and Karpinski to be equivalent to finding an invertible matrix in the linear space $\mathbb{K}^{n \times n}$ of $n \times n$ matrices over $\mathbb{K}$ and to compute the square root in a matrix algebra. While computing square roots of matrices can be done efficiently using numerical methods, it seems difficult to control the bit complexity of such methods. However, we present exact and polynomial-time algorithms for computing the square root in $\mathbb{K}^{n \times n}$ for various fields (including finite fields). We then consider \\#{\tt IP1S}, the counting version of {\tt IP1S} for quadratic instances. In particular, we provide a (complete) characterization of the automorphism group of homogeneous quadratic polynomials. Finally, we also consider the more general {\it Isomorphism of Polynomials} ({\tt IP}) problem where we allow an invertible linear transformation on the variables \emph{and} on the set of polynomials. A randomized polynomial-time algorithm for solving {\tt IP} when \(\mathbf{f}=(x\_1^d,\ldots,x\_n^d)\) is presented. From an algorithmic point of view, the problem boils down to factoring the determinant of a linear matrix (\emph{i.e.}\ a matrix whose components are linear polynomials). This extends to {\tt IP} a result of Kayal obtained for {\tt PolyProj}.Open AccessPolynomial-Time Algorithms for Quadratic Isomorphism of Polynomials: The Regular Case
Let $\mathbf{f}=(f\_1,\ldots,f\_m)$ and $\mathbf{g}=(g\_1,\ldots,g\_m)$ be two sets of $m\geq 1$ nonlinear polynomials over $\mathbb{K}[x\_1,\ldots,x\_n]$ ($\mathbb{K}$ being a field). We consider the computational problem of finding -- if any -- an invertible transformation on the variables mapping $\mathbf{f}$ to $\mathbf{g}$. The corresponding equivalence problem is known as {\tt Isomorphism of Polynomials with one Secret} ({\tt IP1S}) and is a fundamental problem in multivariate cryptography. The main result is a randomized polynomial-time algorithm for solving {\tt IP1S} for quadratic instances, a particular case of importance in cryptography and somewhat justifying {\it a posteriori} the fact that {\it Graph Isomorphism} reduces to only cubic instances of {\tt IP1S} (Agrawal and Saxena). To this end, we show that {\tt IP1S} for quadratic polynomials can be reduced to a variant of the classical module isomorphism problem in representation theory, which involves to test the orthogonal simultaneous conjugacy of symmetric matrices. We show that we can essentially {\it linearize} the problem by reducing quadratic-{\tt IP1S} to test the orthogonal simultaneous similarity of symmetric matrices; this latter problem was shown by Chistov, Ivanyos and Karpinski to be equivalent to finding an invertible matrix in the linear space $\mathbb{K}^{n \times n}$ of $n \times n$ matrices over $\mathbb{K}$ and to compute the square root in a matrix algebra. While computing square roots of matrices can be done efficiently using numerical methods, it seems difficult to control the bit complexity of such methods. However, we present exact and polynomial-time algorithms for computing the square root in $\mathbb{K}^{n \times n}$ for various fields (including finite fields). We then consider \\#{\tt IP1S}, the counting version of {\tt IP1S} for quadratic instances. In particular, we provide a (complete) characterization of the automorphism group of homogeneous quadratic polynomials. Finally, we also consider the more general {\it Isomorphism of Polynomials} ({\tt IP}) problem where we allow an invertible linear transformation on the variables \emph{and} on the set of polynomials. A randomized polynomial-time algorithm for solving {\tt IP} when \(\mathbf{f}=(x\_1^d,\ldots,x\_n^d)\) is presented. From an algorithmic point of view, the problem boils down to factoring the determinant of a linear matrix (\emph{i.e.}\ a matrix whose components are linear polynomials). This extends to {\tt IP} a result of Kayal obtained for {\tt PolyProj}. - 20 March 2015
- Published by Springer Nature in Designs, Codes and Cryptography
- Vol. 79 (2) , 261-302
Polly Cracker, revisited
- 20 March 2015
- Published by Springer Nature in Designs, Codes and Cryptography
- Vol. 79 (2) , 261-302
Polly Cracker, revisited
- 3 February 2015
- Published by Springer Nature in Designs, Codes and Cryptography
- Vol. 79 (1) , 87-112
Structural cryptanalysis of McEliece schemes with compact keys
- 3 February 2015
- Published by Springer Nature in Designs, Codes and Cryptography
- Vol. 79 (1) , 87-112
Structural cryptanalysis of McEliece schemes with compact keys
- Open Access
Algebraic Algorithms for LWE Problems
We analyse the complexity of algebraic algorithms for solving systems of linear equations with \emph{noise}. Such systems arise naturally in the theory of error-correcting codes as well as in computational learning theory. More recently, linear systems with noise have found application in cryptography. The \emph{Learning with Errors} (LWE) problem has proven to be a rich and versatile source of innovative cryptosystems, such as fully homomorphic encryption schemes. Despite the popularity of the LWE problem, the complexity of algorithms for solving it is not very well understood, particularly when variants of the original problem are considered. Here, we focus on and generalise a particular method for solving these systems, due to Arora \& Ge, which reduces the problem to non-linear but noise-free system solving. Firstly, we provide a refined complexity analysis for the original Arora-Ge algorithm for LWE. Secondly, we study the complexity of applying algorithms for computing Gröbner basis, a fundamental tool in computational commutative algebra, to solving Arora-Ge-style systems of non-linear equations. We show positive and negative results. On the one hand, we show that the use of Gröbner bases yields an exponential speed-up over the basic Arora-Ge approach. On the other hand, we give a negative answer to the natural question whether the use of such techniques can yield a subexponential algorithm for the LWE problem. Under a mild algebraic assumption, we show that it is highly unlikely that such an improvement exists. We also consider a variant of LWE known as BinaryError-LWE introduced by Micciancio and Peikert recently. By combining Gröbner basis algorithms with the Arora-Ge modelling, we show under a natural algebraic assumption that BinaryError-LWE can be solved in subexponential time as soon as the number of samples is quasi-linear, e.g.\ m=O(nloglogn)m=O(n \log \log n). We also derive precise complexity bounds for BinaryError-\LWE with m=O(n)m=O(n), showing that this new approach yields better results than best currently-known generic (exact) CVP solver as soon as m/n≥6.6m/n \geq 6.6. More generally, our results provide a good picture of the hardness degradation of BinaryError-LWE for a number of samples ranging from m=n(1+Ω(1/log(n))m=n\left(1+\Omega\big(1/{\rm log}(n)\right) (a case for which BinaryError-\LWE{} is as hard as solving some lattice problem in the worst case) to m=O(n2)m=O(n^2) (a case for which it can be solved in polynomial-time). This addresses an open question from Micciancio and Peikert. Whilst our results do not contradict the hardness results obtained by Micciancio and Peikert, they should rule out BinaryError-\LWE for many cryptographic applications. The results in this work depend crucially on the assumption the algebraic systems considered systems are not easier and not harder to solve than a random system of equations. We have verified experimentally such hypothesis. We also have been able to prove formally the assumptions is several restricted situations. We emphasize that these issues are highly non-trivial since proving our assumptions in full generality would allow to prove a famous conjecture in commutative algebra known as Fröberg's Conjecture.
Open AccessAlgebraic Algorithms for LWE Problems
We analyse the complexity of algebraic algorithms for solving systems of linear equations with \emph{noise}. Such systems arise naturally in the theory of error-correcting codes as well as in computational learning theory. More recently, linear systems with noise have found application in cryptography. The \emph{Learning with Errors} (LWE) problem has proven to be a rich and versatile source of innovative cryptosystems, such as fully homomorphic encryption schemes. Despite the popularity of the LWE problem, the complexity of algorithms for solving it is not very well understood, particularly when variants of the original problem are considered. Here, we focus on and generalise a particular method for solving these systems, due to Arora \& Ge, which reduces the problem to non-linear but noise-free system solving. Firstly, we provide a refined complexity analysis for the original Arora-Ge algorithm for LWE. Secondly, we study the complexity of applying algorithms for computing Gröbner basis, a fundamental tool in computational commutative algebra, to solving Arora-Ge-style systems of non-linear equations. We show positive and negative results. On the one hand, we show that the use of Gröbner bases yields an exponential speed-up over the basic Arora-Ge approach. On the other hand, we give a negative answer to the natural question whether the use of such techniques can yield a subexponential algorithm for the LWE problem. Under a mild algebraic assumption, we show that it is highly unlikely that such an improvement exists. We also consider a variant of LWE known as BinaryError-LWE introduced by Micciancio and Peikert recently. By combining Gröbner basis algorithms with the Arora-Ge modelling, we show under a natural algebraic assumption that BinaryError-LWE can be solved in subexponential time as soon as the number of samples is quasi-linear, e.g.\ m=O(nloglogn)m=O(n \log \log n). We also derive precise complexity bounds for BinaryError-\LWE with m=O(n)m=O(n), showing that this new approach yields better results than best currently-known generic (exact) CVP solver as soon as m/n≥6.6m/n \geq 6.6. More generally, our results provide a good picture of the hardness degradation of BinaryError-LWE for a number of samples ranging from m=n(1+Ω(1/log(n))m=n\left(1+\Omega\big(1/{\rm log}(n)\right) (a case for which BinaryError-\LWE{} is as hard as solving some lattice problem in the worst case) to m=O(n2)m=O(n^2) (a case for which it can be solved in polynomial-time). This addresses an open question from Micciancio and Peikert. Whilst our results do not contradict the hardness results obtained by Micciancio and Peikert, they should rule out BinaryError-\LWE for many cryptographic applications. The results in this work depend crucially on the assumption the algebraic systems considered systems are not easier and not harder to solve than a random system of equations. We have verified experimentally such hypothesis. We also have been able to prove formally the assumptions is several restricted situations. We emphasize that these issues are highly non-trivial since proving our assumptions in full generality would allow to prove a famous conjecture in commutative algebra known as Fröberg's Conjecture.
- 1 August 2014
- Published by Elsevier in Journal of Symbolic Computation
- Vol. 64, 1-2
Mathematical and computer algebra techniques in cryptology
- 1 August 2014
- Published by Elsevier in Journal of Symbolic Computation
- Vol. 64, 1-2
Mathematical and computer algebra techniques in cryptology
- Open Access
Folding Alternant and Goppa Codes with Non-Trivial Automorphism Groups
The main practical limitation of the McEliece public-key encryption scheme is probably the size of its key. A famous trend to overcome this issue is to focus on subclasses of alternant/Goppa codes with a non trivial automorphism group. Such codes display then symmetries allowing compact parity-check or generator matrices. For instance, a key-reduction is obtained by taking quasi-cyclic (QC) or quasi-dyadic (QD) alternant/Goppa codes. We show that the use of such symmetric alternant/Goppa codes in cryptography introduces a fundamental weakness. It is indeed possible to reduce the key-recovery on the original symmetric public-code to the key-recovery on a (much) smaller code that has not anymore symmetries. This result is obtained thanks to a new operation on codes called folding that exploits the knowledge of the automorphism group. This operation consists in adding the coordinates of codewords which belong to the same orbit under the action of the automorphism group. The advantage is twofold: the reduction factor can be as large as the size of the orbits, and it preserves a fundamental property: folding the dual of an alternant (resp. Goppa) code provides the dual of an alternant (resp. Goppa) code. A key point is to show that all the existing constructions of alternant/Goppa codes with symmetries follow a common principal of taking codes whose support is globally invariant under the action of affine transformations (by building upon prior works of T. Berger and A. D{\"{u}}r). This enables not only to present a unified view but also to generalize the construction of QC, QD and even quasi-monoidic (QM) Goppa codes. All in all, our results can be harnessed to boost up any key-recovery attack on McEliece systems based on symmetric alternant or Goppa codes, and in particular algebraic attacks.
Open AccessFolding Alternant and Goppa Codes with Non-Trivial Automorphism Groups
The main practical limitation of the McEliece public-key encryption scheme is probably the size of its key. A famous trend to overcome this issue is to focus on subclasses of alternant/Goppa codes with a non trivial automorphism group. Such codes display then symmetries allowing compact parity-check or generator matrices. For instance, a key-reduction is obtained by taking quasi-cyclic (QC) or quasi-dyadic (QD) alternant/Goppa codes. We show that the use of such symmetric alternant/Goppa codes in cryptography introduces a fundamental weakness. It is indeed possible to reduce the key-recovery on the original symmetric public-code to the key-recovery on a (much) smaller code that has not anymore symmetries. This result is obtained thanks to a new operation on codes called folding that exploits the knowledge of the automorphism group. This operation consists in adding the coordinates of codewords which belong to the same orbit under the action of the automorphism group. The advantage is twofold: the reduction factor can be as large as the size of the orbits, and it preserves a fundamental property: folding the dual of an alternant (resp. Goppa) code provides the dual of an alternant (resp. Goppa) code. A key point is to show that all the existing constructions of alternant/Goppa codes with symmetries follow a common principal of taking codes whose support is globally invariant under the action of affine transformations (by building upon prior works of T. Berger and A. D{\"{u}}r). This enables not only to present a unified view but also to generalize the construction of QC, QD and even quasi-monoidic (QM) Goppa codes. All in all, our results can be harnessed to boost up any key-recovery attack on McEliece systems based on symmetric alternant or Goppa codes, and in particular algebraic attacks.