Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

On Quantum Algorithms for Exact Polynomial System Solving

Semwell Ferrari

Published Aug 1, 2026• 0 citations
OpenAlex

Abstract

A large-scale quantum computer, if constructed, would break the public-key cryptography in everyday use outright. It is therefore essential to gather evidence that current post-quantum schemes truly resist quantum attack. For multivariate schemes, whose security rests on the hardness of solving polynomial systems over a finite field (the PoSSo problem), this boils down to asking how far quantum algorithms can accelerate exact solving. The standard approach consists of linearisation methods such as XL and F4, which reduce solving to linear algebra on large Macaulay matrices; performing that linear algebra with a quantum linear-systems solver such as HHL, rather than classically, is the natural route to a speed-up. The ill-conditioning of those matrices, however, undermines the expected gain. We explore an alternative approach based on symbolic homotopy and Newton–Hensel lifting, a symbolic variant of Newton iteration. A numerical quantum version of it is due to Xue, Wu and Guo; we ask whether an exact one, over a finite field, can sidestep the construction of ill-conditioned matrices altogether. Our answer is that, given the current state of the art, it cannot. The thesis assembles the classical and quantum tools needed for a comparative complexity analysis and clarifies the obstacles that stand in the way of exact solving. The evidence gathered is that the quantum paradigms surveyed here do not threaten, at their current parameters, multivariate UOV-based schemes such as MAYO; a quantum attack on them, should one exist, would have to exploit their structure directly.

Related papers

On Quantum Solvers for Linear Algebraic Systems

Papagiannis Nikos, Vavalis Manolis

Abstract Solving large-scale linear systems is an integral part of many scientific disciplines. Classical linear solvers have a polynomial time complexity and it seems impossible to further improve their performance. This fact has directed scientific research to the study of corresponding quantum algorithms, which promise even exponential acceleration compared to existing methods. In this paper, we present and analyze some of the most important related results. In particular, we present the HHL and WZP algorithms based on the eigen-decomposition of a matrix, the row and column iteration methods, as well as two hybrid algorithms that require the cooperation of a classical and a quantum computer, namely an algorithm that uses random walks and the VQLS algorithm. The latter is also examined from an experimental standpoint using the Qiskit open-source framework and a suitable quantum circuit is proposed which can enhance its performance.

Quantum Information and Computation•Dec 1, 2025•0 citations

A comparative analysis of post-quantum cryptographic schemes over discrete algebraic structures for enhanced information security in large-scale networks

Suhail Javed Quraishi, Dharm Raj, Danish Ather +3 more

Abstractly, the fast development of quantum computing is a threat to classical public-key cryptographic infrastructures.Asymmetric algorithms (which are widely used and include RSA and Elliptic Curve Cryptography (ECC)) are susceptible to the Shor algorithm, which can break them in a time-polynomial manner.This paper will give a detailed comparative study of Post-Quantum Cryptography (PQC) schemes founded on discrete algebraic structures such as lattice-based, code-based, hash-based, and multivariate polynomials based cryptosystems.These paradigms are systematically assessed according to computational complexity, key and ciphertext sizes, security reduction assumptions, and how they can be deployed on large scale networks.The NIST-standardized algorithms, which are the focus of our analysis, are ML-KEM (CRYSTALS-Kyber), ML-DSA (CRYSTALS Dilithium), FN-DSA (Falcon), and SLH-DSA (SPHINCS+).We also consider hybrid cryptography transitional measures to provide backward compatibility and security guarantee in the process of migrating the classical to quantum-resistant systems.As we found, the current state of lattice-based schemes provides the most desirable ratio of security to performance in large-scale applications, although, in the long run, code-based and multivariate schemes are necessary as their complements.

Journal of Discrete Mathematical Sciences and Cryptography•Sep 30, 2026•0 citations

Post Quantum Cryptography (PQC): Securing Data In The Age Of Quantum Computers

P. Ganga Bhavani, P. Nandini Lakshmi, V. Jahnavi +2 more

The emergence of quantum computing is a serious threat to the principles of modern crypto-logical mathematics. The classical public-key cryptography, including Rivest-Shamir-Adleman (RSA), Elliptic Curve Cryptography (ECC), and Diffie-Hellman are very safe against classical adversaries yet become susceptible to quantum algorithms, including the Shor algorithm, which can easily solve the underlying mathematical problems. This weakness is jeopardizing confidentiality and integrity of the world-wide systems of communication, money transactions, and essential structures, and requires the immediate creation of safe alternatives. The current literature on post-quantum cryptography (PQC) has covered various classes of algorithm, such as lattice-based, code-based, multivariate schemes, and isogeny-based schemes. Although lattice-based approaches like Nth Degree Truncated Polynomial Ring Unit (NTRU) and FrodoKEM can be highly theoretically resistant, they can be computationally and memory-intensive. Cryptosystems based on code such as Classic McEliece are secure but not practicable because they have huge public key sizes. Multivariate schemes like Rainbow, and isogeny-based schemes like Super singular Isogeny Key Encapsulation (SIKE) have been attacked recently by cryptanalytic attacks, and broken completely. Such restrictions open the necessity to find more efficient and secure quantum-resistant solutions.This research study postulates a hybrid post-quantum cryptographic (PQC) system that combines CRYSTALS-Kyber for encryption with CRYSTALS-Dilithium for digital signatures both of which are approved through the National Institute of Standards and Technology (NIST) PQC standardization program. The model will be such that it ensures quantum resistance but at the same time it will be scalable, efficient and compatible with the existing infrastructures. The test outcomes indicate that the hybrid PQC model is 35-45 percent faster to encrypt and decrypt, signature performance is enhanced by up to 40 percent, and the throughput is 20 times higher (98.7 Mbps) than the same base PQC scheme including Nth Degree Truncated Polynomial Ring Unit (NTRU), McEliece and Rainbow. These enhancements affirm that the suggested model provides a viable trade-off between the security, speed, and efficiency in terms of key size, which makes it a viable and a sound base to ensure secure communication in the quantum age.

International Journal of Science Engineering and Technology•May 26, 2026•0 citations

Quantum Algorithms for Boolean Equation Solving and Quantum Algebraic Attack on Cryptosystems

Yu-Ao Chen, Xiao-Shan Gao

Decision of whether a Boolean equation system has a solution is an NPC problem and finding a solution is NP hard. In this paper, we present a quantum algorithm to decide whether a Boolean equation system FS has a solution and compute one if FS does have solutions with any given success probability. The runtime complexity of the algorithm is polynomial in the size of FS and the condition number of FS. As a consequence, we give a polynomial-time quantum algorithm for solving Boolean equation systems if their condition numbers are small, say polynomial in the size of FS. We apply our quantum algorithm for solving Boolean equations to the cryptanalysis of several important cryptosystems: the stream cipher Trivum, the block cipher AES, the hash function SHA-3/Keccak, and the multivariate public key cryptosystems, and show that they are secure under quantum algebraic attack only if the condition numbers of the corresponding equation systems are large. This leads to a new criterion for designing cryptosystems that can against the attack of quantum computers: their corresponding equation systems must have large condition numbers.

arXiv:1712.06239•Dec 18, 2017•8 citations

Post-Quantum Cryptography for Secure Communication: A Systematic Review of Algorithms, Performance Trade-offs, and Emerging Challenges

Suvhodip Saha

The rapid growth of quantum computing poses a critical threat to classical cryptographic systems. That is due in large part to the fact that they represent efficient solutions for some of the most challenging mathematical problems such as integer factoring or finding discrete logarithms. Schemes currently in wide use including RSA, Diffie–Hellman, and elliptic curve cryptography are particularly susceptible to being attacked by quantum computers, using algorithms like Shor's Algorithm and Grover's Algorithm. The advent of post-quantum cryptography (PQC) provides a promising potential answer to providing longterm security from adversaries using quantum computing capabilities. This paper presents a comprehensive state-of-the-art review of various PQC techniques currently being researched, including lattice-based methods, code-based methods, multivariate methods, hash-based methods, and isogeny-based methods. key challenges that will need to be addressed include computational overhead, large key sizes and implementation complexity. Furthermore the study reviews the current standardization efforts by the National Institute of Standards and Technology related to PQC and discusses some of the very specific practical considerations that need to be considered before widely deploying these techniques. The paper concludes by a complete list of existing research challenges and proposed future work that will assist in the development of efficient and scalable systems that will resist attacks from quantum computers.

International Journal for Research in Applied Science and Engineering Technology•Mar 24, 2026•0 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 Sciences•Dec 31, 2017•3 citations
A large-scale quantum computer, if constructed, would break the public-key cryptography in everyday use outright. It is therefore essential to gather evidence that current post-quantum schemes truly resist quantum attack. For multivariate schemes, whose security rests on the hardness of solving polynomial systems over a finite field (the PoSSo problem), this boils down to asking how far quantum algorithms can accelerate exact solving. The standard approach consists of linearisation methods such as XL and F4, which reduce solving to linear algebra on large Macaulay matrices; performing that linear algebra with a quantum linear-systems solver such as HHL, rather than classically, is the natural route to a speed-up. The ill-conditioning of those matrices, however, undermines the expected gain. We explore an alternative approach based on symbolic homotopy and Newton–Hensel lifting, a symbolic variant of Newton iteration. A numerical quantum version of it is due to Xue, Wu and Guo; we ask whether an exact one, over a finite field, can sidestep the construction of ill-conditioned matrices altogether. Our answer is that, given the current state of the art, it cannot. The thesis assembles the classical and quantum tools needed for a comparative complexity analysis and clarifies the obstacles that stand in the way of exact solving. The evidence gathered is that the quantum paradigms surveyed here do not threaten, at their current parameters, multivariate UOV-based schemes such as MAYO; a quantum attack on them, should one exist, would have to exploit their structure directly.
Abstract Solving large-scale linear systems is an integral part of many scientific disciplines. Classical linear solvers have a polynomial time complexity and it seems impossible to further improve their performance. This fact has directed scientific research to the study of corresponding quantum algorithms, which promise even exponential acceleration compared to existing methods. In this paper, we present and analyze some of the most important related results. In particular, we present the HHL and WZP algorithms based on the eigen-decomposition of a matrix, the row and column iteration methods, as well as two hybrid algorithms that require the cooperation of a classical and a quantum computer, namely an algorithm that uses random walks and the VQLS algorithm. The latter is also examined from an experimental standpoint using the Qiskit open-source framework and a suitable quantum circuit is proposed which can enhance its performance.
Abstractly, the fast development of quantum computing is a threat to classical public-key cryptographic infrastructures.Asymmetric algorithms (which are widely used and include RSA and Elliptic Curve Cryptography (ECC)) are susceptible to the Shor algorithm, which can break them in a time-polynomial manner.This paper will give a detailed comparative study of Post-Quantum Cryptography (PQC) schemes founded on discrete algebraic structures such as lattice-based, code-based, hash-based, and multivariate polynomials based cryptosystems.These paradigms are systematically assessed according to computational complexity, key and ciphertext sizes, security reduction assumptions, and how they can be deployed on large scale networks.The NIST-standardized algorithms, which are the focus of our analysis, are ML-KEM (CRYSTALS-Kyber), ML-DSA (CRYSTALS Dilithium), FN-DSA (Falcon), and SLH-DSA (SPHINCS+).We also consider hybrid cryptography transitional measures to provide backward compatibility and security guarantee in the process of migrating the classical to quantum-resistant systems.As we found, the current state of lattice-based schemes provides the most desirable ratio of security to performance in large-scale applications, although, in the long run, code-based and multivariate schemes are necessary as their complements.
The emergence of quantum computing is a serious threat to the principles of modern crypto-logical mathematics. The classical public-key cryptography, including Rivest-Shamir-Adleman (RSA), Elliptic Curve Cryptography (ECC), and Diffie-Hellman are very safe against classical adversaries yet become susceptible to quantum algorithms, including the Shor algorithm, which can easily solve the underlying mathematical problems. This weakness is jeopardizing confidentiality and integrity of the world-wide systems of communication, money transactions, and essential structures, and requires the immediate creation of safe alternatives. The current literature on post-quantum cryptography (PQC) has covered various classes of algorithm, such as lattice-based, code-based, multivariate schemes, and isogeny-based schemes. Although lattice-based approaches like Nth Degree Truncated Polynomial Ring Unit (NTRU) and FrodoKEM can be highly theoretically resistant, they can be computationally and memory-intensive. Cryptosystems based on code such as Classic McEliece are secure but not practicable because they have huge public key sizes. Multivariate schemes like Rainbow, and isogeny-based schemes like Super singular Isogeny Key Encapsulation (SIKE) have been attacked recently by cryptanalytic attacks, and broken completely. Such restrictions open the necessity to find more efficient and secure quantum-resistant solutions.This research study postulates a hybrid post-quantum cryptographic (PQC) system that combines CRYSTALS-Kyber for encryption with CRYSTALS-Dilithium for digital signatures both of which are approved through the National Institute of Standards and Technology (NIST) PQC standardization program. The model will be such that it ensures quantum resistance but at the same time it will be scalable, efficient and compatible with the existing infrastructures. The test outcomes indicate that the hybrid PQC model is 35-45 percent faster to encrypt and decrypt, signature performance is enhanced by up to 40 percent, and the throughput is 20 times higher (98.7 Mbps) than the same base PQC scheme including Nth Degree Truncated Polynomial Ring Unit (NTRU), McEliece and Rainbow. These enhancements affirm that the suggested model provides a viable trade-off between the security, speed, and efficiency in terms of key size, which makes it a viable and a sound base to ensure secure communication in the quantum age.
Decision of whether a Boolean equation system has a solution is an NPC problem and finding a solution is NP hard. In this paper, we present a quantum algorithm to decide whether a Boolean equation system FS has a solution and compute one if FS does have solutions with any given success probability. The runtime complexity of the algorithm is polynomial in the size of FS and the condition number of FS. As a consequence, we give a polynomial-time quantum algorithm for solving Boolean equation systems if their condition numbers are small, say polynomial in the size of FS. We apply our quantum algorithm for solving Boolean equations to the cryptanalysis of several important cryptosystems: the stream cipher Trivum, the block cipher AES, the hash function SHA-3/Keccak, and the multivariate public key cryptosystems, and show that they are secure under quantum algebraic attack only if the condition numbers of the corresponding equation systems are large. This leads to a new criterion for designing cryptosystems that can against the attack of quantum computers: their corresponding equation systems must have large condition numbers.
The rapid growth of quantum computing poses a critical threat to classical cryptographic systems. That is due in large part to the fact that they represent efficient solutions for some of the most challenging mathematical problems such as integer factoring or finding discrete logarithms. Schemes currently in wide use including RSA, Diffie–Hellman, and elliptic curve cryptography are particularly susceptible to being attacked by quantum computers, using algorithms like Shor's Algorithm and Grover's Algorithm. The advent of post-quantum cryptography (PQC) provides a promising potential answer to providing longterm security from adversaries using quantum computing capabilities. This paper presents a comprehensive state-of-the-art review of various PQC techniques currently being researched, including lattice-based methods, code-based methods, multivariate methods, hash-based methods, and isogeny-based methods. key challenges that will need to be addressed include computational overhead, large key sizes and implementation complexity. Furthermore the study reviews the current standardization efforts by the National Institute of Standards and Technology related to PQC and discusses some of the very specific practical considerations that need to be considered before widely deploying these techniques. The paper concludes by a complete list of existing research challenges and proposed future work that will assist in the development of efficient and scalable systems that will resist attacks from quantum computers.
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.