[Resource Topic] 2024/834: Fine-Grained Non-Interactive Key Exchange, Revisited

Welcome to the resource topic for 2024/834

Fine-Grained Non-Interactive Key Exchange, Revisited

Authors: Balthazar Bauer, Geoffroy Couteau, Elahe Sadeghi


We revisit the construction of multiparty non-interactive key-exchange protocols with fine-grained security, which was recently studied in (Afshar et al., Eurocrypt 2023). Their work introduced a 4-party non-interactive key exchange with quadratic hardness, and proved it secure in Shoup’s generic group model. This positive result was complemented with a proof that n-party non-interactive key exchange with superquadratic security cannot exist in Maurer’s generic group model, for any n\geq 3. Because Shoup’s model is stronger than Maurer’s model, this leaves a gap between the positive and the negative result, and their work left as an open question the goal of closing this gap, and of obtaining fine-grained non-interactive key exchange without relying on idealized models.

In this work, we make significant progress on both questions. We obtain two main results:

A 4-party non-interactive key exchange protocol with quadratic security gap, assuming the existence of exponentially secure injective pseudorandom generators, and the subexponential hardness of the computational Diffie-Hellman assumption. In addition, our scheme is conceptually simpler, and can be generalized to other settings (with more parties or from other assumptions).

Assuming the existence of non-uniformly secure injective pseudorandom generators with exponential hardness, we further show that our protocol is secure in Maurer’s model, albeit with a smaller hardness gap (up to N^{1.6}), making progress on filling the gap between the positive and the negative result of (Afshar et al., Eurocrypt 2023). Somewhat intriguingly, proving the security of our scheme in Maurer’s idealized model turns out to be significantly harder than proving its security in the standard model.

ePrint: https://eprint.iacr.org/2024/834

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 .