SNARGs for P/poly from SIS
0Hoeteck Wee (NTT Research)
https://simons.berkeley.edu/talks/hoeteck-wee-ntt-research-2025-07-15
Proofs
We present new constructions of succinct non-interactive functional commitments and arguments for circuits (i.e. P/poly), based on the SIS assumption without random oracles. For boolean circuits of depth d, we obtain
a non-interactive functional commitment scheme with O(1)-sized transparent CRS, O(1)-sized commitment, and O(d)-sized openings;
a non-interactive succinct argument (SNARG for P/poly) with O(1)-sized transparent CRS, and O(d)-sized unambiguous proofs.
Moreover, both schemes support fast online verification after a circuit-dependent pre-processing phase, and do not impose a bound on circuit parameters during set-up. Our constructions are simple, elementary and do not rely on correlation-intractable hashing.