布尔函数构造与代数攻击研究

论文摘要

近年来,代数攻击已经获得了密码学界的广泛关注。为了抵制各种攻击,布尔函数必须具有好的密码性质：平衡,高的代数免疫,高的代数次数,高的非线性度以及好的抵制快速代数攻击的能力。本文研究了具有好的密码性质的布尔函数构造与代数攻击,主要贡献如下：第一,提出了利用本原多项式来构造密码上重要的布尔函数的方法,并构造了三类布尔函数具有非常好的密码性质：平衡,最优代数次数,最优代数免疫和高的非线性度。在08年Asiacrypt上,Carlet和Feng研究了一类具有好的密码性质的布尔函数,其非线性度好于之前提出的所有无限类布尔函数,而我们导出的非线性度的界比他们的还要好。第二,提出了一种新方法来研究布尔函数的非线性等价,讨论了在每一个等价类中布尔函数的个数,进一步研究了等价类的一些性质,包括代数次数,代数免疫和非线性度,并给出了它们的界。我们发现有很多等价类具有最优代数次数,最优代数免疫和好的非线性度,并讨论了如何来构造具有特定性质的等价类,进而证明构造布尔函数使得其所在等价类具有好的密码性质是可能的。第三,研究了布尔函数抵制快速代数攻击的能力,给出了快速代数免疫和高阶非线性度之间的一个界（这是首次有人给出这两个密码性质之间的界）,接着证明了下面两类布尔函数的快速代数免疫是不好的：（a） Carlet提出的Tu-Deng函数的修复函数。Tu-Deng函数具有最优代数次数,最优代数免疫和非常好的非线性度,但它抵制快速代数攻击的能力非常弱,Carlet发现了这个弱点并试图修复它。（b） Tang等人提出的一类函数,具有最优代数次数,最优代数免疫和非常好的非线性度。第四,提出了代数攻击的一个改进版本,并将其应用于流密码分析,新的攻击方法在许多情形下都有效,其时间复杂度要比经典的代数攻击小得多。特别地,我们考察了流密码Trivium和E0,发现针对它们的经典代数攻击可以被极大地加速。第五,提出了一种新的代数攻击,称之为高阶代数攻击,并将其应用于流密码分析,其效率通过新概念r阶代数免疫来描述。我们证明了下面两类布尔函数的2阶代数免疫为1,从而给出了针对它们的极其有效的攻击（极大地超过了已知的所有攻击）：（a） Carlet-Feng函数,具有最优代数次数,最优代数免疫,好的非线性度以及好的抵制快速代数攻击的能力。（b）旋转对称布尔函数,一类非常有趣且已被很好研究的布尔函数,可以被有效地实现。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 引言
• 1.1.1 流密码
• 1.1.2 线性反馈移位寄存器
• 1.1.3 布尔函数
• 1.1.4 过滤生成器
• 1.1.5 代数攻击与快速代数攻击
• 1.2 预备知识
• 1.3 国内外研究情况
• 1.4 本文贡献
• 第二章 利用本元多项式构造具有好的密码性质的布尔函数
• 2.1 研究背景
• 2.2 具有好的密码性质的布尔函数构造
• 2.2.1 构造1
• 2.2.2 构造2
• 2.2.3 构造3
• 2.3 结论
• 第三章 布尔函数的非线性等价研究
• 3.1 研究背景
• 3.2 序列与布尔函数的表示
• 3.3 布尔函数的等价
• 3.4 等价类的密码性质
• 3.5 具有最优代数次数,最优代数免疫以及好的非线性度的等价类
• 3.6 具有特定性质的等价类构造
• 3.7 结论
• 第四章 关于布尔函数抵制快速代数攻击的能力
• 4.1 研究背景
• 4.2 快速代数免疫和高阶非线性度之间的界
• 4.3 关于Carlet提出的修补函数
• 4.4 关于Tang等人提出的布尔函数
• 4.5 结论
• 第五章 一种改进的代数攻击
• 5.1 研究背景
• 5.2 一种改进的代数攻击
• 5.3 针对Trivium和EO的代数攻击
• 5.4 结论
• 第六章 高阶代数攻击
• 6.1 研究背景
• 6.2 过滤生成器以及它们的循环群
• 6.3 引入高阶代数攻击
• 6.4 针对Carlet-Feng函数的二阶代数攻击
• 6.5 针对旋转对称布尔函数的二阶代数攻击
• 6.6 结论
• 参考文献
• 攻读学位期间论文发表情况
• 致谢