Cryptology ePrint Archive: Report 2020/944

Secure Conflict-free Replicated Data Types

Manuel Barbosa and Bernardo Ferreira and João Marques and Bernardo Portela and Nuno Preguiça

Abstract: Conflict-free Replicated Data Types (CRDTs) are abstract data types that support developers when designing and reasoning about distributed systems with eventual consistency guarantees. In their core they solve the problem of how to deal with concurrent operations, in a way that is transparent for developers. However in the real world, distributed systems also suffer from other relevant problems, including security and privacy issues and especially when participants can be untrusted.

In this paper we present the first formal cryptographic treatment of CRDTs, as well as proposals for secure implementations. We start by presenting a security notion that is compatible with standard definitions in cryptography. We then describe new privacy-preserving CRDT protocols that can be used to help secure distributed cloud-backed applications, including NoSQL geo-replicated databases. Our proposals are based on standard CRDTs, such as sets and counters, augmented with cryptographic mechanisms that allow operations to be performed on encrypted data.

Our proposals are accompanied with formal security proofs and implement and integrate them in AntidoteDB, a geo-replicated NoSQL database that leverages CRDTs for its operations. Experimental evaluations based on the Danish Shared Medication Record dataset (FMK) exhibit the tradeoffs that our different proposals make and show that they are ready to be used in practical applications.

Category / Keywords: cryptographic protocols / Distributed Systems, Cloud Computing, Homomorphic Encryption

Date: received 31 Jul 2020

Contact author: b portela at fct unl pt, bernardolferreira@gmail com, nuno preguica@fct unl pt, mbbarbosa@gmail com

Available format(s): PDF | BibTeX Citation

Version: 20200731:184637 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]