Paper 2018/237

On Tightly Secure Non-Interactive Key Exchange

Julia Hesse, Dennis Hofheinz, and Lisa Kohl


We consider the reduction loss of security reductions for non-interactive key exchange (NIKE) schemes. Currently, no tightly secure NIKE schemes exist, and in fact Bader et al. (EUROCRYPT 2016) provide a lower bound (of O(n^2), where n is the number of parties an adversary interacts with) on the reduction loss for a large class of NIKE schemes. We offer two results: the first NIKE scheme with a reduction loss of n/2 that circumvents the lower bound of Bader et al., but is of course still far from tightly secure. Second, we provide a generalization of Bader et al.'s lower bound to a larger class of NIKE schemes (that also covers our NIKE scheme), with an adapted lower bound of n/2 on the reduction loss. Hence, in that sense, the reduction for our NIKE scheme is optimal.

Note: Corrected Figure 1 (Comparison of existing NIKE schemes). Fixed typos and inconsistencies. Added explanations.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2018
non-interactive key exchangehash proof systemstight security
Contact author(s)
lisa kohl @ kit edu
2018-06-11: revised
2018-03-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Julia Hesse and Dennis Hofheinz and Lisa Kohl},
      title = {On Tightly Secure Non-Interactive Key Exchange},
      howpublished = {Cryptology ePrint Archive, Paper 2018/237},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.