Introduction
There has been a lot of excitement recently about post-quantum cryptography (PQC), so I thought I would summarize it here.
Who am i ?
I'm just a humble engineer.
Why is there so much talk about PQC?
In recent years, the development of quantum computers has been accelerating, and they are now scaling up to exceed 60 q-bits. It is speculated that a quantum computer (CRQC) capable of solving Shor's algorithm, which poses a threat to existing public key cryptography, may be developed around 2030, and the current situation is that the preparations for this have been gaining momentum since around 2020. Just to be
clear, the computer mentioned here refers to a computer called a gate type, not an annealing type.
Where is the impact of CRQC critical?
Famous quantum algorithms include Grover's algorithm and Shor's algorithm, but Shor's algorithm solves prime factorization and discrete logarithm problems in polynomial time, which means that the assumptions on the security of existing RSA and elliptic curve cryptography collapse. In other words, "As long as prime factorization and discrete logarithm problems cannot be solved efficiently, RSA and elliptic curve cryptography based on it are also secure." However, it was known that Shor's algorithm could be solved in polynomial time when run on CRQC, so it was argued that prime factorization and discrete logarithm problems would not actually be solved in polynomial time unless a realistic CRQC was developed. In recent years, the development of gate-type quantum computers has progressed, so we need to think about next-generation cryptography to match them, and that is why the discussion is progressing. Shor's algorithm was published in a paper around 1994, so the discussion itself has been going on for 30 years.
Trends in quantum computer development
There seem to be many different types of quantum computers, but the most popular one in Japan is one that artificially creates a quantum state by using superconducting states.
However, some say that a CRQC that can be used in practice would need at least 1000 q-bits, and it seems that it is still not at a level where it can be used for decryption. This is something we would like to keep an eye on.
There are many other methods being researched to create quantum states.
This was compiled by the Japan Research Institute and is easy to understand.
PQC Trends
Regarding PQC trends, NIST standardization is progressing, and FIPS is also in the DRAFT state. We just have to wait for NIST standardization.
Discussions are also underway at the IETF.
The materials compiled by Mr. Une of the Bank of Japan are very easy to understand.
The situation in Japan
The Ministry of Internal Affairs and Communications recently uploaded some documents.
Materials have also been uploaded to CRYPTREC.
lastly
As post-quantum cryptography has been gaining attention, crypto-agility has also become a hot topic of discussion. I will eagerly await the NIST standardization.