劉志高

馬鞍山職業(yè)技術(shù)學(xué)院，安徽 馬鞍山 243031

0 引 言

布爾函數(shù)作為序列密碼、分組密碼和Hash函數(shù)的重要組件，其密碼學(xué)性質(zhì)的好壞直接影響到密碼系統(tǒng)的安全性. 文獻(xiàn)[1]提出了一類密碼學(xué)性質(zhì)優(yōu)良的函數(shù)——擬Bent函數(shù), 它是包含Bent函數(shù)和部分Bent函數(shù)的更大的函數(shù)類, 可以具有Bent 函數(shù)所不具有的密碼學(xué)性質(zhì), 如: 平衡性、相關(guān)免疫性, 能有效抵抗線性攻擊、相關(guān)攻擊和差分攻擊等. 隨后, 人們相繼研究了擬Bent函數(shù)的一些構(gòu)造方法及其非線性度、代數(shù)次數(shù)、相關(guān)免疫性、擴(kuò)散性、正規(guī)性、對偶性等密碼學(xué)指標(biāo)[2-6]. 研究表明, 擬Bent 函數(shù)的密碼學(xué)性質(zhì)優(yōu)良, 在密碼設(shè)計(jì)及通信領(lǐng)域中有廣泛的應(yīng)用.

隨著密碼技術(shù)的不斷發(fā)展, 各種新興的攻擊方法相繼出現(xiàn). 尤其是代數(shù)攻擊[7]的出現(xiàn), 在密碼學(xué)界引起軒然大波, 人們利用代數(shù)攻擊成功地破譯了Toyocrypt和LILI. 代數(shù)攻擊對現(xiàn)有的密碼體制形成了巨大威脅, 為抵抗代數(shù)攻擊, Meier等人于2004年引入了度量布爾函數(shù)安全性的新指標(biāo)——代數(shù)免疫性[8]. 代數(shù)免疫一經(jīng)提出就受到密碼學(xué)界的廣泛關(guān)注, 研究成果主要集中在兩方面: 一是最優(yōu)代數(shù)免疫函數(shù)的構(gòu)造方法研究[9-12]; 二是對已有的密碼學(xué)性質(zhì)良好的布爾函數(shù)的代數(shù)免疫性研究[13-15].關(guān)于代數(shù)免疫與其他密碼學(xué)指標(biāo)之間的關(guān)系已有少量的研究，如文獻(xiàn)[16]研究了布爾函數(shù)的代數(shù)免疫與擴(kuò)散階之間的關(guān)系. 但是, 針對擬Bent函數(shù)的代數(shù)免疫性分析還未得到系統(tǒng)的成果, 探討擬Bent函數(shù)是否存在低次零化子, 能否抵抗代數(shù)攻擊, 具有很強(qiáng)的現(xiàn)實(shí)意義.

本文基于布爾函數(shù)非線性度與代數(shù)免疫度之間的關(guān)系, 利用Walsh譜、組合數(shù)等工具對擬Bent函數(shù)(包括偶數(shù)變元和奇數(shù)變元)的代數(shù)免疫性進(jìn)行系統(tǒng)地分析, 得到了判定其存在低次零化子的一個(gè)充分條件. 該條件只需要根據(jù)擬Bent函數(shù)的階數(shù)k與變元個(gè)數(shù)n之間的關(guān)系就可進(jìn)行判定, 不需要利用Walsh循環(huán)譜或代數(shù)正規(guī)形來判定, 非常直觀有效. 進(jìn)一步, 還研究了如何根據(jù)擬Bent函數(shù)的階數(shù)k與變元個(gè)數(shù)n之間的具體關(guān)系來確定其代數(shù)免疫度的上界.

1 預(yù)備知識

一個(gè)n元布爾函數(shù)f是指從GFn(2)={0,1}n到GF(2)={0,1}的一個(gè)映射. 記Bn為所有n元布爾函數(shù)組成的集合, 記An為所有n元仿射布爾函數(shù)的集合.

易知,n為偶數(shù)時(shí), 0階擬Bent函數(shù)就是Bent函,n階擬Bent函數(shù)就是仿射函數(shù).

定義4[7]設(shè)f∈Bn, 若?0≠g∈Bn, 使得f·g=0恒成立, 則稱g是f的零化子.

由于f·(1+f)=0, 因此f的零化子一定存在. 記f的全體零化子構(gòu)成的集合為An(f).

定義5[8]設(shè)f∈Bn, 稱f的零化子和1+f的零化子的代數(shù)次數(shù)的最小值為f的代數(shù)免疫度. 記作AI(f), 即AI(f)=min{deg(g)|g∈An(f)org∈An(1+f)}.

2 主要結(jié)論

引理1[17]設(shè)f(x)∈Bn, 則

引理2[8]設(shè)f(x)∈Bn,若AI(f)=d,則

定理1給出了n元k階擬Bent函數(shù)存在低次零化子的一個(gè)充分條件, 它只需要根據(jù)k與n的關(guān)系來進(jìn)行判定, 而不需要利用Walsh循環(huán)譜或代數(shù)正規(guī)形來判定, 非常直觀有效. 由定理1知, 在變元個(gè)數(shù)確定的情況下, 擬Bent函數(shù)的階數(shù)越高, 其存在低次零化子的可能性越大, 抵抗代數(shù)攻擊的能力越弱. 反之, 在階數(shù)確定的情況下, 擬Bent函數(shù)的變元個(gè)數(shù)越大, 其存在低次零化子的可能性越小, 抵抗代數(shù)攻擊的能力越強(qiáng). 進(jìn)一步, 還可分析擬Bent函數(shù)的階數(shù)k與其變元個(gè)數(shù)n之間的距離對代數(shù)免疫性的影響.f(x)為此, 需要探討一些組合數(shù)的性質(zhì).

綜合(1)、(2)知原命題成立.

類似可得如下結(jié)論:

由定理1和結(jié)論1可得如下推論:

推論1 設(shè)f(x)是n元k階擬Bent函數(shù), 且n為偶數(shù). 若n-k=2, 則對于一切n≥10,f(x)存在低次零化子.

類似可得如下推論:

推論2 設(shè)f(x)是n元k階擬Bent函數(shù), 且n為奇數(shù). (1) 若n-k=2, 則對于一切n≥5,f(x)存在低次零化子; (2) 若n-k=4, 則對于一切n≥11,f(x)存在低次零化子.

推論1和推論2表明, 擬Bent函數(shù)的階數(shù)k與其變元個(gè)數(shù)n之間的距離對代數(shù)免疫性的影響很大, 距離越小, 代數(shù)免疫能力越弱.

進(jìn)一步, 還可把定理1推廣得定理2.

證明(1) 當(dāng)n為偶數(shù)時(shí), 由定理1的證明知,

(2) 當(dāng)n為奇數(shù)時(shí), 由定理1的證明知,

定理2表明, 可以根據(jù)擬Bent函數(shù)的階數(shù)k與變元個(gè)數(shù)n之間的具體關(guān)系來確定其代數(shù)免疫度的上界.

3 結(jié) 語

本文研究表明當(dāng)擬Bent函數(shù)的階數(shù)k與變元個(gè)數(shù)n滿足一定的關(guān)系時(shí), 就可充分判定其存在低次零化子, 為密碼系統(tǒng)中密碼函數(shù)的選擇提供了借鑒. 遺憾的是, 該條件是充分的而非必要的. 能否找到充要條件, 還有待進(jìn)一步研究.

致 謝

感謝安徽省高校優(yōu)秀青年人才計(jì)劃給予的經(jīng)費(fèi)支持,誠摯感謝張福泰教授的辛勤指導(dǎo)!

[1] 李世取, 劉文芬, 滕吉紅.k階擬Bent 函數(shù)的性質(zhì)及其應(yīng)用[C]//謝仁宏. 第7 屆全國青年通信學(xué)術(shù)會(huì)議論文集.北京: 電子工業(yè)出版社, 2001:939-943.

LI Shi-qu, LIU Wen-fen, TENG Ji-hong. Some properties ofk-order quasi-bent functions and its applications[C]//XIE Ren-hong. The proceedings of the Seventh National Youth Conference on communication. Beijing: Electronic Industry Press, 2001:939-943.(in Chinese)

[2] 滕吉紅, 李世取, 劉文芬.k階擬Bent 函數(shù)在密碼設(shè)計(jì)和通信中的應(yīng)用[J]. 通信學(xué)報(bào), 2003, 24(12):58-66.

TENG Ji-hong, LI Shi-qu, LIU Wen-fen. The application ofk-order quasi-bent functions in cryptology and communication fields [J]. Journal of China Institute of Communication, 2003,24(12):58-66.(in Chinese)

[3] 張習(xí)勇, 韓文報(bào). 擬Bent 函數(shù)的性質(zhì)和構(gòu)造[J]. 數(shù)學(xué)學(xué)報(bào), 2004, 47(6):1175-1184.

ZHANG Xi-yong, HAN Wen-bao. Some properties and constructions of quasi-bent functions [J]. Acta Mathematica Sinica, 2004, 47(6):1175-1184.(in Chinese)

[4] 胡斌, 金晨輝, 馮春海. Plateaued 函數(shù)的密碼學(xué)性質(zhì)[J]. 電子與信息學(xué)報(bào), 2008, 30(3): 660-664.

HU Bin, JIN Chen-hui, FENG Chun-hai. Cryptographic properties of plateaued functions[J]. Journal of Electronics & Information Technology, 2008, 30(3): 660-664.(in Chinese)

[5] 劉志高. 兩類多輸出一階擬Bent函數(shù)的構(gòu)造 [J]. 武漢工程大學(xué)學(xué)報(bào),2010, 32(9):108-110.

LIU Zhi-gao. The constructions of two classes of 1-order multi-output quasi-bent functions[J]. Journal of Wuhan Institute of Technology, 2010, 32(9):108-110.(in Chinese)

[6] 王維瓊, 肖國鎮(zhèn). Plateaued函數(shù)的對偶性[J]. 計(jì)算機(jī)科學(xué), 2013, 40(5): 19-20.

WANG Wei-qiong, XIAO Guo-zhen. Dulity of plateaued functions[J]. Computer Science, 2013, 40(5): 19-20.(in Chinese)

[7] COURTOIS N, MEIER W. Algebraic attacks on stream ciphers with linear feedback [C]//Advances in Cryptology- EUROCRYPT 2003. Berlin:Springer-Verlag 2003: 346-359.

[8] MEIER W, PASALIC E, CARLET C. Algebraic attacks and decomposition of Boolean functions[C] //Advances in Cryptology-EUROCRYPT 2004. Berlin:Springer-Verlag 2004: 474-491.

[9] CARLET C, DALAI D K, GUPTA K C, et al. Algebraic immunity for cryptographically significant Boolean functions: analysis and construction[J]. IEEE Transactions on Information Theory, 2006, 52(7): 3105-3121.

[10] 張鳳榮, 胡予濮. 具有高階代數(shù)免疫的彈性函數(shù)[J]. 武漢大學(xué)學(xué)報(bào):理學(xué)版, 2010, 56(2): 207-210.

ZHANG Feng-rong, HU Yu-pu. Resilient boolean functions with high algebraic immunity[J]. Journal of Wuhan University:Natural Science Edition, 2010, 56(2): 207-210.(in Chinese)

[11] 熊曉雯, 屈龍江, 李超. 具有最大代數(shù)免疫度的布爾函數(shù)的構(gòu)造[J]. 計(jì)算機(jī)科學(xué), 2011, 38(1): 26-30.

XIONG Xiao-wen, QU Long-jiang, LI Chao. Construction of boolean function with maximum algebraic immunity [J]. Computer Science, 2011, 38(1): 26-30.(in Chinese)

[12] 董新鋒, 張文政, 周宇,等. 基于代數(shù)正規(guī)型構(gòu)造的代數(shù)免疫最優(yōu)布爾函數(shù)[J]. 計(jì)算機(jī)工程, 2013, 39(7): 169-172.

DONG Xin-feng, ZHANG Wen-zheng,ZHOU Yu,et al. Optimal algebraic immune boolean function based on algebraic normal form construction[J]. Computer Engineering, 2013, 39(7): 169-172.(in Chinese)

[13] 馮克勤, 廖群英. 對稱布爾函數(shù)的代數(shù)免疫性[J]. 工程數(shù)學(xué)學(xué)報(bào), 2008, 25(2): 191-198.

FENG Ke-qin, LIAO Qun-ying. On algebraic immunity of symmetric boolean functions[J]. Chinese Journal of Engineering Mathematics, 2008, 25(2): 191-198.(in Chinese)

[14] 吳瑋玲, 王永娟, 張世武. 奇數(shù)變元plateaued函數(shù)代數(shù)免疫性質(zhì)研究[J]. 計(jì)算機(jī)工程與應(yīng)用, 2012, 48(2): 96-98.

WU Wei-lin, WANG Yong-juan，ZHANG Shi-wu. On algebraic immunity of plateaued functions in odd variables[J]. Computer Engineering and Applications，2012, 48(2): 96-98.(in Chinese)

[15] 劉志高. 級聯(lián)函數(shù)的代數(shù)免疫性研究[J]. 計(jì)算機(jī)工程, 2012, 38(1): 117-119.

LIU Zhi-gao. Research on algebraic immunity of Boolean functions by concatenation[J]. Computer Engineering, 2012, 38(1): 117-119.(in Chinese)

[16] 周宇, 曹云飛, 張文政，等. 布爾函數(shù)的代數(shù)免疫與擴(kuò)散階的關(guān)系[J]. 計(jì)算機(jī)工程與科學(xué), 2011, 33(10): 34-38.

ZHOU Yu, CAO Yun-fei,ZHANG Wen-zheng et al. Relationship between algebraic immunity and propagation characteristics of the boolean functions[J]. Computer Engineering & Science, 2011, 33(10): 34-38.(in Chinese)

[17] 馮登國. 頻譜理論及其在密碼學(xué)中的應(yīng)用[M]. 北京: 科學(xué)出版社, 2000:41-45.

FENG Deng-guo. Spectrum theory and its applications in cryptography[M]. Beijing: Science Press, 2000:41-45.(in Chinese)