On the Security of Non-Interactive Key Exchange against Related-Key Attacks

Hiraku MORITA  Jacob C.N. SCHULDT  Takahiro MATSUDA  Goichiro HANAOKA  Tetsu IWATA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E100-A   No.9   pp.1910-1923
Publication Date: 2017/09/01
Online ISSN: 1745-1337
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
related-key attacks,  Non-Interactive Key Exchange,  Diffie-Hellman key exchange scheme,  

Full Text: PDF(1.1MB)
>>Buy this Article

Non-Interactive Key Exchange (NIKE) is a cryptographic primitive that allows two users to compute a shared key without any interaction. The Diffie-Hellman key exchange scheme is probably the most well-known example of a NIKE scheme. Freire et al. (PKC 2013) defined four security notions for NIKE schemes, and showed implications among them. In these notions, we consider an adversary that is challenged to distinguish a shared key of a new pair of users from a random value, using only its knowledge of keys shared between other pairs of users. To take into account side-channel attacks such as tampering and fault-injection attacks, Bellare and Kohno (Eurocrypt 2003) formalized related-key attacks (RKA), where stronger adversaries are considered. In this paper, we introduce four RKA security notions for NIKE schemes. In these notions, we consider an adversary that can also manipulate the secret keys of users and obtain shared keys computed under the modified secret keys. We also show implications and separations among the security notions, and prove that one of the NIKE schemes proposed by Freire et al. is secure in the strongest RKA sense in the random oracle model under the Double Strong Diffie-Hellman (DSDH) assumption over the group of signed quadratic residues, which is implied by the factoring assumption.