Quantum Cryptanalysis on a Multivariate Cryptosystem Based on Clipped Hopfield Neural Network

Songsong Dai

2021IEEE Transactions on Neural Networks and Learning Systems18 citationsDOI

Abstract

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.

Topics & Concepts

CryptosystemCryptanalysisCryptographyQuantum cryptographyDiscrete logarithmQuantum computerComputer scienceTheoretical computer scienceNeural cryptographyPost-quantum cryptographyQuantum algorithmAlgorithmPublic-key cryptographyQuantumEncryptionQuantum informationQuantum mechanicsComputer securityPhysicsPolynomial and algebraic computationCryptography and Residue ArithmeticCoding theory and cryptography