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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Functional Commitments and SNARGs for P/poly from SIS

  • Hoeteck Wee

摘要

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.