Technical point of view | Big country contest, the war of post-quantum cryptography has been ignited?

This year's May 17th is a special day. A letter from Huawei Haisi to the staff announced that "the multi-year spare tire chip turns "positive" overnight, and the technology will be self-reliant in the future", attracting thousands of netizens to boil, I know what Calling science and technology is a national prosperity. This year's October 1st is also a special day. When Dongfeng 41 appeared on the 70th anniversary of the National Day military parade, it drove through Tiananmen Square. I know what is the big country and the technology is strong.

The dispute between big powers is not only a dispute over the underlying technology, but also a dispute over the right to formulate rules of the game. In the previous technical point of view, we pointed out that once the quantum computer is realized, we will enter the post-quantum era. Because quantum computers can efficiently solve the computational difficulties in the traditional sense with their unique parallelism, some mainstream cryptosystems will be greatly impacted, including the security of many information systems including blockchain, financial systems and communication systems. Sex will be affected. When we are in danger, where should we go? Can we seize the commanding heights in the development of coping techniques such as post-quantum cryptography ? This is a problem that every blockchain technology worker has to think about.

Big country contest, who is the king?

A cryptographic technique that protects communication security in the post-quantum era is called anti-quantum cryptography , or post-quantum cryptography . A long time ago, the United States had quietly launched the demonstration of anti-quantum public key cryptography . In August 2015, the National Security Agency (NSA) officially announced that it would replace the existing Suit B cryptosystem with an anti-quantum cryptosystem (ie NSA Suit B Cryptography, a US NSA-published cryptographic standard, including AES, ECDSA). , SHA-256 , etc., there is a trade secret algorithm in China . In November of the same year, the US NIST announced a timetable indicating that the current cryptosystem will be phased out.

At the 7th International Conference on Quantum Cryptography (PQCrypto 2016) , NIST- related personnel on behalf of the US government issued a roadmap and timetable for anti-quantum cryptography, and it is planned to use 8 years or so to complete the standardization of anti-quantum cryptography. jobs. In addition, NIST has held an international seminar before the official launch of anti-quantum cryptography, and invited famous experts in the field of quantum computers and anti-quantum cryptography to discuss. The US NIST's schedule for working on anti-quantum cryptography is roughly as follows:

• Bitcoin options, the next battlefield of the exchange?
• Ratio Chain Research Institute | A Threshold Signature System under the Hypochronous Network Hypothesis
• Bitcoin developers: 51% of attacks are not terrible, terrible is the disregard of decentralization

• Characterization standard set before the fall of 2016
• In the fall of 2016, it officially began to collect anti-quantum cryptography solutions worldwide.
• November 2017, the deadline for submission of proposals
• Security analysis and reporting for the next 3-5 years
• After two years, the draft standard was drafted.

The scope of NIST's anti-quantum cryptography is mainly focused on basic algorithms such as signature , encryption and key agreement , and does not make complex algorithms such as identity-based cryptosystems. In standard setting, NIST will work with other organizations (such as IETF , ETSI , PQCrypto , ISO/IEC JTC 1/SC 27, etc.).

When the standard is completed, while providing guidance on migration from the current cryptosystem to the anti-quantum cryptosystem, algorithms are also substituted on protocols such as IKE and TLS to make these protocols resistant to quantum attacks. On January 30, 2019, NIST published a list of 26 algorithms for the second round of the finalists.

World-renowned IT companies, including Intel , Microsoft , Amazon , Cisco, and Google , also attach great importance to this anti-quantum password labeling work. Intel has long been planning to deploy anti-quantum cryptography plans to use anti-quantum cryptography on general-purpose chips that will be produced in the future. As a cloud service provider for large enterprises such as the US government and banks, Amazon 's important customers require the company to prepare for the migration to the anti-quantum cryptosystem .

In June 2016, in order to participate in the research and development of anti-quantum cryptographic algorithms with other countries (especially Asian countries and regions), the Chinese researchers held the first Asian Forum on Anti-Quantum Cryptography in Chengdu. Experts from South Korea and Europe and the United States conducted technical exchanges. In May of this year, the 4th Asian Forum on Anti-Quantum Cryptography was held in Chongqing, and experts from various countries once again discussed related technologies. At the same time, the Chinese Cryptography Society also encouraged the design of anti-quantum computing attack algorithms in the national cryptographic algorithm design competition that was launched in 2018.

In addition, quantum communication, which is vigorously developed in China, can also be used to guarantee communication security in the post-quantum era. (Quantum communication mainly refers to quantum key distribution, which is not equivalent to anti-quantum cryptography, nor can it replace quantum cryptosystem. Generally, quantum key distribution technology is used to distribute keys and then perform symmetric cryptographic operations.) Wu Lebin, chairman of the Chinese Academy of Sciences Holdings and chairman of Quantum Networks, said that China is in a leading position in the field of quantum communication. In the future, quantum communication is expected to become a major technological innovation to safeguard national strategic security and support the sustainable development of the national economy. The impact is far-reaching. In this contest, who wins and who loses is not fixed.

What is post-quantum cryptography?

Post-quantum cryptography is a cryptographic algorithm that can resist quantum computer attacks . Of course, the post-quantum cryptosystem described here does not include the cryptographic system in the sense of information theory. It only refers to the computationally secure cryptosystem, that is, the cryptosystem that quantum computers cannot break in polynomial time. Typical post-quantum cryptographic algorithms mainly include : lattice-based public key cryptosystem , public key cryptosystem based on coding (linear error correction code), public key cryptosystem based on multivariate polynomial equations, and digital signature based on hash function. Wait. In the researchers' understanding, these cryptosystems are not only resistant to attacks from classic computers, but also against quantum computer attacks. In addition, such as quantum public key cryptography , DNA cryptography, etc. are also considered post-quantum cryptography.

Table 2: Representative algorithm for post-quantum cryptosystem

Here we focus on the lattice-based public key cryptosystem and the digital signature based on the hash function .

Grid-based public key cryptosystem   The origin of the grid is very early, and its research can be traced back to the Goss era. In cryptography, lattices were originally used for cryptanalysis, that is, people use lattices to analyze the security of cryptosystems such as RSA. Until 1996, researchers first proposed a one-dimensional function based on lattice. With such a basic cryptographic tool, the grid has been applied to various fields of cryptography, forming a grid-based cryptography. The lattice-based cryptographic algorithm is very simple to construct, efficient, and highly parallelizable, but its key is relatively large.

It is worth mentioning that IBM researchers used the lattice to construct a fully homomorphic password scheme in 2009. A fully homomorphic cryptographic scheme refers to an encryption scheme in which a function operation is performed on a ciphertext and decrypted, and the result is equivalent to the same function operation on the plaintext. The concept of fully homomorphic encryption was introduced in the 1960s, and it was not until 2009 that a solution was developed and developed.

Digital signature based on hash function   The hash-based digital signature scheme has good features, and it only uses cryptographic components such as password hash functions. In addition, the security of the hash-based signature scheme is well understood and its quantitative security level is clear. At the same time, some research work shows that the security proof of many hash-based signature schemes is still valid in the presence of quantum enemies, and for many other post-quantum signature schemes (such as grid-based signature algorithms), the security proof is in front of the quantum enemies. It is not known whether it is effective or not. It is worth mentioning that in April this year, the IETF adopted the RFC 8554 standard to standardize the LMS signature algorithm .

postscript

Today, with the development of quantum computing, a large number of scientific research workers in China have taken precautions to find solutions such as post-quantum cryptography. As a mature blockchain team, the ontology has always been eagerly pursued in relevant cutting-edge technologies, and even if the future is unpredictable, we will embrace change and take advantage of the trend. We do not want to see the motherland fall into a situation of embattled in any technological war, and we will prove by practical actions that that day will never come!

We will continue to update Blocking; if you have any questions or suggestions, please contact us!