International Association
for Cryptologic Research

The matrix code equivalence problem consists, given two matrix spaces $\mathcal{C},\mathcal{D} \subset \Fq^{m\times n}$ of dimension $k$, in finding invertible matrices $P\in\mathrm{GL}_m(\mathbb{F}_q)$ and $Q\in\mathrm{GL}_n(\mathbb{F}_q)$ such that $\mathcal{D}=P\mathcal{C} Q^{-1}$. Recent signature schemes such as MEDS and ALTEQ relate their security to the hardness of this problem. Recent works by Narayanan, Qiao and Tang on the one hand and by Ran and Samardjiska on the other hand tackle this problem. The former is restricted to the ``cubic'' case $k = m =n$ and succeeds in $\widetilde{\mathcal{O}}(q^{\frac k 2})$ operations. The latter is an algebraic attack on the general problem whose complexity is not fully understood and which succeeds only on $\mathcal{O}(1/q)$ instances. We present a novel algorithm which solves the problem in the general case. Our approach consists in reducing the problem to the matrix code conjugacy problem, \emph{i.e.} the case $P=Q$. For the latter problem, similarly to the permutation code equivalence problem in Hamming metric, a natural invariant based on the \emph{Hull} of the code can be used. Next, the equivalence of codes can be deduced using a usual list collision argument. For $k=m=n$, our algorithm achieves the same time complexity as Narayanan \emph{et al.} but with a lower space complexity. Moreover, ours extends to a much broader range of parameters.

The McEliece scheme is a generic frame which allows to use any error correcting code of which there exists an efficient decoding algorithm to design an encryption scheme by hiding the generator matrix code. Similarly, the Niederreiter frame is the dual version of the McEliece scheme, and achieves smaller ciphertexts. In the present paper, we propose a generalization of the McEliece frame and the Niederreiter frame to matrix codes and the MinRank problem, that we apply to Gabidulin matrix codes (Gabidulin rank codes considered as matrix codes). The masking we consider consists in starting from a rank code C, to consider a matrix version of C and to concatenate a certain number of rows and columns to the matrix codes version of the rank code C and then apply to an isometry for matric codes, i.e. right and left multiplications by fixed random matrices. The security of the schemes relies on the MinRank problem to decrypt a ciphertext, and the structural security of the scheme relies on a new problem EGMC-Indistinguishability problem that we introduce and that we study in detail. The main structural attack that we propose consists in trying to recover the masked linearity over the extension field which is lost during the masking process. Overall, starting from Gabidulin codes we obtain a very appealing tradeoff between the size of ciphertext and the size of the public key. For 128b of security we propose parameters ranging from ciphertext of size 65 B (and public keys of size 98 kB) to ciphertext of size 138B (and public key of size 41 kB). Our new approach permits to achieve better trade-off between ciphertexts and public key than the classical McEliece scheme. Our new approach permits to obtain an alternative scheme to the classic McEliece scheme, to obtain very small ciphertexts, with moreover smaller public keys than in the classic McEliece scheme. For 256 bits of security, we can obtain ciphertext as low as 119B, or public key as low as 87kB.

Secure Multi-party Computation (MPC) allows two or more parties to compute any public function over their privately-held inputs, without revealing any information beyond the result of the computation. Modern protocols for MPC generate a large amount of input-independent preprocessing material called multiplication triples, in an offline phase. This preprocessing can later be used by the parties to efficiently instantiate an input-dependent online phase computing the function. To date, the state-of-the-art secure multi-party computation protocols in the preprocessing model are tailored to secure computation of arithmetic circuits over large fields and require little communication in the preprocessing phase, typically O(N · m) to generate m triples among N parties. In contrast, when it comes to computing preprocessing for computations that are naturally represented as Boolean circuits, the state-of-the-art techniques have not evolved since the 1980s, and in particular, require every pair of parties to execute a large number of oblivious transfers before interacting to convert them to N-party triples, which induces an Ω(N^2 · m) communication overhead. In this paper, we introduce F4OLEAGE, which addresses this gap by introducing an efficient preprocessing protocol tailored to Boolean circuits. F4OLEAGE exhibits excellent performance: it generates m multiplication triples over F2 using only N · m + O(N^2 · log m) bits of communication for N-parties, and can concretely produce over 12 million triples per second in the 2-party setting on one core of a commodity machine. Our result builds upon an efficient Pseudorandom Correlation Generator (PCG) for multiplications triples over the field F4. Roughly speaking, a PCG enables parties to stretch a short seed into a large number of pseudorandom correlations non-interactively, which greatly improves the efficiency of the offline phase in MPC protocols. Our construction significantly outperforms the state-of-the-art, which we demonstrate via a prototype implementation. This is achieved by introducing a number of protocol-level, algorithmic-level, and implementation-level optimizations on the recent PCG construction of Bombar et al. (Crypto 2023) from the Quasi-Abelian Syndrome Decoding assumption.

Secure computation often benefits from the use of correlated randomness to achieve fast, non-cryptographic online protocols. A recent paradigm put forth by Boyle et al. (CCS 2018, Crypto 2019) showed how pseudorandom correlation generators (PCG) can be used to generate large amounts of useful forms of correlated (pseudo)randomness, using minimal interactions followed solely by local computation, yielding silent secure two-party computation protocols (protocols where the preprocessing phase requires almost no communication). Furthermore, programmable PCGs can be used similarly to generate multiparty correlated randomness to be used in silent secure N-party protocols. Previous works constructed very efficient (non-programmable) PCGs for correlations such as random oblivious transfer. However, the situation is less satisfying for the case of random oblivious linear evaluation (OLE), which generalize oblivious transfers over large field, and are a core resource for secure computation of arithmetic circuits. The state-of-the-art work of (Boyle et al., Crypto 2020) constructed programmable PCGs for OLE, but their work suffers from two important downsides: (1) it only generates OLEs over large fields, and (2) it relies on a relatively new ``splittable'' ring-LPN assumption, which lacks strong security foundations. In this work, we construct new programmable PCGs for the OLE correlation, that overcome both limitations. To this end, we introduce the Quasi-Abelian Syndrome Decoding problem (QASD), a family of assumption which generalizes the well-established Quasi-Cyclic Syndrome Decoding assumption. Building upon QASD, we construct new programmable PCGs for OLEs over any field Fq with q > 2. Furthermore, we provide strong security foundations for QASD, showing that it resists all attacks from the linear test framework (Couteau et al., Crypto 2021) and admits a search-to-decision reduction. In particular, our analysis also sheds light on the security of the ring-LPN assumption used in Boyle et al., Crypto 2020). Using our new PCGs, we obtain the first efficient N-party silent secure computation protocols for computing general arithmetic circuit over Fq for any q > 2.

Recent code-based cryptosystems rely, among other things, on the hardness of the decisional decoding problem. If the search version is well understood, both from practical and theoretical standpoints, the decision version has been less studied in the literature, and little is known about its relationships with the search version, especially for structured variants. On the other hand, in the world of Euclidean lattices, the situation is rather different, and many reductions exist, both for unstructured and structured versions of the underlying problems. For the latter versions, a powerful tool called the OHCP framework (for Oracle with Hidden Center Problem), which appears to be very general, has been introduced by Peikert et al. (STOC 2017) and has proved to be very useful as a black box inside reductions. In this work, we revisit this technique and extract the very essence of this framework, namely the Oracle Comparison Problem (OCP), to show how to recover the support of the error, solving an Oracle with Hidden Support Problem (OHSP), more suitable for code-based cryptography. This yields a new worst-case to average-case search-to-decision reduction for the Decoding Problem, as well as a new average-case to average-case reduction. We then turn to the structured versions and explain why this is not as straightforward as for Euclidean lattices. If we fail to give a search-to-decision reduction for structured codes, we believe that our work opens the way towards new reductions for structured codes, given that the OHCP framework proved to be so powerful in lattice-based cryptography. Furthermore, we also believe that this technique could be extended to codes endowed with other metrics, such as the rank metric, for which no reduction is known.

We introduce a novel algebraic approach for attacking the McEliece cryptosystem which is currently at the $4$-th round of the NIST competition. The contributions of the article are twofold. (1) We present a new distinguisher on alternant and Goppa codes working in a much broader range of parameters than \cite{FGOPT11}. (2) With this approach we also provide a polynomial--time key recovery attack on alternant codes which are distinguishable with the distinguisher \cite{FGOPT11}. These results are obtained by introducing a subspace of matrices representing quadratic forms. Those are associated with quadratic relations for the component-wise product in the dual of the Goppa (or alternant) code of the cryptosystem. It turns out that this subspace of matrices contains matrices of unusually small rank in the case of alternant or Goppa codes ($2$ or $3$ depending on the field characteristic) revealing the secret polynomial structure of the code. MinRank solvers can then be used to recover the secret key of the scheme. We devise a dedicated algebraic modeling in characteristic $2$ where the Gröbner basis techniques to solve it can be analyzed. This computation behaves differently when applied to the matrix space associated with a random code rather than with a Goppa or an alternant code. This gives a distinguisher of the latter code families, which contrarily to the one proposed in \cite{FGOPT11} working only in a tiny parameter regime is now able to work for code rates above $\frac{2}{3}$. It applies to most of the instantiations of the McEliece cryptosystem in the literature. It coincides with the one of \cite{FGOPT11} when the latter can be applied (and is therefore of polynomial complexity in this case). However, its complexity increases significantly when \cite{FGOPT11} does not apply anymore, but stays subexponential as long as the co-dimension of the code is sublinear in the length (with an asymptotic exponent which is below those of all known key recovery or message attacks). For the concrete parameters of the McEliece NIST submission \cite{ABCCGLMMMNPPPSSSTW20}, its complexity is way too complex to threaten the cryptosystem, but is smaller than known key recovery attacks for most of the parameters of the submission. This subspace of quadratic forms can also be used in a different manner to give a polynomial time attack of the McEliece cryptosystem based on generic alternant codes or Goppa codes provided that these codes are distinguishable by the method of \cite{FGOPT11}, and in the Goppa case we need the additional assumption that its degree is less than $q-1$, where $q$ is the alphabet size of the code.

It is a long standing open problem to find search to decision reductions for structured versions of the decoding problem of linear codes. Such results in the lattice-based setting have been carried out using number fields: Polynomial–LWE, Ring–LWE, Module–LWE and so on. We propose a function field version of the LWE problem. This new framework leads to another point of view on structured codes, e.g. quasi-cyclic codes, strengthening the connection between lattice-based and code-based cryptography. In particular, we obtain the first search to decision reduction for structured codes. Following the historical constructions in lattice–based cryptography, we instantiate our construction with function fields analogues of cyclotomic fields, namely Carlitz ex- tensions, leading to search to decision reductions on various versions of Ring-LPN, which have applications to secure multi party computation and to an authentication protocol.

We present an efficient key recovery attack on code based encryption schemes using some quasi-dyadic alternant codes with extension degree 2. This attack permits to break the proposal DAGS recently submitted to NIST.