Cryptology ePrint Archive: Report 2018/889

Bidirectional Asynchronous Ratcheted Key Agreement with Linear Complexity

F. Betül Durak and Serge Vaudenay

Abstract: 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.

Category / Keywords: cryptographic protocols / secure communication, post-compromise security, ratchet

Original Publication (with minor differences): IWSEC 2019

Date: received 21 Sep 2018, last revised 11 Sep 2019

Contact author: serge vaudenay at epfl ch, durakfbetul@gmail com

Available format(s): PDF | BibTeX Citation

Version: 20190911:091205 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]