类SIMON算法参数等价类研究

Research on Equivalent Class of SIMON-like Cipher Parameters

SIMON算法是由美国国家安全局(NSA)在2013年设计的轻量级分组密码算法.在公布算法时,设计者并未给出其安全评估.为探讨参数选取准则,在CRYPTO 2015上, K?lbl等人提出了类SIMON算法仿射等价,并据此对类SIMON算法循环左移参数进行等价划分,利用计算机遍历搜索得到全部等价类.之后,在ACNS 2016上, Kondo等人利用同样的分类方法,对32比特分组长度的类SIMON算法研究了其积分和不可能差分分析.在ISPEC 2016上, Zhang等人研究了不同分组长度类SIMON算法的积分性质.然而,在已有文献中,算法的仿射等价类均通过计算机遍历搜索得到.本文通过将仿射等价类转化为左乘作用等价类进行研究,从理论上证明了等价类个数与算法分组长度2n之间的关系,并根据证明过程中对参数空间的划分,直接得到算法全部等价类表达式,从而优化类SIMON算法的安全性评估.结果表明,利用仿射等价,类SIMON算法的循环参数空间从全空间O(n^3)降到O(n^2),与计算机模拟实验结果一致.

The SIMON lightweight block cipher is designed by National Security Agency(NSA)in 2013.However,no security assessment was conducted by the designers when it was released.To explore the design criterion,at CRYPTO 2015,K?lbl et al.proposed the concept of affine equivalence of SIMON-like ciphers.By this equivalent relationship,equivalence partition is applied to the parameter space of SIMON-like ciphers.K?lbl’s analysis acquires differential and linear characteristics by computer searching.Hereafter,using the same equivalent relationship,Kondo et al.studied the influence of parameters on integral and impossible differential analysis at ACNS 2016.At ISPEC2016,Zhang et al.analyzed the integral properties of all block size of SIMON-like ciphers.It is known from public literature that,the equivalent subsets can be acquired by computer searching.This study theoretically proves the relationship between the number of equivalent subsets and the block size.Moreover,by partition of parameter space,the equivalent subsets can be represented explicitly,which is beneficial for the assessment of SIMON-like ciphers.The results in this study show that,by finding the affine equivalence,the search space can be reduced from O(n^3)to O(n^2),which is coincident with the experimental results.