Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper establishes a new framework for constructing Proofs of Space (PoS) that combines derandomization and cryptographic assumptions, addressing the limitations of existing PoS protocols which are primarily secure only in the random oracle model. The authors demonstrate that non-trivial PoS can be derived from assumptions about the hardness of exponential-size nondeterministic circuits and the existence of collision-resistant hash functions. Additionally, they achieve nearly optimal parameters and interaction patterns for PoS by leveraging these assumptions alongside SNARGs for P, significantly advancing the theoretical foundation of PoS protocols.
Non-trivial Proofs of Space can be constructed from fundamental complexity assumptions, challenging the reliance on random oracles.
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) $\mathsf{E}=\mathsf{DTIME[2^{O(n)}]}$ is hard for exponential-size nondeterministic circuits (an assumption introduced to show $\mathsf{AM}=\mathsf{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 $\mathsf{P}$.