Interactive Oracle Proofs (IOPs) form the backbone of some of the most efficient general-purpose cryptographic proof-systems. In an IOP, the prover can interact with the verifier over multiple rounds, where in each round the prover sends a long message, from which the verifier only queries a few symbols. State-of-the-art IOPs achieve a linear-size prover and a poly-logarithmic time verifier but require a relatively large, logarithmic, number of rounds. While the Fiat-Shamir heuristic can be used to eliminate the need for actual interaction, in modern highly-parallelizable computer architectures such as GPUs, the large number of rounds still translates into a major bottleneck for the prover, since it needs to alternate between computing the IOP messages and the Fiat-Shamir hashes. Motivated by this fact, in this work we study the round complexity of linear-prover IOPs. Our main result is an IOP for a large class of Boolean circuits, with only \(O(\log ^*(S))\) rounds, where \(\log ^*\) denotes the iterated logarithm function (and S is the circuit size). The prover has linear size O(S) and the verifier runs in time \(\textrm{polylog}(S)\) and has query complexity \(O(\log ^*(S))\) . The protocol is both conceptually simpler, and strictly more efficient, than prior linear prover IOPs for Boolean circuits.

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

Linear Prover IOPs in Log Star Rounds

  • Noor Athamnah,
  • Noga Ron-Zewi,
  • Ron D. Rothblum

摘要

Interactive Oracle Proofs (IOPs) form the backbone of some of the most efficient general-purpose cryptographic proof-systems. In an IOP, the prover can interact with the verifier over multiple rounds, where in each round the prover sends a long message, from which the verifier only queries a few symbols. State-of-the-art IOPs achieve a linear-size prover and a poly-logarithmic time verifier but require a relatively large, logarithmic, number of rounds. While the Fiat-Shamir heuristic can be used to eliminate the need for actual interaction, in modern highly-parallelizable computer architectures such as GPUs, the large number of rounds still translates into a major bottleneck for the prover, since it needs to alternate between computing the IOP messages and the Fiat-Shamir hashes. Motivated by this fact, in this work we study the round complexity of linear-prover IOPs. Our main result is an IOP for a large class of Boolean circuits, with only \(O(\log ^*(S))\) rounds, where \(\log ^*\) denotes the iterated logarithm function (and S is the circuit size). The prover has linear size O(S) and the verifier runs in time \(\textrm{polylog}(S)\) and has query complexity \(O(\log ^*(S))\) . The protocol is both conceptually simpler, and strictly more efficient, than prior linear prover IOPs for Boolean circuits.