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

Lecture notes in computer science

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

Stanisław Jarecki, Nitesh Saxena

Published Jan 1, 2010• 9 citations
Publisher
DOI
10.1007/978-3-642-15317-4_17

Related papers

A New Security Model for Authenticated Key Agreement

Augustin P. Sarr, Philippe Elbaz–Vincent, Jean-Claude Bajard

Lecture notes in computer science•Jan 1, 2010•82 citations

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

Stanisław Jarecki, Nitesh Saxena

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

Contemporary mathematics - American Mathematical Society•Jan 1, 2012•0 citations

Security Model for Authenticated Key Exchange, Reconsidered

Xichen Zhang, Keitaro Hashimoto, Wakaha Ogata

Lecture notes in computer science•Jan 1, 2024•0 citations

The Bare Bounded-Storage Model: The Tight Bound on the Storage Requirement for Key Agreement

Stefan Dziembowski, Ueli M. Maurer

In the bounded-storage model (BSM) for information-theoretic secure encryption and key agreement, one makes use of a random string whose length is greater than the assumed bound on the adversary Eve's storage capacity. The legitimate parties, Alice and Bob, execute a protocol, over an authenticated channel accessible to Eve, to generate a secret key about which Eve has essentially no information even if she has infinite computing power. The string is either assumed to be accessible to all parties or communicated publicly from Alice to Bob. While in the BSM one often assumes that Alice and Bob initially share a short secret key, and the goal of the protocol is to generate a much longer key, in this communication, we consider the bare BSM without any initially shared secret key. It is proved that in the bare BSM, secret key agreement is impossible unless Alice and Bob have themselves very high storage capacity, namely, . This proves the optimality of a scheme proposed by Cachin and Maurer.

IEEE Transactions on Information Theory•May 29, 2008•13 citations

Efficient Identity-Based and Authenticated Key Agreement Protocol

Yongge Wang

Lecture notes in computer science•Jan 1, 2013•91 citations

Post‐quantum identity‐based authenticated multiple key agreement protocol

Yang Yang, Hongji Yuan, Linbo Yan +1 more

Abstract Authenticated multiple key agreement (AMKA) protocols provide participants with multiple session keys after one round of authentication. Many schemes use Diffie–Hellman or authenticated key agreement schemes that rely on hard integer factorizations that are vulnerable to quantum algorithms. Lattice cryptography provides quantum resistance to authenticated key agreement protocols, but the certificate always incurs excessive public key infrastructure management overhead. Thus, a lightweight lattice‐based secure system is needed that removes this overhead. To answer this need, we provide a two‐party lattice‐ and identity‐based AMKA scheme based on bilateral short integer or computational bilateral inhomogeneous small integer solutions, and we provide a security proof based on the random oracle model. Compared with existing AMKA protocols, our new protocol has higher efficiency and stronger security.

ETRI Journal•Jun 27, 2023•11 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).
In the bounded-storage model (BSM) for information-theoretic secure encryption and key agreement, one makes use of a random string whose length is greater than the assumed bound on the adversary Eve's storage capacity. The legitimate parties, Alice and Bob, execute a protocol, over an authenticated channel accessible to Eve, to generate a secret key about which Eve has essentially no information even if she has infinite computing power. The string is either assumed to be accessible to all parties or communicated publicly from Alice to Bob. While in the BSM one often assumes that Alice and Bob initially share a short secret key, and the goal of the protocol is to generate a much longer key, in this communication, we consider the bare BSM without any initially shared secret key. It is proved that in the bare BSM, secret key agreement is impossible unless Alice and Bob have themselves very high storage capacity, namely, . This proves the optimality of a scheme proposed by Cachin and Maurer.
Abstract Authenticated multiple key agreement (AMKA) protocols provide participants with multiple session keys after one round of authentication. Many schemes use Diffie–Hellman or authenticated key agreement schemes that rely on hard integer factorizations that are vulnerable to quantum algorithms. Lattice cryptography provides quantum resistance to authenticated key agreement protocols, but the certificate always incurs excessive public key infrastructure management overhead. Thus, a lightweight lattice‐based secure system is needed that removes this overhead. To answer this need, we provide a two‐party lattice‐ and identity‐based AMKA scheme based on bilateral short integer or computational bilateral inhomogeneous small integer solutions, and we provide a security proof based on the random oracle model. Compared with existing AMKA protocols, our new protocol has higher efficiency and stronger security.