CryptoDB
Fine-Grained Non-Interactive Key-Exchange: Constructions and Lower Bounds
| Authors: |
|
|---|---|
| Download: |
|
| Presentation: | Slides |
| Conference: | EUROCRYPT 2023 |
| Abstract: | In 1974, Merkle showed that an ideal hash function (modeled as a random oracle) can be used between two parties to agree on a key that remains \emph{mildly} secure against adversaries whose running time is quadratic in those of honest parties. Shortly after, Diffie and Hellman improved this idea to a full-fledged key exchange protocol that is conjectured to be secure against super-polynomial adversaries. Both of these protocols have a crucial aspect in common: they are \emph{non-interactive}, as parties send their single message in parallel, and then they use their secret randomness and the public messages to derive the common key. Constructing $K$-NIKE protocols on well-founded assumptions turned out to be much challenging for $K>2$. For $K=3$ one can do this based on pairing-based assumptions, and for $K>3$ even stronger assumptions such as indistinguishability obfuscations have been used. In this work, we initiate a study of $K$-NIKE protocols in the \emph{fine-grained} setting, in which there is a \emph{polynomial} gap between the running time of the honest parties and that of the adversary. Our goal is to show the possibility, or impossibility, of basing such protocols on weaker assumptions than those of $K$-NIKE protocols for $K \geq 3$. Our contribution is threefold. 1. We show that random oracles can be used to obtain fine-grained $K$-NIKE protocols for \emph{every} constant $K$. In particular, we show how to generalize Merkle's two-party protocol to $K$ parties in such a way that the honest parties ask $n$ queries each, while the adversary needs $n^{K/(K-1)}$ queries to the random oracle to find the key. 2. We then improve the security by further using algebraic structure, while avoiding pairing. In particular, we show that there is a 4-party NIKE in Shoup's generic group model with a \emph{quadratic} gap between the number of queries by the honest parties vs. that of the adversary. 3. Finally, we show a limitation of using purely algebraic methods for obtaining $3$-NIKE. In particular, we show that any $n$-query $3$-NIKE protocol in Maurer's generic group model can be broken by a $O(n^2)$-query attacker. Maurer's GGM is more limited compared with Shoup's both for the parties and the adversary, as there are no explicit labels for the group elements. Despite being more limited, this model still captures the Diffie Hellman protocol. Prior to our work, it was open to break $3$-NIKE protocols in Maurer's model with \emph{any} polynomial number of queries. Our work leaves open to understand the optimality of our $K$-NIKE protocol in the random oracle model, which we conjecture to be optimal, and also to close the gap between our positive result in Shoup's model and the negative result in Maurer's model. |
BibTeX
@inproceedings{eurocrypt-2023-32973,
title={Fine-Grained Non-Interactive Key-Exchange: Constructions and Lower Bounds},
publisher={Springer-Verlag},
doi={10.1007/978-3-031-30545-0_3},
author={Abtin Afshar and Geoffroy Couteau and Mohammad Mahmoody and Elahe Sadeghi},
year=2023
}