量子前沿

彩虹签名 (Rainbow Signature) 属于多元公钥密码系统家族，基于多元二次多项式 (MQ, Multivariate Quadratic polynomial) 问题，是潜在后量子密码系统的安全基础之一。

彩虹签名是由现任(2021)北京清华大学丘成桐数学科学中心-丁津泰教授于 2005 年6月发表于Lecture Notes in Computer Science 3531:164-175，它是以 Jacques Patarin 发明的油醋 (OV) 签名与不平衡油醋 (UOV)  签名为基础。与Falcon相同为NIST三个正选的数字签名算法之一，也是NIST第三轮评选中唯一由华人主导的算法。

由于多变量体系的密码系统使用有限域 (Galois field) 运算，而彩虹签名采用相对较小的有限域并采用基础的逻辑运算，这让软件与硬件相关的实作面更加有效率 (逻辑运算是数字硬件的基础)。ps. 关于有限域 (Galois field) 运算可以参考这个视频。

彩虹签名应用上的优势在于有非常短的签名长度(66 byte)，但公钥与私钥与其它后量子签名相比略长(私钥约:100000 byte, 公钥约:  160000 byte)。

Rainbow 也是NIST 后量子密码学项目中为一有专利的数字签名算法 (该专利于2029-08-26到期)。

密钥与签名长度