Bidirectional Asynchronous Ratcheted Key Agreement with Linear Complexity

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(n2). 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.


Published in:
Advances in Information and Computer Security 14th International Workshop on Security, IWSEC 2019, Tokyo, Japan, August 28–30, 2019. Proceedings, Springer
Presented at:
14th International Workshop on Security - IWSEC 2019, Tokyo, Japan, August 28–30, 2019
Year:
Jul 24 2019
Publisher:
Nuttapong Attrapadung, Takeshi Yagi
ISBN:
978-3-030-26834-3
Additional link:
Laboratories:




 Record created 2019-09-30, last modified 2019-10-01

Fulltext:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)