The latest developments in the field of quantum computing have made many people worried about the prospects of classical cryptography. On December 4, Chinese scientists successfully verified the optical quantum computer—Jiuzhang, which has built a quantum computing prototype with 76 photons (qubits). , which is no longer so far away from the thousands of available qubits needed to break classical cryptography. (In terms of speed, it only takes 200 seconds to solve the mathematical algorithm Gaussian Bose sampling, while the current supercomputer takes 600 million years. It is generally believed that 50 qubits are the key threshold to prove that quantum computers are expected to surpass traditional computers) .
If quantum computing makes a breakthrough in the future, according to some people's estimates, by 2031, the probability of RSA and ECC (elliptic encryption) algorithms being cracked is about 50%, and blockchains such as Bitcoin and Ethereum are using In addition to classical cryptography, although Bitcoin uses a double SHA256 algorithm, which makes it an additional line of defense compared with the security systems used by banks and Alipay, it still has a variety of attack vectors. It seems that quantum computing is becoming the development of the blockchain. The Sword of Mocles, what will the world be like from now on? Will Quantum Computers Get Blockchain Secrets?In fact, even with quantum computers, many classical security algorithms will still be effective, not to mention that quantum security technology is also booming. Some researchers in the blockchain industry are also constantly researching related quantum-resistant encryption algorithms. As early as 2017, NIST started the post-quantum cryptography standardization process, hoping to prepare quantum-resistant cryptography before 2022 ( quantum-resistant cryptography), when a total of 69 candidate algorithms met both the minimum acceptance criteria and submission requirements. Because of the strict evaluation criteria and selection process, the third-round shortlist and candidate candidates were not announced until July 22, 2020. The digital signature that everyone has been most optimistic about is the anti-quantum signature promoted by the Swiss ABCMint Mathematical Algorithm Foundation. scheme, one of the anti-quantum algorithms supported by the Post-Quantum Encryption Foundation, the signature anti-quantum signature scheme with the shortest signature length - rainbow signature Rainbow, undoubtedly entered the third round of NIST digital signature list.
The National Institute of Standards and Technology (National Institute of Standards and Technology, NIST enjoys a high international reputation. NIST has four researchers who have won the Nobel Prize for their achievements in physics: William Daniel Phillips (1997), Eric Cornell (2001), John Hall (2005) and David Vineland (2012), the most recipients of any US government laboratory.#The third round shortlist (digital signature)Among them, Rainbow is the signature with the minimum signature length, and the signature lengths of Falcon and Dilithium are very long; the three selected Dilithiums have the highest probability of being cracked. Falcon is an NTRU architecture, and NTRU is a bit like a leaky pot. It is patched up, but there are always problems. Falcon is the one that the most people are researching and besieging to crack. The biggest advantage of Rainbow is that it has the longest history, it is almost recognized that there is no way to crack it, and the signature is the shortest. Rainbow is an NP-Hard problem, and it is difficult to find loopholes. Therefore, Rainbow should be the only quantum-resistant signature that digital currencies can adopt for a long time in the future.
Figure: Comparison of the public key and signature sizes of the three algorithms
Rainbow is a multivariate signature scheme whose layered structure is based on the Unbalanced Oil-Gooseberry (UOV) signature scheme. The extra structure imposed by the Rainbow layer exposes the scheme to more cryptanalytic techniques, but increases the efficiency of the scheme. Rainbow provides fast signing and verification and very short signatures, but with very large public keys.Rainbow is a multivariate signature scheme whose layered structure is based on the Unbalanced Oil-Gooseberry (UOV) signature scheme. The extra structure imposed by the Rainbow layer exposes the scheme to more cryptanalytic techniques, but increases the efficiency of the scheme. Rainbow provides fast signing and verification and very short signatures, but with very large public keys.Choosing Rainbow increases the diversity of shortlisted signature schemes; however, due to the very large key size, Rainbow is not suitable as a general-purpose signature algorithm to replace the algorithms currently appearing in FIPS 186-4. In particular, large public keys make certificate chains very large. However, some applications do not need to send keys very often. For such applications, Rainbow provides small and fast signatures. The only other advanced signature candidate with similar performance characteristics, GeMSS, has a much larger key and seems difficult to implement on very low-end devices. For these reasons, Rainbow was selected as a finalist.
NIST researchers noted a gap between the performance and theoretical complexity of some attack vectors related to the Rainbow scheme. In the second round, some closer theoretical analyzes (along with new algorithms) of these famous attacks have been published. In particular, parameter tuning for all parameter sets is necessary in order to achieve the declared level of safety. However, with more conservative parameter choices, it should be possible to achieve the declared level of safety with minimal performance cost.Before Rainbow is ready for standardization, its parameters must be tuned to ensure it meets its stated security goals. Additionally, NIST prefers algorithms with royalty-free licenses to encourage widespread adoption.
# CRYSTALS-DILITHIUM #
The security of DILITHIUM relies on the hardness of MLWE and the Modular Short Integer Solution Problem (MSIS), and follows the Fiat-Shamir and abort techniques. DILITHIUM uses the same modulus and ring for all parameter sets and samples via a uniform distribution, which makes it simpler to implement than its main competitor, FALCON.Overall, DILITHIUM has strong, well-balanced performance in key and signature sizes, as well as in the efficiency of key generation, signing, and verification algorithms. DILITHIUM performed well in practical experiments.In the second round, DILITHIUM added the option to generate signatures non-deterministically, and added an implementation based on using AES instead of SHAKE to illustrate the future advantages of hardware instructions. In addition, new research on security in QROM, applicable to DILITHIUM, was published.NIST encouraged the DILITHIUM team to add a 5-category parameter set. More research is needed in understanding the specific security, as DILITHIUM's CoreSVP security strength parameter set is the lowest of all grid schemes that are still in progress. NIST selected DILITHIUM as a finalist and expects either DILITHIUM or FALCON to be standardized as the main post-quantum signature scheme by the end of the third round.
# FALCON #
FALCON is a grid-based signature scheme that utilizes"Hashes and signatures"paradigm. The security is based on the difficulty of the SIS (short integer solution) problem on the NTRU grid. Security proofs are given in both the random Olympiad model (ROM) and QROM, and strict reduction is carried out. The implementation of FALCON is more complex than DILITHIUM, requiring tree-like data structures, lots of floating-point operations, and random sampling from several discrete Gaussian distributions.One of the advantages of FALCON is that it provides the smallest bandwidth (public key size and signature size) of all second-round digital signature schemes. FALCON is also efficient at signing and verification, although key generation is slower. FALCON can be easily dropped into existing protocols and applications and provides very good overall performance.At the beginning of the second round, FALCON removed their category 3 parameter set, which simplified their specification and implementation as they used different modulus and ring choices. Another major update during the second round was the constant-time implementation released shortly after NIST's second PQC standardization meeting.In a third round, NIST encouraged more scrutiny of the FALCON implementation to determine whether using floating-point arithmetic was more prone to implementation errors than other schemes, or provided an avenue for side-channel attacks. Also, if a sampler's test vectors are available, it might be possible to make it deterministically test random seeds, so that the implementation can be verified using known answer tests (KATs). Like several other candidates, the CoreSVP security strength of FALCON's category 1 parameters is relatively low, so further research is needed.
Appendix: Rainbow Signature 3rd Round Finalist Link: https://groups.google.com/a/list.nist.gov/forum/m/#!topic/pqc-forum/0ieuPB-b8egScreenshots of the original text of the third round of rainbow signature:
