论文标题
半指数离散对数问题的亚指数量子算法
A Subexponential Quantum Algorithm for the Semidirect Discrete Logarithm Problem
论文作者
论文摘要
基于组的密码学是一个相对尚未探索的量子加密家族，而所谓的半程离散对数问题（SDLP）是其最中心的问题之一。但是，SDLP的复杂性及其与更知名的硬度问题的关系，尤其是在针对量子对手的安全性方面，尚未得到充分理解，对于该领域的研究人员来说，这是一个重大的开放问题。在本文中，我们对SDLP进行了第一个专用的安全分析。特别是，我们提供了SDLP和组动作之间的联系，该上下文已知将应用量子亚指数算法。因此，我们能够构建用于求解SDLP的亚指数量子算法，从而对SDLP的复杂性进行分类及其与已知的计算问题的关系。
Group-based cryptography is a relatively unexplored family in post-quantum cryptography, and the so-called Semidirect Discrete Logarithm Problem (SDLP) is one of its most central problems. However, the complexity of SDLP and its relationship to more well-known hardness problems, particularly with respect to its security against quantum adversaries, has not been well understood and was a significant open problem for researchers in this area. In this paper we give the first dedicated security analysis of SDLP. In particular, we provide a connection between SDLP and group actions, a context in which quantum subexponential algorithms are known to apply. We are therefore able to construct a subexponential quantum algorithm for solving SDLP, thereby classifying the complexity of SDLP and its relation to known computational problems.
