Paper 2019/808

2-Message Publicly Verifiable WI from (Subexponential) LWE

Alex Lombardi, Vinod Vaikuntanathan, and Daniel Wichs

Abstract

We construct a 2-message publicly verifiable witness indistinguishable argument system for NP assuming that the Learning with Errors (LWE) problem is subexponentially hard. Moreover, the protocol is ``delayed input''; that is, the verifier message in this protocol does not depend on the instance. This means that a single verifier message can be reused many times. We construct two variants of this argument system: one variant is adaptively sound, while the other is public-coin (but only non-adaptively sound). We obtain our result via a generic transformation showing that the correlation intractable hash families constructed by Canetti et al. (STOC 2019) and Peikert and Shiehian (CRYPTO 2019) suffice to construct such 2-message WI arguments when combined with an appropriately chosen ``trapdoor Sigma-protocol.'' Our construction can be seen as an adaptation of the Dwork-Naor ``reverse randomization'' paradigm (FOCS '00) for constructing ZAPs to the setting of computational soundness rather than statistical soundness. Our adaptation of the Dwork-Naor transformation crucially relies on complexity leveraging to prove that soundness is preserved.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Contact author(s)
alexjl @ mit edu
History
2019-07-14: received
Short URL
https://ia.cr/2019/808
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/808,
      author = {Alex Lombardi and Vinod Vaikuntanathan and Daniel Wichs},
      title = {2-Message Publicly Verifiable WI from (Subexponential) LWE},
      howpublished = {Cryptology ePrint Archive, Paper 2019/808},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/808}},
      url = {https://eprint.iacr.org/2019/808}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.