CryptoDB
Maxime Bombar
ORCID: 0000-0001-9081-6094
Publications
Year
Venue
Title
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.
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.
Coauthors
- Geoffroy Couteau (1)
- Alain Couvreur (3)
- Thomas Debris-Alazard (2)
- Clément Ducros (1)