Lattice-based non-interactive argument systems
Abstract/Contents
- Abstract
- 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 long-standing 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 lattice-based SNARG candidates. In fact, we show that one of our new candidates 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). This is the first quasi-optimal SNARG from any concrete cryptographic assumption. Again, because of our reliance on lattice-based techniques, all of our new candidates resist quantum attacks (in contrast to existing pairing-based constructions).
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource. |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | 2018; ©2018 |
| Publication date | 2018; 2018 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Wu, David J |
|---|---|
| Degree supervisor | Boneh, Dan, 1969- |
| Thesis advisor | Boneh, Dan, 1969- |
| Thesis advisor | Reingold, Omer |
| Thesis advisor | Wootters, Mary |
| Degree committee member | Reingold, Omer |
| Degree committee member | Wootters, Mary |
| Associated with | Stanford University, Computer Science Department. |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | David J. Wu. |
|---|---|
| Note | Submitted to the Computer Science Department. |
| Thesis | Thesis Ph.D. Stanford University 2018. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2018 by David Junzi Wu
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...