張習(xí)勇， 李乃江， 魯志波, 李德全

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

?

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

張習(xí)勇1,2， 李乃江1,2， 魯志波1, 李德全2

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

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

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

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)的兩個(gè)函數(shù)f和g擴(kuò)展仿射等價(jià)，簡稱EA等價(jià).易知，EA等價(jià)的非常數(shù)函數(shù)具有相同的代數(shù)次數(shù).文獻(xiàn)[5]提出一種更一般的等價(jià)概念，即CCZ等價(jià).

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

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

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

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

證明 對(duì)任意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)

是一個(gè)線性化多項(xiàng)式.

因?yàn)棣(f(x))=0與Δa(f(ax))=0的解的個(gè)數(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)中的解個(gè)數(shù).

對(duì)等式(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)

因?yàn)镈obbertin函數(shù)的Walsh譜與所有二次函數(shù)的Walsh譜均不相同[8-9]，而擴(kuò)展Walsh譜是函數(shù)的CCZ等價(jià)的一個(gè)不變量，故得定理2.

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

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

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

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

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

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

(4)

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

(5)

因?yàn)閡是GF(2n)上的一個(gè)本原元，所以u(píng)2m-1≠1.

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

(6)

(7)

(8)

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

(9)

bj-m=0.

(10)

bj+r-m=0.

(11)

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

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

(12)

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

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

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

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

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

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

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

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

(13)

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

(14)

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

(15)

(16)

(17)

假設(shè)存在j使得aj≠0.如果存在k使得bj+k-t≠0，當(dāng)z≠r時(shí)，由(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不等價(jià)的.[10]

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

[2] 涂自然, 鄧映蒲. 一類M-M型bent函數(shù)的代數(shù)免疫度[J]. 河南科技大學(xué)學(xué)報(bào)(自然科學(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.

(責(zé)任編輯：方惠敏)

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é)基金資助項(xiàng)目(61572027)．

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

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

O174.4

A

1671-6841(2016)04-0001-05

10.13705/j.issn.1671-6841.2016601