OROlivier Ruatta

Olivier Ruatta

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Olivier Ruatta has a total of 20 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Linearized Polynomial Chinese Remainder codes

    by Philippe Gaborit, Camille Garnier, Olivier Ruatta

  • Open Access

    Linearized Polynomial Chinese remainder codes

    by Philippe Gaborit, Camille Garnier, Olivier Ruatta

    In this paper, we introduce a new family of codes relevent for rank and sum-rank metrics. These codes are based on an effective Chinese remainders theorem for linearized polynomials over finite fields. We propose a decoding algorithm for some instances of these codes.

    • 10 May 2025
    • Published by HAL in HAL
    Open Access

    Linearized Polynomial Chinese remainder codes

    by Philippe Gaborit, Camille Garnier, Olivier Ruatta, Olivier, Ruatta May

    Der theorem tailored to these rings. This enables us to construct a wide range of linearized CRT codes with diverse parameters. 2. We present explicit constructions and examples of linearized CRT codes, highlighting their relation to known codes in the literature. 3. We propose a decoding algorithm for a special case of linearized CRT codes and extend it to a broader range of applications. This algorithm has an associated failure rate, which we analyze and discuss. 4. Finally, we study the parameters of these new codes to provide insights into their decoding properties and potential applications in various fields. Organization: The remainder of this paper is structured as follows. Section 2 introduces rank and sum-rank metric codes and their applications. In Section 3, we discuss linearized polynomial rings over finite fields and the effective Chinese remainder theorem for these rings. Section 4 presents the construction of linearized CRT codes, along with examples and connections to existing codes. A decoding algorithm is proposed in Section 5, followed by an analysis of its failure rate and parameters. We extend this algorithm to a wider class in Section 6 together with the parameters and failure rate in this case. Rank and sum-rank metric codesIn this section, we introduce the notation and foundational concepts for rank and sum-rank metric codes. For a more extensive presentation of rank metric codes, we refer to [2]. Let q be a power of a prime and let m ∈ N, we denote F q the field with q elements and F q m an extension of F q of degree m. The field F q m can be considered as a F q -vector space of dimension m, i.e. ) is a linear isomorphism in a way that every subspace W of V can be identified to a subspace M(W ) of matrices. Conversely, every F q -linear subspace in M m×n (F q ) can be identified to a F qsubvector space of V . Definition 1 Rank Metric: Let V and W be two finite dimensional F q -vector spaces and let c ∈ End(V, W ), we define the rank weight w r (c) of c as its rank

  • Security Analysis of a Cryptosystem Based on Subspace Subcodes

    by Thierry P. Berger, Anta Niane Gueye, Cheikh Thiecoumba Gueye, M. Anwarul Hasan, Jean Belo Klamti, Edoardo Persichetti, Tovohery H. Randrianarisoa, Olivier Ruatta

  • Open Access

    Flip procedure in geometric approximation of multiple-component shapes -- Application to multiple-inclusion detection

    by Pierre Bonnelie, Loïc Bourdin, Fabien Caubet, Olivier Ruatta

    We are interested in geometric approximation by parameterization of two-dimensional multiple-component shapes, in particular when the number of components is a priori unknown. Starting a standard method based on successive shape deformations with a one-component initial shape in order to approximate a multiple-component target shape usually leads the deformation flow to make the boundary evolve until it surrounds all the components of the target shape. This classical phenomenon tends to create double points on the boundary of the approximated shape. In order to improve the approximation of multiple-component shapes (without any knowledge on the number of components in advance), we use in this paper a piecewise B\'ezier parameterization and we consider two procedures called intersecting control polygons detection and flip procedure. The first one allows to prevent potential collisions between two parts of the boundary of the approximated shape, and the second one permits to change its topology by dividing a one-component shape into a two-component shape. For an experimental purpose, we include these two processes in a basic geometrical shape optimization algorithm and test it on the classical inverse obstacle problem. This new approach allows to obtain a numerical approximation of the unknown inclusion, detecting both the topology (i.e. the number of connected components) and the shape of the obstacle. Several numerical simulations are performed.

  • Open Access

    On the complexity of the Rank Syndrome Decoding problem

    by Philippe Gaborit, Olivier Ruatta, Julien Schrek

    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(q^m)$ and let $y=x+e$ be a received word such that $x \in C$ and the $Rank(e)=r$. The first attack is combinatorial and permits to recover an error $e$ of rank weight $r$ in $min(O((n-k)^3m^3q^{r\lfloor\frac{km}{n}\rfloor}, O((n-k)^3m^3q^{(r-1)\lfloor\frac{(k+1)m}{n}\rfloor}))$ operations on $GF(q)$. This attack dramatically improves on previous attack by introducing the length $n$ of the code in the exponent of the complexity, which was not the case in previous generic attacks. which can be considered The second attack is based on a algebraic attacks: 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(q^m)$ rather than in $GF(q)$ as it is usually the case. We consider two approaches to solve the problem in this new setting. Linearization technics show that if $n \ge (k+1)(r+1)-1$ the RSD problem can be solved in polynomial time, more generally we prove that if $\lceil \frac{(r+1)(k+1)-(n+1)}{r} \rceil \le k$, the problem can be solved with an average complexity $O(r^3k^3q^{r\lceil \frac{(r+1)(k+1)-(n+1)}{r} \rceil})$. We also consider solving with \grob bases for which which we discuss theoretical complexity, we also consider consider hybrid solving with \grob bases on practical parameters. As an example of application we use our new attacks on all proposed recent cryptosystems which reparation the GPT cryptosystem, we break all examples of published proposed parameters, some parameters are broken in less than 1 s in certain cases.

  • Open Access

    Generalized companion matrix for approximate GCD

    by Paola Boito, Olivier Ruatta

    We study a variant of the univariate approximate GCD problem, where the coefficients of one polynomial f(x)are known exactly, whereas the coefficients of the second polynomial g(x)may be perturbed. Our approach relies on the properties of the matrix which describes the operator of multiplication by gin the quotient ring C[x]=(f). In particular, the structure of the null space of the multiplication matrix contains all the essential information about GCD(f; g). Moreover, the multiplication matrix exhibits a displacement structure that allows us to design a fast algorithm for approximate GCD computation with quadratic complexity w.r.t. polynomial degrees.

  • Open Access

    On the Computation of the Topology of a Non-Reduced Implicit Space Curve

    by Daouda Niang Diatta, Bernard Mourrain, Olivier Ruatta

    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. It computes a Piecewise Linear Structure (PLS) isotopic to the original space curve. The algorithm is designed to provide the exact result for all inputs. It's a symbolic-numeric algorithm based on subresultant computation. Simple algebraic criteria are given to certify the output of the algorithm. The algorithm uses only one projection of the non-reduced space curve augmented with adjacency information around some "particular points" of the space curve. The algorithm is implemented with the Mathemagix Computer Algebra System (CAS) using the SYNAPS library as a backend.

  • Efficient erasure list-decoding of Reed-Muller codes

    by Philippe Gaborit, Olivier Ruatta

    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