中央研究院 資訊科學研究所

活動訊息

友善列印

列印可使用瀏覽器提供的(Ctrl+P)功能

How hard is deciding trivial versus non-trivial in the dihedral coset problem

:::

How hard is deciding trivial versus non-trivial in the dihedral coset problem

  • 講者Nai-Hui, Chia 先生 (Ph.D. Candidate, Penn State University)
    邀請人:鐘楷閔
  • 時間2015-12-16 (Wed.) 15:00 ~ 17:00
  • 地點資訊所新館101演講廳
摘要

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.