Encrypted key-value stores (Q2152022)

Key-value stores (KVS) are storage systems for storing and maintaining associative arrays a.k.a. hash tables or dictionaries. Since these storage systems are nowadays vital for a lot of Internet-based commercial services, they must provide fast read/write access, considerable scalability to accommodate a huge amount of data, robustness as well as safe and secure transaction capability. Therefore the use of distributed NoSQL-databases is the obvious choice for key-value storage implementation. Due to the sensitive nature of the data stored, the design of reliably secure storage systems is of the essence. Mere encryption/decryption of data being processed does no longer meet the standard user requirements, but end-to-end encryption where data is kept encrypted at all times comes to the rescue and the paper explores this encryption scheme in distributed KVSs. It develops formal security definitions to capture desired properties of a concrete encrypted KVS (EKVS) that can be derived any unencrypted KVS. Thus the authors claim to present the first formally analyzed end-to-end encrypted key-value storage system that only leaks operation equality of search keys in case read-your-writes consistency is guaranteed. To substantiate this claim, the reader is given a quick tour of theoretical key-value store systems, both unencrypted and then encrypted, along with considerations of probability-based key distributions and the associated security issues. These concepts are elaborated on in single-and multi-user settings resulting in a standard EKVS scheme. The interested reader may acquire more detailed information from the sources listed in the thorough reference section of the paper and may even find the full version of the paper at hand referred to in some theorems and corollaries of the presentation. For the entire collection see [Zbl 1490.94002].