ECCC-Report TR17-134https://eccc.weizmann.ac.il/report/2017/134Comments and Revisions published for TR17-134en-usFri, 12 Jan 2018 12:58:51 +0200
Revision 2
| Fast Reed-Solomon Interactive Oracle Proofs of Proximity |
Eli Ben-Sasson,
Iddo Bentov,
Ynon Horesh,
Michael Riabzev
https://eccc.weizmann.ac.il/report/2017/134#revision2The family of Reed-Solomon (RS) codes plays a prominent role in the construction of quasilinear probabilistically checkable proofs (PCPs) and interactive oracle proofs (IOPs) with perfect zero knowledge and polylogarithmic verifiers. The large concrete computational complexity required to prove membership in RS codes is one of the biggest obstacles to deploying such
PCP/IOP systems in practice.
To advance on this problem we present a new interactive oracle proof of proximity (IOPP) for RS codes; we call it the Fast RS IOPP (FRI) because (i) it resembles the ubiquitous Fast Fourier Transform (FFT) and (ii) the arithmetic complexity of its prover is strictly linear and that of the verifier is strictly logarithmic (in comparison, FFT arithmetic complexity is quasi-linear but not strictly linear). Prior RS IOPPs and PCPs of proximity (PCPPs) required super-linear proving time even for polynomially large query complexity.
For codes of block-length n, the arithmetic complexity of the (interactive) FRI prover is less than 6 · n, while the (interactive) FRI verifier has arithmetic complexity ? 21 · log n, query complexity 2 · log n and constant soundness — words that are ?-far from the code are rejected with probability min {? · (1 ? o(1)), ?' } where ?' is a positive constant that depends only on the code rate. The particular combination of query complexity and soundness obtained by FRI is better than that of the quasilinear PCPP of [Ben-Sasson and Sudan, SICOMP 2008], even with the tighter soundness analysis of [Ben-Sasson et al., STOC 2013; ECCC 2016]; consequently, FRI is likely to facilitate better concretely efficient zero knowledge proof and argument systems.
Previous concretely efficient PCPPs and IOPPs suffered a constant multiplicative factor loss in soundness with each round of “proof composition” and thus used at most O(log log n) rounds. We show that when ? is smaller than the unique decoding radius of the code (? < (1 ? ?)/2), FRI suffers only a negligible additive loss in soundness. This observation allows us to increase the number of “proof composition” rounds to ?(log n) and thereby improve prover running time.
Fri, 12 Jan 2018 12:58:51 +0200https://eccc.weizmann.ac.il/report/2017/134#revision2
Revision 1
| Fast Reed-Solomon Interactive Oracle Proofs of Proximity |
Eli Ben-Sasson,
Iddo Bentov,
Ynon Horesh,
Michael Riabzev
https://eccc.weizmann.ac.il/report/2017/134#revision1The family of Reed-Solomon (RS) codes plays a prominent role in the construction of quasilinear probabilistically checkable proofs (PCPs) and interactive oracle proofs (IOPs) with perfect zero knowledge and polylogarithmic verifiers. The large concrete computational complexity required to prove membership in RS codes is one of the biggest obstacles to deploying such
PCP/IOP systems in practice.
To advance on this problem we present a new interactive oracle proof of proximity (IOPP) for RS codes; we call it the Fast RS IOPP (FRI) because (i) it resembles the ubiquitous Fast Fourier Transform (FFT) and (ii) the arithmetic complexity of its prover is strictly linear and that of the verifier is strictly logarithmic (in comparison, FFT arithmetic complexity is quasi-linear but not strictly linear). Prior RS IOPPs and PCPs of proximity (PCPPs) required super-linear proving time even for polynomially large query complexity.
For codes of block-length n, the arithmetic complexity of the (interactive) FRI prover is less than 6 · n, while the (interactive) FRI verifier has arithmetic complexity $\leq$ 21 · log n, query complexity 2 · log n and constant soundness — words that are $\delta$-far from the code are rejected with probability min {$\delta$ · (1 - o(1)), $\delta_0$ } where $\delta_0$ is a positive constant that depends only on the code rate. The particular combination of query complexity and soundness obtained by FRI is better than that of the quasilinear PCPP of [Ben-Sasson and Sudan, SICOMP 2008], even with the tighter soundness analysis of [Ben-Sasson et al., STOC 2013; ECCC 2016]; consequently, FRI is likely to facilitate better concretely efficient zero knowledge proof and argument systems.
Previous concretely efficient PCPPs and IOPPs suffered a constant multiplicative factor loss in soundness with each round of “proof composition” and thus used at most O(log log n) rounds. We show that when $\delta$ is smaller than the unique decoding radius of the code, FRI suffers only a negligible additive loss in soundness. This observation allows us to increase the number of “proof composition” rounds to $\Theta$(log n) and thereby improve prover running time.
Tue, 21 Nov 2017 22:38:13 +0200https://eccc.weizmann.ac.il/report/2017/134#revision1
Paper TR17-134
| Fast Reed-Solomon Interactive Oracle Proofs of Proximity |
Eli Ben-Sasson,
Iddo Bentov,
Ynon Horesh,
Michael Riabzev
https://eccc.weizmann.ac.il/report/2017/134The family of Reed-Solomon (RS) codes plays a prominent role in the construction of quasilinear probabilistically checkable proofs (PCPs) and interactive oracle proofs (IOPs) with perfect zero knowledge and polylogarithmic verifiers. The large concrete computational complexity required to prove membership in RS codes is one of the biggest obstacles to deploying such
PCP/IOP systems in practice.
To advance on this problem we present a new interactive oracle proof of proximity (IOPP) for RS codes; we call it the Fast RS IOPP (FRI) because (i) it resembles the ubiquitous Fast Fourier Transform (FFT) and (ii) the arithmetic complexity of its prover is strictly linear and that of the verifier is strictly logarithmic (in comparison, FFT arithmetic complexity is quasi-linear but not strictly linear). Prior RS IOPPs and PCPs of proximity (PCPPs) required super-linear proving time even for polynomially large query complexity.
For codes of block-length n, the arithmetic complexity of the (interactive) FRI prover is less than 6 · n, while the (interactive) FRI verifier has arithmetic complexity ? 21 · log n, query complexity 2 · log n and constant soundness — words that are ?-far from the code are rejected with probability min {? · (1 ? o(1)), ?' } where ?' is a positive constant that depends only on the code rate. The particular combination of query complexity and soundness obtained by FRI is better than that of the quasilinear PCPP of [Ben-Sasson and Sudan, SICOMP 2008], even with the tighter soundness analysis of [Ben-Sasson et al., STOC 2013; ECCC 2016]; consequently, FRI is likely to facilitate better concretely efficient zero knowledge proof and argument systems.
Previous concretely efficient PCPPs and IOPPs suffered a constant multiplicative factor loss in soundness with each round of “proof composition” and thus used at most O(log log n) rounds. We show that when ? is smaller than the unique decoding radius of the code (? < (1 ? ?)/2), FRI suffers only a negligible additive loss in soundness. This observation allows us to increase the number of “proof composition” rounds to ?(log n) and thereby improve prover running time.
Fri, 08 Sep 2017 15:04:23 +0300https://eccc.weizmann.ac.il/report/2017/134