Non-Interactive Secure Computation of Inner-Product from LPN and LWE - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année : 2022

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

Résumé

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.
Fichier principal
Vignette du fichier
ip_lpn.pdf (649.51 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03860759 , version 1 (18-11-2022)

Identifiants

  • HAL Id : hal-03860759 , version 1

Citer

Geoffroy Couteau, Maryam Zarezadeh. Non-Interactive Secure Computation of Inner-Product from LPN and LWE. Advances in Cryptology - ASIACRYPT 2022, Dec 2022, Taipei, Taiwan. ⟨hal-03860759⟩
43 Consultations
171 Téléchargements

Partager

Gmail Facebook X LinkedIn More