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

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(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(eff) -invariance configurations, spanning fan-out N-t is an element of( ){1,...,32} , hash budgets q(H) up to 2(20) , five lambda(eff) values, and three post-selection rates. Under strict oracle hygiene, the measured tightness gap concentrates at Gamma = 1.022 +/- 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.