Welcome to the resource topic for 2025/2015
Title:
Proving Authenticated Key Exchange via Memory-Efficient Reductions
Authors: Jiaxin Pan, Runzhi Zeng
Abstract: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 comprising 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-efficient reductions in the random oracle model. We refer to our reductions as memory-efficient rather than memory-tight, since their memory requirements grow proportionally with the number of users. This growth is not an artifact of our analysis, but rather stems from the necessity of solving the dictionary problem within our proof. By the result of Pagh (SIAM J. Computing, 2002), such user-dependent memory consumption is unavoidable. Nevertheless, our proof is more memory-efficient than the previous reductions for AKE, including even those that are non-tight. Given that most post-quantum assumptions (e.g., the Learning-With-Errors and Short-Integer-Solution assumptions) are memory-sensitive, our work holds significant value for post-quantum AKE protocols.
ePrint: https://eprint.iacr.org/2025/2015
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .