Paper 2022/1404

Reducing an LWE Instance by Modular Hints and its Applications to Primal Attack, Dual Attack and BKW Attack

Abstract

An emerging direction of investigating the resilience of post-quantum cryptosystems under side-channel attacks is to consider the situations where leaked information is combined with traditional attack methods in various forms. In CRYPTO 2020, Dachman-Soled et al. integrated hints from side-channel information to the primal attack against LWE schemes. This idea is further developed in this paper. An accurate characterization of the information from perfect hints and modular hints is obtained through the establishment of an interesting decomposition of $\mathbb{Z}^n$. It is observed that modular hints with modulus $p$ produce some orthogonal projection of the secret in $\mathbb{Z}_p$, which is exactly an extension of the case of perfect hints in $\mathbb{R}$. Based on these, a new attack framework is described when some modular hints with modulus $q$ are available. In this framework, an adversary first reduces the LWE instance using such hints, and then performs various attacks on the new instance. One of the key characters of our framework is that the dimension of the secret in the new instance always decreases under some moderate conditions. A comparison with the previous work shows that our approach is in some sense more essential and applicable to various kinds of attacks. The new way of integrating modular hints to primal attack improves the existing work. The first attempt of using modular hints in dual attack and BKW attack is also discussed in the paper and better analysis results are produced. Experiments have been carried out and shown that multiple modular hints with modulus $q$ can indeed significantly reduce their attack costs. For examples, with just 100 hints, the blocksize can be reduced by 101 and the time complexity can be reduced by a factor of $2^{30}$ in both primal attack and dual attack against a Newhope1024 instance. As for the BKW attack, if 90 hints are available, the number of queries to the LWE oracle can be decreased by a factor of $2^{60}$, as do the time complexity and memory complexity when attacking an instance of Regev cryptosystem $(384,147457,39.19)$.