Signed Diffie-Hellman Key Exchange with Tight Security

Hai Huang, Zhenfu Cao

Dirk Fischer

Jiaxin Pan, Chen Qian, Magnus Ringerud

Abstract We propose the first tight security proof for the ordinary two-message signed Diffie–Hellman key exchange protocol in the random oracle model. Our proof is based on the strong computational Diffie–Hellman assumption and the multiuser security of a digital signature scheme. With our security proof, the signed DH protocol can be deployed with optimal parameters, independent of the number of users or sessions, without the need to compensate any security loss. We abstract our approach with a new notion called verifiable key exchange. In contrast to a known tight three-message variant of the signed Diffie–Hellman protocol (Gjøsteen and Jager, in: Shacham, Boldyreva (eds) CRYPTO 2018, Part II. LNCS, Springer, Heidelberg, 2018), we do not require any modification to the original protocol, and our tightness result is proven in the “Single-Bit-Guess” model which we know can be tightly composed with symmetric cryptographic primitives to establish a secure channel. Finally, we extend our approach to the group setting and construct the first tightly secure group authenticated key exchange protocol.

Runzhi Zeng, Libin Wang

Tight security is an important requirement of practical cryptographic schemes. Compared with loosely‐secure schemes, tightly‐secure schemes allow shorter security parameters hence are more efficient. In CRYPTO 2018, Gjøsteen and Jager proposed a tightly‐secure authenticated key exchange (AKE) protocol. They used ‘commitment trick’ to construct a tight security reduction for their protocol. However, this technique leads to a three‐pass execution in their protocol, and their protocol cannot achieve key confirmation unless it is modified to have a four‐pass execution. In this study, the authors propose a tightly‐secure two‐pass AKE protocol. They use the twin Diffie–Hellman problem and the ‘re‐patch’ trick of random oracles to construct a tight security reduction for their protocol. This technique allows their protocol to have a two‐pass execution. Their protocol provides several security properties such as key‐compromise‐impersonation security, unknown‐key‐share security, and weak perfect forward secrecy. Moreover, a three‐pass variant of their protocol provides key confirmation.

Emmanuel Bresson, Olivier Chevassut, David Pointcheval

Hai Huang

SUMMARY This paper investigates authenticated key exchange (AKE) protocol under computational Diffie–Hellman assumption in the extended Canetti–Krawczyk model. The core technical component of our protocol is the trapdoor test technique, which is originally introduced to remove the gap Diffie–Hellman (GDH) assumption for the public key encryption schemes. Our contributions are twofold.First, we clarify some misunderstandings of the usage of the trapdoor test technique in AKE protocols showing its adaptation to the AKE protocols is not trivial. We point out some errors in some recent work which attempts to make use of the trapdoor test technique to remove GDH assumption.Second, based on trapdoor test technique, we propose an efficient extended Canetti–Krawczyk secure AKE protocol under computational Diffie–Hellman assumption instead of GDH assumption. Additionally, our protocol does not make use of NAXOS trick and has a tight reduction. In comparison with all existing AKE protocols with the properties as previously mentioned, our protocol with only three exponentiations is most efficient. Copyright © 2013 John Wiley & Sons, Ltd.