How hard is deciding trivial versus non-trivial in the dihedral coset problem
- LecturerMr. Nai-Hui, Chia (Ph.D. Candidate, Penn State University)
Host: Kai-Min Chung - Time2015-12-16 (Wed.) 15:00 ~ 17:00
- LocationAuditorium 101 at IIS new Building
Abstract
The dihedral coset problem (DCP) is an important open problem in quantum algorithms and has been studied since the early days of quantum computing. This problem attracts attention even from experts in cryptography due to its application to the lattice-based cryptosystems. It has been shown by Oded Regev in 2005 that the DCP has deep connections to the unique shortest vector problem and the random subset sum problem. One of the implications is that solving the DCP could provide a pathway to a quantum algorithm for lattice problems. On the other hand, it is still open if an efficient quantum algorithm for the DCP solves the random subset sum with a constant density which problem is though to be hard in cryptography.
In this talk, I will first present a relaxed definition of the dihedral coset problem, which we call the dihedral coset space problem (DCSP). I will then discuss some reducibility relations between the DCP, the DCSP, the random subset sum problem and the unique shortest vector problem. The DCSP turns out to be equivalent to the DCP for some settings of parameters. Furthermore, the unique shortest vector problem also reduces to the DCSP. In the last, though we have been able to efficiently solve the DCSP, I will show our approach to this problem and some hardness results.
Joint work with Sean Hallgren.