Cryptanalysis of the quaternion Rainbow
Cryptanalysis of the quaternion Rainbow
复制标题
四元数 Rainbow 的密码分析
DOI：
10.1007/978-3-642-41383-4_16
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Yasufumi Hashimoto
中科院分区：
文献类型：
--
作者：
Taisei Motomura;Kazunori Takahashi; Yuji Kasashima;Fumihiko Uesugi and Akira Ando;土岡俊介;土岡俊介;土岡俊介;Shunsuke Tsuchioka;Shunsuke Tsuchioka;Shunsuke Tsuchioka;Yasufumi Hashimoto;橋本康史;橋本康史;Yasufumi Hashimoto
彩虹签名方案是一种基于求解多元二次方程组的签名方案。虽然它的签名生成和验证速度很快，并且在适当的参数选择下目前安全性足够，但密钥长度相对较大。最近，四元数彩虹--四元数环上的彩虹--是由Yasuda，Sakurai和Takagi(CT-RSA‘12)提出的，目的是在不损害安全性的情况下减小彩虹的密钥尺寸。然而，一个新的漏洞出现在四元数环的结构中；事实上，Thomae(SCN‘12)发现四元数彩虹比相同大小的原始彩虹更不安全。在本文中，我们进一步研究了四元数彩虹的结构，并证明了四元数彩虹是彩虹的稀疏版本之一。它的稀疏结构导致了四元数彩虹的脆弱性。特别是，我们发现偶数特征域上的四元数彩虹，其安全级别经Thomae分析估计约为原始彩虹的3/4，其安全性几乎与原始彩虹的1/4大小相同。
Rainbow is one of signature schemes based on the problem solving a set of multivariate quadratic equations. While its signature generation and verification are fast and the security is presently sufficient under suitable parameter selections, the key size is relatively large. Recently, Quaternion Rainbow — Rainbow over a quaternion ring — was proposed by Yasuda, Sakurai and Takagi (CT-RSA'12) to reduce the key size of Rainbow without impairing the security. However, a new vulnerability emerges from the structure of quaternion ring; in fact, Thomae (SCN'12) found that Quaternion Rainbow is less secure than the same-size original Rainbow. In the present paper, we further study the structure of Quaternion Rainbow and show that Quaternion Rainbow is one of sparse versions of the Rainbow. Its sparse structure causes a vulnerability of Quaternion Rainbow. Especially, we find that Quaternion Rainbow over even characteristic field, whose security level is estimated as about the original Rainbow of at most 3/4 by Thomae's analysis, is almost as secure as the original Rainbow of at most 1/4-size.