《密碼函式二階非線性度快速算法及其緊下界研究》是依託西安電子科技大學，由李雪蓮擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：密碼函式二階非線性度快速算法及其緊下界研究
- 項目類別：青年科學基金項目
- 項目負責人：李雪蓮
- 依託單位：西安電子科技大學
中文摘要,結題摘要,
中文摘要
布爾函式的二階非線性度在評估流密碼和分組密碼的安全性方面有非常重要的作用，同時二階非線性度也和二階Reed-Muller碼的覆蓋半徑密切相關。當前缺少計算二階非線性度的快速算法，並且對任意一個布爾函式，給出二階非線性度緊下界也是困難的。本項目主要研究內容包括：1、利用逐次遞歸方法，指數和與Reed-Muller碼列表解碼結合方法研究具有高非線性度密碼函式的二階非線性度緊下界；試圖給出證明二階非線性度緊下界的新型理論方法。2、利用改進的疊代分別征服方法和離散變換與解方程結合法研究二階非線性度的快速算法；3、利用特定函式分析法研究二階Reed-Muller碼的覆蓋半徑，並利用疊代方嚮導數擴展研究任意階Reed-Muller碼的覆蓋半徑。力圖給出證明高次密碼函式二階非線性度緊下界的新方法以及計算密碼函式二階非線性度的快速算法，為密碼及其套用方案的設計提供系統的理論支撐和安全保證。
結題摘要
密碼函式的非線性度是衡量目標函式與仿射函式類的距離。隨著計算技術的不斷進步，人們發現某些易解的二次函式組成的方程組也可能存在快速求解算法。這使得人們開始關注密碼函式與二次函式及仿射函式的距離，即密碼函式的二階非線性度。本項目針對密碼函式的二階非線性度及其下界展開研究。針對特定類型的密碼函式給出其二階非線性度下界，研究了密碼函式在區塊鏈，安全多方計算以及多線性映射中的套用。項目取得研究成果：已發表或錄用SCI或EI檢索學術論文14 篇；申請8項國內專利，已經授權3項。重要結果：1、在密碼函式二階非線性度方面，針對四次Bent和半Bent函式（這些函式由法國密碼學家Charpin等提出，具有較好的非線性度）採用了分別征服方法，基於二次型和跡函式給出了這些函式所有導數的非線性度的下界。最後給出了這類四次函式的二階非線性度下界。與此同時，我們給出了這些函式有最佳二階非線性度的條件，並給出了達到該條件的函式類。這些結果表明此類布爾函式具有較好的二階非線性度，能夠抵抗二次逼近攻擊。2、針對下一代密碼算法中使用的多線性映射提出了一種新的攻擊方法。其中利用了布爾邏輯提出了一種稱為 “downgrading” 的攻擊方法,使攻擊者能夠從一個高級編碼得到一個低級編碼。攻擊者可以在CDH假設下攻擊多線性映射。除此之外，這種方法對屬性加密的身份基聚合簽名都是有效的。這種方法可以分析基於多線性映射構造的密碼算法的潛在安全弱點。3、原計畫中希望採用的尋找密碼函式的二階非線性度快速方法並不奏效，還需要尋找其他替代方法展開相關研究。另外，原計畫中計畫使用Reed-Muller碼覆蓋半徑計算密碼函式的二階非線性度及其下界的方法，對於特殊類型的函式是起作用的，但通常會得到一些與編碼方面的平行結果。本項目的結果對於密碼函式在密碼算法設計和分析以及其套用具有一定的指導意義。
