布尔函式--中文百科全书

简介

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

带有定义域 {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(x,y) = y + xy + x = x + y + xy。