Paper 2018/889

Bidirectional Asynchronous Ratcheted Key Agreement with Linear Complexity

F. Betül Durak and Serge Vaudenay


Following up mass surveillance and privacy issues, modern secure communication protocols now seek more security such as forward secrecy and post-compromise security. They cannot rely on an assumption such as synchronization, predictable sender/receiver roles, or online availability. Ratcheting was introduced to address forward secrecy and post-compromise security in real-world messaging protocols. At CSF 2016 and CRYPTO 2017, ratcheting was studied either without zero round-trip time (0-RTT) or without bidirectional communication. At CRYPTO 2018, ratcheting with bidirectional communication was done using heavy key-update primitives. At EUROCRYPT 2019, another protocol was proposed. All those protocols use random oracles. Furthermore, exchanging $n$ messages has complexity $O(n^2)$. In this work, we define the bidirectional asynchronous ratcheted key agreement (BARK) with formal security notions. We provide a simple security model and design a secure BARK scheme using no key-update primitives, no random oracle, and with $O(n)$ complexity. It is based on a cryptosystem, a signature scheme, one-time symmetric encryption, and a collision-resistant hash function family. We further show that BARK (even unidirectional) implies public-key cryptography, meaning that it cannot solely rely on symmetric cryptography.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. IWSEC 2019
secure communicationpost-compromise securityratchet
Contact author(s)
serge vaudenay @ epfl ch
durakfbetul @ gmail com
2019-09-11: last of 5 revisions
2018-09-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {F.  Betül Durak and Serge Vaudenay},
      title = {Bidirectional Asynchronous Ratcheted Key Agreement with Linear Complexity},
      howpublished = {Cryptology ePrint Archive, Paper 2018/889},
      year = {2018},
      doi = {10.1007/978-3-030-26834-3_20},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.