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

IEEE Access

Q-AMT: Multi-Target Security Assessment for Lattice KEMs

Gwang-Sik Kim, Young-Sik Kim

Published Jan 1, 2026• 0 citations
Publisher

Abstract

Security reductions for Fujisaki–Okamoto (FO)-style lattice key-encapsulation mechanisms (KEMs) in the quantum random-oracle model (QROM) incur non-tight loss terms that grow with an adversary’s oracle access and the number of simultaneously attacked targets. While these losses are well characterized theoretically, their practical impact at deployment scale—where thousands of public keys may coexist under a single administrative domain—has not been systematically quantified. We present Q-AMT (QROM-motivated Amplified Multi-Target), a scheme-agnostic measurement framework that makes these losses operational for engineering decisions. Q-AMT formalizes a multi-target adversary model, derives practical surrogates for multi-target advantage, and defines a tightness gap metric $\Gamma $ that compares measured multi-target advantage to single-target baselines. The framework provides a round-based scheduler that allocates oracle budgets across targets, controls post-selection, and toggles oracle-hygiene configurations (domain separation and binding of KDF inputs to public-key–ciphertext context). We explicitly frame our classical proxy parameter $q_{G}$ as a concavity-sharing diagnostic—a tool for traversing the concavity regime of the single-target advantage function—rather than a simulation of quantum superposition queries. We prove that the resulting $\Gamma $ metric is invariant to the choice of concavity model and to the absolute security level, so that relative results at reduced $\lambda _{\mathrm {eff}}$ transfer to production-scale $\lambda = 128$ . We instantiate Q-AMT across representative lattice KEM families—MLWE/MLWR (ML-KEM/Kyber, SABER), NTRU-style (NTRU+), and FO-variant profiles—under constant-time, implicitly rejecting implementations and evaluate 1,056 configurations, including $192~\lambda _{\mathrm {eff}}$ -invariance configurations, spanning fan-out $N_{t} \in \{1,\ldots,32\}$ , hash budgets $q_{H}$ up to $2^{20}$ , five $\lambda _{\mathrm {eff}}$ values, and three post-selection rates. Under strict oracle hygiene, the measured tightness gap concentrates at $\Gamma = 1.022 \pm 0.310$ across all configurations; disabling separation and/or binding raises the mean to $\Gamma = 1.127$ with peaks near 2.0, confirming super-linear multi-target amplification from cross-target coupling, consistent with the formal multi-user QROM analysis of Duman et al. (2021). From the measured surfaces we extract operator-facing guidance: safe per-key query caps for given fan-out and acceptance rates, a worked 10,000-key enterprise deployment example, and an overhead–risk frontier showing that redundant FO/FO ${}^{\perp }$ validation incurs 2–4% overhead across five hardware platforms (Cortex-M4/M7, ARMv8-A, x86-64, RISC-V) while substantially reducing the effective success probability of validation bypasses—even under targeted structural faults. Q-AMT does not directly compromise lattice KEMs; rather, it quantifies residual risk from multi-user accumulation and turns it into concrete engineering guidance.

DOI
10.1109/access.2026.3710172

Related papers

NIST’s Module-Lattice-Based Key-Encapsulation Mechanism and its security

Anna Jokiniemi

This thesis is an in-depth introduction to NIST's post-quantum Module-Lattice-Based Key-Encapsulation Mechanism (ML-KEM). We begin by introducing the problem at the core of ML-KEM, known as the Module Learning With Errors (MLWE) problem. In this problem, an adversary attempts to distinguish between samples selected from a specific distribution and samples from uniformly random samples. We also discuss the hardness of the MLWE problem, under the conjecture that certain lattice problems over modules are hard. ML-KEM utilizes a variant of the Fujisaki-Okamoto transformation, which employs a weakly secure Public-Key Encryption (PKE) scheme to construct a strongly secure key-encapsulation mechanism in the Random Oracle Model (ROM). We explain the working principle of the MLWE-based public-key encryption scheme and demonstrate how ML-KEM is constructed from it. Finally, we analyze the security of ML-KEM. We provide a tight security bound for IND-CCA security of ML-KEM in ROM, under the assumption that the underlying PKE is IND-CPA secure. Additionally, we present two security theorems in the Quantum Random Oracle Model (QROM). The first theorem establishes non-tightly IND-CCA security of ML-KEM in QROM if the MLWE problem is hard to solve. The second theorem assumes that the deterministic PKE is ciphertext-indistinguishable. Under this assumption, we derive a tighter bound for the IND-CCA security of ML-KEM in QROM.

Työväentutkimus Vuosikirja•Feb 26, 2025•0 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

Enhancing Post-Quantum KEMs: A Secure and Efficient Transformation

Sai Charan Reddy Nevuri

This paper proposes a new generic Encrypt-thenMAC (EtM) transformation for constructing IND-CCA secure Key Encapsulation Mechanisms (KEMs) in the post-quantum setting. The transformation builds on a public-key encryption scheme satisfying one-wayness under plaintext-checking attacks (OW-PCA) and an existentially unforgeable MAC, and formally achieves tight IND-CCA security in the random oracle model via a rigorous security reduction. Unlike the widely used FujisakiOkamoto (FO) transformation, our approach eliminates the need for ciphertext re-encryption during decapsulation-a major source of computational overhead and side-channel vulnerability in lattice-based implementations. We instantiate the transformation using the ML-KEM (FIPS 203) subroutine, yielding the ML-KEM-EtM variant. Experimental results show that ML-KEMEtM reduces decapsulation cycle counts by$72-79 {\%}$across security levels, with only a modest increase in encapsulation cost$(1.8-7.3 {\%})$and ciphertext size$(1.0-2.1 {\%})$. The scheme thus offers a practical and efficient a lternative to F O-based KEMs, especially in performance-critical scenarios such as post-quantum TLS handshakes, where decapsulation efficiency is paramount.

International Symposium on Digital Forensics and Security (ISDFS)•Mar 19, 2026•0 citations

Faster Lattice-Based KEMs via a Generic Fujisaki-Okamoto Transform Using Prefix Hashing

Julien Duman, Kathrin Hövelmanns, Eike Kiltz +2 more

Constructing an efficient CCA-secure KEM is generally done by first constructing a passively-secure PKE scheme, and then applying the Fujisaki-Okamoto (FO) transformation. The original FO transformation was designed to offer security in a single user setting. A stronger notion, known as multi-user security, considers the attacker's advantage in breaking one of many user's ciphertexts. Bellare et al. (EUROCRYPT 2000) showed that standard single user security implies multi-user security with a multiplicative tightness gap equivalent to the number of users.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Nov 12, 2021•33 citations

CRYSTALS - Kyber: A CCA-Secure Module-Lattice-Based KEM

Joppe W. Bos, Léo Ducas, Eike Kiltz +6 more

Rapid advances in quantum computing, together with the announcement by the National Institute of Standards and Technology (NIST) to define new standards for digitalsignature, encryption, and key-establishment protocols, have created significant interest in post-quantum cryptographic schemes. This paper introduces Kyber (part of CRYSTALS - Cryptographic Suite for Algebraic Lattices - a package submitted to NIST post-quantum standardization effort in November 2017), a portfolio of post-quantum cryptographic primitives built around a key-encapsulation mechanism (KEM), based on hardness assumptions over module lattices. Our KEM is most naturally seen as a successor to the NEWHOPE KEM (Usenix 2016). In particular, the key and ciphertext sizes of our new construction are about half the size, the KEM offers CCA instead of only passive security, the security is based on a more general (and flexible) lattice problem, and our optimized implementation results in essentially the same running time as the aforementioned scheme. We first introduce a CPA-secure public-key encryption scheme, apply a variant of the Fujisaki-Okamoto transform to create a CCA-secure KEM, and eventually construct, in a black-box manner, CCA-secure encryption, key exchange, and authenticated-key-exchange schemes. The security of our primitives is based on the hardness of Module-LWE in the classical and quantum random oracle models, and our concrete parameters conservatively target more than 128 bits of postquantum security.

IEEE European Symposium on Security and Privacy•Apr 1, 2018•1,196 citations

Analysis of the FO Transformation in the Lattice-Based Post-Quantum Algorithms

Miguel Ángel González de la Torre, Luis Hernández Encinas, Araceli Queiruga‐Dios

Newer variants of the Fujisaki–Okamoto transformation are used in most candidates of the third round of the NIST Post-Quantum Cryptography standardization call in the category of public key encryption schemes. These transformations are applied to obtain a highly secure key encapsulation mechanism from a less secure public key encryption scheme. Furthermore, there are five candidates (three finalists and two alternatives) that passed to the third round of the process and whose security is based in lattice problems. This work analyzes the different ways in which the lattice-based candidates of the NIST call apply the Fujisaki–Okamoto transformation and the particularities of each application. The study of such differences and their repercussion in the design of the proposals will allow a better understanding of the algorithms. Moreover, we propose a modification of the Kyber algorithm—the only public key encryption candidate established as a PQC standard by NIST in its more recent publication—in order to avoid the re-encryption in the decapsulation algorithm and, in this way, to reduce the side channel attacks vulnerability.

Mathematics•Aug 17, 2022•2 citations
Security reductions for Fujisaki–Okamoto (FO)-style lattice key-encapsulation mechanisms (KEMs) in the quantum random-oracle model (QROM) incur non-tight loss terms that grow with an adversary’s oracle access and the number of simultaneously attacked targets. While these losses are well characterized theoretically, their practical impact at deployment scale—where thousands of public keys may coexist under a single administrative domain—has not been systematically quantified. We present Q-AMT (QROM-motivated Amplified Multi-Target), a scheme-agnostic measurement framework that makes these losses operational for engineering decisions. Q-AMT formalizes a multi-target adversary model, derives practical surrogates for multi-target advantage, and defines a tightness gap metric Γ\Gamma Γ that compares measured multi-target advantage to single-target baselines. The framework provides a round-based scheduler that allocates oracle budgets across targets, controls post-selection, and toggles oracle-hygiene configurations (domain separation and binding of KDF inputs to public-key–ciphertext context). We explicitly frame our classical proxy parameter qGq_{G}qG​ as a concavity-sharing diagnostic—a tool for traversing the concavity regime of the single-target advantage function—rather than a simulation of quantum superposition queries. We prove that the resulting Γ\Gamma Γ metric is invariant to the choice of concavity model and to the absolute security level, so that relative results at reduced λeff\lambda _{\mathrm {eff}}λeff​ transfer to production-scale λ=128\lambda = 128λ=128 . We instantiate Q-AMT across representative lattice KEM families—MLWE/MLWR (ML-KEM/Kyber, SABER), NTRU-style (NTRU+), and FO-variant profiles—under constant-time, implicitly rejecting implementations and evaluate 1,056 configurations, including 192 λeff192~\lambda _{\mathrm {eff}}192 λeff​ -invariance configurations, spanning fan-out Nt∈{1,…,32}N_{t} \in \{1,\ldots,32\}Nt​∈{1,…,32} , hash budgets qHq_{H}qH​ up to 2202^{20}220 , five λeff\lambda _{\mathrm {eff}}λeff​ values, and three post-selection rates. Under strict oracle hygiene, the measured tightness gap concentrates at Γ=1.022±0.310\Gamma = 1.022 \pm 0.310Γ=1.022±0.310 across all configurations; disabling separation and/or binding raises the mean to Γ=1.127\Gamma = 1.127Γ=1.127 with peaks near 2.0, confirming super-linear multi-target amplification from cross-target coupling, consistent with the formal multi-user QROM analysis of Duman et al. (2021). From the measured surfaces we extract operator-facing guidance: safe per-key query caps for given fan-out and acceptance rates, a worked 10,000-key enterprise deployment example, and an overhead–risk frontier showing that redundant FO/FO ⊥{}^{\perp }⊥ validation incurs 2–4% overhead across five hardware platforms (Cortex-M4/M7, ARMv8-A, x86-64, RISC-V) while substantially reducing the effective success probability of validation bypasses—even under targeted structural faults. Q-AMT does not directly compromise lattice KEMs; rather, it quantifies residual risk from multi-user accumulation and turns it into concrete engineering guidance.
This thesis is an in-depth introduction to NIST's post-quantum Module-Lattice-Based Key-Encapsulation Mechanism (ML-KEM). We begin by introducing the problem at the core of ML-KEM, known as the Module Learning With Errors (MLWE) problem. In this problem, an adversary attempts to distinguish between samples selected from a specific distribution and samples from uniformly random samples. We also discuss the hardness of the MLWE problem, under the conjecture that certain lattice problems over modules are hard. ML-KEM utilizes a variant of the Fujisaki-Okamoto transformation, which employs a weakly secure Public-Key Encryption (PKE) scheme to construct a strongly secure key-encapsulation mechanism in the Random Oracle Model (ROM). We explain the working principle of the MLWE-based public-key encryption scheme and demonstrate how ML-KEM is constructed from it. Finally, we analyze the security of ML-KEM. We provide a tight security bound for IND-CCA security of ML-KEM in ROM, under the assumption that the underlying PKE is IND-CPA secure. Additionally, we present two security theorems in the Quantum Random Oracle Model (QROM). The first theorem establishes non-tightly IND-CCA security of ML-KEM in QROM if the MLWE problem is hard to solve. The second theorem assumes that the deterministic PKE is ciphertext-indistinguishable. Under this assumption, we derive a tighter bound for the IND-CCA security of ML-KEM in QROM.
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.
This paper proposes a new generic Encrypt-thenMAC (EtM) transformation for constructing IND-CCA secure Key Encapsulation Mechanisms (KEMs) in the post-quantum setting. The transformation builds on a public-key encryption scheme satisfying one-wayness under plaintext-checking attacks (OW-PCA) and an existentially unforgeable MAC, and formally achieves tight IND-CCA security in the random oracle model via a rigorous security reduction. Unlike the widely used FujisakiOkamoto (FO) transformation, our approach eliminates the need for ciphertext re-encryption during decapsulation-a major source of computational overhead and side-channel vulnerability in lattice-based implementations. We instantiate the transformation using the ML-KEM (FIPS 203) subroutine, yielding the ML-KEM-EtM variant. Experimental results show that ML-KEMEtM reduces decapsulation cycle counts by72−79%72-79 {\%}72−79%across security levels, with only a modest increase in encapsulation cost(1.8−7.3%)(1.8-7.3 {\%})(1.8−7.3%)and ciphertext size(1.0−2.1%)(1.0-2.1 {\%})(1.0−2.1%). The scheme thus offers a practical and efficient a lternative to F O-based KEMs, especially in performance-critical scenarios such as post-quantum TLS handshakes, where decapsulation efficiency is paramount.
Constructing an efficient CCA-secure KEM is generally done by first constructing a passively-secure PKE scheme, and then applying the Fujisaki-Okamoto (FO) transformation. The original FO transformation was designed to offer security in a single user setting. A stronger notion, known as multi-user security, considers the attacker's advantage in breaking one of many user's ciphertexts. Bellare et al. (EUROCRYPT 2000) showed that standard single user security implies multi-user security with a multiplicative tightness gap equivalent to the number of users.
Rapid advances in quantum computing, together with the announcement by the National Institute of Standards and Technology (NIST) to define new standards for digitalsignature, encryption, and key-establishment protocols, have created significant interest in post-quantum cryptographic schemes. This paper introduces Kyber (part of CRYSTALS - Cryptographic Suite for Algebraic Lattices - a package submitted to NIST post-quantum standardization effort in November 2017), a portfolio of post-quantum cryptographic primitives built around a key-encapsulation mechanism (KEM), based on hardness assumptions over module lattices. Our KEM is most naturally seen as a successor to the NEWHOPE KEM (Usenix 2016). In particular, the key and ciphertext sizes of our new construction are about half the size, the KEM offers CCA instead of only passive security, the security is based on a more general (and flexible) lattice problem, and our optimized implementation results in essentially the same running time as the aforementioned scheme. We first introduce a CPA-secure public-key encryption scheme, apply a variant of the Fujisaki-Okamoto transform to create a CCA-secure KEM, and eventually construct, in a black-box manner, CCA-secure encryption, key exchange, and authenticated-key-exchange schemes. The security of our primitives is based on the hardness of Module-LWE in the classical and quantum random oracle models, and our concrete parameters conservatively target more than 128 bits of postquantum security.
Newer variants of the Fujisaki–Okamoto transformation are used in most candidates of the third round of the NIST Post-Quantum Cryptography standardization call in the category of public key encryption schemes. These transformations are applied to obtain a highly secure key encapsulation mechanism from a less secure public key encryption scheme. Furthermore, there are five candidates (three finalists and two alternatives) that passed to the third round of the process and whose security is based in lattice problems. This work analyzes the different ways in which the lattice-based candidates of the NIST call apply the Fujisaki–Okamoto transformation and the particularities of each application. The study of such differences and their repercussion in the design of the proposals will allow a better understanding of the algorithms. Moreover, we propose a modification of the Kyber algorithm—the only public key encryption candidate established as a PQC standard by NIST in its more recent publication—in order to avoid the re-encryption in the decapsulation algorithm and, in this way, to reduce the side channel attacks vulnerability.