Paper 2020/944

Secure Conflict-free Replicated Data Types

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


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.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Distributed SystemsCloud ComputingHomomorphic Encryption
Contact author(s)
b portela @ fct unl pt
bernardolferreira @ gmail com
nuno preguica @ fct unl pt
mbbarbosa @ gmail com
2020-07-31: received
Short URL
Creative Commons Attribution


      author = {Manuel Barbosa and Bernardo Ferreira and João Marques and Bernardo Portela and Nuno Preguiça},
      title = {Secure Conflict-free Replicated Data Types},
      howpublished = {Cryptology ePrint Archive, Paper 2020/944},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.