Paper 2020/1426
Linear-Time Arguments with Sublinear Verification from Tensor Codes
Jonathan Bootle, Alessandro Chiesa, and Jens Groth
Abstract
Minimizing the computational cost of the prover is a central goal in the area of succinct arguments. In particular, it remains a challenging open problem to construct a succinct argument where the prover runs in linear time and the verifier runs in polylogarithmic time.
We make progress towards this goal by presenting a new linear-time probabilistic proof. For any fixed
Note: Added full version.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- A major revision of an IACR publication in TCC 2020
- Keywords
- interactive oracle proofstensor codessuccinct arguments
- Contact author(s)
-
jbt @ zurich ibm com
alexch @ berkeley edu - History
- 2020-12-28: revised
- 2020-11-15: received
- See all versions
- Short URL
- https://ia.cr/2020/1426
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2020/1426, author = {Jonathan Bootle and Alessandro Chiesa and Jens Groth}, title = {Linear-Time Arguments with Sublinear Verification from Tensor Codes}, howpublished = {Cryptology {ePrint} Archive, Paper 2020/1426}, year = {2020}, url = {https://eprint.iacr.org/2020/1426} }