Paper 2021/702

Symmetric Key Exchange with Full Forward Security and Robust Synchronization

Colin Boyd, Gareth T. Davies, Bor de Kock, Kai Gellert, Tibor Jager, and Lise Millerjord

Abstract

We construct lightweight authenticated key exchange protocols based on pre-shared keys, which achieve full forward security and rely only on simple and efficient symmetric-key primitives. All of our protocols have rigorous security proofs in a strong security model, all have low communication complexity, and are particularly suitable for resource-constrained devices. We describe three protocols that apply linear key evolution to provide different performance and security properties. Correctness in parallel and concurrent protocol sessions is difficult to achieve for linearly key-evolving protocols, emphasizing the need for assurance of availability alongside the usual confidentiality and authentication security goals. We introduce synchronization robustness as a new formal security goal, which essentially guarantees that parties can re-synchronize efficiently. All of our new protocols achieve this property. Since protocols based on linear key evolution cannot guarantee that all concurrently initiated sessions successfully derive a key, we also propose two constructions with non-linear key evolution based on puncturable PRFs. These are instantiable from standard hash functions and require O( C log(|CTR|)) memory, where C is the number of concurrent sessions and |CTR| is an upper bound on the total number of sessions per party. These are the first protocols to simultaneously achieve full forward security, synchronization robustness, and concurrent correctness.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in Asiacrypt 2021
DOI
10.1007/978-3-030-92068-5_23
Contact author(s)
davies @ uni-wuppertal de
History
2021-12-02: revised
2021-05-28: received
See all versions
Short URL
https://ia.cr/2021/702
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/702,
      author = {Colin Boyd and Gareth T.  Davies and Bor de Kock and Kai Gellert and Tibor Jager and Lise Millerjord},
      title = {Symmetric Key Exchange with Full Forward Security and Robust Synchronization},
      howpublished = {Cryptology ePrint Archive, Paper 2021/702},
      year = {2021},
      doi = {10.1007/978-3-030-92068-5_23},
      note = {\url{https://eprint.iacr.org/2021/702}},
      url = {https://eprint.iacr.org/2021/702}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.