International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Proofs of Work From Worst-Case Assumptions

Authors:
Marshall Ball
Alon Rosen
Manuel Sabin
Prashant Nalini Vasudevan
Download:
DOI: 10.1007/978-3-319-96884-1_26
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2018
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.
Video from CRYPTO 2018
Video provided under Creative Commons / CC BY 3.0
BibTeX
@inproceedings{crypto-2018-28859,
  title={Proofs of Work From Worst-Case Assumptions},
  booktitle={Advances in Cryptology – CRYPTO 2018},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  volume={10991},
  pages={789-819},
  doi={10.1007/978-3-319-96884-1_26},
  author={Marshall Ball and Alon Rosen and Manuel Sabin and Prashant Nalini Vasudevan},
  year=2018
}