Paper 2019/1126

Encrypted Distributed Dictionaries

Abstract

End-to-end encrypted databases have been heavily studied in the last two decades. A crucial aspect that previous work has neglected, however, is that real-world databases are distributed in the sense that data is partitioned among a cluster of nodes---as opposed to being stored on a single node. In this work, we initiate the study of encrypted distributed data structures which are end-to-end encrypted variants of distributed data structures; themselves fundamental to the design of distributed databases. In particular, we design and analyze encrypted variants of distributed dictionaries (EDDX), which are an important building block in distributed system design and have applications ranging from content delivery networks to off-chain storage networks for blockchains and smart contracts. We formalize the notion of an encrypted DDX and provide simulation-based security definitions that capture the security properties one would desire from such an object. We propose an EDDX construction that uses a distributed hash table (DHT) as a black box. Interestingly, we show that our construction leaks information probabilistically, where the probability is a function of how well the underlying DHT load balances its data. We also show that in order to be securely used with our construction, a plaintext DHT needs to satisfy a form of "programmability", a property that usually only emerges in the context of cryptographic primitives. To show that these properties are indeed achievable in practice, we study the balancing properties of the Chord DHT---arguably one of the most influential DHT---and show that it is also programmable. Finally, we consider the problem of encrypted DDXs in the context of transient networks, where nodes can be arbitrarily added or removed from the network.