## CryptoDB

### Alain Couvreur

#### ORCID: 0000-0003-4554-6720

#### Publications

**Year**

**Venue**

**Title**

2024

ASIACRYPT

FOLEAGE: F4-OLE-Based Multi-Party Computation for Boolean Circuits
Abstract

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.

2024

ASIACRYPT

MinRank Gabidulin encryption scheme on matrix codes
Abstract

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.

2023

CRYPTO

Correlated Pseudorandomness from the Hardness of Quasi-Abelian Decoding
Abstract

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.

2023

ASIACRYPT

Pseudorandomness of Decoding, Revisited: Adapting OHCP to Code-Based Cryptography
Abstract

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.

2023

ASIACRYPT

A new approach based on quadratic forms to attack the McEliece cryptosystem
Abstract

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.

2022

CRYPTO

On Codes and Learning with Errors over Function Fields
📺
Abstract

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.

2018

ASIACRYPT

An Efficient Structural Attack on NIST Submission DAGS
Abstract

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.

#### Coauthors

- Nicolas Aragon (1)
- Élise Barelli (1)
- Maxime Bombar (4)
- Dung Bui (1)
- Geoffroy Couteau (2)
- Alain Couvreur (9)
- Thomas Debris-Alazard (2)
- Clément Ducros (2)
- Victor Dyseryn (1)
- Philippe Gaborit (1)
- Valérie Gauthier-Umaña (1)
- Rocco Mora (1)
- Ayoub Otmani (2)
- Sacha Servan-Schreiber (1)
- Jean-Pierre Tillich (3)
- Adrien Vinçotte (1)