Paper 2023/571

Fine-Grained Non-Interactive Key-Exchange: Constructions and Lower Bounds

Abtin Afshar, University of Virginia
Geoffroy Couteau, CNRS, IRIF, Université de Paris
Mohammad Mahmoody, University of Virginia
Elahe Sadeghi, The University of Texas at Austin

In this work, we initiate a study of $K$-NIKE protocols in the fine-grained setting, in which there is a 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 for $K \geq 3$. Our contribution is threefold. - We show that random oracles can be used to obtain fine-grained $K$-NIKE protocols for 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. - We then improve the security by further using algebraic structures, while avoiding pairings. In particular, we show that there is a 4-party NIKE in Shoup's generic group model with a quadratic gap between the number of queries by the honest parties vs. that of the adversary. - 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 any polynomial number of queries.

Available format(s)
Cryptographic protocols
Publication info
Published by the IACR in EUROCRYPT 2023
non-interactive key-exchangelower boundsfine-grainconstructions
Contact author(s)
abtin @ virginia edu
couteau @ irif fr
mohammad @ virginia edu
elahesadeghi @ utexas edu
2023-04-24: approved
2023-04-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Abtin Afshar and Geoffroy Couteau and Mohammad Mahmoody and Elahe Sadeghi},
      title = {Fine-Grained Non-Interactive Key-Exchange: Constructions and Lower Bounds},
      howpublished = {Cryptology ePrint Archive, Paper 2023/571},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.