布尔函数是对称密码中的本质性“存在”，它是对称密码的“灵魂”。

世界上的许多现象都可表现出两种状态，比如海潮的起与落，电路的开与关，搏击的攻与防等等。我国传统道家哲学把这种相依且相反的二元现象辩证地抽象为“阴”与“阳”，认为宇宙间任何事物都有阴阳两个方面，由阴阳互补互动而体现出宇宙秩序。遗憾的是，这种阴阳哲学没有数学化地发展成科学，而是局限地“模糊”在玄学层面。在西方近代以来，发展出处理二元问题的布尔符号逻辑（布尔函数），成为一门数学，并在工程中得到广泛应用。

布尔函数能在工程中被成功应用，不得不提到两个人：一个是乔治·布尔（George Boole, 1815-1864），另一个是克劳德·艾尔伍德·香农（Claude Elwood Shannon, 1916-2001）。布尔分别在1847年和1854年发表论著《The Mathematical Analysis of Logic》和《An Investigation into the Laws of Thought》，创建了布尔代数。布尔代数奠定了用逻辑思维的方式，而不是形象思维的方式，处理二元逻辑问题的数学基础。1938年，香农在他的硕士论文《A Symbolic Analysis of Relay and Switching Circuits》中，科学严谨地论述了如何使用布尔代数对开关电路进行设计和分析，为布尔函数在数字电路系统（包括密码系统）中的实际应用奠定了基础。

香农另一了不起的工作是在1949年发表了论文《Communication Theory of Secrecy Systems》，从信息论的角度为对称密码（包括流密码和分组密码）的设计和分析指明了方向。在这一先驱性的论文中，香农提出了“扩散”（diffusion）和“混淆”（confusion）两个设计原则，至今仍是指导我们设计对称密码和Hash函数的主要原则。这篇论文具有里程碑意义，迈出了有史以来对称密码科学化进程中最重要的一步。

在1976年分组密码和公钥密码出现之前，流密码是占统治地位的加解密方式。早在一百年前（1917年），布尔逻辑结构就在Vernam流密码中出现。布尔函数在流密码中真正被理性地作为研究对象始于它在线性反馈移位寄存器（LFSR）中的应用。在1960年代末，Berlekamp-Massey算法的提出，使人们意识到提高密钥流序列线性复杂度的重要性。从1970年代开始，人们开始考虑在多个LFSR之间引入乘法运算，用非线性组合模式来提高生成序列的线性复杂度；后来又出现基于LFSR滤波模式的序列生成器。决定基于LFSR的流密码安全强度的核心部件是系统中的非线性组合布尔逻辑和非线性滤波布尔逻辑结构，它们就是狭义上的流密码中的密码函数。

1980年代中期，出现了针对基于LFSR的流密码的相关分析，这对密码函数设计提出新的要求，要求用于流密码中的密码函数具有相关免疫性质。在同一时期，我国学者肖国镇（1934-2016）把频谱技术用于密码函数的分析，提出相关免疫函数的频谱化定理（Xiao-Massey定理），通过频谱简洁地刻画了相关免疫函数的特征。这一定理对密码函数的设计和分析具有重要的指导意义。

利用频谱技术还可以研究密码函数的另一重要指标（性质）：非线性度。密码函数的非线性度被定义为密码函数和所有仿射函数汉明距离的最小值。非线性度这一指标的提出，受到了香农1949年论文中“相似系统”（Similar Systems）思想的启发。我们如何度量一个东西有多“好”呢？那就是看这个东西有多大程度上“不像”我们认为的“坏”的东西。在布尔函数之间，这种“不像”是用汉明距离来度量的。对特定密码指标的研究本质上是对特定条件下0和1分布的研究，当在特定条件下的0和1严重失衡时，就成为被利用的密码学缺陷。非线性度是度量对称密码抵抗线性逼近攻击能力的指标，在流密码和分组密码中都很重要。

不同密码学指标之间往往存在着制约关系，比如非线性度和相关免疫性就是相互“冲突”的两个密码指标，平衡的相关免疫函数（弹性函数）的非线性度的紧上界至今仍是悬而未决的难题（《10000个科学难题·信息科学卷》, 科学出版社，2011）。如何实现多种密码学指标的优化折中，是密码函数设计中的核心难题。

密码分析技术直接地促进和引导了密码函数设计理论的发展。对流密码和分组密码的分析（攻击）本质上都是利用了密码中布尔逻辑（函数）结构或性质上的缺陷。比如，用布尔函数的高阶差分来降低代数次数以实现对流密码的立方攻击；分组密码攻击所用的区分器与布尔函数的基本性质密切相关等。值得一提的是，我国学者曾肯成（1927-2004）等人早在1987-1990年间，就在美密会等国际会议上发表了一系列有关密码分析的重要论文；近十年来，我国学者在流密码和分组密码分析方面取得一些进展，这些论文对分析和设计对称密码具有重要参考价值。限于篇幅，这里不一一列举。此外，在密码算法的工程实现及防护上，密码部件硬件快速实现需要的对合性质，以及硬件防护的布尔掩码、域分解等技术均依赖布尔函数的各种性质来达成。

1990年代是研究密码函数的重要十年，我国学者在这一研究方向上取得了一系列重要进展。比较有代表性的成果是丁存生和肖国镇提出的“流密码的稳定性理论”（《The Stability Theory of Stream Ciphers》，Springer, 1991）和冯登国的博士学位论文《频谱理论及其在通信保密技术中的应用》。2000年之后的几年里，密码函数的研究陷入低潮，直到代数攻击（包括快速代数攻击）的出现。和相关攻击一样，代数攻击也是利用了基于LFSR的流密码本身固有的缺陷。这种缺陷可以通过精心设计密码函数得到弥补，为了抵抗代数攻击，密码学家又提出新的密码指标——代数免疫（包括快速代数免疫）。代数攻击出现后，密码函数又作为热门课题被研究了十年。研究的问题从最初的如何设计具有最优代数免疫阶的布尔函数，到后来如何同时兼顾非线性度、平衡性、弹性、代数次数等密码指标。我国学者特别是青年学者在这一研究方向上有很多值得一提的成果，读者可参考本期综述论文《布尔函数的(快速)代数免疫性质研究进展》。

基于LFSR的流密码是被研究的较为充分的密码，如何利用非线性密码函数“掩盖”系统中线性部分（LFSR部分）是保证这类密码安全性的主要任务。近十年中出现的流密码，都在避免出现“纯线性”的部分，在系统中融入各种非线性元素，但其生成序列的伪随机性（安全性）比较难以从理论的角度解释清楚。无论流密码采用什么样的形式结构，其中非线性部件中的运算仍然还是布尔逻辑运算。

相对于公钥密码学而言，流密码学的科学化发展还有很长的路要走。无论如何发展，布尔函数都将扮演重要角色。

布尔函数的密码价值还表现在它在分组密码中的“存在”。S盒作为分组密码的非线性模块，可以看做是一个多输出布尔函数，是密码函数研究的重要对象。为了抵抗针对分组密码的线性攻击和差分攻击，需要S盒具有高非线性度和低差分均匀度。如何构造同时具有高非线性度和低差分均匀度的均衡（包括置换）S盒，是研究用于分组密码中的密码函数（S盒）主要考虑的问题。当然，S盒还要具有简洁的结构，以便于实现。这一研究方向上最具挑战性的公开难题是“大APN问题”：在n为不小于8的偶数时，是否存在GF(2^n)上的APN置换？

布尔函数在Hash函数、秘密共享、量子密码等领域也有应用。作为布尔函数最具前景的一个研究方向，是对用于非线性反馈移位寄存器（NFSR）的反馈函数的研究。这些场合的布尔函数都可以看做是广义的密码函数。

在本期密码学报“密码函数”专栏，我们刊登4篇论文，希望对从事这一研究方向的同行有参考价值。

第1篇论文题目是“布尔函数的(快速)代数免疫性质研究进展”。布尔函数的代数免疫性质和快速代数免疫性质分别衡量了基于LFSR的流密码抵抗代数攻击和快速代数攻击的能力。这一课题已研究了十多年，仍有很多问题没有弄清楚。该论文较全面地总结了近十余年来国内外学者在构造具有优良代数免疫性质（包括快速代数免疫性质）且兼顾其他密码学性质相关方面的主要研究进展。

第2篇论文题目是“旋转对称布尔函数研究综述”。旋转对称布尔函数具有规则简洁的结构，使之便于采用代数工具进行研究，也便于硬件实现。更值得一提的是，旋转对称布尔函数可以具有优良的密码学性质。例如，早在1983年Patterson和Wiedemann就发现了覆盖半径是16276的[2¹⁵,16] RM码，实际上就是找到了非线性度是16276的15元旋转对称布尔函数。旋转对称布尔函数除了可以具有高非线性度，还可以是弹性函数，可以具有优良的代数免疫性质。本文对旋转对称布尔函数，特别是旋转对称bent函数和旋转对称半bent函数的研究现状，进行了较全面的总结；对高非线性度旋转对称布尔函数的搜索、旋转对称布尔函数代数结构和密码学性质之间的关系等研究问题也有较好的介绍。

第3篇论文题目是“有限域上置换多项式的几种构造”。置换是密码函数的一种重要性质，具有简单代数形式的置换多项式在分组密码中具有应用价值。本文构造了有限域的偶次扩域上几类置换二项式，并由此得到新的完全置换单项式，丰富了已有结果。此外，给出了两类与迹函数有关的多项式置换，推广了已知的相关构造。

第4篇论文题目是“具有高维输出的半bent弹性S盒的构造”。半bent函数是一种非线性度几乎最优的密码函数，可以同时具有弹性和高非线性度。但对多输出半bent弹性S盒而言，输出维数很难提高。前人曾构造出半bent弹性S盒，但输出维数都不超过输入维数的1/4。本文给出的这种方案，在输入维数比较大时，输出维数可大于输入维数的1/4。随着输入维数的增大，这一比例有继续变大的趋势。

值得一提的是，在这4篇论文末尾都列出了值得进一步研究的问题供读者思考。

   张卫国2017年3月30日晚于西电