Generic Transformation of a CCA2-Secure Public-Key Encryption Scheme to an eCK-Secure Key Exchange Protocol in the Standard Model.

Janaka Alawatugoda

Published Jan 1, 2015• 1 citation

Abstract

LaMacchia, Lauter and Mityagin presented a strong security model for authenticated key agreement, namely the eCK model. They also constructed a protocol, namely the NAXOS protocol, that enjoys a simple security proof in the eCK model. However, the NAXOS protocol uses a random-oracle-based technique to combine the long-term secret key and the per-session-randomness; so-called NAXOStrick, in order to achieve the eCK security definition. For NAXOS-trick-based protocols, the leakage of per-session-randomness modelled in the eCK model is somewhat unnatural, because the eCK model leaks per-session-randomness, while the output of the NAXOS-trick computation remains safe. In this work, we present a standard model eCK-secure protocol construction, eliminating the NAXOS-trick. Moreover, our protocol is a generic constructions, which can be instantiated with arbitrary suitable cryptographic primitives. Thus, we present a generic eCK-secure, NAXOS-free, standard model key exchange protocol. To the best of our knowledge this is the first paper on generic transformation of a CCA2-secure public key encryption scheme to an eCK-secure key exchange protocol in the standard model.

Related papers

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

Efficient eCK-secure Authenticated Key Exchange Protocols in the Standard Model.

Zheng Yang

The extended Canetti–Krawczyk (eCK) security models, are widely used to provide security arguments for authenticated key exchange protocols that capture leakage of various kinds of secret information like the long-term private key and session-specific secret state. In this paper, we study the open problem on constructing eCK secure AKE protocol without random oracles and NAXOS like trick. A generic construction GC-KKN satisfying those requirements is first given relying on standard cryptographic primitives following the guideline of efficiency. On the second 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. Both proposed schemes can be more efficiently implemented with secure device than previous eCK secure protocols in the standard model, where the secure device might be normally used to store the long-term private key and implement algorithms of protocol which require to be resilience of state leakage.

Jan 1, 20130 citations

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

Efficient and Secure Authenticated Key Exchange Protocols in the eCK Model

Jooyoung Lee, Je Hong Park

In this paper, we propose two authenticated key exchange (AKE) protocols and prove their security in the extended Canetti-Krawczyk model. The first protocol, called NAXOS+, is obtained by slightly modifying the NAXOS protocol proposed by LaMacchia, Lauter and Mityagin [15]. We prove its security under the Computational Diffie-Hellman (CDH) assumption by using the trapdoor test introduced in [6]. To the authors' knowledge, this is the first AKE protocol which is secure under the CDH assumption in the eCK model. The second protocol, called NETS, enjoys a simple and tight security reduction compared to existing schemes including HMQV and CMQV without using the Forking Lemma. Since each session of the NETS protocol requires only three exponentiations per party, its efficiency is also comparable to MQV, HMQV and CMQV.

IEICE Transactions on Fundamentals of Electronics Communications and Computer SciencesJan 1, 20110 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