Paper 2023/072

Non-Interactive Secure Computation of Inner-Product from LPN and LWE

Geoffroy Couteau, CNRS, IRIF, Université Paris Cité
Maryam Zarezadeh, Barkhausen Institut

We put forth a new cryptographic primitive for securely computing inner-products in a scalable, non-interactive fashion: any party can broadcast a public (computationally hiding) encoding of its input, and store a secret state. Given their secret state and the other party's public encoding, any pair of parties can non-interactively compute additive shares of the inner-product between the encoded vectors. We give constructions of this primitive from a common template, which can be instantiated under either the LPN (with non-negligible correctness error) or the LWE (with negligible correctness error) assumptions. Our construction uses a novel twist on the standard non-interactive key exchange based on the Alekhnovich cryptosystem, which upgrades it to a non-interactive inner product protocol almost for free. In addition to being non-interactive, our constructions have linear communication (with constants smaller than all known alternatives) and small computation: using LPN or LWE with quasi-cyclic codes, we estimate that encoding a length-$2^{20}$ vector over a 32-bit field takes less that 2s on a standard laptop; decoding amounts to a single cheap inner-product. We show how to remove the non-negligible error in our LPN instantiation using a one-time, logarithmic-communication preprocessing. Eventually, we show to to upgrade its security to the malicious model using new sublinear-communication zero-knowledge proofs for low-noise LPN samples, which might be of independent interest.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in ASIACRYPT 2022
secure computationinner productpost-quantum securityLPNLWE
Contact author(s)
couteau @ irif fr
maryam zarezadeh @ barkhauseninstitut org
2023-01-23: approved
2023-01-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Geoffroy Couteau and Maryam Zarezadeh},
      title = {Non-Interactive Secure Computation of Inner-Product from LPN and LWE},
      howpublished = {Cryptology ePrint Archive, Paper 2023/072},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.