Paper 2023/882

Expand-Convolute Codes for Pseudorandom Correlation Generators from LPN

Srinivasan Raghuraman, Visa (United States), Massachusetts Institute of Technology
Peter Rindal, Visa (United States)
Titouan Tanguy, KU Leuven

The recent development of pseudorandom correlation generators (PCG) holds tremendous promise for highly efficient MPC protocols. Among other correlations, PCGs allow for the efficient generation of oblivious transfer (OT) and vector oblivious linear evaluations (VOLE) with sublinear communication and concretely good computational overhead. This type of PCG makes use of a so-called LPN-friendly error-correcting code. That is, for large dimensions the code should have very efficient encoding and have high minimum distance. We investigate existing LPN-friendly codes and find that several candidates are less secure than was believed. Beginning with the recent expand-accumulate codes, we find that for their aggressive parameters, aimed at good concrete efficiency, they achieve a smaller [pseudo] minimum distance than conjectured. This decreases the resulting security parameter of the PCG but it remains unclear by how much. We additionally show that the recently proposed and extremely efficient silver codes achieve only very small minimum distance and result in concretely efficient attacks on the resulting PCG protocol. As such, silver codes should not be used. We introduce a new LPN-friendly code which we call \emph{expand-convolute}. These codes have provably high minimum distance and faster encoding time than suitable alternatives, e.g. expand-accumulate. The main contribution of these codes is the introduction of a convolution step that dramatically increases the minimum distance. This in turn allows for a more efficient parameter selection which results in improved concrete performance. In particular, we observe a 3 times improvement in running time for a comparable security level.

Available format(s)
Cryptographic protocols
Publication info
Published by the IACR in CRYPTO 2023
PCGCoding TheoryOblivious TransferVOLE
Contact author(s)
srini131293 @ gmail com
peterrindal @ gmail com
titouan tanguy @ kuleuven be
2023-06-12: approved
2023-06-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Srinivasan Raghuraman and Peter Rindal and Titouan Tanguy},
      title = {Expand-Convolute Codes for Pseudorandom Correlation Generators from LPN},
      howpublished = {Cryptology ePrint Archive, Paper 2023/882},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.