Subquadratic SNARGs in the Random Oracle Model
summary
Claim: a SNARG in the random‑oracle model with argument size O((log(T/ε))·log T) versus Micali’s roughly (log(T/ε))^2, giving subquadratic size when T is small relative to 1/ε. Construction uses a chopped Merkle tree (stop layer ≈ log Q), domain‑separated oracle queries, and a permute‑and‑block robust PCP notion; analysis scores collisions and inversions to bound multi‑collision advantage. Concrete comparison: with a base PCP of length 2^30 and q≈3 the scheme halves Micali’s size in regimes of interest; construction is ROM and argued post‑quantum secure.
AI-written summary · about
chapters (17)
- 0:00Intro
- 1:34SNARGs in the ROM
- 3:45The Random Oracle Model (ROM)
- 4:20Known SNARG constructions
- 5:21Micali's SNARG root- Prover
- 8:35Micali's argument size
- 16:04Concrete Argument Size
- 17:46Our construction • Starting point: Micall's construction
- 19:55Chopped tree
- 23:55Domain separation
- 25:09Permuting the proof
- 31:19Our construction in full
- 32:51Change 4: Robust PCP
- 34:12Security of our construction
- 36:29Scoring oracle queries
- 39:31Proof of the lemma
- 43:00Conclusions and open problems
related talks
39mSNARGs Beyond Non-Signaling
53mA Pure Indistinguishability Obfuscation Approach to Adaptively-Sound SNARGs for NP
58mSNARGs for P/poly from SIS
01h 15mProofs - Theory
01h 08mTowards SNARGs for NP from Standard Assumptions
44mCorrelation Intractability and SNARGs from Sub-exponential DDH
46mQuantum pseudorandomness in Algorithmica, and its implications to cryptography and complexity
45mNon-interactive Universal Arguments