Dai Songsong
IEEE Trans Neural Netw Learn Syst. 2022 Sep;33(9):5080-5084. doi: 10.1109/TNNLS.2021.3059434. Epub 2022 Aug 31.
Shor's quantum algorithm and other efficient quantum algorithms can break many public-key cryptographic schemes in polynomial time on a quantum computer. In response, researchers proposed postquantum cryptography to resist quantum computers. The multivariate cryptosystem (MVC) is one of a few options of postquantum cryptography. It is based on the NP-hardness of the computational problem to solve nonlinear equations over a finite field. Recently, Wang et al. (2018) proposed a MVC based on extended clipped hopfield neural networks (eCHNN). Its main security assumption is backed by the discrete logarithm (DL) problem over Matrics. In this brief, we present quantum cryptanalysis of Wang et al. 's eCHNN-based MVC. We first show that Shor's quantum algorithm can be modified to solve the DL problem over Matrics. Then we show that Wang et al. 's construction of eCHNN-based MVC is not secure against quantum computers; this against the original intention of that multivariate cryptography is one of a few options of postquantum cryptography.
肖尔量子算法及其他高效量子算法能够在量子计算机上以多项式时间破解许多公钥加密方案。作为回应，研究人员提出了抗量子计算机的后量子密码学。多元密码系统（MVC）是后量子密码学的少数选择之一。它基于在有限域上求解非线性方程这一计算问题的NP难特性。最近，王等人（2018年）提出了一种基于扩展裁剪霍普菲尔德神经网络（eCHNN）的MVC。其主要安全假设基于矩阵上的离散对数（DL）问题。在本简报中，我们展示了对王等人基于eCHNN的MVC的量子密码分析。我们首先表明肖尔量子算法可被修改以解决矩阵上的DL问题。然后我们表明王等人基于eCHNN的MVC构造在量子计算机面前并不安全；这与多元密码学是后量子密码学少数选择之一的初衷相悖。
