布爾函式代數免疫性研究

《布爾函式代數免疫性研究》是依託汕頭大學，由陳銀冬擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：布爾函式代數免疫性研究
• 項目類別：青年科學基金項目
• 項目負責人：陳銀冬
• 依託單位：汕頭大學

項目摘要

代數攻擊是近幾年發展起來的一種新的密碼分析方法，對許多密碼系統都構成很大的威脅。隨著代數攻擊的出現，也提出了關於布爾函式安全性的一個新準則- - 代數免疫度，它衡量了布爾函式抵抗標準代數攻擊的能力。為了有效抵禦代數攻擊所帶來的衝擊，密碼系統必須使用代數免疫度較高（甚至代數免疫最優）的布爾函式。本項目研究布爾函式的代數免疫性：首先，研究所有對稱布爾函式和某類輪換對稱布爾函式達到代數免疫最優的充要條件，並分析這些函式的其它密碼學性質，以期找到在各種密碼學性質上均表現優良的布爾函式，來滿足現實需求；同時，從新的角度入手，探索構造代數免疫最優布爾函式的新型方法；此外，還將引入交換代數中的Gr?bner基計算工具，提出具有更高計算效率的新算法，來計算布爾函式的代數免疫度和零化子。在代數攻擊的背景下，研究布爾函式的代數免疫性，特別是代數免疫最優布爾函式的構造，不但有著特殊的理論意義，更具有重要的現實意義。

結題摘要

代數攻擊的出現對許多密碼系統都構成威脅。為了有效抵禦代數攻擊所帶來的衝擊，密碼系統必須使用代數免疫度較高的布爾函式。本項目主要研究布爾函式的代數免疫性，包括以下內容：首先，關於代數免疫最優的輪換對稱布爾函式。在擇多函式的基礎上，通過改變某些特殊軌道的函式值，得到偶數變元代數免疫最優的輪換對稱布爾函式。在此基礎上加入滿足一定性質的軌道簇，可得到數量更多的布爾函式；對於奇數變元的情形，則在基於整數拆分理論來選取可改變函式值的軌道簇，從而得到既滿足代數免疫最優又具有較高非線性度的布爾函式。而且，從不同的選取角度出發，將得到數量更加豐富的函式。其次，關於代數免疫最優的對稱布爾函式。研究了代數免疫最優對稱布爾函式的標準型：均可表示為擇多函式與兩類特定函式中的若干個之和。同時也研究了該類函式的代數次數和非線性度，藉助標準型的表達方式，給出了非線性度的準確計算式。再次，關於代數免疫最優的布爾函式。主要研究了代數免疫最優布爾函式的遞推構造。首先針對奇數變元的特點，將之前的二階遞歸構造法加以改進，得到平衡的布爾函式。同時引入函式變換，得到一系列的構造方法。最後將上述構造法從二階遞歸推廣到一階遞歸，得到更加豐富的遞歸構造法。最後，關於代數免疫性的快速計算。函式f 的代數免疫度就是理想和理想中多項式的最低代數次數。利用Grobner基的快速算法，結合二元域GF(2)的特殊性，設計計算理想中多項式次數的快速算法。但由於Grobner基算法的複雜性，在具體計算上，對於GF(2)上的不同多項式，表現出不同的效率。目前尚未分析出明確的科學規律。