IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences

Characterization of Strongly Secure Authenticated Key Exchanges without NAXOS Technique

Atsushi Fujioka

Published Jan 1, 2013• 3 citations

Abstract

This paper examines two-pass authenticated key exchange (AKE) protocols that are secure without the NAXOS technique under the gap Diffie-Hellman assumption in the random oracle model: FHMQV [18], KFU1 [21], SMEN- [13], and UP [17]. We introduce two protocol, biclique DH protocol and multiplied biclique DH protocol, to analyze the subject protocols, and show that the subject protocols use the multiplied biclique DH protocol as internal protocols. The biclique DH protocol is secure, however, the multiplied biclique DH protocol is insecure. We show the relations between the subject protocols from the viewpoint of how they overcome the insecurity of the multiplied biclique DH protocol: ·FHMQV virtually executes two multiplied biclique DH protocols in sequence with the same ephemeral key on two randomized static keys.·KFU1 executes two multiplied biclique DH protocols in parallel with the same ephemeral key.·UP is a version of KFU1 in which one of the static public keys is generated with a random oracle.·SMEN- can be thought of as a combined execution of two multiplied biclique DH protocols. In addition, this paper provides ways to characterize the AKE protocols and defines two parameters: one consists of the number of static keys, the number of ephemeral keys, and the number of shared secrets, and the other is defined as the total sum of these numbers. When an AKE protocol is constructed based on some group, these two parameters indicate the number of elements in the group, i.e., they are related to the sizes of the storage and communication data.

DOI: 10.1587/transfun.e96.a.1088

Related papers

Strongly Secure Authenticated Key Exchange without NAXOS' Approach under Computational Diffie-Hellman Assumption

Minkyu Kim, Atsushi Fujioka, Berkant Ustaoğlu

LaMacchia, Lauter and Mityagin [19] proposed a novel security definition for authenticate key exchange (AKE) that gives an adversary the power to obtain ephemeral information regarding a target test session. To demonstrate feasibility of secure protocols in the new definition, henceforth called eCK, the authors described a protocol called NAXOS. NAXOS combines an ephemeral private key x with a static private key a to generate an ephemeral public key X (more precisely in what we call the NAXOS' approach X=gH(x,a)). Thus no one is able to query the discrete logarithm of X without knowing both the ephemeral and static private keys. This idea is crucial in the security argument to guard against leaked ephemeral secrets belonging to the test session. Another important assumption is the gap assumption that allows the protocol to remain secure even in the presence of malicious insiders. Both ideas have been successfully used in creating various protocols secure in the eCK model. In this paper, we construct two eCK-secure protocols without the above mentioned ideas. KFU1 is secure under the GDH assumption without using the NAXOS' approach. KFU2 builds upon KFU1 and drops the gap requirement, thus it is secure under the CDH assumption. Efficiency and security of the proposed protocols are comparable to the well-known HMQV [15] protocol. Furthermore, unlike HMQV and NAXOS the use of the random oracle in KFU1 and KFU2 is restricted to the key derivation function making them more suitable for practical applications.

IEICE Transactions on Fundamentals of Electronics Communications and Computer SciencesJan 1, 20126 citations

An eCK-secure Authenticated Key Exchange Protocol Without Random Oracles

Daisuke Moriyama, Tatsuaki Okamoto

Two-party key exchange protocol is a mechanism in which two parties communicate with each other over an insecure channel and output the same session key.A key exchange protocol that is secure against an active adversary who can control and modify the exchanged messages is called authenticated key exchange (AKE) protocol.LaMacchia, Lauter and Mityagin presented a strong security definition for public key infrastructure (PKI) based two-pass protocol, which we call the extended Canetti-Krawczyk (eCK) security model, and some researchers have provided eCK-secure AKE protocols in recent years.However, almost all protocols are provably secure in the random oracle model or rely on a special implementation technique so-called the NAXOS trick.In this paper, we present a PKI-based two-pass AKE protocol that is secure in the eCK security model.The security of the proposed protocol is proven without random oracles (under three assumptions), and does not rely on implementation techniques such as the NAXOS trick.

KSII Transactions on Internet and Information SystemsJan 1, 201111 citations

Authenticated Key Exchange Secure under the Computational Diffie-Hellman Assumption.

Jooyoung Lee, Je Hong Park

Abstract. In this paper, we present a new authenticated key exchange(AKE) protocol and prove its security under the random oracle assumption and the computational Diffie-Hellman(CDH) assumption. In the extended Canetti-Krawczyk model, there has been no known AKE protocol based on the CDH assumption. Our protocol, called NAXOS+, is obtained by slightly modifying the NAXOS protocol proposed by LaMacchia, Lauter and Mityagin. We establish a formal security proof of NAXOS+ in the extended Canetti-Krawczyk model using as a main tool the trapdoor test presented by Cash, Kiltz and Shoup. Key words: authenticated key exchange, trapdoor test, computational Diffie-Hellman assumption, extended Canetti-Krawzcyk model 1

Jan 1, 200846 citations

Strongly Secure Authenticated Key Exchange in the Standard Model

Zheng Yang

Nowadays many crucial network applications rely on the existence of a confidential channel established by authenticated key exchange (AKE) protocols over public networks.With the rapid development of cyber technology, novel attacks to cryptosystem emerge in an endless stream.This has also led to the development of AKE solutions to provide increasingly stronger security guarantees.In this thesis we focus on provision of practical constructions for AKE protocols which are provably secure in a strong sense without resorting to random oracles.We first we present three new efficient compilers to generically turn passively secure key exchange protocols (KE) into authenticated key exchange protocols (AKE) where security also holds in the presence of active adversaries.Our compilers are not only a useful tool for the design of new AKE systems with many additional security properties in a modular and less error-prone fashion, but they also help to relax the assumptions on existing, practical key exchange mechanisms which are not known to be provably secure AKE protocols.Security of our compilers is shown in a strong modified CK model where the adversary is allowed to reveal either long-term secret key or state information of the protocol participants.On the second, we study the open problem on constructing eCK secure two party AKE protocol without random oracles and NAXOS trick.A generic construction satisfying those requirements is given based on well-known cryptographic primitives following the guideline of efficiency.Then a concrete protocol is proposed which is the first eCK secure protocol in the standard model under both standard assumptions and post-specified peer setting (i.e.without knowing any cryptographic information about its communication peer).Both proposed schemes can be more efficiently implemented with secure device than previous works which are eCK secure in the standard model, where the secure device might be normally used to store the long-term private key and to implement codes of protocol which need to be resilience of state leakage.Finally, we generalize our one-round two party AKE construction to group case that yields an efficient tripartite AKE protocol based on bilinear maps and a candidate group AKE protocol (with more than three members) based on multilinear maps.Up to now they are the first solutions which can be proved secure in the g-eCK model without random oracles.Meanwhile we make first step to show how to simplify the security proof for one-round group AKE under g-eCK model.i

Jan 1, 20130 citations

Tightly-Secure Authenticated Key Exchange without NAXOS’ Approach Based on Decision Linear Problem

Mojahed Mohamed, Xiaofen Wang, Xiaosong Zhang

Design Secure Authenticated Key Exchange (AKE) protocol without NAXOS approach is remaining as an open problem.NAXOS approach [4] is used to hide the ephemeral secret key from an adversary even if the adversary in somehow may obtain the ephemeral secret key.Using NAXOS approach will cause two main drawbacks: (i) leaking of the static secret key which will be utilized in computing the exponent of the ephemeral public key; (ii) maximization of using random oracle when applying to the exponent of the ephemeral public key and session key derivation.In this paper, we present another AKE-secure without NAXOS approach based on decision linear assumption in the random oracle model.We fasten our security using games sequences tool which gives tight security for our protocol.

OALibJan 1, 20163 citations

An efficient strongly secure authenticated key exchange protocol without random oracles

Zheng Yang

Abstract Since the introduction of extended Canetti–Krawczyk (eCK) security model for two‐party key exchange, many protocols have been proposed to provide eCK security. However, most of those protocols are provably secure in the random oracle model or rely on special design technique, which is well known as the NAXOS trick. In contrast to previous schemes, we present an eCK secure protocol in the standard model, without NAXOS trick and without knowledge of secret key assumption for public key registration. The security proof of our scheme is based on standard pairing assumption, collision‐resistant hash functions, Bilinear Decision Diffie–Hellman and Decision Linear Diffie–Hellman assumptions, and pseudo‐random functions with pairwise independent random source. Although our proposed protocol is based on bilinear groups, it does not require any pairing operation during key exchange procedure. Copyright © 2014 John Wiley & Sons, Ltd.

Security and Communication NetworksAug 28, 20140 citations