Welcome to the resource topic for 2024/308
Title:
C’est très CHIC: A compact password-authenticated key exchange from lattice-based KEM
Authors: Afonso Arriaga, Manuel Barbosa, Stanislaw Jarecki, Marjan Skrobot
Abstract:Several Password Authenticated Key Exchange (PAKE) protocols have been recently proposed that leverage a Key-Encapsulation Mechanism (KEM) to create an efficient and easy-to-implement post-quantum secure PAKE. This line of work is driven by the intention of the National Institute of Standards and Technology (NIST) to soon standardize a lattice-based post-quantum KEM called \mathsf{Kyber}. In two recent works, Beguinet et al. (ACNS 2023) and Pan and Zeng (ASIACRYPT 2023) proposed generic compilers that transform KEM into PAKE, relying on an Ideal Cipher (IC) defined over a group. However, although IC on a group is often used in cryptographic protocols, special care must be taken to instantiate such objects in practice, especially when a low-entropy key is used. To address this concern, Dos Santos et al. (EUROCRYPT 2023) proposed a relaxation of the IC model under the Universal Composability (UC) framework called Half-Ideal Cipher (HIC). They demonstrate how to construct a UC-secure PAKE protocol, named \mathsf{EKE\textrm{-}KEM}, from a KEM and a modified 2-round Feistel construction called \mathsf{m2F}. Remarkably, \mathsf{m2F} sidesteps the use of IC over a group, instead employing an IC defined over a fixed-length bitstring domain, which is easier to instantiate.
In this paper, we introduce a novel PAKE protocol called \mathsf{CHIC} that improves the communication and computation efficiency of \mathsf{EKE\textrm{-}KEM}. We do so by opening \mathsf{m2F} construction in a white-box manner and avoiding the HIC abstraction in our analysis.
We provide a detailed proof of the security of \mathsf{CHIC} and establish precise security requirements for the underlying KEM, including one-wayness and anonymity of ciphertexts, and uniformity of public keys. Our analysis improves prior work by pinpointing the necessary and sufficient conditions for a tight security proof.
Our findings extend to general KEM-based EKE-style protocols, under both game-based definitions (with Perfect Forward Secrecy) and UC PAKE definitions, and show that a passively secure KEM is not sufficient. In this respect, our results align with those of Pan and Zeng (ASIACRYPT 2023), but contradict the analyses of KEM-to-PAKE compilers by Beguinet et al. (ACNS 2023) and Dos Santos et al. (EUROCRYPT 2023).
Finally, we provide an implementation of \mathsf{CHIC}, highlighting its minimal overhead compared to an underlying CCA-secure KEM - \mathsf{Kyber}. An interesting aspect of the implementation is that we reuse existing \mathsf{Kyber} reference code to solve an open problem concerning instantiating the half-ideal cipher construction. Specifically, we reuse the rejection sampling procedure, originally designed for public-key compression, to implement the hash onto the public key space, which is a component in the half-ideal cipher. As of now, to the best of our knowledge, CHIC stands as the most efficient PAKE protocol from black-box KEM that offers rigorously proven UC security.
ePrint: https://eprint.iacr.org/2024/308
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 .