Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2010.11658 · Lecture notes in computer science

On the Compressed-Oracle Technique, and Post-Quantum Security of Proofs of Sequential Work

Kai-Min Chung, Serge Fehr, Yu‐Hsuan Huang, Tai-Ning Liao

Published Jan 1, 2021• 57 citations
arXivHTMLPDF
DOI
10.1007/978-3-030-77886-6_21

Related papers

Mind the Bad Norms: Revisiting Compressed Oracle-Based Quantum Indistinguishability Proofs

Ritam Bhaumik, Benoît Cogliati, Jordan Ethan +1 more

Lecture notes in computer science•Dec 7, 2024•7 citations

Quantum Security Proofs Using Semi-classical Oracles

Andris Ambainis, Mike Hamburg, Dominique Unruh

Lecture notes in computer science•Jan 1, 2019•143 citations

Encryption Schemes Using Random Oracles: From Classical to Post-Quantum Security

Juliane Krämer, Patrick Struck

Lecture notes in computer science•Jan 1, 2020•9 citations

Tighter Proofs of CCA Security in the Quantum Random Oracle Model

Nina Bindel, Mike Hamburg, Kathrin Hövelmanns +2 more

Lecture notes in computer science•Jan 1, 2019•110 citations

On the Security of Proofs of Sequential Work in a Post-Quantum World

Jeremiah Blocki, Seunghoon Lee, Samson Zhou

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).

arXiv:2006.10972•Leibniz international proceedings in informatics•Jun 19, 2020•17 citations

How to Prove Post-quantum Security for Succinct Non-interactive Reductions

Alessandro Chiesa, Zijing Di, Zihan Hu +1 more

Lecture notes in computer science•Jan 1, 2026•1 citation
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 H\mathcal{H}H-sequence and that any malicious party running in sequential time T−1T-1T−1 will fail to produce an H\mathcal{H}H-sequence of length TTT except with negligible probability. In this paper, we prove that any quantum attacker running in sequential time T−1T-1T−1 will fail to produce an H\mathcal{H}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).