Repository Collection: null

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

2026-06-30T15:00:00Z

Title: Q-AMT: Multi-Target Security Assessment for Lattice KEMs Author(s): Kim, Gwang-Sik; Kim, Young-Sik 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.

Fast polynomial inversion algorithms for the post-quantum cryptography

2025-07-31T15:00:00Z

Title: Fast polynomial inversion algorithms for the post-quantum cryptography Author(s): Seo, Eun-Young; Kim, Young-Sik; No, Jong-Seon Abstract: Several cryptosystems suggested for the post-quantum cryptography candidates, including Falcon, BIKE, and NTRU, are defined in a polynomial ring. They must derive the inverse polynomial of any given polynomial for generating a public key. This process consumes considerable processing time; therefore, reducing the time to derive the inverse polynomial significantly improves many cryptosystems’ performance. In this paper, we primarily suggest two polynomial inversion algorithms, combined-variable-time and combined-constant-time algorithms, based on the modification of the extended Euclidean algorithm. The combined-variable-time algorithm shows how to calculate the inverse polynomial by introducing the combined matrix fast, which is generated by merging several steps of the polynomial operations. In cryptosystems, to defend against side-channel attacks, the implementation with constant running time is essential in preventing information leakage. Thus, we propose the combined-constant-time polynomial inversion algorithm, which expends less running time than the conventional NTRU inversion algorithm. For binary polynomial inversion, the proposed combined-variable-time algorithm is 1.95 times faster than the variable-time algorithm used in the previous NTRU (Silverman Almost inverses and fast NTRU key creation, NTRU Tech Report, no. 014v1, Mar. 15, 1999), and the combined-constant-time algorithms are 1.43 times faster than the reference constant-time algorithms submitted to round 3 of the NIST PQC standardization, respectively. For ternary polynomial inversion, the proposed combined-variable-time and combined-constant-time algorithms are 1.59 and 1.29 times faster than the corresponding reference algorithms. © 2025 Elsevier B.V., All rights reserved.

Channel-Hopping Sequence and Searching Algorithm for Rendezvous of Spectrum Sensing

2024-12-31T15:00:00Z

Title: Channel-Hopping Sequence and Searching Algorithm for Rendezvous of Spectrum Sensing Author(s): Choi, Young-June; Kim, Young-Sik; Jang, Ji-Woong Abstract: In this paper, we propose a method for applying the p-ary m-sequence as a channel-searching pattern for rendezvous in the asymmetric channel model of cognitive radio. We mathematically analyzed and calculated the ETTR when the m-sequence is applied to the conventional scheme, and our simulation results demonstrated that the ETTR performance is significantly better than that of the JS algorithm. Furthermore, we introduced a new channel-searching scheme that maximizes the benefits of the m-sequence and proposed a method to adapt the generation of the m-sequence for use in the newly proposed scheme. We also derived the ETTR mathematically for the new scheme with the m-sequence and showed through simulations that the performance of the new scheme with the m-sequence is superior to that of the conventional scheme with the m-sequence. Notably, when there is only one common channel, the new scheme with the m-sequence achieved approximately four times the improvement in the ETTR compared to the conventional scheme. © 2024 by the authors.

Lazy Modular Reduction for NTT

2024-11-30T15:00:00Z

Title: Lazy Modular Reduction for NTT Author(s): Kim, Geumtae; Seo, Eun-Young; Lee, Yongwoo; Kim, Young-Sik; No, Jong-Seon Abstract: The number theoretic transform (NTT) is a fundamental operation in cryptography, especially for lattice-based cryptographic schemes. This paper introduces LazyNTT, a novel method that reduces the number of Montgomery multiplications required in the NTT computation by replacing some of them with standard multiplication without modular reduction. This approach enhances the performance of the NTT computation and modular polynomial multiplication in lattice-based cryptographic schemes. The proposed LazyNTT can be generalized by increasing the number of standard multiplications. The experimental results show that the proposed LazyNTT improves the cycle counts of the NTT by up to (Formula presented.) and (Formula presented.), respectively, by allowing two and one standard multiplications. © 2024 by the authors.