The Computer Journal

Simpler Generic Constructions for Strongly Secure One-round Key Exchange from Weaker Assumptions

Zheng Yang, Junyu Lai, Chao Liu, Wanping Liu, Shuangqing Li

Published Nov 10, 2016• 7 citations

Abstract

In PKC 2015, Bergsma et al. introduced a generic one-round key exchange (ORKE) protocol (which is referred to as BJS) from digital signature (SIG) and simplified non-interactive key exchange (NIKE) without involving any identity. The BJS scheme is shown to satisfy extended Canetti and Krawczyk-PFS security if the NIKE is adaptive-CKS-light secure and the SIG is strongly secure against existential unforgeability under chosen message attacks. However, the BJS scheme cannot be instantiated with NIKE scheme with identity (e.g. the one proposed by Boneh and Zhandry in Crypto 2014). In this paper, we propose a much simpler generic construction for ORKE from NIKE and SIG. In particular, our scheme only makes weaker security assumptions on the underlying building blocks. Namely, we first show that the static-CKS-light security of NIKE, where the target identities are chosen by the adversary before seeing the system parameters, is sufficient for our construction. On the second, we observe that the SIG only needs to provide strong existential unforgeability under weak chosen message attacks for our construction. These results enable our proposal to have more concrete instantiations which might be easier to build and realize. At the same time, our new protocol is much more computationally efficient than the BJS protocol.

DOI: 10.1093/comjnl/bxw095

Related papers

Authenticated Key Exchange Protocol in the Standard Model under Weaker Assumptions

Janaka Alawatugoda

A two-party authenticated key exchange (AKE) protocol allows each of the two parties to share a common secret key over insecure channels, even in the presence of active adversaries who can actively control and modify the exchanged messages. To capture the malicious behaviors of the adversaries, there have been many efforts to define security models. Amongst them, the extended Canetti–Krawczyk (eCK) security model is considered one of the strongest security models and has been widely adopted. In this paper, we present a simple construction of a pairing-based eCK-secure AKE protocol in the standard model. Our protocol can be instantiated with a suitable signature scheme (i.e., an existentially unforgeable signature scheme against adaptive chosen message attacks). The underlying assumptions of our construction are the decisional bilinear Diffie–Hellman assumption and the existence of a pseudorandom function. Note that the previous eCK-secure protocol constructions either relied on random oracles for their security or used somewhat strong assumptions, such as the existence of strong-pseudorandom functions, target collision-resistant functions, etc., while our protocol construction uses fewer and more-standard assumptions in the standard model. Furthermore, preserving the same security argument, our protocol can be instantiated with any appropriate signature scheme that comes in the future with better efficiency.

CryptographyJan 5, 20232 citations

Cryptanalysis of a generic one‐round key exchange protocol with strong security

Zheng Yang, Junyu Lai, Guoyuan Li

In Public‐Key Cryptography (PKC) 2015, Bergsma et al . introduced an interesting one‐round key exchange protocol (which will be referred to as BJS scheme) with strong security in particular for perfect forward secrecy (PFS). In this study, the authors unveil a PFS attack against the BJS scheme. This would simply invalidate its security proof. An improvement is proposed to fix the problem of the BJS scheme with minimum changes.

IET Information SecuritySep 4, 20170 citations

SignORKE: improving pairing‐based one‐round key exchange without random oracles

Zheng Yang, Junyu Lai, Wanping Liu +2 more

The study presents a new efficient way to construct the one‐round key exchange (ORKE) without random oracles based on standard hard complexity assumptions. The authors propose a (PKI‐based) ORKE protocol which is more computational efficient than existing pairing‐based ORKE protocols without random oracles in the post‐specified peer setting. The core idea of this construction is to integrate the consistency check of the ephemeral public key and the verification of the signature into the session key generation. This enables us to roughly save two pairing operations. The authors just call this kind of scheme that is deeply composed by signature and one‐round key exchange as SignORKE. The authors’ protocol is shown to be secure in a variant of the Canetti–Krawczyk security model which covers the majority of state‐of‐the‐art active attacks.

IET Information SecurityNov 4, 20162 citations

Adaptive Multiparty Non-interactive Key Exchange Without Setup In The Standard Model.

Vanishree Rao

Non-interactive key exchange (NIKE) is a fundamental notion in Cryptography. This notion was introduced by Diffie and Hellman in 1976. They proposed the celebrated 2-party NIKE protocol and left open as a fascinating question, whether NIKE could be realized in the mul-tiparty setting. NIKE has since then been an active area of research with an ultimate goal of obtaining best possible security in the multiparty setting. Although this has evaded researchers for many decades, advancements have been made through relaxations in multiple directions such as restricting to 3-parties, static/semi-static model (where the adversary needs to commit to the set of parties he wishes to be challenged upon ahead of time), random-oracle model, allowing initial setup, etc. In this work, we settle the longstanding open question: we present the first multiparty NIKE protocol that is adaptively secure with no setup and in the standard model. Our construction is based on indistinguishability obfuscation and obliviously-patchable punc-turable pseudorandom functions, a new notion that we introduce. We employ novel techniques of using indistinguishability obfuscation, which are interesting in their own right and which we believe would find wider applications in other settings. One such technique pertains overcoming, the somewhat inherent, drawback of non-adaptivity of the puncturing technique introduced by Sahai and Waters [STOC’14]. Central to this technique is our new notion of obliviously-patchable puncturable pseudorandom functions. We present a concrete construction of these pseudorandom functions using multilinear maps and their recent approximations – the leveled-graded encoding schemes. Note that pseudorandom functions amount to an interactive assumption. We shall establish via a meta-reduction technique that, in natural settings, an interactive assumption is necessary (even with setup). ∗University of California, Los Angeles.

Jan 1, 20149 citations

Strongly Unforgeable Signatures and Hierarchical Identity-based Signatures from Lattices without Random Oracles.

Markus Rückert

Abstract. We propose a variant of the “bonsai tree ” signature scheme, a lattice-based existentially unforgeable signature scheme in the standard model. Our construction offers the same efficiency as the “bonsai tree” scheme but supports the stronger notion of strong unforgeability. Strong unforgeability demands that the adversary is unable to produce a new message-signature pair (m, s), even if he or she is allowed to see a different signature s ′ for m. In particular, we provide the first treeless signature scheme that supports strong unforgeability for the post-quantum era in the standard model. Moreover, we show how to directly implement identity-based, and even hierarchical identity-based, signatures (IBS) in the same strong security model without random oracles. An additional advantage of this direct approach over the usual generic conversion of hierarchical identity-based encryption to IBS is that we can exploit the efficiency of ideal lattices without significantly harming security. We equip all constructions with strong security proofs based on mild worst-case assumptions on lattices and we also propose concrete security parameters.

Jan 1, 20100 citations

One Round Group Key Exchange with Forward Security in the Standard Model.

M. Choudary Gorantla, Colin Boyd, Juan Manuel González Nieto

Abstract. Constructingaoneround group key exchange (GKE) protocol that provides forwardsecrecy is an open problem in the literature. In this paper, we investigate whether or not the security of one round GKE protocols can be enhanced with any form of forward secrecy without increasing the number of rounds. We apply the key evolving approach used for forward secure encryption/signature schemes and then model the notion of forward security for the first time for key exchange protocols. This notion is slightly weaker than forward secrecy, considered traditionally for key exchange protocols. We then revise an existing one round GKE protocol to propose a GKE protocol with forward security. In the security proof of the revised protocol we completely avoid reliance on the random oracle assumption that was needed for the proof of the base protocol. Our security proof can be directly applied to the base protocol, making it the most efficient one round GKE protocol secure in the standard model. Our one round GKE protocol is generically constructed from the primitive of forward secure encryption. We also propose a concrete forward secure encryption scheme with constant size ciphertext that can be used to efficiently instantiate our protocol.

Jan 1, 20104 citations