布尔函数

数学函数

在数学中，布尔函数（Boolean function）描述如何基于对布尔输入的某种逻辑计算确定布尔值输出，它们在复杂性理论的问题和数字计算机的芯片设计中扮演基础角色。布尔函数的性质在密码学中扮演关键角色，特别是在对称密钥算法的设计中（参见S-box）。

定义

布尔函数，是由到上的函数或映射称为n元函数，记为f（x1,…,xn），简记为f（x）或f，其中x=（x1,…,xn）=，即（x1,…,xn）是x的二进制表示。

简介

布尔函数是研究密码算法和密码技术的重要工具，无论在流密码还是在分组密码中，在对称还是在非对称密码中都有重要的应用。

带有定义域 {1,2,3,... } 的这种函数通常叫做二进制序列，就是说 0 和 1 的无限序列；通过限制到 { 1,2,3,...,n }，布尔函数是编码长度为 n 的序列的自然的方法。

它有 2^{2^n} 个布尔函数；它们在复杂性理论的问题和数字计算机的芯片设计中扮演基础角色。布尔函数的性质在密码学中扮演关键角色，特别是在对称密钥算法的设计中(参见 S-box)。

在布尔值函数上的布尔运算逐点（point-wise）组合值（比如通过 XOR 或其他布尔运算符）。

布尔函数可以唯一的写为积（AND）之和（XOR）。这叫做代数范式（ANF），也叫做Zhegalkin多项式。

f(x1,x2,...,xn) =a0 +a1x1 + a2x2 + ... + anxn +

a{1,2}x1x2 + a{n-1,n}x(n-1）xn +

... +

a{1,2,...,n}x1x2...xn

序列 a0,a1,...,a{1,2,...,n} 的值因此还唯一的表示一个布尔函数。布尔函数的代数度被定义为出现在乘积项中的 xi 的最高数。所以 f(x1,x2,x3） = x1 + x3 有度数 1 （线性），而 f(x1,x2,x3） = x1 + x1x2x3 有度数 3 （立方）。

特点

布尔函数必须满足一定的密码学性质，以保证密码系统符合安全性的基本要求，并能抵抗现有的各种攻击。下面介绍几条衡量布尔函数密码学性质的指标。

为了抵抗最佳仿射逼近攻击，布尔函数必须与仿射函数保持尽可能大的汉明距离。为了衡量布尔函数抵抗“仿射攻击”的能力，引入了非线性度的概念。

代数范式

布尔函数可以唯一的写为积（AND）之和（XOR）。这叫做代数范式（ANF），也叫做Zhegalkin多项式。

这里的序列的值因此还唯一的表示一个布尔函数。布尔函数的代数次数被定义为出现在乘积项中的 xi 的最高次数。所以 f(x1,x2,x3） = x1 + x3 有次数 1 （线性），而 f(x1,x2,x3） = x1 + x1x2x3 有次数 3 （立方）。

对于每个函数 f 都有一个唯一的 ANF。只有四个函数有一个参数: f(x) = 0,f(x) = 1,f(x) = x,f(x) = 1 + x （它们都可以在 ANF 中给出），要表示有多个参数的函数，可以使用如下等式：，这里的并且。实际上，如果 x1 = 0 则 x1h = 0 并因此；如果 x1 = 1 则 x1h = h 并因此。因为 g 和 h 二者都有比 f 少的参数，可以得出递归的使用这个过程将完成于只有一个变量的函数。例如，让我们构造一个（逻辑或）的 ANF: f(x,y) = f(0,y) + x(f(0,y) + f（1,y））；因为并且，可以得出 f(x,y) = y + x（y + 1）；通过打开括号我们得到最终的 ANF: f（

应用

应用程序中

一个布尔函数介绍了如何确定一个布尔值输出基于某种逻辑输入计算的布尔值。这些职能发挥作用的问题的基本理论，复杂性，以及作为设计的电路芯片和数字电脑。布尔函数的性质研究中发挥关键作用密码学，特别是在设计的对称密钥算法（见替代框）。

布尔函数通常代表中的句子命题逻辑，有时作为多元多项式超过绿 ⑵，但更有效的申述，二元决策图（BDD）的，正常的否定形式，与命题向无环图（PDAG）。

在合作博弈论，布尔函数被称为游戏）简单的游戏（表决；这个概念应用到解决问题的社会选择理论。

密码学中

布尔函数是流密码系统的核心部件，研究布尔函数是流密码系统重点。代数攻击是密码学的研究热点。布尔函数必须具有好的密码性质:平衡，高的代数免疫，高的代数次数，高的非线性度，代数攻击的能力。

对称布尔函数

对于 n元d次初等对称布尔函数 X(d,n) ，当时，对于给定的s 和q，证明了如果w充分大，则，即证明了 X(d,n)不是平衡的，并且利用泰勒展式估计了w的大小；对于给定的 wq 和 t，证明了如果s 充分大，则

即证明了 X(d,n)不是平衡的

参见

代数集