A New Approach for Non-Interactive Zero-Knowledge from Learning with Errors
summary
New result builds a concrete LWE-based hidden bits generator that yields NIZKs with a dual-mode CRS (statistically binding versus computationally hiding) using lattice trapdoors but no correlation intractability or FHE. Construction makes a large seed t produce a small U·t commitment and openings pi = Wi·t, verifier checks Ai·pi equals the commitment and rounds an inner product; soundness follows from small noise while hiding follows via a bit-flipping vector c (leftover hash lemma) and hybrids reducing to LWE. Followups shrink the CRS and make setup transparent.
AI-written summary · about
chapters (13)
- 0:00Non-interactive zero-knowledge intro
- 1:05Hidden bits model and NIZK history
- 3:13Why hidden bits model failed
- 4:36New hidden bits from LWE
- 7:54Design principles
- 9:04Binding mode construction
- 12:27GenBits algorithm
- 16:01Correctness and binding analysis
- 19:00Hiding mode construction
- 21:15Hiding mode security
- 25:16Summary and assumptions
- 28:45Follow-up works
- 30:55Conclusion and future
related talks
49mLattice-Based Zero Knowledge and Applications
38mNew Techniques for Zero-Knowledge: Leveraging Inefficient Provers to Reduce Assumptions, ...
01h 06mLattice-based Zero-knowledge Proofs
33mHow to Share an NP Statement or Combiners for Zero-Knowledge Proofs
26mPractical, Efficient ZKPs, Economic and Social Processes
01h 29mLattices, Multilinear Maps and Program Obfuscation
33mAn Introduction to Zero Knowledge Proofs
01h 04mThe Mathematics of Lattices II