Lattice-Based Non-Interactive Argument Systems

David J. Wu


Advised by Professor Dan Boneh


Non-interactive argument systems are an important building block in many cryptographic protocols. In this work, we begin by studying non-interactive zero-knowledge (NIZK) arguments for general NP languages. In a NIZK argument system, a prover can convince a verifier that a statement is true without revealing anything more about the statement. Today, NIZK arguments can be instantiated from random oracles, or, in the common reference string (CRS) model, from trapdoor permutations, pairings, or indistinguishability obfuscation. Notably absent from this list are constructions from lattice assumptions, and realizing NIZKs (for general NP languages) from lattices has been a longstanding open problem. In this work, we make progress on this problem by giving the first construction of a multi-theorem NIZK argument from standard lattice assumptions in a relaxed model called the preprocessing model, where we additionally assume the existence of a trusted setup algorithm that generates a proving key (used to construct proofs) and a verification key (used to verify proofs). Moreover, by basing hardness on lattice assumptions, our construction gives the first candidate that plausibly resists quantum attacks.

We then turn our attention to constructing succinct non-interactive arguments (SNARGs) for general NP languages. SNARGs enable verifying computations with substantially lower complexity than that required for classic NP verification. Prior to this work, all SNARG constructions relied on random oracles, pairings, or indistinguishability obfuscation. This work gives the first candidate constructions of a lattice-based SNARG in the CRS model. In fact, we show that our new SNARGs satisfy an appealing property called “quasi-optimality,” which means that the SNARG simultaneously minimizes both the prover complexity and the proof size (up to polylogarithmic factors). Our work gives the first quasi-optimal SNARGs from a concrete cryptographic assumption. Again, because of our reliance on lattice-based assumptions, they resist quantum attacks (in contrast to existing pairing-based constructions).

  author = {David J. Wu},
  title  = {Lattice-Based Non-Interactive Argument Systems},
  school = {Stanford University},
  year   = {2018}