International Association for Cryptologic Research

International Association
for Cryptologic Research


Symmetric Key Exchange with Full Forward Security and Robust Synchronization

Colin Boyd , NTNU, Norwegian University of Science and Technology
Gareth T. Davies , Bergische Universität Wuppertal
Bor de Kock , NTNU, Norwegian University of Science and Technology
Kai Gellert , Bergische Universität Wuppertal
Tibor Jager , Bergische Universität Wuppertal
Lise Millerjord , NTNU, Norwegian University of Science and Technology
DOI: 10.1007/978-3-030-92068-5_23
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2021
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.
Video from ASIACRYPT 2021
  title={Symmetric Key Exchange with Full Forward Security and Robust Synchronization},
  author={Colin Boyd and Gareth T. Davies and Bor de Kock and Kai Gellert and Tibor Jager and Lise Millerjord},