We introduce a new family of rank metric codes: Low Rank Parity Check codes (LRPC), for which we propose an efficient probabilistic decoding algorithm. This family of codes can be seen as the equivalent of classical LDPC codes for the rank metric. We then use these codes to design cryptosystems à la McEliece: more precisely we propose two schemes for key encapsulation mechanism (KEM) and public key encryption (PKE). Unlike rank metric codes used in previous encryption algorithms -notably Gabidulin codes - LRPC codes have a very weak algebraic structure. Our cryptosystems can be seen as an equivalent of the NTRU cryptosystem (and also to the more recent MDPC code-based cryptosystem) in a rank metric context, due to the similar form of the public keys. The present paper is an extended version of the article introducing LRPC codes, with important new contributions. We have improved the decoder thanks to a new approach which allows for decoding of errors of higher rank weight, namely up to$\frac {2}{3}(n-k)$when the previous decoding algorithm only decodes up to$\frac {n-k}{2}$errors. Our codes therefore outperform the classical Gabidulin code decoder which deals with weights up to$\frac {n-k}{2}$. This comes at the expense of probabilistic decoding, but the decoding error probability can be made arbitrarily small. The new approach can also be used to decrease the decoding error probability of previous schemes, which is especially useful for cryptography. Finally, we introduce ideal rank codes, which generalize double-circulant rank codes and allow us to avoid known structural attacks based on folding. To conclude, we propose different parameter sizes for our schemes and we obtain a public key of 3337 bits for key exchange and 5893 bits for public key encryption, both for 128 bits of security.

In this paper, we propose two new generic attacks on the rank syndrome decoding (RSD) problem. Let C be a random [n, k] rank code over GF(qm) and let y = x + e be a received word, such that x ∈ C and rank(e) = r. The first attack, the support attack, is combinatorial and permits to recover an error e of rank weight r in min(O((n - k)3m3qr1(km/n)J, O((n - k)3m3q⌈(r-1)I(((k+1)m)/n)J))⌉operations on GF(q). This new attack improves the exponent for the best generic attack for the RSD problem in the case n > m, by introducing the ratio m/n in the exponential coefficient of the previously best known attacks. The second attack, the annulator polynomial attack, is an algebraic attack based on the theory of q-polynomials introduced by Ore. We propose a new algebraic setting for the RSD problem that permits to consider equations and unknowns in the extension field GF(qm) rather than in GF(q) as it is usually the case. We consider two approaches to solve the problem in this new setting. The linearization technique shows that if n ≥ (k + 1) (r + 1) - 1 the RSD problem can be solved in polynomial time. More generally, we prove that if [(((r + 1)(k + 1)- (n + 1))/r)1 ≤ k, the RSD problem can be solved with an average complexity of O(r3k3qrΓ(((r+1)(k+1)-(n+1))/r)l)⌉operations in the base field GF(q). We also consider solving with Gröbner bases for which we discuss theoretical complexity, we also consider hybrid solving with Gröbner bases on practical parameters. As an example of application, we use our new attacks on all recent cryptosystems parameters, which repair the GPT cryptosystem, we break all examples of published proposed parameters, and some parameters are broken in less than 1 s in certain cases.

An algorithm is presented for the computation of the topology of a non-reduced space curve defined as the intersection of two implicit algebraic surfaces.

In this paper we give an algorithm with complexity O(mu2) to solve Hermite multivariate polynomial interpolation with mu conditions on its Hasse derivatives. In the case of bivariate interpolation used to perform list-decoding on Reed-Solomon of length n and dimension k with multiplicity m on each point, it permits to obtain a complexity in O(n2m4) which does not depend on the rate k/n and better than previously known complexity in O( n2m5(n/k)(1/2)). This algorithm can also be used for recent interpolation list-decoding with three and more variables. For interpolation on polynomial with n points and M variables with prescribed multiplication order m the general complexity of the algorithm is O(n2m2M)

In this paper we describe an algorithm which permits to perform the erasure list-decoding of q-ary Reed-Muller codes with a quadratic complexity in the dimension of the code rather than with the usual cubic complexity for random linear codes with not too large length. The algorithm is based on a multivariable interpolation algorithm

We propose new Las Vegas randomized algorithms for the solution of a square nondegenerate system of equations, with well-separated roots. The algorithms use $\Oc (\delta\, \csttn D^{2} \log(D) \log(b))$ arithmetic operations (in addition to the operations required to compute the normal form of the boundary monomials modulo the ideal) to approximate all real roots of the system as well as all roots lying in a fixed n-dimensional box or disc. Here D is an upper bound on the number of all complex roots of the system (e.g., Bezout or Bernshtein bound), $\delta$ is the number of real roots or the roots lying in the box or disc, and $\epsilon=2^{-b}$ is the required upper bound on the output errors. For computing the normal form modulo the ideal, the efficient practical algorithms of [B. Mourrain and P. Trébuchet, in Proceedings of the International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2000, pp. 231--238] or [J. C. Faugère, J. Pure Appl. Algebra, 139 (1999), pp. 61--88] can be applied. We also yield the bound $\Oc( \csttn D^{2} \log(D) )$ on the complexity of counting the numbers of all roots in a fixed box (disc) and all real roots. For a large class of inputs and typically in practical computations, the factor $\delta$ is much smaller than $D, \delta=o(D)$. This improves by the order of magnitude the known complexity estimates of the order of at least 3 n D 4 + D 3 log(b) or D 4 , which so far are the record estimates even for the approximation of a single root of a system and for each of the cited counting problems, respectively. Our progress relies on proposing several noveltechniques. In particular, we exploit the structure of matrices associated to a given polynomial system and relate it to the associated linear operators, dual space of linear forms, and normal forms of polynomials in the quotient algebra; furthermore, our techniques support the new nontrivial extension of the matrix sign and quadratic inverse power iterations to the case of multivariate polynomial systems, where we emulate the recursive splitting of a univariate polynomial into factors of smaller degree.

We propose an algorithm to compute simultaneously all the solutions of an algebraic system (of n equations in n variables) that define a zero-dimentional variety. This new approach generalises the univariate Weierstrass's method. We study the arithmetic complexity of this method that has a quadratic convergence in a neighbourhood of the solutions. Hereafter, we describe a method based on the iteration function of the multivariate Weierstrass's method and on the continuation method for computing the roots of polynomial systems. Finally we describe some numerical experiments of those methods.