Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > REED-SOLOMON CODE:
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

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 >>>

TR19-044 | 28th March 2019
Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf

#### DEEP-FRI: Sampling Outside the Box Improves Soundness

Revisions: 2

Motivated by the quest for scalable and succinct zero knowledge arguments, we revisit worst-case-to-average-case reductions for linear spaces, raised by [Rothblum, Vadhan, Wigderson, STOC 2013]. The previous state of the art by [Ben-Sasson, Kopparty, Saraf, CCC 2018] showed that if some member of an affine space $U$ is $\delta$-far in ... more >>>

ISSN 1433-8092 | Imprint