擇多邏輯函數(shù)的若干性質(zhì)

陳濤+童玉珂+卓澤朋

摘要：擇多邏輯函數(shù)（SML函數(shù)）在密碼學(xué)和計(jì)算機(jī)通信領(lǐng)域應(yīng)用廣泛.利用Wlash 循環(huán)譜和代數(shù)理論，系統(tǒng)的對(duì)SML函數(shù)的Wlash譜特性、平衡性、代數(shù)次數(shù)、非線性 度和相關(guān)免疫性等性質(zhì)進(jìn)行研究討論，得出一些重要結(jié)論。

關(guān)鍵詞：擇多邏輯函數(shù)；Wlash譜；平衡性；非線性度；相關(guān)免疫性

中圖分類(lèi)號(hào)：TN918.1 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）01-0067-03

Abstract： Majority logic functions （SML Functions） are widely used in cryptography and computer communications. This paper systematic discuss the Wlash spectrum、balance、algebraic numbers、nonlinearity and correlation immunity of SML functions by Wlash spectrum and algebra， and get some important conclusions.

Key words： majority logic functions；Wlash spectrum；balance；nonlinearity；correlation immunity

1 概述

Courtois等人于2003年提出基于LSFR代數(shù)攻擊以來(lái)，Toyocrypt、LILI-128等流密碼陸續(xù)被攻破，對(duì)密碼體制造成巨大威脅.而擇多邏輯函數(shù)（以下簡(jiǎn)稱(chēng)SML函數(shù)）由于具有最高代數(shù)免疫度，可有效抵抗代數(shù)攻擊，因此備受關(guān)注.

目前對(duì)SML函數(shù)的研究已取得較豐富成果.Bruer在文獻(xiàn)[4]中提出SML函數(shù)的概念，發(fā)現(xiàn)其密碼學(xué)性能較好而引入流密碼中產(chǎn)生SML密鑰流生成器.文獻(xiàn)[5]中討論了當(dāng)時(shí)，SML函數(shù)的代數(shù)正規(guī)形中階數(shù)的變化情況以及SML函數(shù)的非線性度性質(zhì).Dalai在文獻(xiàn)[6]中發(fā)現(xiàn)SML函數(shù)代數(shù)免疫度最大，為，并利用SML函數(shù)遞歸構(gòu)造一類(lèi)最優(yōu)密碼函數(shù).文獻(xiàn)[8]討論了偶數(shù)元SML函數(shù)的穩(wěn)定性和代數(shù)結(jié)構(gòu)性，得出SML函數(shù)變?cè)^大時(shí)，函數(shù)非線性度較高的結(jié)論.文獻(xiàn)[9]證明了SML函數(shù)代數(shù)免疫階最大時(shí)，穩(wěn)定性和相關(guān)攻擊抵抗性能良好.文獻(xiàn)[10]對(duì)SML函數(shù)的一些性質(zhì)進(jìn)行討論，并根據(jù)其性質(zhì)構(gòu)造了最優(yōu)代數(shù)免疫階的一類(lèi)布爾函數(shù).本文在文獻(xiàn)[4-10]基礎(chǔ)上，利用代數(shù)知識(shí)和Wlash 循環(huán)譜，對(duì)SML函數(shù)的密碼學(xué)性質(zhì)進(jìn)行系統(tǒng)研究討論.

2 預(yù)備知識(shí)

設(shè)是元素0和1的有限域，元布爾函數(shù)是的映射，記是元布爾函數(shù)所組成的集合.數(shù)集Z，R和C，這些數(shù)域加法記為+，上加法記作，.向量的漢明重量記作：，若滿足，則稱(chēng)是平衡布爾函數(shù).對(duì)于任意的代數(shù)正規(guī)型（ANF）可表示為

3.2 代數(shù)次數(shù)

定理3 若是元SML函數(shù)，則的代數(shù)次數(shù)為：.

證明：根據(jù)文獻(xiàn)[5]中證明代數(shù)免疫度的方法，我們可利用定義3，的小項(xiàng)表示可以表示如下：

上式中，令，可得，因?yàn)椋孕№?xiàng)表示中任意一個(gè)項(xiàng)代數(shù)次數(shù)都大于或等于，因此.證畢.

3.3 平衡性和對(duì)稱(chēng)性

平衡性和對(duì)稱(chēng)性是判斷密碼函數(shù)安全性能的重要指標(biāo).根據(jù)SML函數(shù)的定義，SML函數(shù)的自變量是的輸入值，輸出值為0或1.當(dāng)變?cè)獮槠鏀?shù)時(shí)，的個(gè)數(shù)和的個(gè)數(shù)相等，則SML函數(shù)具有平衡性，也具有對(duì)稱(chēng)性.若變?cè)獮榕紨?shù)時(shí)，的個(gè)數(shù)和的個(gè)數(shù)相等，使得SML函數(shù)的值為0或1的概率相等，因此具有平衡性，顯然此時(shí)不具有對(duì)稱(chēng)性.

3.4 非線性度

首先給出非線性度和Walsh循環(huán)譜的一個(gè)重要關(guān)系式：

參考文獻(xiàn)：

[1] Courtois N， Meier W. Algebraic attacks on stream ciphers with linear feedback[C]//Lec- ture Notes in Computer Science： Advances in Cryptology eurocrypt. Berlin： Springer Heidelberg， 2003： 345-359.

[2] Meier W， Pasalic E， Carlet C. Algebraic attacks and decomposition of Boolean functions[C]//Lecture Notes in Computer Science： Advances in Cryptology eurocrypt. Berlin： Springer Heidelberg， 2004： 474-491.

[3] 溫巧燕，鈕心忻，楊義先. 現(xiàn)代密碼學(xué)中的布爾函數(shù)[M]. 北京：科學(xué)出版社，2000.

[4] Bruer J O. On Pseudo Random Sequences as Crypto Generators[A]. Proc of 1984 International Zurich Seminar on Digital Communications. 1984：157-161.

[5] Dalai D K， Maitra S， Sarkar S. Basic theory in construction of Boolean functions with maxim-um possible annihilator immunity[J]. Designs，Codes and Cryptography， 2006， 40（1）：41-58.

[6] 馮登國(guó). 嚴(yán)格擇多邏輯函數(shù)的非線性度[J].電子科技雜志， 1994， 27（1）：25- 27.

[7] 何良生. 一類(lèi)具有最高代數(shù)免疫階的布爾函數(shù)[J].計(jì)算機(jī)學(xué)報(bào)， 2009， 29（9）：1579-1583.

[8] 梁增，李世取. 偶數(shù)元擇多邏輯函數(shù)的穩(wěn)定性和代數(shù)結(jié)構(gòu)[J].信息工程大學(xué)學(xué)報(bào)， 2005， 6（3）：40-44.

[9] 王永娟，韓文報(bào)，李世取. 偶數(shù)元擇多邏輯函數(shù)的密碼學(xué)性質(zhì)[J].計(jì)算機(jī)工程與應(yīng)用， 2009， 45（12）：38-41.

[10] Sihong Su， Xiaohu Tang.Constructing of rotation symmetric Boolean functions with optimal- algebraic immunity and high nonlinearty[J]. De-signs， Codes and Cryptography， 2014， 71（2）： 183-199.

[11] Ding C. A construction of binary linear codes from Boolean functions[J]. Discrete Mathematics， 2016， 339（9）：2288-2303.endprint