论文标题
时间和查询的复杂性权衡二面coset问题
Time and Query Complexity Tradeoffs for the Dihedral Coset Problem
论文作者
论文摘要
$ z_n $中的二面coset问题（DCP）已在量子计算和量词后加密术中进行了广泛的研究，例如，具有错误问题的学习减少了。虽然已知Ettinger-Hoyer算法可以在$ O（log（n））$ Queries中求解DCP，但它在时间$ o（n）$中效率低下。 Kuperberg引入（后来改进）（Siam J.Comput。2005）引入了第一个时间效率的算法。这些算法以次指数的时间运行，查询$ o {2^{\ sqrt {c_ {dcp} log（n）}}} $，对于某些常数$ c_ {dcp} $。 Kuperberg的筛分算法承认，量子和经典时间，记忆和查询之间的许多权衡。这些权衡中的一些使攻击者可以减少查询数量特别昂贵的数量，这在Quantum后钥匙交换CSIDH中尤其是这种情况。此类优化已经研究了，但通常分为两类：由此产生的算法是基于Regev用二次查询将DCP减少到子集中的实例的方法，或者基于在时间和Queries的筛子中重新审视时，时间和Queries均为两种次数。 在本文中，我们介绍了第一种算法，以改善Ettinger-Hoyer算法的线性查询态度。然后，我们证明我们实际上可以通过在预处理步骤中使用后者来创建多个量子状态，并求解一个量子子集合实例，以从获得的状态中恢复完整的秘密，从而在该算法和Kuperberg的筛子之间进行插值。这允许在线性查询 - 指数时间复杂性情况下平稳地插值，并进行了指数查询和时间复杂性案例，从而考虑了考虑查询成本的复杂性进行微调。我们还对非肿瘤状态中的量子子集算法进行精确研究。
The Dihedral Coset Problem (DCP) in $Z_N$ 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-Hoyer 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 $O{2^{\sqrt{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-Hoyer 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.
