An Improved Key Mismatch Attack on Kyber

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.