布爾函數(shù)構造與代數(shù)攻擊研究.pdf

1、近年來，代數(shù)攻擊已經(jīng)獲得了密碼學界的廣泛關注。為了抵制各種攻擊，布爾函數(shù)必須具有好的密碼性質：平衡，高的代數(shù)免疫，高的代數(shù)次數(shù)，高的非線性度以及好的抵制快速代數(shù)攻擊的能力。本文研究了具有好的密碼性質的布爾函數(shù)構造與代數(shù)攻擊，主要貢獻如下：
　　第一，提出了利用本原多項式來構造密碼上重要的布爾函數(shù)的方法，并構造了三類布爾函數(shù)具有非常好的密碼性質：平衡，最優(yōu)代數(shù)次數(shù)，最優(yōu)代數(shù)免疫和高的非線性度。在08年Asiacrypt上，Carle

2、t和Feng研究了一類具有好的密碼性質的布爾函數(shù)，其非線性度好于之前提出的所有無限類布爾函數(shù)，而我們導出的非線性度的界比他們的還要好。
　　第二，提出了一種新方法來研究布爾函數(shù)的非線性等價，討論了在每一個等價類中布爾函數(shù)的個數(shù)，進一步研究了等價類的一些性質，包括代數(shù)次數(shù)，代數(shù)免疫和非線性度，并給出了它們的界。我們發(fā)現(xiàn)有很多等價類具有最優(yōu)代數(shù)次數(shù)，最優(yōu)代數(shù)免疫和好的非線性度，并討論了如何來構造具有特定性質的等價類，進而證明構造布爾函

3、數(shù)使得其所在等價類具有好的密碼性質是可能的。
　　第三，研究了布爾函數(shù)抵制快速代數(shù)攻擊的能力，給出了快速代數(shù)免疫和高階非線性度之間的一個界(這是首次有人給出這兩個密碼性質之間的界)，接著證明了下面兩類布爾函數(shù)的快速代數(shù)免疫是不好的：
　　(a)Carlet提出的Tu-Deng函數(shù)的修復函數(shù)。Tu-Deng函數(shù)具有最優(yōu)代數(shù)次數(shù)，最優(yōu)代數(shù)免疫和非常好的非線性度，但它抵制快速代數(shù)攻擊的能力非常弱，Carlet發(fā)現(xiàn)了這個弱點并試圖修

4、復它。
　　(b)Tang等人提出的一類函數(shù)，具有最優(yōu)代數(shù)次數(shù)，最優(yōu)代數(shù)免疫和非常好的非線性度。
　　第四，提出了代數(shù)攻擊的一個改進版本，并將其應用于流密碼分析，新的攻擊方法在許多情形下都有效，其時間復雜度要比經(jīng)典的代數(shù)攻擊小得多。特別地，我們考察了流密碼Trivium和E0，發(fā)現(xiàn)針對它們的經(jīng)典代數(shù)攻擊可以被極大地加速。
　　第五，提出了一種新的代數(shù)攻擊，稱之為高階代數(shù)攻擊，并將其應用于流密碼分析，其效率通過新概念r階