Computational Integrity with a Public Random String from Quasi-Linear PCPs

By Eli Ben-Sasson, Iddo Bentov, Alessandro Chiesa, Ariel Gabizon, Daniel Genkin, Matan Hamilis, Evgenya Pergament, Michael Riabzev, Mark Silberstein, Eran Tromer and 1 more. 2017

74 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Eli Ben-Sasson
2. Srinath T. V. Setty
3. Michael Riabzev
4. Michael Walfish
5. Iddo Bentov
6. Yinon Horesh
7. Andrew Justin Blumberg
8. Dan Boneh

In Computational Theory and Mathematics

1. Eli Ben-Sasson
2. Michael Walfish
3. Michael Riabzev
4. Iddo Bentov
5. Andrew Justin Blumberg
6. Yinon Horesh
7. Justin Thaler
8. Srinath T. V. Setty

Citations in the corpus

• Doubly-Efficient zkSNARKs Without Trusted Setup (2018, unknown): “builds non-interactive ZK arguments from short PCPs, following the seminal work of Kilian [62, 63] and Micali [73], the landmark result of Ben-Sasson and Sudan [17], and recent generalizations of PCPs [9, 14, 87].”
• Scalable, transparent, and post-quantum secure computational integrity (2018, methodology): “• SCI (same measurements used in [13]) with 80-bit security”
• Aurora: Transparent Succinct Arguments for R1CS (2019, methodology): “This compilation retains the foregoing advantages (transparency, lightweight cryptography, and plausible post-quantum security) and, in addition, facilitates greater efficiency, as IOPs have superior efficiency compared to PCPs [17, 15, 12, 14, 13].”
• Scalable Zero Knowledge with No Trusted Setup (2019, methodology): “The largest contributor to communication complexity, and to verifier time and space complexity in our ZK-STARK (and prior related works [27, 17, 33, 9]) is the cost of checking authentication paths.”
• Privacy-Preserving Solutions for Blockchain: Review and Challenges (2019, background): “The origin of STARKs relates to the research of Scalable Computational Integrity and Privacy (SCIP) [119].”
• Full Accounting for Verifiable Outsourcing (2017, background): “The second is SCI [17], which aims to be general Session J1: Outsourcing CCS’17, October 30-November 3, 2017, Dallas, TX, USA”
• Ligero: Lightweight Sublinear Arguments Without a Trusted Setup (2017, background): “These zk-STARK constructions signi cantly improve over the previous ones from [4].”
• The Efficient Server Audit Problem, Deduplicated Re-execution, and the Web (2017, background): “Execution integrity has long been studied by theorists [15, 37, 38, 42, 60], and these ideas have been refined and implemented [19, 32, 65, 75] (see [89] for a survey and [12, 18, 88, 96] for recent developments).”