Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Reed-Solomon code:
TR12-045 | 22nd April 2012
Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer

On the Concrete-Efficiency Threshold of Probabilistically-Checkable Proofs

Revisions: 3

Probabilistically-Checkable Proofs (PCPs) form the algorithmic core that enables succinct verification of long proofs/computations in many cryptographic constructions, such as succinct arguments and proof-carrying data.

Despite the wonderful asymptotic savings they bring, PCPs are also the infamous computational bottleneck preventing these cryptographic constructions from being used in practice. This reflects ... more >>>

TR16-073 | 7th May 2016
Eli Ben-Sasson, iddo Ben-Tov, Ariel Gabizon, Michael Riabzev

Improved concrete efficiency and security analysis of Reed-Solomon PCPPs

Revisions: 1 , Comments: 1

A Probabilistically Checkable Proof of Proximity (PCPP) for a linear code $C$, enables to determine very efficiently if a long input $x$, given as an oracle, belongs to $C$ or is far from $C$.
PCPPs are often a central component of constructions of Probabilistically Checkable Proofs (PCP)s [Babai et al. ... more >>>

ISSN 1433-8092 | Imprint