Formal Power Series on Algebraic Cryptanalysis
Formal Power Series on Algebraic Cryptanalysis
复制标题
DOI：
--
复制
发表时间：
2020-07
期刊：
影响因子：
--
通讯作者：
Shuhei Nakamura
中科院分区：
文献类型：
--
作者：
Shuhei Nakamura
在密码学中，利用Grobner基的攻击已经破坏了几个密码系统。计算Grobner基的复杂性占主导地位的整体计算和它的估计是重要的，这样的密码分析。复杂度是通过求解度来给出的，但对于密码学产生的大规模系统，复杂度的值很难确定。在大量实验的基础上，提出了用规则度和首落度作为求解度的指标。如果一个给定的系统是半正则的，则通过使用从某个幂级数导出的正则度来估计复杂性，否则，通过使用从合点的构造导出的第一下降度来估计复杂性。在非半正则系统上也定义了正则度，并且在实验上正则度大于第一次下降度，但理论上这些关系并不明确。此外，与正则度相反，第一次下降度专门针对每个密码系统进行了研究，并且没有给出对一般系统的讨论。在本文中，我们给出了足够大的域上多项式系统第一次下降度的上界。详细地，我们证明了这个上界是一个非半正则系统的正则度。此外，我们还证明了多阶多项式系统的上界是一个仅由其多阶数决定的值。此外，我们证明了我们的结果中的域的顺序的条件是满足对实际的多变量密码系统的攻击。从而，在域的阶数一定的条件下，明确了域的首落度与正则度之间的关系，为利用多元幂级数进行密码分析提供了一种理论方法。
In cryptography, attacks that utilize a Grobner basis have broken several cryptosystems. The complexity of computing a Grobner basis dominates the overall computing and its estimation is important for such cryptanalysis. The complexity is given by using the solving degree, but it is hard to decide this value of a large scale system arisen from cryptography. Thus the degree of regularity and the first fall degree are used as proxies for the solving degree based on a wealth of experiments. If a given system is semi-regular, the complexity is estimated by using the degree of regularity derived from a certain power series, otherwise, by using the first fall degree derived from a construction of a syzygy. The degree of regularity is also defined on a non-semi-regular system and is experimentally larger than the first fall degree, but those relation is not clear theoretically. Moreover, in contrast to the degree of regularity, the first fall degree has been investigated specifically for each cryptosystem and its discussion on generic systems is not given. In this paper, we show an upper bound for the first fall degree of a polynomial system over a sufficiently large field. In detail, we prove that this upper bound for a non-semi-regular system is the degree of regularity. Moreover, we prove that the upper bound for a multi-graded polynomial system is a certain value only decided by its multi-degree. Furthermore, we show that the condition for the order of a field in our results is satisfied in attacks against actual multivariate cryptosystems. Consequently, under a reasonable condition for the order of a field, we clear a relation between the first fall degree and the degree of regularity and provide a theoretical method using a multivariate power series for cryptanalysis.