Cryptology ePrint Archive: Report 2018/889

Bidirectional Asynchronous Ratcheted Key Agreement without Key-Update Primitives

F. Betül Durak and Serge Vaudenay

Abstract: Following up mass surveillance and privacy issues, modern secure communication protocols now seek for more security such as forward secrecy and post-compromise security. They cannot rely on any assumption such as synchronization, predictable sender/receiver roles, or online availability. At EUROCRYPT 2017 and 2018, key agreement with forward secrecy and zero round-trip time (0-RTT) were studied. 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 0-RTT or without bidirectional communication. At CRYPTO 2018, it was done using key-update primitives, which involve hierarchical identity-based encryption (HIBE).

In this work, we define the bidirectional asynchronous ratcheted key agreement (BARK) with formal security notions. We provide a simple security model with a pragmatic approach and design the first secure BARK scheme not using key-update primitives. Our notion offers forward secrecy and post-compromise security. It is asynchronous, with random roles, and 0-RTT. It is based on a cryptosystem, a signature scheme, and a collision-resistant hash function family without key-update primitives or random oracles. 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

Date: received 21 Sep 2018, last revised 29 Nov 2018

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

Available format(s): PDF | BibTeX Citation

Note: We received outstanding comments by colleagues. We also saw some follow up papers. Changes: a bug in the correctness definition and in the RECOVER security definition; cosmetic details; proofs should be clearer; comparison with two new papers; new section to address coin reveals; some sections were dropped.

Version: 20181129:120834 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]