Non-interactive Universal Arguments
summary
Constructs non-interactive universal arguments by lifting existing SNARGs for P into a universal protocol using fully homomorphic encryption plus a family of T-hard puzzles placed in the CRS (puzzles of difficulty 2^i, prover solves the log T puzzle). Assumptions are standard LWE or DLIN, FHE, and a mild worst‑case non‑uniform complexity hypothesis to get soundness against non‑uniform adversaries; only uniform soundness avoids that extra hypothesis. Extension to incremental verifiable computation is included and the scheme is shown to work under those hypotheses.
AI-written summary · about
chapters (19)
- 0:00Intro
- 1:31Universal Arguments [Barak-Goldreich08]
- 4:55Universal Arguments Barak-Goldreich08
- 6:43Universal Arguments Motivation
- 8:44Known Results
- 12:01Non-interactive Arguments (SNARGS)
- 16:20Main Result
- 17:21Results (cont.)
- 21:38Lifting Theorem
- 24:14Existing Constructions Aren't Universal
- 25:36Main Idea
- 27:31Cryptographic Puzzles
- 30:30Proof Idea
- 31:49Constructing Puzzles
- 32:54Worst Case Hard Problem
- 34:10The Puzzle
- 39:23A Technical Challenge
- 39:53Universal Argument Construction
- 41:43Future Directions
related talks
01h 08mTowards SNARGs for NP from Standard Assumptions
53mA Pure Indistinguishability Obfuscation Approach to Adaptively-Sound SNARGs for NP
01h 15mProofs - Theory
58mSNARGs for P/poly from SIS
23mSonic: Nearly Trustless SNARK Setups
01h 07mBatch Arguments for NP and SNARGs for P from LWE
33mA New Approach for Non-Interactive Zero-Knowledge from Learning with Errors
01h 04mHow to Encrypt a Functionality