Group-based cryptography is a relatively young family in post-quantum cryptography. In this paper we give the first dedicated security analysis of a central problem in group-based cryptography: the so-called Semidirect Product Key Exchange (SDPKE). We present a subexponential quantum algorithm for solving SDPKE. To do this we reduce SDPKE to the Abelian Hidden Shift Problem (for which there are known quantum subexponential algorithms). We stress that this does not per se constitute a break of SDPKE; rather, the purpose of the paper is to provide a connection to known problems.
翻译:基于集团的加密法是一个相对年轻的家庭,在分子后加密法中。在本文中,我们对基于集团的加密法中的一个中心问题作了第一次专门的安全分析:所谓的半直接产品钥匙交换(SDPKE),我们提出了解决SDPKE的次级量子算法。为了做到这一点,我们把SDPKE减少到了别家隐藏的转移问题(对此已知有亚化算法 ) 。我们强调,这本身并不构成SDPKE的断裂;相反,该文件的目的是提供与已知问题的联系。