A New Approach for Non-Interactive Zero-Knowledge from  Learning with Errors

Brent Waters

Paper 2024/340

A New Approach for Non-Interactive Zero-Knowledge from Learning with Errors

Brent Waters

, The University of Texas at Austin, NTT Research

Abstract

We put forward a new approach for achieving non-interactive zero-knowledge proofs (NIKZs) from the learning with errors (LWE) assumption (with subexponential modulus to noise ratio). We provide a LWE-based construction of a hidden bits generator that gives rise to a NIZK via the celebrated hidden bits paradigm. A noteable feature of our construction is its simplicity. Our construction employs lattice trapdoors, but beyond that uses only simple operations. Unlike prior solutions we do not rely on a correlation intractability argument nor do we utilize fully homomorphic encryption techniques. Our solution provides a new methodology that adds to the diversity of techniques for solving this fundamental problem.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published elsewhere. Major revision. STOC 2024
Keywords: Non-interactive Zero Knowledge Learning with Errors
Contact author(s): bwaters @ cs utexas edu
History: 2024-02-29: revised; 2024-02-27: received; See all versions
Short URL: https://ia.cr/2024/340
License: CC BY

BibTeX

@misc{cryptoeprint:2024/340,
      author = {Brent Waters},
      title = {A New Approach for Non-Interactive Zero-Knowledge from  Learning with Errors},
      howpublished = {Cryptology ePrint Archive, Paper 2024/340},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/340}},
      url = {https://eprint.iacr.org/2024/340}
}