Paper 2022/1580

Multi-ciphertext security degradation for lattices

Abstract

Typical lattice-based cryptosystems are commonly believed to resist multi-target attacks. For example, the New Hope proposal stated that it avoids "all-for-the-price-of-one attacks". An ACM CCS 2021 paper from Duman–Hövelmanns–Kiltz–Lyubashevsky–Seiler stated that "we can show that Adv_{PKE}^{IND-CPA} ≈ Adv_{PKE}^{(n,q_C)-IND-CPA} for "lattice-based schemes" such as Kyber, i.e. that one-out-of-many-target IND-CPA is as difficult to break as single-target IND-CPA, assuming "the hardness of MLWE as originally defined for the purpose of worst-case to average-case reductions". Meanwhile NIST expressed concern regarding multi-target attacks against non-lattice cryptosystems. This paper quantifies the asymptotic impact of multiple ciphertexts per public key upon standard analyses of known primal lattice attacks, assuming existing heuristics. The qualitative conclusions are that typical lattice PKEs asymptotically degrade in heuristic multi-ciphertext IND-CPA security as the number of ciphertexts increases. These PKE attacks also imply multi-ciphertext IND-CCA2 attacks against typical constructions of lattice KEMs. Quantitatively, the asymptotic heuristic security degradation is exponential in Θ(n) for decrypting many ciphertexts, cutting a constant fraction out of the total number of bits of security, and exponential in Θ(n/log n) for decrypting one out of many ciphertexts, for conservative cryptosystem parameters. This shows a contradiction between the existing heuristics and the idea that multi-target security matches single-target security. Also, whether or not the existing heuristics are correct, (1) there are flaws in the claim of an MLWE-based proof of tight multi-target security, and (2) there is a 2^{88}-guess attack breaking one out of 2^{40} ciphertexts for a FrodoKEM-640 public key, disproving FrodoKEM's claim that "the FrodoKEM parameter sets comfortably match their target security levels with a large margin".