CryptoDB
Functional Commitments and SNARGs for P/poly from SIS
| Authors: |
|
|---|---|
| Download: | |
| Conference: | CRYPTO 2025 |
| Abstract: | We present new constructions of succinct non-interactive functional commitments and arguments for circuits, based on the SIS assumption without random oracles. For boolean circuits of depth $d$ and size $s$ over $\ell$-bit inputs, 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. Here, $O(\cdot)$ hides $\poly(\lambda,\log \ell, \log s)$ factors. Moreover, both schemes support fast online verification, after a circuit-dependent pre-processing phase; do not impose a bound on circuit parameters during set-up; and avoid non-black-box use of cryptography. * Our functional commitment scheme achieves a substantial improvement over the lattice-based schemes of Albrecht, et.~al (CRYPTO 22), Wee and Wu (EUROCRYPT 2023), Balbas, et.~al (TCC 2023), and Wee (EUROCRYPT 2025), all of which (i) rely on strong, non-standard variants of SIS, (ii) require a structured CRS, (iii) impose an a-priori bound on the depth or width of the circuit during set-up. * Our SNARG constitutes the first non-trivial SNARG for general computation based a standard search assumption (without random oracles). Prior works relied on a decisional assumption like LWE, sub-exponential DDH, or $k$-Lin; or non-standard variants of SIS. |
BibTeX
@inproceedings{crypto-2025-35833,
title={Functional Commitments and SNARGs for P/poly from SIS},
publisher={Springer-Verlag},
author={Hoeteck Wee},
year=2025
}