all InfoSec news
Quantum Algorithms for Lattice Problems
April 10, 2024, 3:54 p.m. |
IACR News www.iacr.org
ePrint Report: Quantum Algorithms for Lattice Problems
Yilei Chen
We show a polynomial time quantum algorithm for solving the learning with errors problem (LWE) with certain polynomial modulus-noise ratios. Combining with the reductions from lattice problems to LWE shown by Regev [J.ACM 2009], we obtain polynomial time quantum algorithms for solving the decisional shortest vector problem (GapSVP) and the shortest independent vector problem (SIVP) for all $n$-dimensional lattices within approximation factors of $\tilde{\Omega}(n^{4.5})$. Previously, no polynomial or even subexponential time …
acm algorithm algorithms chen eprint report errors noise problem problems quantum quantum algorithms report
More from www.iacr.org / IACR News
Jobs in InfoSec / Cybersecurity
Social Engineer For Reverse Engineering Exploit Study
@ Independent study | Remote
Information Security Specialist, Sr. (Container Hardening)
@ Rackner | San Antonio, TX
Principal Security Researcher (Advanced Threat Prevention)
@ Palo Alto Networks | Santa Clara, CA, United States
EWT Infosec | IAM Technical Security Consultant - Manager
@ KPMG India | Bengaluru, Karnataka, India
Security Engineering Operations Manager
@ Gusto | San Francisco, CA; Denver, CO; Remote
Network Threat Detection Engineer
@ Meta | Denver, CO | Reston, VA | Menlo Park, CA | Washington, DC