  A Proof of Sequential Work (PoSW) allows a prover to convince a
resource-bounded verifier that the prover invested a substantial amount of
sequential time to perform some underlying computation. PoSWs have many
applications including time-stamping, 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 depth-robust graphs. In a recent breakthrough, Cohen and
Pietrzak (EUROCRYPT 2018) gave an efficient PoSW construction that does not
require expensive depth-robust graphs.
  In the classical parallel random oracle model, it is straightforward to argue
that any successful PoSW attacker must produce a long $\mathcal{H}$-sequence
and that any malicious party running in sequential time $T-1$ will fail to
produce an $\mathcal{H}$-sequence of length $T$ except with negligible
probability. In this paper, we prove that any quantum attacker running in
sequential time $T-1$ will fail to produce an $\mathcal{H}$-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 post-quantum security of a
non-interactive PoSW obtained by applying the Fiat-Shamir transform to Cohen
and Pietrzak's efficient construction (EUROCRYPT 2018).

Cryptography and Security