International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: On Tightly Secure Non-Interactive Key Exchange

Julia Hesse
Dennis Hofheinz
Lisa Kohl
DOI: 10.1007/978-3-319-96881-0_3 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2018
Abstract: 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 $$\varOmega (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.
Video from CRYPTO 2018
  title={On Tightly Secure Non-Interactive Key Exchange},
  booktitle={Advances in Cryptology – CRYPTO 2018},
  series={Lecture Notes in Computer Science},
  author={Julia Hesse and Dennis Hofheinz and Lisa Kohl},