**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: **ia.cr/2020/617

[ Cryptology ePrint archive ]