由於近年來對量子計算、量子電腦等相關方面的研究，量子發展對現今密碼系統可能造成的破壞也引起了大家的警覺，像我們所熟知的RSA、DSA和橢圓曲線密碼學在面對量子電腦時都被認為是脆弱的。基於此，美國國家標準與技術局(NIST)提出了後量子密碼學標準化競賽，來選出適用於未來的公鑰加密和數位簽章系統，而本文中提到的Rainbow簽名系統則在數位簽章部分進入第三輪成為決賽的候選者之一。
我們將會先介紹目前較為主流的四種不同類別的後量子密碼系統，接著一步步走進本文主題，先由可以被視為Rainbow系統前身的UOV加密法，再到Rainbow系統本身的結構，對其有了初步的了解後，就接著進入各種不同的針對UOV和Rainbow系統的攻擊演算法，其中包含了存在已久的攻擊方法和近年來由於後量子密碼學標準化競賽而被發現的新攻擊演算法，而其中特別是由Beullens在2020提出的兩個新攻擊演算法，被宣稱是會極大地影響到Rainbow在標準化競賽中所宣稱的安全性等級，而Rainbow的團隊也基於此做出了回應，表示Rainbow簽章仍舊具有足夠的安全等級，雖然這些討論依舊可能影響NIST在標準化競賽中對Rainbow的信心，但也同時讓我們對於Rainbow系統的結構有了更進一步的了解，和指引關於未來可以增進改良方向的一大契機。

Due to the probability of the advent of large-scale quantum computer, most of current public-key cryptosystems, such as RSA, DSA and elliptic curve cryptosystems which security depends on the integer factorization, the discrete logarithm problem or the elliptic-curve discrete logarithm problem will be insecure. Searching for cryptosystems which are able to resist quantum computing is immediate. The Rainbow signature scheme proposed in 2005 by J. Ding and D. Schmidt is one of the most promising candidates to against quantum computer attacks. In this thesis, we first introduce the ``precursor" of the Rainbow signature system called the Unbalance Oil and Vinegar scheme and the Rainbow signature scheme afterword. Moreover, we will see some general attack systems which existed for a long time against the Unbalance Oil and Vinegar scheme and the Rainbow signature scheme. Then we show that how these known attack systems restrict the choices of the parameter sets for the Rainbow signature scheme at the beginning of finding secure post-quantum cryptosystems. Last, we will show some relatively new attacks which were proposed after the Rainbow signature scheme has been submitted to NIST's competition to run for the post-quantum cryptographic standards. Those new attacks impacted the known security of the Rainbow and the submitted parameter sets and may effect the choices of NIST when they decide the standards. These new attacks also take an important position on the current multivariate cryptography analysis, because before the quantum algorithms and post-quantum cryptography have been all the rage, there has been no great progress of multivariate cryptanalysis for a long time. After the Rainbow team's response of the attacks proposed by Beullens, it seems that the Rainbow signature scheme is still secure enough and may be a good choice of the post-quantum cryptography standards.

Neal Koblitz, Alfred J Menezes, Yi-Hong Wu, and Robert J Zuccherato. Algebraic
aspects of cryptography, volume 198. Springer, 1998.
Daniel J Bernstein. Introduction to post-quantum cryptography. In Post-quantum cryptography, pages 1–14. Springer, 2009.
Daniel J Bernstein and Tanja Lange. Post-quantum cryptography. Nature, 549(7671):188–194, 2017.
Jintai Ding and Bo-Yin Yang. Multivariate public key cryptography. In Post-quantum cryptography, pages 193–241. Springer, 2009.
Jacques Patarin. The oil and vinegar algorithm for signatures. In Dagstuhl Workshop on Cryptography, 1997, 1997.
Aviad Kipnis and Adi Shamir. Cryptanalysis of the oil and vinegar signature
scheme. In Annual international cryptology conference, pages 257–266. Springer, 1998.
Aviad Kipnis, Jacques Patarin, and Louis Goubin. Unbalanced oil and vinegar signature schemes. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 206–222. Springer, 1999.
Jintai Ding and Dieter Schmidt. Rainbow, a new multivariable polynomial signature scheme. In International conference on applied cryptography and network security, pages 164–175. Springer, 2005.
Enrico Thomae. About the security of multivariate quadratic public key schemes. 2013.
Nicolas Courtois, Alexander Klimov, Jacques Patarin, and Adi Shamir. Efficient algorithms for solving overdefined systems of multivariate polynomial equations. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 392–407. Springer, 2000.
Bo-Yin Yang and Jiun-Ming Chen. All in the xl family: Theory and practice. In International Conference on Information Security and Cryptology, pages 67–86. Springer, 2004.
Javier Verbel, John Baena, Daniel Cabarcas, Ray Perlner, and Daniel Smith-Tone. On the complexity of “superdetermined” minrank instances. In International Conference on Post-Quantum Cryptography, pages 167–186. Springer, 2019.
Shuhei Nakamura, Yacheng Wang, and Yasuhiko Ikematsu. Analysis on the minrank attack using kipnis-shamir method against rainbow. Cryptology ePrint Archive, 2020.
Ray Perlner and Daniel Smith-Tone. Rainbow band separation is better than we thought. Cryptology ePrint Archive, 2020.
Enrico Thomae. A generalization of the rainbow band separation attack and its applications to multivariate schemes. Cryptology ePrint Archive, 2012.
Kyung-Ah Shim and Namhun Koo. Algebraic fault analysis of uov and rainbow with the leakage of random vinegar values. IEEE Transactions on Information Forensics and Security, 15:2429–2439, 2020.
Ward Beullens. Improved cryptanalysis of uov and rainbow. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 348–373. Springer, 2021.
The Rainbow Team. Response to recent paper by ward beullens. https://troll.iis.sinica.edu.tw/by-publ/recent/response-ward.pdf.