3月11日，在罗马对称密钥密码学春季学校上，我邀请大家试着证明以下等式。 如果$F \colon \mathbf{F}_2^n \to \mathbf{F}_2^m$是任意一个函数，那么它的差分转移矩阵和相关矩阵满足下面这个方程：

当$u = 0$和$v = 0$时, 由于$D^F_{(0, b), (0, a)}$表示一般差分近似的概率，这个方程就变成了Chabaud-Vaudenay关系式：

我今天想聊聊这两个等式的证明。

我们先把上面的等式推广一下。假设$G$和$H$是有限交换群，而$F \colon G \to H$是任意函数。现在，上面的等式成为

这里，$\psi$和$\chi$是两个不可约群特征标。如果和之前一样$G = \mathbf{F}_2^n$、$H = \mathbf{F}_2^m$，那么$\psi \colon x \mapsto (-1)^{u^t x}$、$\chi \colon x \mapsto (-1)^{v^t x}$。 我在春季学校设想的证明是一个比较又长又繁琐的计算（好像当时没有人完全找到证明出来）。归根结底，应该用特征标的正交关系。可是，这种计算不太精辟。

对任意函数$F$，我们可以再定义一个函数$F' \colon G \times G \to H \times H$为

根据这个定义，$F$的差分转移矩阵就是$D^F = (\mathscr{F}_H \otimes \mathrm{id}) T^{F'}(\mathscr{F}_G \otimes \mathrm{id})^{-1}$。 这里，$\mathscr{F}$是傅立叶变换，而且$T^{F'}$是$F'$的转移矩阵。 此外，$F'$的相关矩阵是$C^{F'} = (\mathscr{F}_H \otimes \mathscr{F}_H) T^{F'}(\mathscr{F}_G \otimes \mathscr{F}_G)^{-1}$。也就是说，有下面的交换图：

根据上面的交换图，我们有$C^{F'} = (\mathrm{id} \otimes \mathscr{F}_H)\,D^{F}\,(\mathrm{id} \otimes \mathscr{F}_G)^{-1}$。 相关矩阵的子块也有下面的等式：

相差一个标量因子的话，傅立叶变换是酉算子，所以它保持弗罗比尼乌斯范数：

实际上，可以把左侧的前置因子$|G|/|H|$放在弗罗比尼乌斯范数的定义中。 就像我博士论文第三章里讨论的，$\mathbb{C}[G]$上的自然范数是$\big\|\sum_x u_x \,\delta_x\big\| = \sqrt{|G|\,\sum_{x} |u_x|^2}$。 最后，根据线性密码分析，我们有