Paper 2023/845

Correlated Pseudorandomness from the Hardness of Quasi-Abelian Decoding

Maxime Bombar, École Polytechnique, Computer Science Laboratory of the École Polytechnique, Inria Saclay - Île-de-France Research Centre
Geoffroy Couteau, French National Centre for Scientific Research, Institut de Recherche en Informatique Fondamentale, Université Paris-Cité
Alain Couvreur, Inria Saclay - Île-de-France Research Centre, Computer Science Laboratory of the École Polytechnique
Clément Ducros, Institut de Recherche en Informatique Fondamentale, Université Paris-Cité

Secure computation often benefits from the use of correlated randomness to achieve fast, non-cryptographic online protocols. A recent paradigm put forth by Boyle $\textit{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 computations, yielding silent secure two-party computation protocols (protocols where the preprocessing phase requires almost no communication). Furthermore, programmable PCG's 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) PCG's for correlations such as random oblivious transfers. However, the situation is less satisfying for the case of random oblivious linear evaluation (OLE), which generalises oblivious transfers over large fields, and are a core resource for secure computation of arithmetic circuits. The state-of-the-art work of Boyle $\textit{et al.}$ (Crypto 2020) constructed programmable PCG's for OLE, but their work suffers from two important downsides: (1) it only generates OLE's over large fields, and (2) it relies on relatively new "splittable" ring-LPN assumption, which lacks strong security foundations. In this work, we construct new programmable PCG's for the OLE correlation, that overcome both limitations. To this end, we introduce the quasi-abelian syndrome decoding problem (QA-SD), a family of assumptions which generalises the well-established quasi-cyclic syndrome decoding assumption. Building upon QA-SD, we construct new programmable PCG's for OLE's over any field $\mathbb{F}_q$ with $q>2$. Our analysis also sheds light on the security of the ring-LPN assumption used in Boyle $\textit{et al.}$ (Crypto 2020). Using our new PCG's, we obtain the first efficient N-party silent secure computation protocols for computing general arithmetic circuit over $\mathbb{F}_q$ for any $q>2$.

Note: This is a long version of a paper accepted at CRYPTO'23.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2023
Pseudorandom correlation generatorsoblivious linear evaluationquasi-abelian codessilent secure computation
Contact author(s)
maxime bombar @ inria fr
couteau @ irif fr
alain couvreur @ inria fr
cducros @ irif fr
2023-06-06: approved
2023-06-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Maxime Bombar and Geoffroy Couteau and Alain Couvreur and Clément Ducros},
      title = {Correlated Pseudorandomness from the Hardness of Quasi-Abelian Decoding},
      howpublished = {Cryptology ePrint Archive, Paper 2023/845},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.