Paper 2023/1418

Short Concurrent Covert Authenticated Key Exchange (Short cAKE)

Karim Eldafrawy, SRI International
Nicholas Genise, Duality Technologies
Stanislaw Jarecki, University of California, Irvine

Von Ahn, Hopper and Langford introduced the notion of steganographic a.k.a. covert computation, to capture distributed computation where the attackers must not be able to distinguish honest parties from entities emitting random bitstrings. This indistinguishability should hold for the duration of the computation except for what is revealed by the intended outputs of the computed functionality. An important case of covert computation is mutually authenticated key exchange, a.k.a. mutual authentication. Mutual authentication is a fundamental primitive often preceding more complex secure protocols used for distributed computation. However, standard authentication implementations are not covert, which allows a network adversary to target or block parties who engage in authentication. Therefore, mutual authentication is one of the premier use cases of covert computation and has numerous real-world applications, e.g., for enabling authentication over steganographic channels in a network controlled by a discriminatory entity. We improve on the state of the art in covert authentication by presenting a protocol that retains covertness and security under concurrent composition, has minimal message complexity, and reduces protocol bandwidth by an order of magnitude compared to previous constructions. To model the security of our scheme we develop a UC model which captures standard features of secure mutual authentication but extends them to covertness. We prove our construction secure in this UC model. We also provide a proof-of-concept implementation of our scheme.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in ASIACRYPT 2023
anonymitysteganographycovert protocolssecure computationuniversal composabilityauthenticated key exchange
Contact author(s)
eldefrawy @ gmail com
ngenise @ dualitytech com
stanislawjarecki @ gmail com
2023-09-24: approved
2023-09-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Karim Eldafrawy and Nicholas Genise and Stanislaw Jarecki},
      title = {Short Concurrent Covert Authenticated Key Exchange (Short cAKE)},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1418},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.