Recently, American National Institute of Standards and Technology (NIST) announced Kyber as the first KEM candidate to be standardized. The security of Kyber is based on the modular learning with errors (MLWE) problem, which achieves excellent efficiency and size. This work proposes an improved key mismatch on Kyber, which can reduce the number of queries required to recover the secret key. We first transform the problem of finding a certain parameter of ciphertexts into a quantum ordered search problem. Then we give the procedure of finding the value of a parameter in the ciphertexts by the quantum method. Finally, we instantiate this attack method on Kyber512, Kyber768 and Kyber1024. Compared with the existing attack algorithm, our improved attack reduces the number of queries for Kyber512, Kyber768 and Kyber1024 by 63%, 59% and 45%, respectively.
Recently, American National Institute of Standards and Technology (NIST) announced Kyber as the first KEM candidate to be standardized. The security of Kyber is based on the modular learning with errors (MLWE) problem, which achieves excellent efficiency and size. This work proposes an improved key mismatch on Kyber, which can reduce the number of queries required to recover the secret key. We first transform the problem of finding a certain parameter of ciphertexts into a quantum ordered search problem. Then we give the procedure of finding the value of a parameter in the ciphertexts by the quantum method. Finally, we instantiate this attack method on Kyber512, Kyber768 and Kyber1024. Compared with the existing attack algorithm, our improved attack reduces the number of queries for Kyber512, Kyber768 and Kyber1024 by 63%, 59% and 45%, respectively.
Abstract Quantum algorithm uses the quantum parallel method to calculate, which can better solve the encryption and decryption problems in cryptography and secure communication. This paper proposeS a quantum pairwise-parallel mismatch attack on Kyber using the quantum binary search method. We first give quantum search methods for finding the secret key and show that our method can be applied to Kyber. Then, According to the proposed quantum search method, we compute the number of queries required and computational complexity for recovering the full key on Kyber. Compared with the existing results, our improved attack significantly reduces the number of queries and computational complexity.
The concatenation of encryption and decryption can be interpreted as data transmission over a noisy communication channel. In this work, we use finite blocklength methods (normal approximation and random coding union bound) as well as asymptotics to show that ciphertext and key sizes of the state-of-the-art post-quantum secure key encapsulation mechanism (KEM) Kyber can be reduced without compromising the security of the scheme. We show that in the asymptotic regime, it is possible to reduce the sizes of ciphertexts and secret keys by 25% for the parameter set Kyber1024 while keeping the bitrate at 1 as proposed in the original scheme. For a single Kyber encryption block used to share a 256-bit AES key, we furthermore show that reductions in ciphertext size of 39% and 33% are possible for Kyber1024 and Kyber512, respectively.
In post-quantum cryptography (PQC), Learning With Errors (LWE) is one of the dominant underlying mathematical problems. For example, in NIST’s PQC standardization process, the Key Encapsulation Mechanism (KEM) protocol chosen for standardization was Kyber, an LWE-based scheme. Recently the dual attack surpassed the primal attack in terms of concrete complexity for solving the underlying LWE problem for multiple cryptographic schemes, including Kyber. The dual attack consists of a reduction part and a distinguishing part. When estimating the cost of the distinguishing part, one has to estimate the expected cost of enumerating over a certain number of positions of the secret key. Our contribution consists of giving a polynomial-time approach for calculating the expected complexity of such an enumeration procedure. This allows us to revise the complexity of the dual attack on the LWE-based protocols Kyber, Saber and TFHE. For all these schemes we improve upon the total bit-complexity in both the classical and the quantum setting.As our method of calculating the expected cost of enumeration is fairly general, it might be of independent interest in other areas of cryptography or even in other research areas.
In order to resist the security risks caused by quantum computing, post-quantum cryptography (PQC) has been a research focus. Constructing a key encapsulation mechanism (KEM) based on lattices is one of the promising PQC routines. The algebraically structured learning with errors (LWE) problem over power-of-two cyclotomics has been one of the most widely used hardness assumptions for lattice-based cryptographic schemes. However, power-of-two cyclotomic rings may be exploited in the inflexibility of selecting parameters. Recently, trinomial cyclotomic rings of the form Zq[x]/(xn−xn/2+1), where n=2k3l, k≥1,l≥0, have received widespread attention due to their flexible parameter selection. In this paper, we propose Tyber, a variant scheme of the NIST-standardized KEM candidate Kyber over trinomial cyclotomic rings. We provide three parameter sets, aiming at the quantum security of 128, 192, and 256 bits (actually achieving 129, 197, and 276 bits) with matching and negligible error probabilities. When compared to Kyber, our Tyber exhibits stronger quantum security, by 22, 31, and 44 bits, than Kyber for three security levels.
The widespread use of Internet of Things devices alongside advances in quantum computing presents urgent challenges for secure communication. RSA and ECC have become inadequate, prompting the need for Post-quantum Cryptography (PQC). This work introduces a novel reconciliation-based Module-LWE key exchange protocol that eliminates the traditional encapsulation-decapsulation structure in schemes like Kyber.KE, thereby reducing computational cycles, communication size, and memory footprint. Unlike Kyber and NewHope, the proposed design employs modular rounding with Peikert reconciliation, optimizing the entire key exchange process without requiring additional randomness or ciphertext transmission. By leveraging Peikert’s error reconciliation technique and modular rounding, the proposed protocol achieves a 15% reduction in computational cycles, a 78-byte reduction in communication size, and a 10% decrease in memory usage. Using Open Quantum Safe (OQS) benchmark data, we evaluate performance across Kyber512, Kyber768, and Kyber1024 levels, demonstrating the protocol’s superior energy efficiency and lightweight design. These improvements position our protocol as a secure, efficient, and scalable solution for post-quantum key exchange in resource-constrained environments such as embedded systems and IoT networks.
The imminent arrival of quantum computing has accelerated the need for cryptographic systems resistant to quantum attacks. Such attacks exploit the vulnerability in private and public key encryption systems, where the public key is derived from the private key, which could be refactored from the public key. To address this issue, the National Institute of Standards and Technology (NIST) launched a global competition in 2016 to create quantum-resistant algorithms. CRYSTALS-Kyber, a lattice-based algorithm focused on the learning with errors (LWE) problem, was selected for standardization. This work introduces RKyber, a variant that instead targets the learning with rounding (LWR) problem, simplifying computations by using deterministic errors rather than random noise. Both algorithms were executed 1000 times, showing that RKyber offers improved speed at the cost of some security.