Paper 2025/2015
Proving Authenticated Key Exchange via Memory-Efficient Reductions
, University of Kassel, University of KasselAbstract
We initiate the study of memory efficiency in proving the security of authenticated key exchange (AKE) protocols: We first revise the security model for AKE protocols in order to prove their security in a memory-efficient manner without compromising its capability of capturing usual attacks. We formally show that security in our model implies previous ones, and thus our model captures the same security as before. After that we propose a generic construction of AKE from key encapsulation mechanisms (KEMs) and digital signature schemes, motivated by the signed Diffie-Hellman protocol. Under the multi-user security of the signature scheme and (relatively weak) oneway-security against plaintext checking attacks of the KEM, our generic construction is proven to be tightly secure (in terms of success probability) via memory-tight reductions in the random oracle model. This gives us the first memory-tight AKE protocol, and it largely reduces the memory consumption of proving AKE protocols. Given that most post-quantum assumptions (e.g., the Learning-With-Errors and Short-Integer-Solution assumptions) are memory-sensitive, our improvement on memory consumption holds significant value for post-quantum AKE protocols.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Authenticated key exchangememory tightnessrandom oracles
- Contact author(s)
-
jiaxin pan @ uni-kassel de
runzhi zeng @ uni-kassel de - History
- 2026-07-08: revised
- 2025-10-29: received
- See all versions
- Short URL
- https://ia.cr/2025/2015
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/2015,
author = {Jiaxin Pan and Runzhi Zeng},
title = {Proving Authenticated Key Exchange via Memory-Efficient Reductions},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/2015},
year = {2025},
url = {https://eprint.iacr.org/2025/2015}
}
