Paper 2020/617
New Techniques in Replica Encodings with Client Setup
Rachit Garg, 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 finedgrained 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 finegrained 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 ``sequencethenswitch''. 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.
Metadata
 Available format(s)
 Publication info
 A minor revision of an IACR publication in TCC 2020
 Keywords
 replica encodingreplicated storageproof of replication
 Contact author(s)

rachit0596 @ gmail com
georgelu97 @ gmail com
bwaters @ cs utexas edu  History
 20200928: last of 2 revisions
 20200526: received
 See all versions
 Short URL
 https://ia.cr/2020/617
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/617, author = {Rachit Garg and George Lu and Brent Waters}, title = {New Techniques in Replica Encodings with Client Setup}, howpublished = {Cryptology ePrint Archive, Paper 2020/617}, year = {2020}, note = {\url{https://eprint.iacr.org/2020/617}}, url = {https://eprint.iacr.org/2020/617} }