Game-Changing Quantum Algorithm Factors Large Integers, Challenges RSA Cryptosystems

On December 23, 2022, a group of Chinese experts issued a research paper claiming to have cracked the 2048-bit RSA algorithm. However, the research is difficult to understand and leaves many questions unanswered. [ Link to the research paper is mentioned below]

I am a polymath with an insatiable desire to learn new things, and I would like to state unequivocally that I am not an expert in quantum computers or cryptography; my interpretation of this research paper is only an attempt to be so.

Context:

In the field of computer science, integer factorization is a fundamental concept with significant applications in areas such as cryptography and secure communication. For instance, the widely used RSA cryptosystem is founded on the premise that factoring large integers is computationally unfeasible. Nonetheless, with the advent of quantum computers, it is feasible that these integers might be factored quickly using quantum algorithms, hence compromising the security of RSA and other public key cryptosystems.

Researchers have considered the possibility that quantum computers could factor numbers more effectively than conventional methods. The use of variational quantum algorithms, such as the quantum approximate optimization algorithm (QAOA), which can be utilized to find approximate solutions to optimization problems, has generated considerable interest.

The quantum approximate optimization algorithm is a variational quantum technique for finding approximate solutions to optimization problems (QAOA). It operates by encoding the problem at hand into a quantum Hamiltonian and then preparing the ground state of the Hamiltonian using a quantum computer. The answer to the optimization problem should correspond to this initial state.

The algorithm consists of two sections: a quantum state preparation step in which a parametrized quantum state is generated using a series of quantum gates, and a classical optimization step in which the quantum state's parameters are optimized to minimize an objective function defined over the quantum state. For optimization, conventional methods such as gradient descent and stochastic gradient descent can be utilized.

QAOA is used in this research to optimize the most time-consuming element of Schnorr's algorithm, which is a traditional approach for integer factorization based on lattice reduction. The researchers are able to factor integers utilizing just a sublinear number of qubits by optimizing this component of the process with QAOA.

The algorithm's qubit efficiency is defined by the O(log N) scaling, where N is the number of bits in the integer being factored. This indicates that the number of qubits needed to factor an N-bit integer grows logarithmically rather than linearly or exponentially with N. This is in contrast to Shor's method, which requires an increasing amount of qubits as N increases. The proposed algorithm's O(log N) scalability makes it more viable to operate on existing and future quantum hardware since it requires less qubits than other known integer factorization techniques.

The development of effective quantum algorithms for integer factorization has the potential to have a substantial impact on the fields of cryptography and electronic communication security.

While the current scale of quantum computers is insufficient to break realistic cryptographic systems, the rapid speed of growth in quantum computing implies that the academic community must continue to investigate and comprehend the prospective capabilities and limits of these algorithms.

Link to research paper: https://arxiv.org/pdf/2212.12372.pdf

Actual research paper interpretation:

The purpose of this research is to use quantum computers to solve the difficulty of effectively factoring large integers.

The researchers have proposed a solution by combining the classical lattice reduction approach and the quantum approximate optimization algorithm (QAOA). a challenge with substantial ramifications for the fields of information security and cryptography.

The RSA algorithm, one of the most extensively used public key encryption systems, is based on the idea that factoring huge integers is computationally infeasible. The discovery of Shor's algorithm in 1994, on the other hand, indicated that quantum computers have the capacity to solve this problem quickly, posing a significant danger to the security of RSA and other comparable systems.

The proposed approach relies heavily on lattice principles such as the LLL algorithm and Babai's nearest plane algorithm. In addition, the researchers use Schnorr's integer factoring technique and the sieve method to develop a sublinear approach to solving the closest vector problem (CVP) in lattices.

The researchers who wrote this paper propose a quantum algorithm for integer factorization that combines the classical lattice reduction method with the quantum approximate optimization algorithm in order to overcome this issue (QAOA). Lattice reduction is a mathematical approach used to identify the shortest vector in a lattice. It has been implemented in a number of integer factorization techniques, including the LLL algorithm and Babai's closest plane algorithm. QAOA is a quantum method that can be used to solve optimization problems approximatively.

It is based on Schnorr's integer factorization algorithm, which finds the integer's factors using lattice reduction. They use QAOA to optimize the most time-consuming part of Schnorr's algorithm, yielding a quantum algorithm that only requires sublinear resources in the form of qubits. They illustrate the usefulness of their method in their research by factoring 48-bit integers with 10 superconducting qubits, the largest integer ever factored on a quantum device.

This approach's qubit efficiency is one of its merits; it requires only O(log N) qubits for an N-bit integer, making it the most qubit-saving factorization algorithm to date. In contrast, Shor's algorithm requires millions of qubits to decrypt the RSA-2048 encryption system. The researchers also predict that using their approach, a quantum circuit with 372 physical qubits and a depth of thousands would be adequate to challenge RSA-2048. This is likely to be attainable in the near future on noisy intermediate scale quantum (NISQ) devices.

This method has a few potential flaws. For example, considering it has only been tested on small integers, it is unclear how well it would scale to larger integers with cryptographic importance. Second, the algorithm is based on QAOA, which has been demonstrated to be vulnerable to noise and flaws in quantum hardware. This could limit the algorithm's practical applications until more reliable quantum hardware becomes available.

After trying to understand the research, I'd like to know more about the following:?

·?????How does the noise and error tolerance of the proposed algorithm compare to other quantum algorithms for integer factorization? How does this affect the practical usefulness of the algorithm in the current noisy intermediate scale quantum (NISQ) era?

·?????How does the proposed algorithm compare to traditional ways of factoring integers, like the sieve method and lattice-based techniques? Is there a clear quantum speedup in some cases, or is the benefit of the quantum algorithm more subtle?

·?????Could the proposed algorithm be used to break other lattice-based cryptographic schemes, such as those based on the learning with errors (LWE) or the closest vector problem (CVP)? How does this affect the overall security of these schemes?

Do like & Share and please tell me what you think & believe.

Disclaimer: This blog or post was authored by an individual. Unless otherwise specified, the views and opinions expressed on this site are solely those of the author and do not represent those of any other individuals, institutions, or organizations with whom the author may or may not be professionally or personally affiliated. Any opinions or remarks expressed are not intended to be disrespectful to any religion, ethnic group, club, organization, or person.