International Journal of Security and Its Applications

Quantum Cryptanalysis of Multivariate Permutation Problem

Guodong Sun, Shenghui Su, Maozhi Xu

Published Nov 30, 2014• 1 citation

Abstract

Quantum computation is a new computational model based on quantum mechanical principle.Shor invented the polynomial time algorithms for the prime factorization and discrete logarithm problem, which indicated that the cryptosystems based on them are totally unsafe in the quantum world.Grover constructed an algorithm that finds a solution in only O( 2 n )steps whereas the exhaustive search algorithm needs O( 2n ) steps on average.In this paper we investigate the cryptanalysis of a new cryptography problem----multivariate permutation problem (MPP), which could be used to design public-key cryptosystem, with the help of the two quantum algorithms.Specially, we discuss the strength of a private key of the REESSE1+ public-key cryptosystem, whose security is based on the hardness of MPP.Besides, some suggestions are also given about the implementation of the REESSE1+.

DOI: 10.14257/ijsia.2014.8.6.23

Related papers

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

Songsong Dai

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.

IEEE Transactions on Neural Networks and Learning SystemsMar 1, 202120 citations

Analysis of RSA and Shor’s algorithm for cryptography: A quantum perspective

Seema Kute, Chitra G. Desai, Mukti E. Jadhav

The complexity of public key algorithms like RSA and variants of Elgamal is based on the involvement of exponentiation in encryption and decryption. RSA is based on integer factorization and variants of Elgamal or based on discrete logarithms and are formed as hard problems. To achieve the perceived level of security, the required key length for public key cryptosystem needs to be determined. Quantum computers are capable of conducting an exponential number of simultaneous computations because of which they can find factors in polynomial time. Shor’s algorithm is popular algorithm for factoring huge integers in polynomial time on quantum computers. This paper presents RSA algorithm followed by various possible attacks for factoring and demonstrates Shor’s algorithm for factoring and discuss results for interpretations.

AIP conference proceedingsJan 1, 20245 citations

Recent Developments in Post-Quantum Cryptography

Tsuyoshi Takagi

The security of current public-key cryptosystems relies on the hardness of factoring large integers or solving discrete logarithm problems. However, these mathematical problems can be solved in polynomial time using a quantum computer. This vulnerability has prompted research into post-quantum cryptography using alternative mathematical problems that are secure in the era of quantum computers. In this regard, the National Institute of Standards and Technology (NIST) began to standardize post-quantum cryptography in 2016. In this expository article, we give an overview of recent research on post-quantum cryptography. In particular, we describe the construction and security of multivariate polynomial cryptosystems and lattice-based cryptosystems, which are the main candidates of post-quantum cryptography.

IEICE Transactions on Fundamentals of Electronics Communications and Computer SciencesDec 31, 20173 citations

Multivariate Quadratic Solver in GF(31) with Grover's Algorithm

Seong-Min Cho, Aeyoung Kim, Seung-Hyun Seo

The development of quantum computers has led to the possibility of solving problems intractable to deal with in clas-sical computers. That threatens the current standard of public-key cryptography based on factoring or discrete-log problem. As a result, it is necessary to use a secure cryptosystem even in a quantum computing environment. NIST has been conducting a Post-Quantum Cryptography (PQC) standardization process. Recently, there have been attempting to design binary MQ solver with the Grover's algorithm to solve the binary Multivariate Quadratic (MQ) problem. However, most PQC candidates based on the MQ problem do not select a small security parameter and are over GF(16) and above. In this paper, we design the Grover's oracle circuit to solve the MQ problem over GF(31) that can be used to analyze the quantum security of PQC candidates such as Rainbow and MQDSS.

International Conference on Electronics, Information, and Communication (ICEIC)Feb 6, 20220 citations

Survey of computational assumptions used in cryptography broken or not by Shor's algorithm

Hong Ping Zhu

We survey the computational assumptions of various cryptographic schemes, and discuss the security threat posed by Shor's quantum algorithm. One-way functions form the basis of public-key cryptography. Although we have candidate hard problems that are believed to be one-way, none has been proven to be so. Therefore the security of the corresponding cryptographic schemes depends on the intractability assumptions of these problems. Two major species of such problems, factoring and discrete logarithm, are widely believed to be intractable, and serve as the basis of many popular schemes. However, these two problems turned out to be polynomial-time solvable on a hypothetical quantum computer using Shor's algorithm. This is the most worrisome long-term threat to current public-key cryptosystems. In the thesis we provide a review of existing cryptosystems, with a focus on their underlying computational assumptions and the security. Other than factoring and discrete logarithm, schemes have been proposed based on error-correcting codes, subset-sum and subset-product problems, lattice, polynomials, combinatorial group theory, number fields, etc. Many are to be furtherly evaluated in future research.

Jan 1, 20015 citations

Quantum Cryptanalysis: Breaking Classical Encryption with Shor's and Grover's Algorithms

Godwin Olaoye

The advent of quantum computing presents a paradigm shift in the field of cryptanalysis, challenging the security of classical encryption schemes that underpin modern digital communications. This study explores the capabilities of quantum algorithms, particularly Shor's algorithm and Grover's algorithm, in undermining widely used cryptographic systems. Shor's algorithm poses a direct threat to publickey cryptosystems such as RSA and ECC by enabling efficient integer factorization and discrete logarithm computation, which are computationally infeasible for classical computers. Meanwhile, Grover's algorithm provides a quadratic speedup for bruteforce attacks on symmetric-key cryptosystems like AES, significantly reducing their effective security. Through theoretical analysis and simulation-based evaluation, this paper highlights the vulnerabilities of classical encryption in the face of quantum advances and underscores the urgent need for post-quantum cryptographic solutions. The findings emphasize the critical importance of transitioning to quantum-resistant algorithms to ensure long-term data confidentiality in a future dominated by quantum technologies.

Apr 10, 20253 citations