Abstract
A Proof of Sequential Work (PoSW) allows a prover to convince a resourcebounded verifier that the prover invested a substantial amount of sequential time to perform some underlying computation. PoSWs have many applications including timestamping, blockchain design, and universally verifiable CPU benchmarks. Mahmoody, Moran, and Vadhan (ITCS 2013) gave the first construction of a PoSW in the random oracle model though the construction relied on expensive depthrobust graphs. In a recent breakthrough, Cohen and Pietrzak (EUROCRYPT 2018) gave an efficient PoSW construction that does not require expensive depthrobust graphs.
In the classical parallel random oracle model, it is straightforward to argue that any successful PoSW attacker must produce a long ℋsequence and that any malicious party running in sequential time T1 will fail to produce an ℋsequence of length T except with negligible probability. In this paper, we prove that any quantum attacker running in sequential time T1 will fail to produce an ℋsequence except with negligible probability  even if the attacker submits a large batch of quantum queries in each round. The proof is substantially more challenging and highlights the power of Zhandry’s recent compressed oracle technique (CRYPTO 2019). We further extend this result to establish postquantum security of a noninteractive PoSW obtained by applying the FiatShamir transform to Cohen and Pietrzak’s efficient construction (EUROCRYPT 2018).
BibTeX  Entry
@InProceedings{blocki_et_al:LIPIcs.ITC.2021.22,
author = {Blocki, Jeremiah and Lee, Seunghoon and Zhou, Samson},
title = {{On the Security of Proofs of Sequential Work in a PostQuantum World}},
booktitle = {2nd Conference on InformationTheoretic Cryptography (ITC 2021)},
pages = {22:122:27},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771979},
ISSN = {18688969},
year = {2021},
volume = {199},
editor = {Tessaro, Stefano},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14341},
URN = {urn:nbn:de:0030drops143415},
doi = {10.4230/LIPIcs.ITC.2021.22},
annote = {Keywords: Proof of Sequential Work, Parallel Quantum Random Oracle Model, Lower Bounds}
}
Keywords: 

Proof of Sequential Work, Parallel Quantum Random Oracle Model, Lower Bounds 
Collection: 

2nd Conference on InformationTheoretic Cryptography (ITC 2021) 
Issue Date: 

2021 
Date of publication: 

19.07.2021 