International Association
for Cryptologic Research

Secure cryptographic storage is one of the most important issues that both businesses and end-users take into account before moving their data to either centralized clouds or blockchain-based decen- tralized storage marketplace. Recent work [4 ] formalizes the notion of Proof of Storage-Time (PoSt) which enables storage servers to demonstrate non-interactive continuous availability of outsourced data in a publicly verifiable way. The work also proposes a stateful compact PoSt construction, while leaving the stateless and transpar- ent PoSt with support for proof of replication as an open problem. In this paper, we consider this problem by constructing a proof system that enables a server to simultaneously demonstrate con- tinuous availability and dedication of unique storage resources for encoded replicas of a data file in a stateless and publicly verifi- able way. We first formalize Proof of Replication-Time (PoRt) by extending PoSt formal definition and security model to provide support for replications. Then, we provide a concrete instantia- tion of PoRt by designing a lightweight replica encoding algorithm where replicas’ failures are efficiently located through an efficient comparison-based verification process, after the data deposit period ends. PoRt’s proofs are aggregatable: the prover can take several sequentially generated proofs and efficiently aggregate them into a single, succinct proof. The protocol is also stateless in the sense that the client can efficiently extend the deposit period by incre- mentally updating the tags and without requiring to download the outsourced file replicas. We also demonstrate feasible extensions of PoRt to support dynamic data updates, and be transparent to enable its direct use in decentralized storage networks, a property not supported in previous proposals. Finally, PoRt’s verification cost is independent of both outsourced file size and deposit length.