Cryptology ePrint Archive: Report 2018/237

On Tightly Secure Non-Interactive Key Exchange

Julia Hesse and Dennis Hofheinz and Lisa Kohl

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 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.

Category / Keywords: public-key cryptography / non-interactive key exchange, hash proof systems, tight security

Original Publication (with major differences): IACR-CRYPTO-2018

Date: received 1 Mar 2018, last revised 11 Jun 2018

Contact author: lisa kohl at kit edu

Available format(s): PDF | BibTeX Citation

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

Version: 20180611:143349 (All versions of this report)

Short URL: ia.cr/2018/237

Discussion forum: Show discussion | Start new discussion