Document Open Access Logo

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

Authors Jeremiah Blocki , Seunghoon Lee , Samson Zhou

PDF
Thumbnail PDF

File

LIPIcs.ITC.2021.22.pdf
  • Filesize: 0.96 MB
  • 27 pages

Document Identifiers

Author Details

Jeremiah Blocki
  • Department of Computer Science, Purdue University, West Lafayette, IN, USA
Seunghoon Lee
  • Department of Computer Science, Purdue University, West Lafayette, IN, USA
Samson Zhou
  • School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, USA

Funding

  • Blocki, Jeremiah: Research supported in part by NSF CNS-1755708 and NSF CNS-1931443.
  • Lee, Seunghoon: Research supported in part by NSF Award CNS-1755708 and by the Center for Science of Information at Purdue University (NSF CCF-0939370).

Acknowledgements

The authors wish to thank Fang Song (shepherd) and other anonymous reviewers for comments which improved the presentation of this paper.

Cite AsGet BibTex

Jeremiah Blocki, Seunghoon Lee, and Samson Zhou. On the Security of Proofs of Sequential Work in a Post-Quantum World. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 199, pp. 22:1-22:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ITC.2021.22

Abstract

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 ℋ-sequence and that any malicious party running in sequential time T-1 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 T-1 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 post-quantum security of a non-interactive PoSW obtained by applying the Fiat-Shamir transform to Cohen and Pietrzak’s efficient construction (EUROCRYPT 2018).

Subject Classification

ACM Subject Classification
  • Security and privacy → Hash functions and message authentication codes
  • Security and privacy → Information-theoretic techniques
Keywords
  • Proof of Sequential Work
  • Parallel Quantum Random Oracle Model
  • Lower Bounds

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Scott Aaronson. Quantum copy-protection and quantum money. In Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC, pages 229-242, 2009. Google Scholar
  2. Scott Aaronson and Paul Christiano. Quantum money from hidden subspaces. Theory of Computing, 9:349-401, 2013. Google Scholar
  3. Hamza Abusalah, Chethan Kamath, Karen Klein, Krzysztof Pietrzak, and Michael Walter. Reversible proofs of sequential work. In Advances in Cryptology - EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings, Part II, pages 277-291, 2019. Google Scholar
  4. Gorjan Alagic, Christian Majenz, Alexander Russell, and Fang Song. Quantum-access-secure message authentication via blind-unforgeability. In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020, Part III, volume 12107 of LNCS, pages 788-817. Springer, Heidelberg, May 2020. URL: https://doi.org/10.1007/978-3-030-45727-3_27.
  5. Joël Alwen and Jeremiah Blocki. Efficiently computing data-independent memory-hard functions. In Matthew Robshaw and Jonathan Katz, editors, CRYPTO 2016, Part II, volume 9815 of LNCS, pages 241-271. Springer, Heidelberg, August 2016. URL: https://doi.org/10.1007/978-3-662-53008-5_9.
  6. Joël Alwen, Jeremiah Blocki, and Krzysztof Pietrzak. Depth-robust graphs and their cumulative memory complexity. In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, EUROCRYPT 2017, Part III, volume 10212 of LNCS, pages 3-32. Springer, Heidelberg, April / May 2017. URL: https://doi.org/10.1007/978-3-319-56617-7_1.
  7. Joël Alwen, Jeremiah Blocki, and Krzysztof Pietrzak. Sustained space complexity. In Jesper Buus Nielsen and Vincent Rijmen, editors, EUROCRYPT 2018, Part II, volume 10821 of LNCS, pages 99-130. Springer, Heidelberg, April / May 2018. URL: https://doi.org/10.1007/978-3-319-78375-8_4.
  8. Joël Alwen and Vladimir Serbinenko. High parallel complexity graphs and memory-hard functions. In Rocco A. Servedio and Ronitt Rubinfeld, editors, 47th ACM STOC, pages 595-603. ACM Press, June 2015. URL: https://doi.org/10.1145/2746539.2746622.
  9. Andris Ambainis, Mike Hamburg, and Dominique Unruh. Quantum security proofs using semi-classical oracles. In Alexandra Boldyreva and Daniele Micciancio, editors, CRYPTO 2019, Part II, volume 11693 of LNCS, pages 269-295. Springer, Heidelberg, August 2019. URL: https://doi.org/10.1007/978-3-030-26951-7_10.
  10. Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh V. Vazirani. Strengths and weaknesses of quantum computing. SIAM J. Comput., 26(5):1510-1523, 1997. Google Scholar
  11. Nina Bindel, Mike Hamburg, Kathrin Hövelmanns, Andreas Hülsing, and Edoardo Persichetti. Tighter proofs of CCA security in the quantum random oracle model. In Dennis Hofheinz and Alon Rosen, editors, TCC 2019, Part II, volume 11892 of LNCS, pages 61-90. Springer, Heidelberg, December 2019. URL: https://doi.org/10.1007/978-3-030-36033-7_3.
  12. Jeremiah Blocki, Benjamin Harsha, Siteng Kang, Seunghoon Lee, Lu Xing, and Samson Zhou. Data-independent memory hard functions: New attacks and stronger constructions. In Advances in Cryptology - CRYPTO - 39th Annual International Cryptology Conference, Proceedings, Part II, pages 573-607, 2019. Google Scholar
  13. Jeremiah Blocki, Ling Ren, and Samson Zhou. Bandwidth-hard functions: Reductions and lower bounds. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS, pages 1820-1836, 2018. Google Scholar
  14. Jeremiah Blocki and Samson Zhou. On the depth-robustness and cumulative pebbling cost of argon2i. In Theory of Cryptography - 15th International Conference, TCC Proceedings, Part I, pages 445-465, 2017. Google Scholar
  15. Dan Boneh, Joseph Bonneau, Benedikt Bünz, and Ben Fisch. Verifiable delay functions. In Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, Proceedings, Part I, pages 757-788, 2018. Google Scholar
  16. Dan Boneh, Özgür Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, and Mark Zhandry. Random oracles in a quantum world. In Dong Hoon Lee and Xiaoyun Wang, editors, ASIACRYPT 2011, volume 7073 of LNCS, pages 41-69. Springer, Heidelberg, December 2011. URL: https://doi.org/10.1007/978-3-642-25385-0_3.
  17. Dan Boneh and Mark Zhandry. Secure signatures and chosen ciphertext security in a quantum computing world. In Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference. Proceedings, Part II, pages 361-379, 2013. Google Scholar
  18. Gilles Brassard, Peter Hoyer, Kassem Kalach, Marc Kaplan, Sophie Laplante, and Louis Salvail. Merkle puzzles in a quantum world. In Advances in Cryptology - CRYPTO 2011. Proceedings, pages 391-410, 2011. Google Scholar
  19. Gilles Brassard and Louis Salvail. Quantum merkle puzzles. In Second International Conference on Quantum, Nano, and Micro Technologies, ICQNM, pages 76-79, 2008. Google Scholar
  20. Ethan Cecchetti, Ben Fisch, Ian Miers, and Ari Juels. PIEs: Public incompressible encodings for decentralized storage. In Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, editors, ACM CCS 2019, pages 1351-1367. ACM Press, November 2019. URL: https://doi.org/10.1145/3319535.3354231.
  21. Alessandro Chiesa, Peter Manohar, and Nicholas Spooner. Succinct arguments in the quantum random oracle model. In Dennis Hofheinz and Alon Rosen, editors, TCC 2019, Part II, volume 11892 of LNCS, pages 1-29. Springer, Heidelberg, December 2019. URL: https://doi.org/10.1007/978-3-030-36033-7_1.
  22. Kai-Min Chung, Serge Fehr, Yu-Hsuan Huang, and Tai-Ning Liao. On the compressed-oracle technique, and post-quantum security of proofs of sequential work, 2020. To appear at EUROCRYPT 2021. URL: http://arxiv.org/abs/2010.11658.
  23. Bram Cohen and Krzysztof Pietrzak. Simple proofs of sequential work. In Jesper Buus Nielsen and Vincent Rijmen, editors, EUROCRYPT 2018, Part II, volume 10821 of LNCS, pages 451-467. Springer, Heidelberg, April / May 2018. URL: https://doi.org/10.1007/978-3-319-78375-8_15.
  24. Jelle Don, Serge Fehr, Christian Majenz, and Christian Schaffner. Security of the Fiat-Shamir transformation in the quantum random-oracle model. In Alexandra Boldyreva and Daniele Micciancio, editors, CRYPTO 2019, Part II, volume 11693 of LNCS, pages 356-383. Springer, Heidelberg, August 2019. URL: https://doi.org/10.1007/978-3-030-26951-7_13.
  25. Jelle Don, Serge Fehr, Christian Majenz, and Christian Schaffner. Online-extractability in the quantum random-oracle model, 2021. URL: http://arxiv.org/abs/2103.03085.
  26. Nico Döttling, Russell W. F. Lai, and Giulio Malavolta. Incremental proofs of sequential work. In Advances in Cryptology - EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings, Part II, pages 292-323, 2019. Google Scholar
  27. Stefan Dziembowski, Sebastian Faust, Vladimir Kolmogorov, and Krzysztof Pietrzak. Proofs of space. In Rosario Gennaro and Matthew J. B. Robshaw, editors, CRYPTO 2015, Part II, volume 9216 of LNCS, pages 585-605. Springer, Heidelberg, August 2015. URL: https://doi.org/10.1007/978-3-662-48000-7_29.
  28. Amos Fiat and Adi Shamir. How to prove yourself: Practical solutions to identification and signature problems. In Andrew M. Odlyzko, editor, CRYPTO'86, volume 263 of LNCS, pages 186-194. Springer, Heidelberg, August 1987. URL: https://doi.org/10.1007/3-540-47721-7_12.
  29. Ben Fisch. Tight proofs of space and replication. In Yuval Ishai and Vincent Rijmen, editors, EUROCRYPT 2019, Part II, volume 11477 of LNCS, pages 324-348. Springer, Heidelberg, May 2019. URL: https://doi.org/10.1007/978-3-030-17656-3_12.
  30. Lov K. Grover and J. Radhakrishnan. Quantum search for multiple items using parallel queries. arXiv: Quantum Physics, 2004. Google Scholar
  31. Yassine Hamoudi and Frédéric Magniez. Quantum time-space tradeoff for finding multiple collision pairs, 2020. URL: http://arxiv.org/abs/2002.08944.
  32. Stacey Jeffery, Frederic Magniez, and Ronald de Wolf. Optimal parallel quantum query algorithms. In Andreas S. Schulz and Dorothea Wagner, editors, Algorithms - ESA 2014, pages 592-604, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg. Google Scholar
  33. Eike Kiltz, Vadim Lyubashevsky, and Christian Schaffner. A concrete treatment of Fiat-Shamir signatures in the quantum random-oracle model. In Jesper Buus Nielsen and Vincent Rijmen, editors, EUROCRYPT 2018, Part III, volume 10822 of LNCS, pages 552-586. Springer, Heidelberg, April / May 2018. URL: https://doi.org/10.1007/978-3-319-78372-7_18.
  34. Qipeng Liu and Mark Zhandry. On finding quantum multi-collisions. In Yuval Ishai and Vincent Rijmen, editors, EUROCRYPT 2019, Part III, volume 11478 of LNCS, pages 189-218. Springer, Heidelberg, May 2019. URL: https://doi.org/10.1007/978-3-030-17659-4_7.
  35. Qipeng Liu and Mark Zhandry. Revisiting post-quantum Fiat-Shamir. In Alexandra Boldyreva and Daniele Micciancio, editors, CRYPTO 2019, Part II, volume 11693 of LNCS, pages 326-355. Springer, Heidelberg, August 2019. URL: https://doi.org/10.1007/978-3-030-26951-7_12.
  36. Mohammad Mahmoody, Tal Moran, and Salil P. Vadhan. Time-lock puzzles in the random oracle model. In Advances in Cryptology - CRYPTO. Proceedings, pages 39-50, 2011. Google Scholar
  37. Mohammad Mahmoody, Tal Moran, and Salil P. Vadhan. Publicly verifiable proofs of sequential work. In Robert D. Kleinberg, editor, ITCS 2013, pages 373-388. ACM, January 2013. URL: https://doi.org/10.1145/2422436.2422479.
  38. Krzysztof Pietrzak. Proofs of catalytic space. In Avrim Blum, editor, ITCS 2019, volume 124, pages 59:1-59:25. LIPIcs, January 2019. URL: https://doi.org/10.4230/LIPIcs.ITCS.2019.59.
  39. Dominique Unruh. Revocable quantum timed-release encryption. J. ACM, 62(6), December 2015. URL: https://doi.org/10.1145/2817206.
  40. Christof Zalka. Grover’s quantum searching algorithm is optimal. Phys. Rev. A, 60:2746-2751, October 1999. URL: https://doi.org/10.1103/PhysRevA.60.2746.
  41. Mark Zhandry. How to construct quantum random functions. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 679-687, 2012. Google Scholar
  42. Mark Zhandry. How to record quantum queries, and applications to quantum indifferentiability. In Alexandra Boldyreva and Daniele Micciancio, editors, CRYPTO 2019, Part II, volume 11693 of LNCS, pages 239-268. Springer, Heidelberg, August 2019. URL: https://doi.org/10.1007/978-3-030-26951-7_9.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact