Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Contemporary mathematics - American Mathematical Society

Authenticated Key Agreement with Key Re-Use in the Short Authenticated Strings Model

Stanisław Jarecki, Nitesh Saxena

Published Jan 1, 2012• 0 citations
Publisher

Abstract

Serge Vaudenay [19] introduced a notion of Message Authentication (MA) protocols in the Short Authenticated String (SAS) model. A SAS-MA protocol authenticates arbitrarily long messages sent over insecure channels as long as the sender and the receiver can additionally send a very short, e.g. 20 bit, authenticated message to each other. The main practical application of a SAS-MA protocol is Authenticated Key Agreement (AKA) in this communication model, i.e. SAS-AKA, which can be used for so-called “pairing” of wireless devices. Subsequent work [8, 11, 9] showed three-round SAS-AKA protocols. However, the Diffie-Hellman (DH) based SAS-AKA protocol of [9] requires choosing fresh DH exponents in each protocol instance, while the generic SAS-AKA construction given by [11] applies only to AKA protocols which have no shared state between protocol sessions. Therefore, both prior works exclude the most efficient, although not perfect-forward-secret, AKA protocols that re-use private keys (for encryption-based AKAs) or DH exponents (for DH-based AKAs) across multiple protocol sessions. In this paper, we propose a novel three-round encryption-based SAS-AKA protocol, using non-malleable commitments and CCA-secure encryption as tools, which we show secure (but without perfect-forward secrecy) if each player re-uses its private/public key across protocol sessions. The cost of this protocol is dominated by a single public key encryption for one party and a decryption for the other, assuming the Random Oracle Model (ROM). When implemented with RSA encryption the new SAS-AKA protocol is especially attractive if the two devices being paired have asymmetric computational power (e.g., a desktop and a keyboard).

DOI
10.1090/conm/582/11556

Related papers

An Efficient Certificate-Based Authenticated Key Agreement Protocol without Bilinear Pairing

Yang Lu, Quanling Zhang, Jiguo Li +1 more

An authenticated key agreement (AKA) protocol is extremely essential to secure communications over insecure public networks. It enables the communication parties to securely set up a shared session key in present of the malicious attackers. Certificate-based cryptography (CBC) is a novel public-key cryptographic primitive that has many attractive merits. It solves the certificate revocation problem in conventional public-key cryptography and the key-escrow problem in identity-based cryptography. Till now, four AKA protocols have been proposed in the setting of CBC. However, all of them adopt the costly bilinear pairings and are not suitable for the devices which have limited computing resources and battery power. So, it is interesting and worthwhile to design a certificate-based AKA protocol without using the bilinear pairings. In this paper, we develop a pairing-free certificate-based AKA protocol. The proposed protocol is proven secure under the classic computational Diffie-Hellman assumption in the random oracle model. Compared with the previous pairing-based certificate-based AKA protocols, the proposed protocol enjoys obvious advantage in the computation efficiency.DOI: http://dx.doi.org/10.5755/j01.itc.46.3.14968

Information Technology And Control•Sep 7, 2017•2 citations

Extended identity-based authenticated key agreement in standard model

Min Chen

The existing identity-based authenticated key agreement(ID-AKA) protocols in standard model either had known security flaws or could be verified security in weak security models.This paper proposed an extended ID-AKA protocol,which fully considered the security needs for leaking the long-term private keys,the session temporary secrets and the PKG master key.It further defined two types of fresh oracle and a session-state query,based on the ID-BJM security model,in which simulated secure games of key-compromise impersonation and perfect forward secrecy respectively.The new protocol was proven to meet the strong security with the improved ID-BJM model.The comparative analysis shows that the new protocol not only has high security,but lower computational costs.And the extended ID-AKA protocol can be used to build secure point to point communication channel on the application scenarios without key escrow.

Jisuanji yingyong yanjiu•Jan 1, 2014•0 citations

Leakage-Resilient Public-Key Cryptography in the Bounded-Retrieval Model.

Joël Alwen, Yevgeniy Dodis, Daniel Wichs

We study the design of cryptographic primitives resilient to key-leakage attacks, where an attacker can repeatedly and adaptively learn information about the secret key, subject only to the constraint that the overall amount of such information is bounded by some parameter ℓ. We construct a variety of leakage-resilient public-key systems including the first known identification schemes (ID), signature schemes and authenticated key agreement protocols (AKA). Our main result is an efficient three-round leakage-resilient AKA in the Random-Oracle model. This protocol ensures that session keys are private and authentic even if (1) the adversary leaks a large fraction of the long-term secret keys of both users prior to the protocol execution and (2) the adversary completely learns the long-term secret keys after the protocol execution. In particular, our AKA protocol provides qualitatively stronger privacy guarantees than leakage-resilient public-encryption schemes (constructed in prior and concurrent works), since such schemes necessarily become insecure if the adversary can perform leakage attacks after seing a ciphertext. Moreover, our schemes can be flexibly extended to the Bounded-Retrieval Model, allowing us to tolerate very large absolute amount of adversarial leakage ℓ (potentially many gigabytes of

•Jan 1, 2009•0 citations

One-round strongly secure key exchange with perfect forward secrecy and deniability

Cas J. F. Cremers, Michèle Feltz

Traditionally, secure one-round key exchange protocols in the PKI setting have either achieved perfect forward secrecy, or forms of deniability, but not both. On the one hand, achieving perfect forward secrecy against active attackers seems to require some form of authentication of the messages, as in signed Diffie-Hellman style protocols, that subsequently sacrifice deniability. On the other hand, using implicit authentication along the lines of MQV and descendants sacrifices perfect forward secrecy in one round and achieves only weak perfect forward secrecy instead. We show that by reintroducing signatures, it is possible to satisfy both a strong key-exchange security notion as well as a strong form of deniability, in one-round key exchange protocols. Our security notion for key exchange is stronger than, e. g., the extended CK model, and captures perfect forward secrecy. Our notion of deniability, which we call peer-and-time deniability, is stronger than that offered by, e. g., the SIGMA protocol. We propose a concrete protocol and prove that it satisfies our definition of key-exchange security in the random oracle model as well as peer-and-time deniability. The protocol combines a signed-Diffie-Hellman message exchange with an MQV-style key computation, and offers a remarkable combination of advanced security properties and efficiency

•Jun 1, 2011•35 citations

Signed (Group) Diffie–Hellman Key Exchange with Tight Security

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.

Journal of Cryptology•Sep 27, 2022•28 citations

A new certificateless authenticated two-party key agreement

YuXiu-Ying, ZhangWen-Fang, HeDa-Ke

Authenticated key agreement (AKA) protocol allows two or multi-parties exchange messages, authenticate each other and establish shared session keys for later secure communications over an open network. The certificateless -based authenticated key agreement protocols combined the advantages of the traditional PKI and the identity-based cryptography. This paper analyzes a proposed AKA protocol[6] and presents a new certificateless AKA protocol. Furthermore, we examines the security of the new protocol and compare it to the existing certificateless key agreement protocols in efficiency. The new proposed scheme achieves almost all of the desired security attributes and is more practicable.

IEEE International Conference on Computer Science and Automation Engineering•Jun 1, 2011•0 citations
Serge Vaudenay [19] introduced a notion of Message Authentication (MA) protocols in the Short Authenticated String (SAS) model. A SAS-MA protocol authenticates arbitrarily long messages sent over insecure channels as long as the sender and the receiver can additionally send a very short, e.g. 20 bit, authenticated message to each other. The main practical application of a SAS-MA protocol is Authenticated Key Agreement (AKA) in this communication model, i.e. SAS-AKA, which can be used for so-called “pairing” of wireless devices. Subsequent work [8, 11, 9] showed three-round SAS-AKA protocols. However, the Diffie-Hellman (DH) based SAS-AKA protocol of [9] requires choosing fresh DH exponents in each protocol instance, while the generic SAS-AKA construction given by [11] applies only to AKA protocols which have no shared state between protocol sessions. Therefore, both prior works exclude the most efficient, although not perfect-forward-secret, AKA protocols that re-use private keys (for encryption-based AKAs) or DH exponents (for DH-based AKAs) across multiple protocol sessions. In this paper, we propose a novel three-round encryption-based SAS-AKA protocol, using non-malleable commitments and CCA-secure encryption as tools, which we show secure (but without perfect-forward secrecy) if each player re-uses its private/public key across protocol sessions. The cost of this protocol is dominated by a single public key encryption for one party and a decryption for the other, assuming the Random Oracle Model (ROM). When implemented with RSA encryption the new SAS-AKA protocol is especially attractive if the two devices being paired have asymmetric computational power (e.g., a desktop and a keyboard).
An authenticated key agreement (AKA) protocol is extremely essential to secure communications over insecure public networks. It enables the communication parties to securely set up a shared session key in present of the malicious attackers. Certificate-based cryptography (CBC) is a novel public-key cryptographic primitive that has many attractive merits. It solves the certificate revocation problem in conventional public-key cryptography and the key-escrow problem in identity-based cryptography. Till now, four AKA protocols have been proposed in the setting of CBC. However, all of them adopt the costly bilinear pairings and are not suitable for the devices which have limited computing resources and battery power. So, it is interesting and worthwhile to design a certificate-based AKA protocol without using the bilinear pairings. In this paper, we develop a pairing-free certificate-based AKA protocol. The proposed protocol is proven secure under the classic computational Diffie-Hellman assumption in the random oracle model. Compared with the previous pairing-based certificate-based AKA protocols, the proposed protocol enjoys obvious advantage in the computation efficiency.DOI: http://dx.doi.org/10.5755/j01.itc.46.3.14968
The existing identity-based authenticated key agreement(ID-AKA) protocols in standard model either had known security flaws or could be verified security in weak security models.This paper proposed an extended ID-AKA protocol,which fully considered the security needs for leaking the long-term private keys,the session temporary secrets and the PKG master key.It further defined two types of fresh oracle and a session-state query,based on the ID-BJM security model,in which simulated secure games of key-compromise impersonation and perfect forward secrecy respectively.The new protocol was proven to meet the strong security with the improved ID-BJM model.The comparative analysis shows that the new protocol not only has high security,but lower computational costs.And the extended ID-AKA protocol can be used to build secure point to point communication channel on the application scenarios without key escrow.
We study the design of cryptographic primitives resilient to key-leakage attacks, where an attacker can repeatedly and adaptively learn information about the secret key, subject only to the constraint that the overall amount of such information is bounded by some parameter ℓ. We construct a variety of leakage-resilient public-key systems including the first known identification schemes (ID), signature schemes and authenticated key agreement protocols (AKA). Our main result is an efficient three-round leakage-resilient AKA in the Random-Oracle model. This protocol ensures that session keys are private and authentic even if (1) the adversary leaks a large fraction of the long-term secret keys of both users prior to the protocol execution and (2) the adversary completely learns the long-term secret keys after the protocol execution. In particular, our AKA protocol provides qualitatively stronger privacy guarantees than leakage-resilient public-encryption schemes (constructed in prior and concurrent works), since such schemes necessarily become insecure if the adversary can perform leakage attacks after seing a ciphertext. Moreover, our schemes can be flexibly extended to the Bounded-Retrieval Model, allowing us to tolerate very large absolute amount of adversarial leakage ℓ (potentially many gigabytes of
Traditionally, secure one-round key exchange protocols in the PKI setting have either achieved perfect forward secrecy, or forms of deniability, but not both. On the one hand, achieving perfect forward secrecy against active attackers seems to require some form of authentication of the messages, as in signed Diffie-Hellman style protocols, that subsequently sacrifice deniability. On the other hand, using implicit authentication along the lines of MQV and descendants sacrifices perfect forward secrecy in one round and achieves only weak perfect forward secrecy instead. We show that by reintroducing signatures, it is possible to satisfy both a strong key-exchange security notion as well as a strong form of deniability, in one-round key exchange protocols. Our security notion for key exchange is stronger than, e. g., the extended CK model, and captures perfect forward secrecy. Our notion of deniability, which we call peer-and-time deniability, is stronger than that offered by, e. g., the SIGMA protocol. We propose a concrete protocol and prove that it satisfies our definition of key-exchange security in the random oracle model as well as peer-and-time deniability. The protocol combines a signed-Diffie-Hellman message exchange with an MQV-style key computation, and offers a remarkable combination of advanced security properties and efficiency
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.
Authenticated key agreement (AKA) protocol allows two or multi-parties exchange messages, authenticate each other and establish shared session keys for later secure communications over an open network. The certificateless -based authenticated key agreement protocols combined the advantages of the traditional PKI and the identity-based cryptography. This paper analyzes a proposed AKA protocol[6] and presents a new certificateless AKA protocol. Furthermore, we examines the security of the new protocol and compare it to the existing certificateless key agreement protocols in efficiency. The new proposed scheme achieves almost all of the desired security attributes and is more practicable.