New Complexity Estimation on the Rainbow-Band-Separation Attack
New Complexity Estimation on the Rainbow-Band-Separation Attack
复制标题
DOI：
10.1016/j.tcs.2021.09.043
复制
发表时间：
2021-10
期刊：
影响因子：
--
通讯作者：
Shuhei Nakamura;Yasuhiko Ikematsu;Yacheng Wang;Jintai Ding;T. Takagi
中科院分区：
文献类型：
--
作者：
Shuhei Nakamura;Yasuhiko Ikematsu;Yacheng Wang;Jintai Ding;T. Takagi
多变量公钥密码学是后量子密码学的候选方案，它允许生成特别短的签名和快速验证。Ding和Schmidt提出的彩虹签名方案就是这样一种多元密码体制，它被认为是对所有已知攻击都是安全的。彩虹-频带分离攻击通过求解某些二次方程组来恢复彩虹的秘密密钥，其复杂性通过称为正则度的众所周知的理论值来估计。然而，在实验中，规则度一般大于解析度，无法得到准确的估计。本文提出了一种基于Gröbner基算法的彩虹带分离攻击复杂度的新的理论值，与使用正则度的算法相比，该算法提供了更精确的估计。该理论值由二元幂函数级数∏i=1m(1−t1d1 t2 di2)(1−t1)n1(1−t2)n2得到。由于二元幂函数级数与一元幂函数级数在t1=t2处重合，从而推导出正则度，在一定条件下，理论值小于或等于正则度。此外，我们还证明了使用混合方法的彩虹带分离攻击与高等级攻击之间的关系。通过考虑这种关系和我们的理论价值，我们得到了彩虹带分离攻击的一个新的复杂性估计。此外，将我们的理论值应用于NIST PQC第二轮中使用的复杂性公式，我们表明需要对建议的彩虹参数集进行轻微修改。从而为NIST PQC标准化项目中影响彩虹参数选择的二次多项式系统解度的一般估计提供了新的理论值。
Multivariate public key cryptography is a candidate for post-quantum cryptography, and it allows generating particularly short signatures and fast verification. The Rainbow signature scheme proposed by Ding and Schmidt is such a multivariate cryptosystem, and it is considered secure against all known attacks. The Rainbow-Band-Separation attack recovers a secret key of Rainbow by solving certain systems of quadratic equations, and its complexity is estimated by the well-known theoretical value called the degree of regularity. However, the degree of regularity is generally larger than the solving degree in experiments, and an accurate estimation cannot be obtained. In this article, we propose a new theoretical value for the complexity of the Rainbow-Band-Separation attack using a Gröbner basis algorithm, which provides a more precise estimation compared to that using the degree of regularity. This theoretical value is deduced by the two-variable power series∏ i= 1 m (1− t 1 d i 1 t 2 d i 2)(1− t 1) n 1 (1− t 2) n 2. Since the two-variable power series coincides with the one-variable power series at t 1= t 2 deriving the degree of regularity, the theoretical value is less than or equal to the degree of regularity under a certain condition. Moreover, we show a relation between the Rainbow-Band-Separation attack using the hybrid approach and the HighRank attack. By considering this relation and our theoretical value, we obtain a new complexity estimation for the Rainbow-Band-Separation attack. Furthermore, applying our theoretical value to the complexity formula used in the NIST PQC 2nd round, we show that a slight modification of the proposed Rainbow parameter sets is required. Consequently, we provide a new theoretical value for generally estimating the solving degree of a bi-graded polynomial system, which can influence the parameter selection of Rainbow in the NIST PQC standardization project.