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)
- 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
-
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}, url = {https://eprint.iacr.org/2018/559} }