[BBHR18] Scalable, transparent, and post-quantum secure computational integrity

Authors: Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, Michael Riabzev | Venue: ePrint 2018 | Source

Introduced the STARK (Scalable Transparent ARgument of Knowledge) proof system. STARKs achieve: (1) transparency — no trusted setup; the verifier’s randomness is public and the reference string is a random oracle; (2) post-quantum security — security relies only on collision-resistant hash functions; (3) scalability — prover runs in quasi-linear time $O(T\log T)$ for a computation of size $T$; proof size is $O({\log }^{2}T)$. The core technical tool is FRI (Fast Reed-Solomon IOP of Proximity), a protocol for proximity testing to Reed-Solomon codes that yields an efficient polynomial commitment without a trusted setup.

BibTeX

Copy

@Misc{EPRINT:BBHR18,
  author = {Eli {Ben-Sasson} and Iddo Bentov and Yinon Horesh and Michael Riabzev},
  title = {Scalable, transparent, and post-quantum secure computational integrity},
  year = {2018},
  url = {https://eprint.iacr.org/2018/046},
  howpublished = {Cryptology ePrint Archive, Report 2018/046},
}