Paper 2018/559

Proofs of Work from Worst-Case Assumptions

Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan

Abstract

We give Proofs of Work (PoWs) whose hardness is based on well-studied worst-case assumptions from fine-grained complexity theory. This extends the work of (Ball et al., STOC '17), that presents PoWs that are based on the Orthogonal Vectors, 3SUM, and All-Pairs Shortest Path problems. These, however, were presented as a `proof of concept' of provably secure PoWs and did not fully meet the requirements of a conventional PoW: namely, it was not shown that multiple proofs could not be generated faster than generating each individually. We use the considerable algebraic structure of these PoWs to prove that this non-amortizability of multiple proofs does in fact hold and further show that the PoWs' structure can be exploited in ways previous heuristic PoWs could not. This creates full PoWs that are provably hard from worst-case assumptions (previously, PoWs were either only based on heuristic assumptions or on much stronger cryptographic assumptions (Bitansky et al., ITCS '16)) while still retaining significant structure to enable extra properties of our PoWs. Namely, we show that the PoWs of (Ball et al, STOC '17) can be modified to have much faster verification time, can be proved in zero knowledge, and more. Finally, as our PoWs are based on evaluating low-degree polynomials originating from average-case fine-grained complexity, we prove an average-case direct sum theorem for the problem of evaluating these polynomials, which may be of independent interest. For our context, this implies the required non-amortizability of our PoWs.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in CRYPTO 2018
Keywords
Proofs of WorkFine-GrainedZero-KnowledgeDirect Sum TheoremNon-Amortizability
Contact author(s)
msabin @ berkeley edu
marshall @ cs columbia edu
alon rosen @ idc ac il
prashvas @ mit edu
History
2018-06-04: received
Short URL
https://ia.cr/2018/559
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/559,
      author = {Marshall Ball and Alon Rosen and Manuel Sabin and Prashant Nalini Vasudevan},
      title = {Proofs of Work from Worst-Case Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2018/559},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/559}},
      url = {https://eprint.iacr.org/2018/559}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.