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

Tighter Security Proofs for Post-quantum Key Encapsulation Mechanism in the Multi-challenge Setting

Zhengyu Zhang, Puwen Wei, Haiyang Xue

Published Jan 1, 2019• 2 citations
Publisher
DOI
10.1007/978-3-030-31578-8_8

Related papers

Tighter Security Proofs for Generic Key Encapsulation Mechanism in the Quantum Random Oracle Model

Haodong Jiang, Zhenfeng Zhang, Zhi Ma

Lecture notes in computer science•Jan 1, 2019•39 citations

Post-quantum Security of Key Encapsulation Mechanism Against CCA Attacks with a Single Decapsulation Query

Haodong Jiang, Zhi Ma, Zhenfeng Zhang

Lecture notes in computer science•Jan 1, 2023•12 citations

On The Multi-target Security of Post-Quantum Key Encapsulation Mechanisms

Lewis Glabush, Kathrin Hövelmanns, Douglas Stebila

Practical deployments of key encapsulation mechanisms (KEMs) may entail large servers each using their public keys to communicate with potentially millions of clients simultaneously. While the standard IND-CCA security definition for KEMs considers only a single challenge public key and single challenge ciphertext, it can be relevant to consider multi-target scenarios where the adversary aims to break one of many challenge ciphertexts, for one of many challenge public keys. Many post-quantum KEMs have been built by applying the Fujisaki-Okamoto (FO) transform to a public key encryption (PKE) scheme. Although the FO transform incurs only a few bits of security loss for the standard, single-challenge IND-CCA property, this does not hold in the multi-target setting. Attacks have been identified against standards-track FO-based KEMs with 128-bit message spaces (FrodoKEM-640 and HQC-128) which become feasible if the adversary is given many challenge ciphertexts (say, 2^64). These attacks exploit the deterministic encryption induced by the FO transform which allows the IND-CCA experiment to be reduced to a search problem on the message space, which in some cases may not be large enough to avoid collisions between pre-computation and challenge values. A cost effective way to amplify the hardness of this search problem is to add a random but public salt during encapsulation. While revised versions of FrodoKEM and HQC have used salts, there has been no proof showing that salting provides multi-ciphertext security. In this work, we formally analyze a salted variant of the Fujisaki-Okamoto transform, in the classical and quantum random oracle model (ROM); for the classical ROM, we show that multi-target IND-CCA security of the resulting KEM tightly reduces to the multi-target IND-CPA security of the underlying PKE. Our results imply that, for FrodoKEM and HQC at the 128-bit security level, replacing the FO transform with the salted variant can recover 62 bits of multi-target security, at the cost of a very small overhead increase.

IACR Communications in Cryptology•May 4, 2026•2 citations

Post - Quantum Cryptography and Authentication: Enhancing Security for the Quantum Era

Nguyễn Thị Phượng Hằng, Lưu Hồng Dũng

•Jan 1, 2025•0 citations

Asymmetric Password Authentication Transport Layer Security Protocol

Yuhao Han, Libin Wang

Transport Layer Security (TLS) protocols are essential for ensuring the confidentiality, integrity, and authentication of data communications. Mutual authentication between client and server is crucial in high-security scenarios such as finance and government. However, existing TLS protocols typically rely on certificate-based public key infrastructures (PKI) for client authentication, which increases deployment complexity and introduces risks associated with third-party trust. In contrast, password-authenticated TLS protocols use memorable passwords for client authentication, offering advantages in simplicity and usability. Nonetheless, such protocols remain vulnerable to server compromise and fail to provide sufficient security against quantum adversaries.To address these challenges, we propose a novel TLS protocol based on asymmetric password-authenticated key exchange (PAKE). The protocol employs an asymmetric PAKE mechanism wherein only password-derived information is stored on the server, while the client derives its private key from the password. This design effectively mitigates the risk of server leakage attacks. The protocol further integrates two types of post-quantum secure key encapsulation mechanisms (KEMs): an OW-ChCCA (One-Way Checkable against Chosen-Ciphertext Attacks) secure KEM for server key exchange and authentication, and an OW-PCA (One-Way Plaintext-Checkable Attacks) secure KEM for binding the client’s password-derived private key to enable client authentication. Both KEMs support multi-user, multi-challenge settings and admit tight, post-quantum secure instantiations.Furthermore, this paper provides a formal security analysis of the proposed protocol within an optimized multi-stage key exchange model. By combining the random oracle and ideal cipher models with a game-based proof methodology, we demonstrate that the protocol achieves mutual authentication and forward secrecy, while also providing tight security bounds and post-quantum resilience. This work thus presents a promising solution for constructing post-quantum password-authenticated TLS protocols.

International Conference on Blockchain Technology and Information Security (ICBCTIS)•Dec 5, 2025•0 citations

The Universal Composable Security of Quantum Key Distribution

Michael Ben-Or, Michał Horodecki, Debbie Leung +2 more

arXiv:quant-ph/0409078•Lecture notes in computer science•Jan 1, 2005•225 citations
Practical deployments of key encapsulation mechanisms (KEMs) may entail large servers each using their public keys to communicate with potentially millions of clients simultaneously. While the standard IND-CCA security definition for KEMs considers only a single challenge public key and single challenge ciphertext, it can be relevant to consider multi-target scenarios where the adversary aims to break one of many challenge ciphertexts, for one of many challenge public keys. Many post-quantum KEMs have been built by applying the Fujisaki-Okamoto (FO) transform to a public key encryption (PKE) scheme. Although the FO transform incurs only a few bits of security loss for the standard, single-challenge IND-CCA property, this does not hold in the multi-target setting. Attacks have been identified against standards-track FO-based KEMs with 128-bit message spaces (FrodoKEM-640 and HQC-128) which become feasible if the adversary is given many challenge ciphertexts (say, 2^64). These attacks exploit the deterministic encryption induced by the FO transform which allows the IND-CCA experiment to be reduced to a search problem on the message space, which in some cases may not be large enough to avoid collisions between pre-computation and challenge values. A cost effective way to amplify the hardness of this search problem is to add a random but public salt during encapsulation. While revised versions of FrodoKEM and HQC have used salts, there has been no proof showing that salting provides multi-ciphertext security. In this work, we formally analyze a salted variant of the Fujisaki-Okamoto transform, in the classical and quantum random oracle model (ROM); for the classical ROM, we show that multi-target IND-CCA security of the resulting KEM tightly reduces to the multi-target IND-CPA security of the underlying PKE. Our results imply that, for FrodoKEM and HQC at the 128-bit security level, replacing the FO transform with the salted variant can recover 62 bits of multi-target security, at the cost of a very small overhead increase.
Transport Layer Security (TLS) protocols are essential for ensuring the confidentiality, integrity, and authentication of data communications. Mutual authentication between client and server is crucial in high-security scenarios such as finance and government. However, existing TLS protocols typically rely on certificate-based public key infrastructures (PKI) for client authentication, which increases deployment complexity and introduces risks associated with third-party trust. In contrast, password-authenticated TLS protocols use memorable passwords for client authentication, offering advantages in simplicity and usability. Nonetheless, such protocols remain vulnerable to server compromise and fail to provide sufficient security against quantum adversaries.To address these challenges, we propose a novel TLS protocol based on asymmetric password-authenticated key exchange (PAKE). The protocol employs an asymmetric PAKE mechanism wherein only password-derived information is stored on the server, while the client derives its private key from the password. This design effectively mitigates the risk of server leakage attacks. The protocol further integrates two types of post-quantum secure key encapsulation mechanisms (KEMs): an OW-ChCCA (One-Way Checkable against Chosen-Ciphertext Attacks) secure KEM for server key exchange and authentication, and an OW-PCA (One-Way Plaintext-Checkable Attacks) secure KEM for binding the client’s password-derived private key to enable client authentication. Both KEMs support multi-user, multi-challenge settings and admit tight, post-quantum secure instantiations.Furthermore, this paper provides a formal security analysis of the proposed protocol within an optimized multi-stage key exchange model. By combining the random oracle and ideal cipher models with a game-based proof methodology, we demonstrate that the protocol achieves mutual authentication and forward secrecy, while also providing tight security bounds and post-quantum resilience. This work thus presents a promising solution for constructing post-quantum password-authenticated TLS protocols.