Time and Query Complexity Tradeoffs for the Dihedral Coset Problem

International audienceThe Dihedral Coset Problem (DCP) in ZN has been extensively studied in quantum computing and post-quantum cryptography, as for instance, the Learning with Errors problem reduces to it. While the Ettinger-Høyer algorithm is known to solve the DCP in O (log N) queries, it runs inefficiently in time O (N). The first time-efficient algorithm was introduced (and later improved) by Kuperberg (SIAM J. Comput. 2005). These algorithms run in a subexponential amount of time and queries Õ 2 √ c DCP log N , for some constant c DCP. The sieving algorithms à la Kuperberg admit many trade-offs between quantum and classical time, memory and queries. Some of these trade-offs allow the attacker to reduce the number of queries if they are particularly costly, which is notably the case in the post-quantum key-exchange CSIDH. Such optimizations have already been studied, but they typically fall into two categories: the resulting algorithm is either based on Regev's approach of reducing the DCP with quadratic queries to a subset-sum instance, or on a re-optimization of Kuperberg's sieve where the time and queries are both subexponential. In this paper, we introduce the first algorithm to improve in the linear queries regime over the Ettinger-Høyer algorithm. We then show that we can in fact interpolate between this algorithm and Kuperberg's sieve, by using the latter in a pre-processing step to create several quantum states, and solving a quantum subset-sum instance to recover the full secret in one pass from the obtained states. This allows to interpolate smoothly between the linear queries-exponential time complexity case and the subexponential query and time complexity case, thus allowing a fine tuning of the complexity taking into account the query cost. We also give on our way a precise study of quantum subset-sum algorithms in the non-asymptotic regime