幾乎最優彈性plateaued函數的性質和構造*

邊康龍,朱海君,董新鋒(.西安電子科技大學ISN國家重點實驗室,陜西西安7007;.張渚高級中學,江蘇宜興4; .保密通信重點實驗室,四川成都6004)

幾乎最優彈性plateaued函數的性質和構造*

邊康龍1,朱海君2,董新鋒3
(1.西安電子科技大學ISN國家重點實驗室,陜西西安710071;2.張渚高級中學,江蘇宜興214231; 3.保密通信重點實驗室,四川成都610041)

研究了幾乎最優plateaued函數的非零線性結構個數,證明了一個具有奇數個變元的幾乎最優plateaued函數要么是沒有非零線性結構的plateaued函數,要么是有一個非零線性結構的部分bent函數;一個具有偶數個變元的幾乎最優plateaued函數的非零線性結構只可能是0,1,3個。還給出一種構造幾乎最優彈性plateaued函數的方法,可以使函數無非零線性結構、滿足嚴格雪崩準則、具有良好的全局雪崩特征等。

密碼學 布爾函數 線性結構 非線性度 彈性

0 引 言

設計同時滿足多種密碼學準則的布爾函數是對稱密碼學中的重要課題[1]。1976年Rothaus引入bent函數[2],這是一類非線性度最高的函數,但它的這種優良性質是以犧牲其它性能為代價的。例如:bent函數既不是平衡函數,也不是相關免疫函數[3],并且變元個數n只能為偶數,代數次數不超過n/2。1993年Carlet在研究布爾函數的自相關函數非零值的個數和Walsh譜值的非零值的個數之間的關系時,引入部分bent函數[4]。這拓展了bent函數的概念,使部分bent函數具備了bent函數所不具備的一些密碼學性質。但這類函數的一個最大缺陷是,在部分bent函數不是bent函數時,它必定具有非零線性結構。后來,Zheng等人又提出pleateaued函數的概念[5],這是一類包含部分bent函數,范圍更廣的函數,在這類函數中包含一類既非bent函數又非部分bent函數,并且不具有非零線性結構的函數,成為研究的重點。

幾乎最優彈性plateaued函數是一類可以實現各種密碼性質的折中、優化的密碼函數。研究幾乎最優plateaued函數的性質和構造等問題是一項既有理論意義又有應用價值的工作。

1 基本概念

用Fn2表示n維向量空間。定義f(x)是一個從Fn2到F2的n元布爾函數,記所有n元布爾函數的集合為Bn。一般將f表示成代數正規型:

f的次數是使姿u屹0的u的最大漢明重量值,記為deg(f),用wt(u)=u1+u2+…+un計算u的漢明重量。當deg(f)=1時,稱f為仿射函數;常數項為0的仿射函數,稱為線性函數。

Walsh變換是研究布爾函數的重要工具,下面給出它的定義[6-8]。

定義1：設f沂Bn,稱

為f(x)在點ω=(ω1,ω2…,ωn)的Walsh變換[6]。其中ωx=ω1x1+ω2x2+…+ωnxn。

定義2 設f沂Bn,當在f真值表中0和1的個數相等,即Wf(0)=0時,稱f為平衡布爾函數。f是t階相關免疫布爾函數當且僅當對所有使1≤wt(ω)≤t的ω,Wf(ω)=0;若f同時為平衡函數,則稱f為t階彈性函數[7]。

定義3 兩個n元布爾函數f,ρ的漢明距離定義為

為f(x)的平方和指標。

定義6 設f沂Bn,如果當x沂,都有f(x+琢)+ f(x)=常值,亦即|rf(琢)|=2n,則稱琢為f(x)的一個線性結構。

引理1 設f沂Bn,f(x)的所有線性結構構成Fn2的一個線性子空間E。

定義7 若所有wt(a)=1的琢都滿足rf(琢)= 0,就稱f(x)滿足嚴格雪崩準則。

定義8 設f沂Bn,如果存在一個上F2的n×n的可逆矩陣A和一個正整數m,0≤m≤n,使f(x A)=g(y)+h(z),其中x=(y,z),y沂Fm,z沂Fn-m,g沂Bm是一個仿射函數,h沂Bn-m是一個bent函數,則稱f為部分bent函數。

引理2[4]設f沂Bn,E是f的所有線性結構構成的線性子空間。f是部分bent函數當且僅當Wf(w)只取三值0,±2(n+dimE)/2。其中,dim E表示E的維數。

定義9[5]設f沂Bn,若Wf(ω)沂{0,±2姿},則稱f為plateaued函數。顯然,bent函數和仿射函數都是部分bent函數。部分bent函數是特殊的plateaued函數。

2 性質和構造

定義10 設f沂Bn,若Wf(ω)沂{0,±2?n/2」+1},則稱f為幾乎最優plateaued函數.如果這種函數是彈性函數,則稱為幾乎最優彈性plateaued函數。

定理1 設f沂Bn是幾乎最優plateaued函數。當n為奇數時,f(x)要么是有一個非零線性結構的部分bent函數,要么是無線性結構的plateaued函數;當n為偶數時,f(x)的非零線性結構個數只可能是0個,1個或3個。

證明：當n為奇數,如果f(x)為幾乎最優plateaued函數,那么Wf(ω)取三值0,±2n+21。由引理2知f(x)可以為部分bent函數,并且dim E=1,即只有一個非零線性結構。此時存在可逆矩陣A使f(x A)=xn+g(x1,x2,…,xn-1),其中g(x1,x2,…, xn-1)為一個bent函數。

假設f(x)是有線性結構的plateaued函數,并且不是部分bent函數,不妨設f(x)可表示為

f(x)=l(x1,x2,…,xm)+g(xm+1,…,xn)其中,l(x1,x2,…,xm)為線性函數,g(xm+1,…,xn)為無線性結構的plateaued函數。f(x)在ω=(ω1, ω2,…,ωm)的譜值可表示為

當(ω1,ω2,…,ωm)=l(X)的系數時,Wf(ω)= 2m·Wg(ωm+1,…,ωn)否則,Wf(ω)=0,Wg(ωm+1,…, ωn)=0或±2姿,姿逸(n-m)/2。顯然,Wf(ω)=0或2m+姿。如果f(x)為幾乎最優plateaued函數,即

2m+姿=2(n+1)/2?(n+1)/2=姿+m逸(n+m)/2得m≤1。故m=1并且姿=(n-m)/2。于是,g(x)為bent函數,f為部分bent函數,這與假設矛盾。因此,f(x)如果不是有一個非零線性結構的部分bent函數,必是無線性結構的plateaued函數。

當n為偶數時,如果f(x)為幾乎最優plateaued函數,那么Wf(ω)取三值0,±2n/2+1。由Parseval恒等式,易知Walsh譜取非零點的個數為22n/(2n/2+1)2= 2n-2。不妨假設

其中m逸3,l(x1,x2,…,xm)表示線性函數。由式(2),當(w1,w2,…,wm)=l(x)的系數時,Wf(ω)= 2m·Wg(ωm+1,…,ωn)。否則,Wf(ω)=0。顯然,

這與假設矛盾。所以m只能取0,1,或2三個值。即f(x)的非零線性結構數目只能為0,1,或3。

i)|T|=2k-1。

max≤3·2k-2},wt(酌)表示酌的漢明重量。

iii)當酌沂T,軈酌沂T,其中軈酌表示酌的補向量。

a)f(x)是一個幾乎最優plateaued函數。

b)f(x)是(t-1)階彈性函數。

c)f(x)滿足嚴格雪崩準則。

d)f(x)沒有非零線性結構。

e)滓f=。

若酌沂T,Wf(琢)=(-1)茁·p-1(酌)·2k+1=±2k+1。若酌?T,Wf(琢)=0。可得Wf(琢)沂{0,±2k+1}。顯然f是幾乎最優plateaued函數。

b)0≤wt(琢)≤t-1?0≤wt(酌)≤t-1,酌?T?Wf(琢)=0。由定義2,f(x)是(t-1)階彈性函數。

3 結 語

本文研究了幾乎最優彈性plateaued函數的性質,提出了一種在偶變元上構造幾乎最優彈性plateaued函數的方法。在定理2中只滿足i),ii),iii)條件的集合T的個數比在滿足i),ii),iii),iv)條件時的集合的T個數多,不過如果沒有條件iv),不能保證該函數沒有非零線性結構。

密碼函數的各種密碼學指標之間存在著錯綜復雜的聯系,如何實現它們之間的折中是困擾密碼學界的難題。本文給出的構造方案較好地實現了非線性度、彈性、嚴格雪崩準則和平方和指標的折中。

[1] Zhang W G,Xiao G Z.Constructions of almost optimal resilient Boolean functions on large even number of variables[J].IEEE Transactions on Information Theory, 2009,55(12):5822-5831.

[2] Rothaus O S.On‘bent'functions[J].Journal of Combinatorial Theory,Ser.A,1976,20:300-305.

[3] 譙通旭,王運兵,謝上明,等.具有最大代數免疫度函數的研究[J].通信技術,2013,46(11):86-89. QIAO Tong-xu,WANG Yun-bing,XIE Shang-ming,et al.Study on Functionswith Optimum Algebraic Immunity [J].Communications Technology,2013,46(11):86-89.

[4] Carlet C.Partially-bent functions[J].Designs Codes and Cryptography,1993,3,(2):135-145.

[5] Zheng Y,Zhang X.M.On Plateaued Functions[J]. IEEE Transaction on Information Theory,2001,47(5): 1215-1223.

[6] ZhangW G,Pasalic E,Highly Nonlinear Balanced S-boxes with Good Differential Properties[J].IEEE Transactions on Information Theory,2014,60(12):7970-7979.

[7] Zhang W G,Pasalic E,Generalized Maiorana-McFarland Construction of Resilient Boolean Functions with High Nonlinearity and Good Algebraic Properties[J]. IEEE Transactions on Information Theory,2014,60 (10):6681-6695.

[8] Zhang W G,Pasalic E,Constrcutions of Resilient S-boxes with Strictly Almost Optimal Nonlinearity Through Disjoint Linear Codes[J].IEEE Transactions on Information Theory,2014,60(3):1638-1651.

BIAN Kang-long(1990-),male,doctoral graduate,mainly engaged in symmetric cryptography.

朱海君(1971—),男,學士,一級教師,主要研究方向為計算機安全;

ZHU Hai-jun(1971-),male,B.Sci.,the first-grade teacher,mainly engaged in computer security.

董新鋒(1985—),男,工程師,主要研究方向為對稱密碼學。

Dong Xin-feng(1985-),male,engineer,mainly engaged in symmetric cryptography.

Property and Construction of Almost Optimal Resilient Plateaued Function

BIAN Kang-long1,ZHU Hai-jun2,DONG Xin-feng3
(1.ISN Laboratory,Xidian University,Xi'an Shaanxi710071,China;2.Zhangzhu Senior Middle School, Yixing Jiangsu 214231,China;3.Key Laboratory for Secure Communications,Chengdu Sichuan 610041,China)

The nonzero-linear-structure number of an almost optimal resilient plateaued function is studied.It is shown that an almost optimal resilient function with odd number of variables is either a plateaued function without nonzero linear structures or a partially-bent function with one nonzero linear structure, and the nonzero-linear-structure number of an almost optimal resilient function with even number of variables is 0,1,or3.Amethod for constructing almostoptimal resilient plateaued functions is also presented. These functions have no nonzero linear structures,satisfy strict avalanche criterion and possess favourable global avalanche characteristics.

cryptography;boolean functions;linear structure;nonlinearity;resiliency

date：2014-09-10;Revised date：2014-12-21

TN918.1

A

1002-0802(2015)02-0199-04

邊康龍(1990—),男,博士研究生,主要研究方向為對稱密碼學;

10.3969/j.issn.1002-0802.2015.02.017

2014-09-10;

2014-12-21