Hey 你好！我来帮你理清这个问题——你想知道n元布尔函数$f(x_1,x_2,...,x_n)=f(x_n,...,x_2,x_1)$的充要条件，还需要检索这类函数的方法，对吧？这类对称函数在密码学算法里确实挺实用的，尤其是那些依赖对称性构造的场景。

一、充要条件 #

我们可以从几个不同的视角来拆解这个等价性条件：

1. 真值表视角

最直接的充要条件是：对于任意输入向量$\mathbf{x}=(x_1,x_2,...,x_n)$，它的反转向量$\text{rev}(\mathbf{x})=(x_n,...,x_2,x_1)$对应的函数值必须和$\mathbf{x}$完全一致。

• 如果n是偶数：所有输入向量都会两两组成“反转对”，每一对的函数值必须相等；
• 如果n是奇数：除了成对的反转向量，还有一类输入向量反转后等于自身（比如n=3时的$(a,b,a)$），这类向量的函数值可以自由选择，没有额外限制。

2. 代数标准型（ANF）视角

布尔函数的代数标准型可以表示为：
$$f(\mathbf{x}) = \sum_{S \subseteq {1,2,...,n}} a_S \prod_{i \in S} x_i$$
（这里的加法是模2加法，也就是异或运算）
对应的充要条件是：对于任意变量子集$S$，其反转子集$\text{rev}(S)$对应的系数必须相等。这里的$\text{rev}(S)$指的是把$S$中每个位置$i$替换为$n+1-i$得到的子集——比如n=5时，$S={1,3}$的反转子集就是${5,3}$。

二、检索/构造这类函数的方法 #

根据上面的条件，我们可以高效地生成或筛选符合要求的函数：

• 真值表构造法：
  不需要遍历所有$2^n$个输入，只需要为每一组“反转等价类”的输入指定函数值即可。比如n=4时，(0,0,0,1)和(1,0,0,0)属于同一类，只需要给其中一个赋值，另一个直接复制；对于反转后等于自身的输入（比如n=3时的(0,0,0)、(0,1,0)、(1,0,1)等），可以自由赋值。这样能把构造的工作量减少一半左右。

• 代数标准型筛选法：
  如果是从已有的布尔函数中筛选，只需要检查它的ANF系数：遍历所有变量子集$S$，验证$a_S = a_{\text{rev}(S)}$是否成立。用程序实现的话，这个逻辑非常直接，很容易批量筛选。

• 密码学场景优化：
  如果需要同时满足其他密码学性质（比如高非线性度、平衡性、抗差分攻击等），可以先通过反转对称条件缩小搜索池，再在池子里筛选符合额外性质的函数。反转对称会大幅减少候选函数的数量：原本有$2^{2n}$个n元布尔函数，符合条件的只有$2^{M$个，其中$M$是反转等价类的总数，计算方式为$\frac{2}n + C}{2}$（$C$是反转后等于自身的输入向量数量，n奇数时$C=2^{{(n+1)/2}$，n偶数时$C=2}{n/2}$）。

备注：内容来源于stack exchange，提问作者roland a.