NGUYEN Thi – Cryptanalysis of LWE with side information

DDGR framework [DSDGR20] was introduced in Crypto 2020 as the first cryptanalysis framework that estimates the impact of some types of side information on the security of Learning with Errors (LWE). Side information can come from many sources either from the construction itself or from the implementation leakage. Some of them can be categorized into perfect hint, modular hint, approximating hint and short vector hint. DDGR examines the impact of these hints by gradually integrating them into the given LWE instance, constructing a new Short Vector Problem (SVP) instance that could be easier (or not) to solve via lattice reduction than the original LWE’s SVP. In Asiacrypt 2023, May et al discovered the « Too many hints” regime [MN23] in which the LWE instances can be practically broken by LLL given a certain number of certain types of hint (for example, n/2 perfect hints with n being the dimension of LWE’s secret). The successful attack in this regime is not predictable by DDGR’s estimator. In this talk, I will explain this mystery which is related to that « random hint » and « non-random hint » have different impacts on lattice reduction.