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
Abstract

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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in ASIACRYPT 2022
Keywords
secure computationinner productpost-quantum securityLPNLWE
Contact author(s)
couteau @ irif fr
maryam zarezadeh @ barkhauseninstitut org
History
2023-01-23: approved
2023-01-22: received
See all versions
Short URL
https://ia.cr/2023/072
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/072,
      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{https://eprint.iacr.org/2023/072}},
      url = {https://eprint.iacr.org/2023/072}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.