Solving LWR via BDD Strategy: Modulus Switching Approach
RIS ID
131119
Abstract
The typical approach in attacking an LWR m,n,q,p(χs) instance parameterized by four integers m, n, q, p (q≥p) and a probability distribution χs is just by simply regarding it as a Learning with Errors (LWE) modulo q instance and then trying to adapt known LWE attacks to this LWE instance. In this paper, we show that for an LWR m,n,q,p(χs) instance whose parameters satisfy a certain sufficient condition, one can use the BDD strategy to recover the secret with higher advantages if one transforms the LWR instance to an LWE modulo q′ instance with q′ chosen appropriately instead of an LWE modulo q instance. The optimal modulus q′ used in our BDD attack is quite close to p as well as typically smaller than q. Especially, our experiments confirm that our BDD attack is much better in solving search-LWR in terms of root Hermite factor, success probability and even running time either in case the ratio log(q)/log(p) is big or/and the dimension n is sufficiently large.
Publication Details
Le, H., Mishra, P., Duong, D. Hoang. & Yasuda, M. (2018). Solving LWR via BDD Strategy: Modulus Switching Approach. Lecture Notes in Computer Science, 11124 357-376. Cryptology and Network Security 17th International Conference, CANS 2018, Naples, Italy, September 30 - October 3, 2018, Proceedings