Bit Security Analysis of Lattice-Based KEMs Under Plaintext-Checking Attacks

Plaintext-checking attack (PCA) is a type of attack where an adversary recovers the secret key with the help of a plaintext-checking (PC) oracle that decides if a given ciphertext decrypts to a given plaintext. In particular, PCA exists in both the key misuse attacks for IND-CPA-secure lattice-based KEMs and generic side-channel attacks for IND-CCA-secure lattice-based KEMs. The query number of PC-oracle is a vital criterion for evaluating a PCA attack. Recently, Qin et al. [ASIACRYPT 2021] gave a systematic approach to finding the theoretical lower bound of PC-oracle query numbers for NIST-PQC lattice-based KEMs. Most of the prior works consider the substantial Oracle queries needed to recover the entire key. However, the adversary often has inadequate access to PC Oracles to fully recover the secret key. The concrete bit security loss with arbitrary PC Oracle access is unknown. In this paper, we give a unified method to analyze the bit security loss with arbitrary PC Oracle access for lattice-based KEMs. First, we model the information leakage in the PC Oracle by PC-hint, and give a generic transformation from PC-hints to the perfect inner-product hint, which allows the adversary to integrate PC-hints progressively. Then, following the security analysis for LWE with the perfect inner-product hint given in Dachman-Soled et al. [CRYPTO 2020], we give a concrete relationship between the PC Oracle query number and the bit-security of the lattice-based KEM under PCA. Our proposed method is applicable to all CCA-secure NIST candidate lattice-based KEMs. Applying our methods to NIST-PQC lattice-based KEMs, we get the bit-security loss of the lattice-based KEM under PCA. Take Kyber768 (original 182-bit-security) as an example, the bit security of Kyber768 is reduced to 128 after 444 PC-oracle queries and reduced to 64 after 998 PC-oracle queries, while in Qin et al. [ASIACRYPT 2021] 1774 queries are required to recover the whole secret key. Our analysis also demonstrates the possibility of reducing the Oracle queries needed in PCA. The adversary may stop querying plaintext-checking oracle and solves the remaining part of reused secret offline with the help of lattice reduction algorithms when the cost of lattice reduction algorithms becomes acceptable.