摘要
对于g(x) =f(xA +b) +l·x +c ,给定f(x) ,g(x) ,如何求取等价关系A ,b ,l,c是一个有用的问题 .该文利用Walsh谱和自相关函数谱作为工具 ,给出的算法 1可以求取g(x) =f(xA)型的等价关系 .针对g(x) =f(xA +b)+l·x +c类型的等价关系 ,当b已知时 ,基于Fuller Millan算法给出的算法 2比Fuller Millan算法至少要快k - 1倍 ,其中k为函数绝对自相关函数谱含有的谱类个数 .应用于AES的S 盒的 8个布尔函数间等价关系的求取 ,算法 2比Fuller Millan算法提高速度近 2 0倍 .应用于IP (IsomorphismofPolynomials)问题的分析 ,指出Patarin所给参数的IP问题是可解的 ,因此基于IP问题的密码体制是不安全的 .
Let f(x),g(x) be two Boolean functions such that g(x)=f(xA+b)+l·x+c. Given the two functions, how to get equivalence relationship A,b,l,c is a useful problem. Using Walsh transform and autocorrelation transform, authors’ first algorithm can get the equivalence relationship of g(x)=f(xA). To g(x)=f(xA+b)+l·x+c, if b is known, authors’ second algorithm based on Fuller-Millan algorithm is at least k-1 times as fast as the Fuller-Millan algorithm, where k is the number of distinct absolute values of the autocorrelation function of f(x). In analyzing the equivalence relationship of Boolean functions in S -box of AES, the second algorithm is about 20 times as fast as the Fuller-Millan algorithm. In analysis of IP (isomorphism of polynomials) problem over F 2, authors point out that the IP problem with the parameters given by Patarin is solvable and thus the cryptosystem based on it is not secure.
出处
《计算机学报》
EI
CSCD
北大核心
2004年第11期1528-1532,共5页
Chinese Journal of Computers
基金
国家自然科学基金 (90 10 40 0 5
66973 0 3 4)
国家"八六三"高技术研究发展计划项目基金 (2 0 0 2AA14 10 5 1)
教育部博士点基金项目 (2 0 0 2 0 4860 46)资助 .
关键词
布尔函数
线性等价
AES
IP问题
Boolean functions
linear equivalence
AES
isomorphism of polynomials
