布爾函數(shù)代數(shù)免疫性研究.pdf

《布爾函數(shù)代數(shù)免疫性研究.pdf》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、第34卷第4期淮北師范大學(xué)學(xué)報(自然科學(xué)版)VO1．34N0．42013年l2月JournalofHuaibeiNormalUniversity(NaturalScience)Dec．2013布爾函數(shù)代數(shù)免疫性研究曹浩，魏仕民(1．安徽科技學(xué)院理學(xué)院，安徽滁州233100；2．淮北師范大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，安徽淮北235000)摘要：針對當(dāng)前密碼學(xué)中對具有多種好的密碼學(xué)性質(zhì)布爾函數(shù)的構(gòu)造需求，通過分析函數(shù)在重量≤d的向量處的取值與代數(shù)免疫階之間的內(nèi)在關(guān)系，在給出高階代數(shù)免疫函數(shù)判斷方法的基礎(chǔ)上，給出適當(dāng)改變函數(shù)在部分點的取值而不降低代數(shù)免疫階的方法，利用該方法，

2、給出了在代數(shù)免疫性、非線性性、平衡性和相關(guān)免疫性等方面均達(dá)到最優(yōu)的布爾函數(shù)的一個構(gòu)造實例．關(guān)鍵詞：布爾函數(shù)；代數(shù)免疫階；支撐點集；相關(guān)免疫階；非線性度中圖分類號：TN918．1文獻(xiàn)標(biāo)識碼：A文章編號：2095—0691(2013)04—0006—04布爾函數(shù)作為密碼學(xué)設(shè)計和分析的重要工具，一直是密碼學(xué)研究熱點．為抵抗各種密碼分析方法，學(xué)者們提出許多布爾函數(shù)的密碼學(xué)指標(biāo)，如相關(guān)免疫性、平衡性、非線性性等．2003年，Courtois和Meier?在歐洲密碼學(xué)年會上提出了一種特別有效的密碼分析方法——代數(shù)攻擊，并成功地攻破了許多種著名的密碼體制．為有效衡量布爾函數(shù)抵抗代

3、數(shù)攻擊的能力，密碼學(xué)者提出了代數(shù)免疫階，它被定義為布爾函數(shù)廠和．①1的最低次數(shù)的非零零化多項式的次數(shù)．為抵抗代數(shù)攻擊，函數(shù)的代數(shù)免疫階不能太低，構(gòu)造具有較高代數(shù)免疫階的布爾函數(shù)顯得非常有意義．國內(nèi)外密碼學(xué)者紛紛對代數(shù)攻擊進(jìn)行研究。，從不同角度給出多種具有高代數(shù)免疫階布爾函數(shù)的構(gòu)造．然而，在滿足代數(shù)免疫階較高的同時，滿足多種其他密碼學(xué)性質(zhì)的良好布爾函數(shù)的構(gòu)造卻仍然是一個難題．本文在深入研究布爾函數(shù)代數(shù)免疫性與其零點集和支撐點集的基礎(chǔ)上，給出了代數(shù)免疫階不低于d的判斷方法和具有較高代數(shù)免疫階布爾函數(shù)的構(gòu)造，本文首次研究了改變布爾函數(shù)在部分點的值卻不降低代數(shù)免疫階的充分條

4、件，并利用該方法，在已具有高代數(shù)免疫性布爾函數(shù)類中，通過適當(dāng)改變部分點的函數(shù)值，可以構(gòu)造在平衡性、代數(shù)免疫性、非線性性和相關(guān)免疫性等方面均達(dá)到最優(yōu)的布爾函數(shù)，并給出一個4元布爾函數(shù)的構(gòu)造實例，為構(gòu)造多元具有良好密碼學(xué)性質(zhì)的布爾函數(shù)提供一條途徑。1基本概念{0，1}到{0，1}的映射稱為元布爾函數(shù)，通常用f，g，h等表示，幾元布爾函數(shù)的全體記為B記o，：{xelO，1}if()=0}和lp={∈{0，1}l廠()：1}，分別稱為布爾函數(shù)_廠的零點集和支撐點集．如果Q，和l，中的元素個數(shù)相同，則稱)是平衡布爾函數(shù)．n元布爾函數(shù)廠()可以用上的多項式唯一地表示為：l廠(2

5、，?，)=n010iXinijXiXj0?OaI_2-一(1),，，I這里ao,a，n，?a?EF2，稱為)的代數(shù)標(biāo)準(zhǔn)f~J．(ANF))的ANF中非零最高次項的次數(shù)稱為／的次，，數(shù)，記為deg∽．如)的次數(shù)等于1，則廠()為仿射函數(shù)．在ANF中)的系數(shù)與函數(shù)值有下列關(guān)系：z，／∽(2)，}收稿日期：20l3一O6—13基金項目：國家自然科學(xué)基金資助項目(60573026)；安徽省自然科學(xué)研究資助項目(KJ2010B059，KJ2013B083)作者簡介：曹浩(1981一)，男，安徽宿州人，碩士，講師，主要研究方向為密碼學(xué)；通訊作者：魏仕民(1962一)男，安徽巢湖

6、人．博士，教授，主要研究方向為密碼學(xué)與信息安全．第4期曹浩等：布爾函數(shù)代數(shù)免疫性研究7其中，sup(x)表示n元向量=(?，％)中元素1的位置集合，即sup(x)={ilx=1}．循環(huán)普是研究布爾函數(shù)密碼學(xué)性質(zhì)的重要工具，定義為5，㈤=2’(一1)(WE{0，1})(3)xe{0，1l布爾函數(shù)的非線性度是衡量密碼函數(shù)抵抗代數(shù)攻擊的能力，它被定義為該函數(shù)與所有仿射函數(shù)的最小距離，非線性度和循環(huán)譜之間有如下重要關(guān)系：Ⅳ，=2’(1-max{IS：(w)l，WE{0，1)(4)如果()=O對所有=(。，W：，??W)∈{0，1}且1≤￡()≤m都成立，則稱廠是m階相關(guān)免疫

7、函數(shù)，如是平衡的，則穆廠為m階彈性函數(shù)．這里wt(w)是指W，W。，?，W中1出現(xiàn)的個數(shù)，即W的重量．文獻(xiàn)[12]指出，布爾函數(shù)的變元個數(shù)、代數(shù)次數(shù)d和相關(guān)免疫階m由如下關(guān)系：，n+≤d(5)當(dāng)布爾函數(shù)為平衡時，式(5)將是嚴(yán)格不等式．謝，geB，g稱為的零化多項式，如果對任意的∈{0，1}都)·g()=0成立．．廠的零化多項式的集合記為Ann∽的代數(shù)免疫階定義為：AI∽=rain{geBIgeAnn∽UAnn(1Of)J~g#O}．文獻(xiàn)[13]指出，含有n個變元的布爾函數(shù)廠，代數(shù)免疫階最大為f．／2]，我們把滿足AI(廠)=fn／2]的布爾函數(shù)稱為代數(shù)免疫最優(yōu)