Cryptology ePrint Archive: Report 2020/617

New Techniques in Replica Encodings with Client Setup

Rachit Garg and George Lu and Brent Waters

Abstract: A proof of replication system is a cryptographic primitive that allows a server (or group of servers) to prove to a client that it is dedicated to storing multiple copies or replicas of a file. Until recently, all such protocols required fined-grained timing assumptions on the amount of time it takes for a server to produce such replicas.

Damgård, Ganesh, and Orlandi (CRYPTO' 19) proposed a novel notion that we will call proof of replication with client setup. Here, a client first operates with secret coins to generate the replicas for a file. Such systems do not inherently have to require fine-grained timing assumptions. At the core of their solution to building proofs of replication with client setup is an abstraction called replica encodings. Briefly, these comprise a private coin scheme where a client algorithm given a file $m$ can produce an encoding $\sigma$. The encodings have the property that, given any encoding $\sigma$, one can decode and retrieve the original file $m$. Secondly, if a server has significantly less than $n \cdot |m|$ bit of storage, it cannot reproduce $n$ encodings. The authors give a construction of encodings from ideal permutations and trapdoor functions.

In this work, we make three central contributions: 1) Our first contribution is that we discover and demonstrate that the security argument put forth by DGO19 is fundamentally flawed. Briefly, the security argument makes assumptions on the attacker's storage behavior that does not capture general attacker strategies. We demonstrate this issue by constructing a trapdoor permutation which is secure assuming indistinguishability obfuscation, serves as a counterexample to their claim (for the parameterization stated). 2) In our second contribution we show that the DGO19 construction is actually secure in the ideal permutation model from any trapdoor permutation when parameterized correctly. In particular, when the number of rounds in the construction is equal to $\lambda \cdot n \cdot b$ where $\lambda$ is the security parameter, $n$ is the number of replicas and $b$ is the number of blocks. To do so we build up a proof approach from the ground up that accounts for general attacker storage behavior where we create an analysis technique that we call ``sequence-then-switch''. 3) Finally, we show a new construction that is provably secure in the random oracle (or random function) model. Thus requiring less structure on the ideal function.

Category / Keywords: replica encoding, replicated storage, proof of replication

Date: received 25 May 2020, last revised 26 May 2020

Contact author: rachit0596 at gmail com, georgelu97@gmail com, bwaters@cs utexas edu

Available format(s): PDF | BibTeX Citation

Version: 20200526:214033 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]