Functional Commitments and SNARGs for P/poly from SIS
摘要
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 and size s over \(\ell \) -bit inputs, we obtain Here, \(O(\cdot )\) hides \(\textsf{poly}(\lambda ,\log \ell , \log s)\) factors. 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, self-contained, and completely elementary: we rely only on simple algebraic operations and do not utilize correlation intractability, sum-check, or non-black-box use of cryptography.