广义多项式函数单圈性判定的一个新证明

A New Proof of Determination for the Generalized Polynomial Single Cycle Function

T-函数是由Klimov和Shamir在2002年提出的一类新的非线性函数,这种函数软硬件实现速度快、效率高,而且所生成的序列线性复杂度高、稳定性强,故有望代替线性反馈移位寄存器,成为新的序列密码设计的非线性驱动环节,多项式函数作为一类密码学中常用的T-函数,其可逆性、周期性一直是相关研究中的重要问题,Klimov利用函数的代数正规型给出了多项式函数f(x)=a_0+a_1x+…+a_dx^d mod 2~n是单圈的充分条件,同时借助于"bit-slice"方法和参数的概念给出了广义多项式函数f(x)=a_0⊕a_1x⊕…⊕…a_dx^d mod 2~n是置换的充分条件.进一步地,刘卓军等借助于徐克舰的2-adic整数的乘法公式,给出了函数f(x)=a_0⊕a_1x⊕…⊕a_dx^d mod 2~n单圈性的判定定理.本文利用1-Lipschitz函数模2-微分理论,发展使用模4-微分确定遍历变换的技术,并结合"bit-slice"方法,给出函数遍历性判定的一种新方法,进而给出了此类函数单圈性判定定理的一个新证明.

T-functions, proposed by Klomiv and Shamir in 2002, is a new class of nonlinear functions,which could be efficiently implemented in both software and hardware and produce sequences with high linear complexity and good stability. T-functions can substitute LFSR as a new driver in stream ciphers. Polynomial functions, as a special class of T-functions, have numerous applications in cryptography.Their invertibility and periodicity are two important research topics. Using the ANF of the function,Klimov et al gave a sufficient condition for polynomial function f(x) = a_O + a_1 x+… +a_dx^d mod 2~n to be a single-cycle, while combing the bit-slice methods and the parameter they gave a sufficient condition for generalized polynomial function f(x) = a_O ⊕ a_1 x⊕…⊕a_dx^d mod 2~n to be a permutation. Further more, Liu Zhuo-Jun et al gave the necessary and sufficient condition for the function f(x)=a_0⊕a_1 x⊕…⊕a_dx^d mod 2~n to be a single-cycle by means of the multiplication formula of2-adic integers given by Xu Ke-Jian. In this paper, by using the modulo 2 derivatives of 1-Lipschitz function, improving the technique of determining the ergodic transformation with use of the modulo4 derivatives, and using the bit-slice methods, a new method to determine the ergodic transformation is proposed, and a new proof of determination of the generalized polynomial single cycle function is given.