A Complexity-Theoretic Approach to Proofs of Space

Computer Science > Cryptography and Security [Submitted on 10 Aug 2026] A Complexity-Theoretic Approach to Proofs of Space Marshall Ball, Jiaxin Guan A Proof of Space, PoS, as introduced by Dziembowski et al. [CRYPTO'15], is a two-phase protocol that enables a Prover to convince an efficient Verifier that it has allocated a large amount of persistent memory to storing some information. To our knowledge, all existing PoS protocols are only known to be secure in the random oracle model (or under ad hoc assumptions about cryptographic assumptions). We provide an elementary framework for constructing PoS from a combination of derandomization assumptions and cryptographic assumptions. We provide a few simple instantiations of the framework. We show that non-trivial PoS follow from (a) E=DTIME[ 2 O(n) ] is hard for exponential-size nondeterministic circuits (an assumption introduced to show AM=NP ), and (b) collision-resistant hash functions. We also show that PoS with nearly optimal parameters and interaction pattern follows from assumption (a) above and (c) SNARGs for P . Subjects: Cryptography and Security (cs.CR); Computational Complexity (cs.CC) Cite as: arXiv:2608.08993 [cs.CR]   (or arXiv:2608.08993v1 [cs.CR] for this version)   https://doi.org/10.48550/arXiv.2608.08993 Focus to learn more Submission history From: Jiaxin Guan [view email] [v1] Mon, 10 Aug 2026 01:28:01 UTC (6,908 KB) Access Paper: view license Current browse context: cs.CR < prev   |   next > new | recent | 2026-08 Change to browse by: cs cs.CC References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)