Existing Cryptosystems Face Critical Risks... Quantum-Resistant Cryptography Essential to Withstand Quantum Computers

Ignoring the Threat of "Shor's Algorithm" in 1994
Leads to Critical Vulnerabilities 30 Years Later
Accelerating the Shift to Post-Quantum Cryptography
Lattice-Based Cryptography:
Exponential Growth in Complexity with "2 to the Power of n"
Quantum Computer Arrival:
"As Soon as 5 Years, No Later Than 20 Years"

Cryptographic technology has always evolved through an endless battle between 'those who create codes' and 'those who break codes.' When a stronger encryption is designed, attempts to break it follow, leading to the emergence of even more powerful encryption. Amid this fierce contest, the hottest topic recently has been 'Post-Quantum Cryptography (PQC)'.

Sim Kyung-ah, head of the Public Infrastructure Research Division at the National Institute for Mathematical Sciences (NIMS), an authority in this field, explains the essence of cryptographic research as follows. In 2020, when she led her research team to develop 'high-speed encryption technology that cannot be broken even by quantum computers,' it became a milestone for Korea’s cryptographic technology to gain global recognition.

Provided by Pixabay

The United Nations (UN) has designated 2025 as the 'International Year of Quantum Science.' The scientific community views this as the inaugural year marking the transition from an era dominated by digital technology to one led by quantum technology. And the busiest people in this transformation are cryptography researchers.

This is because the advent of quantum computers is imminent. The encryption technology we use today maintains security based on mathematical problems that are difficult to solve with current computers. However, once quantum computers become sufficiently advanced, existing cryptographic systems could be rapidly rendered ineffective.

Ignoring the 1994 'Shor's Algorithm' Exposed Fatal Threats 30 Years Later

Kim Kwang-jo, Professor Emeritus at the Korea Advanced Institute of Science and Technology (KAIST), has long warned about this issue. He pointed out, "In 1994, when mathematician Peter Shor announced 'Shor's Algorithm,' which could break the core principles of existing encryption, quantum computers were considered a technology of the distant future. But in just 30 years, the encryption technology we currently use has been exposed to fatal threats."

Professor Kim is the top authority in this field and was the first Korean to be selected as a Fellow of the International Association for Cryptologic Research (IACR). In 2021, he developed 'SOLMAE,' a post-quantum digital signature with superior performance compared to existing methods at the U.S. National Institute of Standards and Technology (NIST), and this year he is working to designate it as a Korean standard.

Kwangjo Kim, Professor Emeritus at the Korea Advanced Institute of Science and Technology (KAIST).

Director Sim Kyung-ah expressed similar concerns. "Once quantum computers emerge, the encryption technology we currently use on the internet is likely to no longer be secure," she said, emphasizing, "To ensure safe communication and data protection in the future, it is essential to switch cryptographic systems to Post-Quantum Cryptography (PQC)."

PQC is an encryption technology that cannot be easily broken even by quantum computers. Current encryption relies on the difficulty of solving specific mathematical problems to maintain security, but if these problems are solved, the encryption is also broken. PQC applies new methods that remain difficult to solve even as quantum computers advance. Both experts agree on one point: "We must hasten the transition to PQC."

Accelerating the Transition to PQC

PQC protects information in a way that cannot be easily solved not only by the conventional computers we use today but also by powerful quantum computers of the future. This technology maintains security based on the principle that certain mathematical problems are difficult to solve. However, if these mathematical problems are solved, the encryption is no longer secure.

One of the widely used encryption methods is RSA. This technology was developed in 1978 by Ronald Rivest, Adi Shamir, and Leonard Adleman. RSA uses the mathematical principle that while it is easy to multiply two very large prime numbers to create a number, reversing this process (prime factorization) to retrieve the original primes is extremely difficult.

Sim Kyung-ah, Director of the Public Infrastructure Research Division at the National Institute for Mathematical Sciences.

Because it takes an enormous amount of time for conventional computers to solve this calculation, RSA encryption has been safely used. However, with the emergence of a new computational method called 'Shor's Algorithm,' it became known that quantum computers could solve the prime factorization problem very quickly. This raised concerns that existing encryption methods, including RSA, might no longer be secure.

To address this issue, PQC was introduced. PQC includes various encryption methods, notably lattice-based cryptography, multivariate polynomial cryptography, and hash-based cryptography. Among these, lattice-based cryptography is particularly recognized as the most secure method, as it is currently considered difficult to break even with known quantum algorithms.

Lattice-Based Cryptography: Explosive Growth in Computational Complexity as '2 to the Power of n'

A lattice is, simply put, a set of points arranged regularly like intersections on a Go board. Starting from one point and moving a fixed distance in a specific direction always leads to another point. While lattices can be easily visualized in two-dimensional space, cryptographic technology extends this concept to much higher dimensions (n dimensions).

As the dimension increases, the number of possible points grows exponentially, and the computational effort required by computers increases explosively in proportion to 2 to the power of n. This is why high-dimensional lattice problems form the basis of cryptographic technology that is difficult to solve even with quantum computers.

It is important to note that lattice-based cryptography is not absolutely unbreakable but is extremely difficult to solve with existing algorithms. Scientists regard lattice-based methods as the strongest among currently available cryptographic technologies and believe they will likely remain secure for at least 10 years even as quantum computers continue to develop. This means lattice-based cryptography is expected to maintain security for a certain period after quantum computers become practical.

Director Sim explained, "Since a lattice is a set of points represented by integer linear combinations in n-dimensional space, the higher the dimension, the harder it is to attack, but if the dimension is too high, the computational load increases and speed may slow down." She added, "While it is currently difficult to solve, efficient attack methods may be developed in the future, so to counter attacks, key lengths such as dimension must be increased."

In fact, in May 2022, researchers at the Electronics and Telecommunications Research Institute (ETRI) in Korea made headlines by developing a quantum algorithm that targets PQC using a 'divide-and-conquer strategy' for the first time in the world. Although further academic verification is needed, this case shows the possibility that PQC could eventually be broken.

Provided by Pixabay

Quantum Computer Arrival: "As Soon as 5 Years, No Later Than 20 Years"

The arrival of quantum computers appears to be imminent. Professor Kim predicted, "Based on Moore's Law, computational power doubles every year and a half, and applying this to quantum computing, 100 qubits will become 100,000 qubits in 10 years." He added, "In 10 years, a 100,000-qubit quantum computer will easily hack current cryptographic systems." He further stated, "It could happen as soon as within 5 years, but certainly no later than 20 years."

According to Director Sim, to address potential vulnerabilities in structured lattices and ensure diversity in cryptographic methods, the U.S. National Institute of Standards and Technology (NIST) reopened a call for new digital signature algorithms last June.

Similarly, the Korean government is moving swiftly to prepare for the PQC transition by 2035. In January, it finalized the selection of 'Korean-style Post-Quantum Cryptography (KpqC)' based on lattice algorithms and is promoting a pilot project to support PQC transition using this technology.

An official from the Ministry of Science and ICT stated, "Since security levels vary by country, problems could arise; therefore, considering the commercialization timeline of quantum computers, major countries are pushing for PQC transition by 2035." The official added, "Through pilot projects applying the selected algorithms in real life, we will verify their proper operation across various fields and ensure the transition by 2035 proceeds without issues."