兩類偶特征有限域上的幾乎完全非線性函數(shù)

張習勇， 李乃江， 魯志波, 李德全

(1.天地一體化信息技術(shù)國家重點實驗室 北京 100020； 2.解放軍信息工程大學(xué) 河南 鄭州 450001)

?

兩類偶特征有限域上的幾乎完全非線性函數(shù)

張習勇1,2， 李乃江1,2， 魯志波1, 李德全2

(1.天地一體化信息技術(shù)國家重點實驗室 北京 100020； 2.解放軍信息工程大學(xué) 河南 鄭州 450001)

密碼學(xué)中所涉及的函數(shù)包括布爾函數(shù)和向量值函數(shù)，這兩類函數(shù)的安全性指標包括差分一致性和非線性度等.構(gòu)造密碼學(xué)性質(zhì)良好的低差分一致性函數(shù)是密碼學(xué)中的熱點問題.構(gòu)造了兩類偶特征有限域上的、新的幾乎完全非線性(almost perfect nonlinear，APN)函數(shù)，并分別證明了它們與偶特征有限域上已知的單項式APN函數(shù)EA不等價.

差分一致性； APN函數(shù)； EA等價； CCZ等價

0 引言

定義2 代數(shù)次數(shù)小于等于1的函數(shù)稱為仿射函數(shù)，滿足f(0)=0的仿射函數(shù)稱為線性函數(shù).

定義3 如果存在仿射置換A1、A2和仿射函數(shù)A使得g=A1°f°A2+A，則稱GF(pn)→GF(pn)的兩個函數(shù)f和g擴展仿射等價，簡稱EA等價.易知，EA等價的非常數(shù)函數(shù)具有相同的代數(shù)次數(shù).文獻[5]提出一種更一般的等價概念，即CCZ等價.

2005年以前，人們主要關(guān)注偶特征有限域上的單項式APN函數(shù)構(gòu)造與等價歸類，表1列出了偶特征有限域GF(2n)上目前已知的6類單項式APN函數(shù)，其中n為擴張次數(shù).2006年以后，學(xué)者們相繼構(gòu)造出了多類偶特征有限域上，與已知的單項式APN函數(shù)不等價的多項式APN函數(shù)，文獻[7]中列出了主要結(jié)果.

本文通過對偶特征有限域上已有的兩類APN函數(shù)添加和式，構(gòu)造了兩類新的APN函數(shù)，利用反證法，通過比較等式兩邊對應(yīng)項系數(shù)，證明了所構(gòu)造的兩類APN函數(shù)與表1中的6類單項式APN函數(shù)EA不等價.

表1 偶特征有限域GF(2n)上已知的單項式APN函數(shù)Tab.1 The previously known monomial APN functions over even characteristic finite fields GF(2n)

1 兩類偶特征有限域上的APN函數(shù)

證明 對任意0≠a∈GF(2n)，令Δa(f(x))=f(x)+f(x+a)+f(a)，則

Δa(f(x))=ax2s+a2sx+ax2m+a2mx+u2m(a2sx2m+a2mx2s+ax2s+m+a2s+mx)+

(1)

是一個線性化多項式.

因為Δa(f(x))=0與Δa(f(ax))=0的解的個數(shù)相同，所以只需考慮等式

Δa(f(ax))=(u2m-1a2s+m+2m+u2ma2s+m+1)x2s+m+(a2m+1+u2ma2s+2m+u2m-1a2s+m+2m)x2m+

(2)

在GF(2n)中的解個數(shù).

對等式(2)做2m次方，可得

Δa2m(f(ax))=(u1-2ma2s+1+ua2s+2m)x2s+(a2s+1+ua2s+m+1+u1-2ma2s+1)x+(a2s+m+2m+ua2s+m+1)x2s+m+

(3)

因為Dobbertin函數(shù)的Walsh譜與所有二次函數(shù)的Walsh譜均不相同[8-9]，而擴展Walsh譜是函數(shù)的CCZ等價的一個不變量，故得定理2.

定理2 定理1中的APN函數(shù)與表1中Dobbertin函數(shù)CCZ不等價.

由于CCZ等價是比EA等價更廣泛的一種等價關(guān)系，可得推論1.

推論1 定理1中的APN函數(shù)與表1中Dobbertin函數(shù)EA不等價.

定理3 定理1中的APN函數(shù)f(x)與已知的單項式APN函數(shù)EA不等價.

證明 由推論1可知定理1中的APN函數(shù)f(x)與Dobbertin函數(shù)EA不等價.

因為Inverse函數(shù)、Welch函數(shù)和Niho函數(shù)的域擴張次數(shù)n只能是奇數(shù)，所以定理1中的APN函數(shù)與Inverse函數(shù)、Welch函數(shù)和Niho函數(shù)EA不等價.EA等價的必要條件是函數(shù)的代數(shù)次數(shù)相同，因而二次函數(shù)f(x)與非二次函數(shù)Kasami函數(shù)EA不等價.

(4)

由式(4)+u2m-1(4)2m可得

(5)

因為u是GF(2n)上的一個本原元，所以u2m-1≠1.

比較等式(5)兩邊的系數(shù)，令t為正整數(shù)，當t≠r時，有

(6)

(7)

(8)

假設(shè)存在j,使得aj≠0.如果存在k,使得bj+k-m≠0，當t≠r時，由(6)式可得

(9)

bj-m=0.

(10)

bj+r-m=0.

(11)

下面給出另外一類偶特征有限域上的與已知的單項式APN函數(shù)EA不等價的APN多項式函數(shù).

Δa(f(ax))=ua2s+t+1(x+x2s+t)+u2sa2s+2t(x2s+x2t)+va2s+t+2t(x2t+x2s+t)+

(12)

在GF(2n)中的解個數(shù).

因為a2s+t+1是3次方元，且F2s中的元素均為3次方元，而u不是3次方元，所以ua2s+t+1?GF(2s)，所以ua2s+t+1+u2sa2s+2t≠0.

定理5 定理4中的APN函數(shù)與Dobbertin函數(shù)CCZ不等價.

推論2 定理4中的APN函數(shù)與Dobbertin函數(shù)EA不等價.

定理6 定理4中的APN函數(shù)與已知的單項式APN函數(shù)EA不等價.

證明 由推論2可知定理4中的APN函數(shù)f(x)與Dobbertin函數(shù)EA不等價.

因為Inverse函數(shù)、Welch函數(shù)、Niho函數(shù)的域擴張次數(shù)n只能是奇數(shù)，所以定理4中的APN函數(shù)與Inverse函數(shù)、Welch函數(shù)、Niho函數(shù)EA不等價.同定理3所述，Kasami函數(shù)因為與函數(shù)f(x)的代數(shù)次數(shù)不同，所以它們EA不等價.

下面證明函數(shù)f(x)與表1中的Gold函數(shù)EA不等價.

(13)

由式(13)+(13)2s可得

(14)

因為v∈GF(22s)GF(2s)，所以v+v2s≠0，比較等式(14)兩邊的系數(shù)，令z為正整數(shù)，當z≠r時有:

(15)

(16)

(17)

假設(shè)存在j使得aj≠0.如果存在k使得bj+k-t≠0，當z≠r時，由(15)式，可得

(18)

bj-t=0，

(19)

bj+r-t=0.

(20)

注 本文所構(gòu)造的兩類APN函數(shù)均為二次函數(shù).所構(gòu)造的兩類APN函數(shù)與Gold函數(shù)和Dobbertin函數(shù)是CCZ不等價的.[10]

[1] 祁傳達, 袁小轉(zhuǎn), 邵輝. 布爾函數(shù)的跡單項式逼近[J]. 信陽師范學(xué)院學(xué)報(自然科學(xué)版), 2014，27(3):440-443.

[2] 涂自然, 鄧映蒲. 一類M-M型bent函數(shù)的代數(shù)免疫度[J]. 河南科技大學(xué)學(xué)報(自然科學(xué)版), 2010, 31(4):81-83.

[3] BIHAM E, SHAMIR A. Differential cryptanalysis of DES-like cryptosystems[J]. Journal of cryptology, 1991, 4(1):3-72.

[4] NYBERG K. Differentially uniform mappings for cryptography[J]. Lecture notes in computer science, 1994, 765:55-64.

[5] CARLET C, CHARPIN P, ZINOVIEV V. Codes, Bent functions and permutations suitable for DES-like cryptosystems[J]. Designs codes and cryptography, 1998, 15(2):125-156.

[6] BUDAGHYAN L, CARLET C, POTT A. New classes of almost bent and almost perfect nonlinear polynomials[J]. IEEE transactions on information theory, 2005, 52(3):1141-1152.

[7] BRACKEN C, BYRNE E, MARKIN N, et al. A few more quadratic APN functions[J]. Cryptography and communications, 2011, 3(1):43-53.

[8] CANTEAUT A, CHARPIN P, DOBBERTIN H. Binarym-sequences with three-valued crosscorrelation: a proof of Welch’s conjecture[J]. IEEE transactions on information theory, 2000, 46(1):4-8.

[9] NYBERG K. S-boxes and round functions with controllable linearity and differential uniformity [C]// International Workshop on Fast Software Encryption. Berlin, 1994:111-130.

[10]BRACKEN C, BYREN E, MCGUIRE G, et al. On the equivalence of quadratic APN functions[J]. Designs codes and cryptography, 2011, 61(3):261-272.

(責任編輯：方惠敏)

Two Classes of Almost Perfect Nonlinear Functions over Even Characteristic Finite Fields

ZHANG Xiyong1,2， LI Naijiang1,2， LU Zhibo1, LI Dequan2

(1.StateKeyLaboratoryofSpace-GroundIntegratedInformationTechnology,Beijing100020,China; 2.ThePLAInformationEngineeringUniversity,Zhengzhou450001,China)

Boolean function and vector function were two classes of functions involved in cryptography. It contained differential uniformity, nonlinearity, etc. as their safety indicator. Constructing low differential uniformity functions with good cryptography property was always a hot topic. Two new types of almost perfect nonlinear (APN) polynomial function over even characteristic finite fields were constructed, moreover, it was proved that the presented functions were EA-inequivalent to the previously known monomial APN functions over even characteristic finite fields.

differential uniformity; almost perfect nonlinear function; extended affine equivalence; Carlet-Charpin-Zinoviev equivalence

2016-05-03

國家自然科學(xué)基金資助項目(61572027)．

張習勇(1975—)，男，湖北武穴人，副教授，主要從事密碼學(xué)研究，E-mail:xiyong.zhang@hotmail.com．

張習勇，李乃江，魯志波,等.兩類偶特征有限域上的幾乎完全非線性函數(shù)[J].鄭州大學(xué)學(xué)報(理學(xué)版)，2016，48(4)：1-5.

O174.4

A

1671-6841(2016)04-0001-05

10.13705/j.issn.1671-6841.2016601