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

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

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

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

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