How hard is deciding trivial versus non-trivial in the dihedral coset problem
Nai-Hui Chia, Pennsylvania State University
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. It is still open if an efficient quantum algorithm for the DCP solves the random subset sum with a constant density.
In this talk, I will first define the DCP and then discuss some reducibility relations between DCP, the random subset sum problem and the unique shortest vector problem. I will then present a relaxed definition of the dihedral coset problem, which we call dihedral coset space problem (DCSP). DCSP turns out to be equivalent to DCP for some settings of parameters. Finally, I will also show that if efficient unitaries exist that can solve the DCSP in certain restricted ways, those unitaries can be used to solve random subset sum with density a constant greater than 1.
Joint work with Sean Hallgren.