Quantum of Solace for Lattice Cryptozoology? One article will help you analyze the academic controversy of lattice cryptography

Quantum security threats of blockchain and responses

On March 10, 2024, Ethereum co-founder Vitalik Buterin published the latest article "How to hard-" on the Ethereum Research Forum (ethresear.ch) fork to save most user's funds in a quantum emergency"[1], the article states: The threat of quantum computing attacks faced by the Ethereum ecosystem can be used to protect the security of user funds through restorative fork strategies and anti-quantum cryptography technology.

What exactly are quantum security threats to blockchain?

Quantum computing [2] is a new computing model that uses quantum mechanics to control quantum information units for calculations. It was proposed in the 1980s. Within ten years after the concept was proposed, quantum computers only remained abstract. theoretical stage. Until the mid-1990s, there were two quantum algorithms: Shor's algorithm [3] (which solves difficult problems of large number decomposition and discrete logarithms in polynomial time) and Grover's algorithm [4] (which provides exhaustive search for unstructured data). The proposal of quadratic acceleration has enabled quantum computing to jump out of the abstract theoretical stage and enter a new stage of physical carrier research and development, which is currently called quantum computer. The figure below shows the physical qubit development roadmap of quantum computers from 1998 to 2026:

Quantum computing is not a panacea, and it cannot solve all computing problems. Currently, it can be used in simulation (simulating processes that occur in nature, suitable for chemical and biological engineering), deciphering (breaking most traditional cryptography systems, suitable for network security), optimization (finding the optimal solution among feasible options, suitable for finance, supply chain) and other specific domain problems.

The current widespread application of blockchain comes from the fact that it brings a new trust basis to the collaboration between different requesting parties, and this trust basis is based on the security guarantee provided by the underlying cryptography:

• Trusted identity and transaction confirmation: Establish a user's trusted identity based on asymmetric public and private key pairs, and manage identity information in a unified manner. The ownership of digital assets is confirmed through digital signatures, and the holder of the private key with a valid signature actually owns the asset.

• Core consensus and operational security: Build a consensus mechanism based on modern cryptographic technologies such as hash functions, threshold signatures, and verifiable random functions to ensure the security of the consensus mechanism.

• Privacy protection and secure sharing: Build a privacy protection solution based on rich-functional cryptographic technologies such as zero-knowledge proof, secure multi-party computation, and fully homomorphic to achieve secure sharing of data on the blockchain.

• Controllable supervision and compliance applications: Integrated deployment of cryptographic technologies such as ring signatures, homomorphic encryption schemes, hidden addresses and secret sharing to ensure the safe supervision of blockchain transactions.

The usage of public key cryptography can be roughly divided into: the digital signature mechanism used to prevent tampering of transactions on the chain, and the secure transmission protocol used for communication between nodes. Affected by the Shor algorithm, the security of the above public key cryptography cannot be effectively guaranteed. While considering the time it would take for dedicated code-breaking quantum computers to be implemented on a large scale, it is also important to consider how long data stored on the blockchain needs to be retained and how long it will take for existing blockchain systems to be upgraded to quantum security levels. If the sum of the latter two times is greater than the former, then the data on the blockchain will be subject to serious security threats brought by quantum computing.

Taking into account the current situation of continuous improvement in computing power brought about by the rapid development of quantum computing, there are currently two main technical ways to effectively deal with security risks:

1. Without the help of The technical route of post-quantum cryptography [5] based on new mathematical problems of physical equipment; the technical route of quantum cryptography [6] based on physical principles with the help of special physical equipment.

2. Comprehensive consideration of various factors such as implementation verification and other factors, in order to ensure the security guarantee under the long-term evolution of the blockchain, on the premise of being compatible with existing cryptographic security, post-quantum can be considered Crypto-migration upgrades blockchain early deployment to quantum security levels. Ideally, upgrading the public key cryptographic algorithm used by the existing blockchain to a quantum-safe post-quantum cryptographic algorithm should satisfy the following characteristics as much as possible:

The key is small and the signature is Short: Every transaction on the blockchain contains signature information, and the public key to verify any transaction is also stored on the chain. If the size of the key and signature is too large, it will greatly increase the storage cost and communication overhead of the blockchain;

• High computational efficiency: each time period can be processed when the blockchain is running The number of transactions is largely related to the running time of the algorithm, especially the signature verification algorithm. The faster computing efficiency of the algorithm can better support high-performance blockchain applications.

Development status of post-quantum cryptography

Post-quantum cryptography, in one sentence, is the first cryptographic algorithm that can resist quantum computer attacks on existing cryptographic algorithms. Generation cryptographic algorithm:

is oriented to public key cryptography system;

• relies on new mathematical problems;

• No need for special equipment support;

• Safe under classical computing and quantum computing conditions;

There are currently five mainstream construction technology routes, as shown in the figure below. From left to right they are grid, encoding, multi-variable, hash and homology:

1. Lattice: Difficult questions based on the grid.

2. Encoding: Based on the difficulty of decoding.

3. Multivariable: Based on the intractability of multivariable quadratic polynomial groups over finite fields.

4. Hash: Collision resistance based on hash function.

5. Same origin: Pseudo-random walk based on super-singular elliptic curves.

The new generation of cryptographic algorithms will naturally involve the establishment of a standard cryptographic system. The most noteworthy thing about post-quantum cryptography standards is: the post-quantum cryptography standardization project of the National Institute of Standards and Technology (NTST) [7], which was launched in 2016 and has now basically entered the end of the formulation of post-quantum cryptography standardization. Looking back on this nearly ten-year standardization timeline, NIST officially announced four post-quantum cryptography standard candidate algorithms [8] on:

On July 5, 2022:

• Public key encryption/key encapsulation: CRYSTALS-KYBER;

• Digital signature: CRYSTALS-Dilithium, FALCON; SPHINCS;

Among them, CRYSTALS-KYBER, CRYSTALS-Dilithium, and FALCON are all lattice cryptographic algorithms, but their security foundations are different. KYBER is based on modular lattice-based MLWE difficult problems, Dilithium is based on modular lattice-based MLWE and MSIS difficult problems, and FALCON It is based on the SIS hard problem of NTRU lattice; in addition, SPHINCS is a stateless hash signature algorithm.

On August 24, 2023, CRYSTALS-KYBER, CRYSTALS-Dilithium, and SPHINCS have been formed into FIPS203, FIPS 204, and FIPS205 standard drafts [9] respectively. The FALCON standard draft will also be announced in 2024.

It is not difficult to see that most of the standard algorithms currently selected by NIST are based on the technical route of lattice cryptography. But NIST does not put eggs in the same basket. They are also actively looking for a variety of options other than lattice construction: while announcing four standard algorithms in 2022, they also announced the launch of the fourth round of post-quantum cryptography standard algorithm evaluation. Work, this round focuses on public key encryption/key encapsulation algorithms, and the selected algorithms are not based on lattice structure. In addition, a new round of solicitation for digital signature algorithms has also been launched. This round of solicitation is conducted independently from the fourth round of evaluation. It aims to enrich the portfolio of post-quantum signature algorithms, so it focuses more on the structural lattice-based algorithm that is different from the existing algorithm. A new proposal with small algorithm signature size and fast verification speed.

In addition to the NIST standard, the International Internet Standardization Organization IETF standardized the stateful hash signature algorithm XMSS as RFC 8391[10] and LMS as RFC 8554[11] in 2018 and 2019 respectively, and they were accepted by NIST.

Quantum algorithm for cracking lattice ciphers

On April 10, 2024, teacher Chen Yilei’s article "Quantum Algorithms for Lattice Problems" [12] on eprint caused a sensation in the academic world . The paper gives a polynomial-time quantum algorithm for solving difficult problems on lattices. This algorithm has a great impact on many cryptographic schemes based on difficult problems on lattice, and can cause many algorithms to no longer have the ability to resist quantum computer attacks. For example, Currently widely used homomorphic encryption algorithm based on LWE assumption. The correctness of the algorithm in the paper is not yet known.

The difficulty of the LWE problem was given a rigorous argument by Oded Regev in the paper "On lattices, learning with errors, random linear codes, and cryptography" [13]. Specifically, the author in the paper The difficulty of the LWE problem is reduced to the discrete Gaussian sampling problem on the lattice, and the discrete Gaussian sampling problem can be easily reduced to classic problems such as GapSVP, SIVP (of course, each specific problem has its specific parameters, here Neglected), which shows that the LWE problem is more difficult than these classic lattice problems. After the difficulty of the LWE problem has been strictly reduced, due to its simple structure, a large number of cryptographic schemes based on LWE have followed, covering basic cryptographic primitives such as (homomorphic) encryption, signatures, and key exchanges. As well as advanced cryptographic primitives such as identity-based encryption and attribute encryption. Among them, the ones that are widely used in the industry are mainly fully homomorphic encryption and the post-quantum standard algorithms (KYBER, Dilithium, etc.) announced by NIST mentioned above.

Summary

After the paper was made public, it caused a great sensation in the academic community and triggered discussions among many professionals. However, due to the extreme difficulty of understanding the paper, there may be less than 5 scholars in the world who can fully understand the content of the paper, and it may take 1-2 years to fully verify the correctness of the paper. At present, many people have expressed some relevant opinions on some forums, public accounts, Zhihu and other platforms. Everyone is analyzing the impact if the algorithm in the paper is correct. As for the correctness of the algorithm in the paper, the issue has not yet been One can draw conclusions. Among them, the famous cryptographer N. P. Smart published a blog article "Implications of the Proposed Quantum Attack on LWE" [14], which details the impact of this attack and some opinions, which is summarized as follows:

• This paper has not yet been peer-reviewed. Even if it is verified to be correct, it still relies on quantum computers. Therefore, as long as quantum computers have not yet come out, it will have no impact on the cryptographic schemes currently in use.

• According to the results given in the paper: it is still impossible to break the standardized algorithms Kyber and Dilithium previously given by NIST, but NIST may re-evaluate the parameters of these algorithms.

• For commonly used RLWE homomorphic encryption algorithms, such as BFV/CKKS/BGV, these algorithms are within the attack capabilities of this paper. However, whether from the perspective of academia or industry, the "homomorphism" of homomorphic encryption technology is more attractive than its "quantum resistance", and few people will use RLWE in pursuit of "quantum resistance". State-of-the-art encryption algorithms, like cryptographic schemes based on elliptic curves, rely on the discrete logarithm hard problem. Quantum algorithms to solve this problem have been proposed very early, but academia and industry are still studying and using these schemes.

Latest news: There is a problem with the calculation of Teacher Chen’s thesis, and the grid password alarm has been temporarily lifted.

[1] https://ethresear.ch/t/how-to-hard-fork-to- save-most-users-funds-in-a-quantum-emergency/18901/9

[2] Benioff P. The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines[J]. Journal of statistical physics, 1980, 22: 563-591.

[3] Shor P W. Algorithms for quantum computation: discrete logarithms and factoring[C]//Proceedings 35th annual symposium on foundations of computer science. Ieee, 1994: 124-134.

[4] Grover L K. A fast quantum mechanical algorithm for database search[C]//Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. 1996: 212-219.

[5] Bernstein, D.J. (2009). Introduction to post-quantum cryptography. In: Bernstein, D.J., Buchmann, J., Dahmen, E. (eds) Post-Quantum Cryptography. Springer, Berlin, Heidelberg.

[6] Gisin N, Ribordy G, Tittel W, et al. Quantum cryptography[J]. Reviews of modern physics, 2002, 74( 1): 145.

[7]https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization

[8]https://csrc.nist.gov/News/2022/pqc-candidates-to-be-standardized-and-round-4

[9]https://csrc.nist.gov/News/2023/three-draft-fips-for-post-quantum-cryptography

[10] Huelsing, A., Butin, D., Gazdag, S., Rijneveld, J., and A. Mohaisen, "XMSS: eXtended Merkle Signature Scheme", RFC 8391, DOI 10.17487/RFC8391, May 2018, https://www.rfc-editor. org/info/rfc8391>.

[11] McGrew, D., Curcio, M., and S. Fluhrer, "Leighton-Micali Hash-Based Signatures", RFC 8554, DOI 10.17487 /RFC8554, April 2019, https://www.rfc-editor.org/info/rfc8554>.

[12] Chen Y. Quantum Algorithms for Lattice Problems[ J]. Cryptology ePrint Archive, 2024.

[13] Regev O. On lattices, learning with errors, random linear codes, and cryptography[J]. Journal of the ACM (JACM), 2009, 56( 6): 1-40.

[14]https://nigelsmart.github.io/LWE.html

This article is written by ZAN Team (X Co-written by Dongni and Jiaxing (account @zan_team).

The above is the detailed content of Quantum of Solace for Lattice Cryptozoology? One article will help you analyze the academic controversy of lattice cryptography. For more information, please follow other related articles on the PHP Chinese website!