Fada Li, Wansu Bao, Xiangqun Fu, Yuchao Zhang, Tan Li
Learning with Errors (LWE) problems are the foundations for numerous applications in lattice-based cryptography and are prov-ably as hard as approximate lattice problems in the worst case. The fastest known classical algorithm takes exponential time, and prior to our work no faster quantum algorithm was known. It would therefore be highly desirable to make algorithmic improvement on LWE. Here we propose a subexponential-time quantum algorithm for LWE problem.The algorithm is based on a reduction to a two point problem and a new reduction from two point problem to dihedral coset problem. Our algorithm introduces the method that may be applicable to other lattice problems.
View original:
http://arxiv.org/abs/1305.3769
No comments:
Post a Comment