抵禦代數和快速代數攻擊的布爾函式的性質與構造

《抵禦代數和快速代數攻擊的布爾函式的性質與構造》是依託中山大學，由杜育松擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：抵禦代數和快速代數攻擊的布爾函式的性質與構造
• 項目類別：青年科學基金項目
• 項目負責人：杜育松
• 依託單位：中山大學

中文摘要

布爾函式是流密碼體制的一個重要設計元素。使用在流密碼中的布爾函式應該具有各種密碼性質以有助於抵禦各種不同的密碼攻擊。本項目研究布爾函式的代數免疫性、非線性度和相關免疫性等幾種密碼性質，並著重考慮布爾函式抵禦快速代數攻擊的性能。研究內容可以分成三個方面：具有較大代數免疫度和較高非線性度的彈性布爾函式的構造，抵禦快速代數攻擊性能良好的布爾函式的性質與構造，基於計算困難問題構造的布爾函式的密碼性質。

結題摘要

布爾函式是流密碼體制的一個重要設計元素。使用在流密碼中的布爾函式應該具有各種密碼性質以有助於抵禦各種不同的密碼攻擊。本項目著重考慮布爾函式抵禦快速代數攻擊的性能。主要在抵禦快速代數攻擊性能良好的布爾函式的判定和構造方面進行了研究。取得的研究結果主要有以下四個方面。對於在設計流密碼時，分析、判定和選擇抵禦快速代數攻擊性能良好的布爾函式，它們具有理論指導意義。首先，重新刻畫了布爾函式抵禦快速代數攻擊的性能與布爾函式的代數免疫性之間的關係，深化了對布爾函式抵禦快速代數攻擊性能的認識。其次，給出了布爾函式抵禦快速代數攻擊性能（幾乎）最優的一個簡化的充分條件。利用這一充分條件，在判斷一個給定布爾函式的抵禦快速代數攻擊的性能時，有可能少計算若干個矩陣的秩，從而減少實際的計算量。再次，對於布爾冪函式，給出了將原來在有限域GF(2^n)上的判定矩陣約化到有限域GF(2)上矩陣的一個充分條件，即如果給定的布爾冪函式滿足這一條件，那么其抵禦快速代數攻擊的性能僅與其冪次相關。利用這一充分條件，通過計算機實驗發現了幾類14元和15元抵禦快速代數攻擊性能亞幾乎最優的布爾冪函式。最後，提出了輪換對稱代數免疫（RS-代數免疫）的概念，即在判定抵禦快速代數攻擊性能時僅考慮使用輪換對稱布爾函式進行快速代數攻擊的情形。考察了代數變元數小於等於15次數大於等於n-3並且係數為1的所有布爾冪函式的RS-代數免疫性，發現它們的RS-代數免疫性與其抵禦快速代數攻擊的性能完全相同，從而構造抵禦快速代數攻擊性能良好的布爾冪函式就等價於構造RS-代數免疫性好的布爾冪函式。RS-代數免疫性的判定矩陣具有更好的代數結構，這使系統地構造抵禦快速代數攻擊性能良好的布爾函式成為可能。