一类可逆移位不变函数的构造

A Construction of a Class of Invertible Shift-Invariant Functions

摘要: 在面向安全多方计算、全同态加密与零知识证明等的对称密码构件的设计中，人们需在大素数有限域上构造乘法复杂度低且可逆的非线性层。移位不变函数因其良好的非线性结构与实现优势而被广泛采用，Lai-Massey构造是其中具有代表性的一类。本文基于广义的Lai-Massey构造，提出了更一般的可逆移位不变函数的构造方法，为面向算术的非线性层设计提供了更丰富的可逆向量值函数。

Abstract: In the design of symmetric cryptographic components for secure multi-party computation, fully homomorphic encryption, and zero-knowledge proofs, one needs to construct nonlinear layers over large prime finite fields that are both invertible and of low multiplicative complexity. Shift invariant functions are widely adopted due to their favorable nonlinear structure and implementation advantages, with the Lai-Massey construction being a representative example. Building on generalized Lai-Massey constructions, this paper proposes a more general method for constructing invertible shift-invariant functions, providing a richer collection of invertible vector valued functions for arithmetization-oriented nonlinear layer design.

1. 引言

近些年来，随着安全多方计算(Secure Multi-Party Computation, MPC)、全同态加密(Fully Homomorphic Encryption, FHE)以及零知识证明(Zero-Knowledge proofs, ZK)等广泛的应用，对称密码的基本构件的设计有了新的要求，其设计重心从传统的运算友好转向在大素数域上减少乘法的次数，即减小乘法复杂度。这一趋势在面向算术化的密码方案中表现得尤为明显(参见文献[1]-[7])。由此，构造一个具有低乘法复杂度且可逆的非线性层成为了值得关注的问题：一方面需要非线性层具有可逆性以支撑迭代轮函数的置换性质，另一方面非线性层需保持足够的代数复杂性质以抵抗代数攻击。

众所周知，迭代型对称密码算法通常是对轮函数进行多轮迭代实现加解密的，而轮函数往往可分解为“非线性层 + 线性层”，可写作

$x\mapsto c+M\cdot S\text{-Box}\left(x\right)\text{,}$

其中$S\text{-Box}$ 为非线性层，$M$ 为可逆的线性层，$c$ 为轮常数。在面向算术化的对称密码算法中仍使用这种迭代结构，只是底层运算从二元域上的比特运算拓展为素数阶有限域上的运算。Lorenzo Grassi等在文献[8]中针对非线性层的构造，定义了一类移位不变(shift-invariant)函数$S_F$ ：从一个局部映射出发，在上定义映射

$S_F\left(x_0,\cdots ,x_{n-1}\right)=\left(y_0,\cdots ,y_{n-1}\right),y_i=F\left(x_i,x_{i+1},\cdots ,x_{i+m-1}\right),$

其中指标按$n$ 取模。该函数$S_F$ 具有移位不变性，即对上的任意平移置换$\Pi$ 都有$S_F\circ \Pi =\Pi \circ S_F$ ，我们把由局部映射所定义的移位不变函数$S_F$ 称为由$F$ 诱导的移位不变$\left(m,n\right)$ -提升函数。上述定义的移位不变函数在二元域上的例子是Wolfram在文献[9]中定义的$\chi$ 函数，随后Daemen在文献[10]对其进行了系统的分析并证明了$\chi$ 所诱导的移位不变函数在奇数长度上可逆。$\chi$ 函数的应用参见文献[11]，[12]等。

然而，将上述可逆构造直接迁移到大素域${\mathbb{F}}_p$ 并不顺利。我们期望构造的是以低次数(尤其是二次)局部映射$F$ 作为基本单元，在较大$n$ 上得到可逆的$S_F$ ，从而在每轮仅用$O\left(n\right)$ 甚至更少的乘法实现非线性层。文献[8]给出了如下结果：当局部映射$F$ 为二次多项式时，使$S_F$ 成为可逆映射的$n$ 存在上界，即对于$m=2$ ，若$n\ge 3$ 则不存在二次多项式$F$ 使$S_F$ 成为可逆映射；对于$m=3$ ，$n\ge 5$ 同样不存在可逆映射$S_F$ ，并进一步猜想，当局部映射$F$ 为二次多项式时，对于固定的$m$ ，使$S_F$ 成为可逆映射的$n$ 的上界为$2m-1$ 。

尽管存在上述结论，但是在某些具备特殊结构且满足一定条件的局部映射族中，可逆是必然存在的。文献[13]给出了一个例子即Lai-Massey构造：由的局部映射$F\left(x_0,x_1\right)=x_0+{\left(x_0-x_1\right)}^2$ 诱导的移位不变函数

$S_F\left(x_0,x_1\right)=x_0+{\left(x_0-x_1\right)}^2\left|\right|x_1+{\left(x_1-x_0\right)}^2$ ,

可验证$S_F\left(x_0,x_1\right)$ 是可逆的。文献[8]给出了对Lai-Massey构造的如下两种推广。

命题1 ([8]) 设$p\ge 2$ 为素数。令$n=m\ge 2$ ，并满足$n$ 是$p$ 的倍数(即$n\equiv 0\left(\mathrm{mod}p\right)$ )或$n$ 是偶数。令局部映射为

$F\left(x_0,\cdots ,x_{n-1}\right)={\displaystyle \sum _{i=0}^{n-1}{\mu }_i}{x}_i+H\left({\displaystyle \sum _{i=0}^{n-1}{\omega }_i}{x}_i\right),$

其中满足其构成的循环矩阵可逆，并且${\omega }_i$ 与$H$ 满足：

1) 若$n\equiv 0\left(\mathrm{mod}p\right)$ ，则对每个$i\in \left\{0,1,\cdots ,n-1\right\}$ 有${\omega }_i=1$ ；

2) 若$n\equiv 0\left(\mathrm{mod}2\right)$ ，则对每个$i\in \left\{0,1,\cdots ,n-1\right\}$ 有${\omega }_i={\left(-1\right)}^i$ ，并且$H:{\mathbb{F}}_p\to {\mathbb{F}}_p$ 为偶函数，即对于任意$t\in {\mathbb{F}}_p$ 有$H\left(-t\right)=H\left(t\right)$ 。

则由$F$ 在上诱导的移位不变函数$S_F$ 是可逆的。

命题2 ([8]) 设$p\ge 2$ 为素数，令$n=m\ge 2$ 。设，使得循环矩阵

可逆，取$\gamma \in {\mathbb{F}}_p\backslash \left\{0\right\}$ 。令$H:{\mathbb{F}}_p\to {\mathbb{F}}_p$ 为任意函数，并定义为

$F\left(x_0,\cdots ,x_{n-1}\right)={\displaystyle \sum _{i=0}^{n-1}{\mu }_i}{x}_i+\gamma {\displaystyle \sum _{i=0}^{n-1}H}\left(x_i-x_{i+1}\right),$

其中下标均按$n$ 取模。则由$F$ 在上诱导的移位不变函数$S_F$ 是可逆的。

上述的命题1和命题2给出了两类可逆的移位不变函数$S_F$ 的构造。本文进一步推广了上述结果。首先，对于命题1，我们考虑了在$n$ 更一般的情况下，${\omega }_i$ 与$H$ 所满足的限制条件，从而给出了更一般的可逆的移位不变函数$S_F$ ；其次对于命题2，我们将局部映射函数做进一步推广，并证明其诱导的移位不变函数依然可逆。通过对命题1和命题2的推广，可为密码算法提供更为丰富的可逆移位不变函数的构造。

2. 预备知识

设$p\ge 2$ 为素数，令表示模$p$ 的整数域，并令表示当$n\ge 1$ 时相应的向量空间。给定，对每个$i\in \left\{0,1,\cdots ,n-1\right\}$ ，用$x_i$ 表示它的第$i$ 个分量，即

$x=\left(x_0,x_1,\cdots ,x_{n-1}\right)$ 或$x=x_0\left|\right|x_1\left|\right|\cdots \left|\right|x_{n-1}.$

定义1 令$p\ge 2$ 为素数。取整数$1\le m\le n$ ，令为一个非线性映射。定义上的移位不变函数$S_F$ 为

$S_F\left(x_0,\cdots ,x_{n-1}\right)=y_0\left|\right|y_1\left|\right|\cdots \left|\right|y_{n-1},$

其中$y_i=F\left(x_i,x_{i+1},\cdots ,x_{i+m-1}\right)$ ，并且下标按$n$ 取模。

记为如下的循环矩阵：

$\text{circ}\left({\mu }_0,{\mu }_1,\cdots ,{\mu }_{n-1}\right):=\left[\begin{array}{ccccc}{\mu }_0& {\mu }_1& \cdots & {\mu }_{n-2}& {\mu }_{n-1}\\ {\mu }_{n-1}& {\mu }_0& \cdots & {\mu }_{n-3}& {\mu }_{n-2}\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ {\mu }_1& {\mu }_2& \cdots & {\mu }_{n-1}& {\mu }_0\end{array}\right].$

3. 主要结果

在本节中，我们给出命题1和命题2的进一步推广。

定理1 设$p\ge 2$ 为素数。令$n=m\ge 2$ ，并满足$n$ 是$p$ 的倍数(即$n\equiv 0\left(\mathrm{mod}p\right)$ )或$\gcd \left(n,p-1\right)>1$ 。令局部映射为

$F\left(x_0,x_1,\cdots ,x_{n-1}\right)={\displaystyle \sum _{i=0}^{n-1}{\mu }_i}{x}_i+H\left({\omega }_0{x}_0+{\omega }_1{x}_1+\cdots +{\omega }_{n-1}{x}_{n-1}\right),$

其中满足其构成的循环矩阵可逆，并且${\omega }_i$ 与$H$ 满足：

1) 若$n\equiv 0\left(\mathrm{mod}p\right)$ ，则对每个$i\in \left\{0,1,\cdots ,n-1\right\}$ 有${\omega }_i=1$ ；

2) 若$\gcd \left(n,p-1\right)>1$ ，则对每个$i\in \left\{0,1,\cdots ,n-1\right\}$ 有${\omega }_i={\lambda }^i$ ，其中$\lambda \ne 1$ 为${\mathbb{F}}_p$ 上的$n$ 次单位根(即${\lambda }^n=1$ )，且$H:{\mathbb{F}}_p\to {\mathbb{F}}_p$ 满足对于任意$t\in {\mathbb{F}}_p$ 有$H\left(\lambda t\right)=H\left(t\right)$ 。

则由$F$ 在上诱导的移位不变函数$S_F$ 是可逆的。

证明 令，$y=S_F\left(x\right)={\left(y_0,\cdots ,y_{n-1}\right)}^{\text{T}}$ 。并记循环矩阵$C:=\text{circ}\left({\mu }_0,\cdots ,{\mu }_{n-1}\right)$ 。对每个$k\in \left\{0,1,\cdots ,n-1\right\}$ ，$S_F$ 的第$k$ 个坐标满足

令$T:={\displaystyle \sum _{i=0}^{n-1}{\omega }_i}{x}_i\in {\mathbb{F}}_p$ ，我们先说明对任意$k$ 都有

$H\left({\displaystyle \sum _{i=0}^{n-1}{\omega }_i}{x}_{k+i}\right)=H\left(T\right),$

若$n\equiv 0\left(\mathrm{mod}p\right)$ 且${\omega }_i=1$ ，此时

${\displaystyle \sum _{i=0}^{n-1}{\omega }_i}{x}_{k+i}={\displaystyle \sum _{i=0}^{n-1}{x}_{k+i}}={\displaystyle \sum _{i=0}^{n-1}{x}_i}=T,$

若$\gcd \left(n,p-1\right)>1$ 且${\omega }_i={\lambda }^i$ 、$\lambda \ne 1$ 、${\lambda }^n=1$ 。则对任意$k$ 都有，

${\displaystyle \sum _{i=0}^{n-1}{\omega }_i}{x}_{k+i}={\displaystyle \sum _{i=0}^{n-1}{\lambda }^i}{x}_{k+i}={\lambda }^{-k}{\displaystyle \sum _{j=0}^{n-1}{\lambda }^j}{x}_j={\lambda }^{-k}T,$

又因$H\left(\lambda t\right)=H\left(t\right)$ 对所有$t$ 成立，从而$H\left({\lambda }^{-k}T\right)=H\left(T\right)$ 。

因此对所有$k$ 都有

$y_k={\displaystyle \sum _{i=0}^{n-1}{\mu }_i}{x}_{k+i}+H\left(T\right),$

即向量形式

令${\mu }^{\prime }:={\displaystyle \sum _{i=0}^{n-1}{\mu }_i}\in {\mathbb{F}}_p$ ，注意到$C1={\mu }^{\prime }1$ ，因此若${\mu }^{\prime }=0$ 则$C$ 有非零核向量$1$ 与$C$ 可逆矛盾，故${\mu }^{\prime }\ne 0$ 。于是$C\left(\frac{1}{{\mu }^{\prime }}1\right)=1$ ，从而

$y=C\left(x+\frac{H\left(T\right)}{{\mu }^{\prime }}1\right).$

令$z:=C^{-1}y$ ，则$z=x+\frac{H\left(T\right)}{{\mu }^{\prime }}1$ 。接下来取$\omega$ 的加权和：

${\displaystyle \sum _{i=0}^{n-1}{\omega }_i}{z}_i={\displaystyle \sum _{i=0}^{n-1}{\omega }_i}{x}_i+\frac{H\left(T\right)}{{\mu }^{\prime }}{\displaystyle \sum _{i=0}^{n-1}{\omega }_i}=T+\frac{H\left(T\right)}{{\mu }^{\prime }}{\displaystyle \sum _{i=0}^{n-1}{\omega }_i}.$

下面我们说明${\displaystyle \sum _{i=0}^{n-1}{\omega }_i}=0$ 在两种情形下都成立：

若${\omega }_i=1$ ，则${\displaystyle \sum _{i=0}^{n-1}{\omega }_i}=n\equiv 0\left(\mathrm{mod}p\right)$ 。

若${\omega }_i={\lambda }^i$ 且$\lambda \ne 1$ 、${\lambda }^n=1$ ，则${\displaystyle \sum _{i=0}^{n-1}{\omega }_i}={\displaystyle \sum _{i=0}^{n-1}{\lambda }^i}=0$ 。

因此总有${\displaystyle \sum _{i=0}^{n-1}{\omega }_i}{z}_i=T$ 。于是$H\left(T\right)=H\left({\displaystyle \sum _{i=0}^{n-1}{\omega }_i}{z}_i\right)$ 可由$z$ 唯一确定，并且

$x=z-\frac{1}{{\mu }^{\prime }}H\left({\displaystyle \sum _{i=0}^{n-1}{\omega }_i}{z}_i\right)1.$

这给出了从$y$ 唯一恢复$x$ 的显式逆映射，从而$S_F$ 是可逆的。证毕。

注释1 注意到，由定理1的条件2，我们可以取$n$ 为偶数，$\lambda =-1$ 为${\mathbb{F}}_p$ 上的$n$ 次单位根，此时$H:{\mathbb{F}}_p\to {\mathbb{F}}_p$ 为偶函数，由此可见文献[8]中的命题1为定理1的一个特殊情况。

推论1 设$p$ 为素数，$\lambda \in {\mathbb{F}}_p\backslash \left\{0\right\}$ ，$H:{\mathbb{F}}_p\to {\mathbb{F}}_p$ 为二次多项式函数$H\left(t\right)=a{t}^2+bt+c$ ，且$a\ne 0$ 。

若对任意$t\in {\mathbb{F}}_p$ 都有$H\left(\lambda t\right)=H\left(t\right)$ ，则必有${\lambda }^2=1$ 。并且若$\lambda =-1$ ，则必有$b=0$ (即$H\left(t\right)=a{t}^2+c$ )。

证明 由$H\left(\lambda t\right)=a{\left(\lambda t\right)}^2+b\left(\lambda t\right)+c=a{\lambda }^2{t}^2+b\lambda t+c$ 与$H\left(t\right)=a{t}^2+bt+c$ 对所有$t$ 恒等，得

$a\left({\lambda }^2-1\right)t^2+b\left(\lambda -1\right)t=0\left(\forall t\in {\mathbb{F}}_p\right).$

作为多项式恒等式，其系数必须为零，故$a\left({\lambda }^2-1\right)=0$ ，$b\left(\lambda -1\right)=0$ 。由$a\ne 0$ 得${\lambda }^2=1$ 。此外若$\lambda =-1\ne 1$ ，则由$b\left(\lambda -1\right)=0$ 推出$b=0$ 。证毕。

由推论1可知，当局部映射为二次函数时，非平凡的单位根的取值只能是$\lambda =-1$ 。

类似推论1的证明，可得如下结论。

推论2 设$p$ 为素数且$p>3$ ，$\lambda \in {\mathbb{F}}_p$ ，并令$H\left(t\right)=a_s{t}^s+a_{s-1}{t}^{s-1}+\cdots +a_0$ 为任意$s$ 次多项式且$a_s\ne 0$ 。若对任意$t\in {\mathbb{F}}_p$ 都有$H\left(\lambda t\right)=H\left(t\right)$ ，则必有

${\lambda }^s=1,a_{s-1}\left({\lambda }^{s-1}-1\right)=0,\cdots ,a_1\left(\lambda -1\right)=0.$

特别地，当$\lambda$ 为本原$s$ 次单位根时，必有$a_{s-1}=\cdots =a_1=0$ ，从而$H\left(t\right)=a_s{t}^s+a_0$ 。

定理2 设$p\ge 2$ 为素数，令$n=m\ge 2$ 。设，使得循环矩阵

可逆。取$\gamma \in {\mathbb{F}}_p\backslash \left\{0\right\}$ ，整数$r$ 满足$2\le r\le n$ ，并取满足${\displaystyle \sum _{j=0}^{r-1}{a}_j}=0$ 。令$H:{\mathbb{F}}_p\to {\mathbb{F}}_p$ 为任意函数，并定义局部映射为

$F\left(x_0,\cdots ,x_{n-1}\right)={\displaystyle \sum _{i=0}^{n-1}{\mu }_i}{x}_i+\gamma {\displaystyle \sum _{i=0}^{n-1}H}\left({\displaystyle \sum _{j=0}^{r-1}{a}_j}{x}_{i+j}\right),$

其中下标均按$n$ 取模。则由$F$ 在上诱导的移位不变函数$S_F$ 是可逆的。

证明令，并令$y=S_F\left(x\right)={\left(y_0,\cdots ,y_{n-1}\right)}^{\text{T}}$ 。记

$g\left(x\right):={\displaystyle \sum _{i=0}^{n-1}H}\left({\displaystyle \sum _{j=0}^{r-1}{a}_j}{x}_{i+j}\right)\in {\mathbb{F}}_p,$

则有。令$\sigma$ 表示循环移位算子，即${\left({\sigma }^{k}x\right)}_t=x_{t+k}$ (下标按$n$ 取模)。则对任意$k$ ，

$g\left({\sigma }^{k}x\right)={\displaystyle \sum _{i=0}^{n-1}H}\left({\displaystyle \sum _{j=0}^{r-1}{a}_j}{\left({\sigma }^{k}x\right)}_{i+j}\right)={\displaystyle \sum _{i=0}^{n-1}H}\left({\displaystyle \sum _{j=0}^{r-1}{a}_j}{x}_{i+j+k}\right).$

令$i^{\prime }=i+k$ ，由于外层对$i$ 的求和是循环的，可得

$g\left({\sigma }^{k}x\right)={\displaystyle \sum _{i^{\prime }=0}^{n-1}H}\left({\displaystyle \sum _{j=0}^{r-1}{a}_j}{x}_{i^{\prime }+j}\right)=g\left(x\right).$

因此由定义1，第$k$ 个输出坐标为

令，则可写成

记${\mu }^{\prime }:={\displaystyle \sum _{i=0}^{n-1}{\mu }_i}\in {\mathbb{F}}_p$ 。注意到$C1={\mu }^{\prime }1$ 。由$C$ 是可逆矩阵，所以${\mu }^{\prime }\ne 0$ 。于是$C^{-1}1=\frac{1}{{\mu }^{\prime }}1$ 。令$z:=C^{-1}y$ ，则

记$\alpha :=\frac{\gamma }{{\mu }^{\prime }}g\left(x\right)$ ，则$z=x+\alpha 1$ 。由${\displaystyle \sum _{j=0}^{r-1}{a}_j}=0$ ，对任意$i$ 有

${\displaystyle \sum _{j=0}^{r-1}{a}_j}{z}_{i+j}={\displaystyle \sum _{j=0}^{r-1}{a}_j}\left(x_{i+j}+\alpha \right)={\displaystyle \sum _{j=0}^{r-1}{a}_j}{x}_{i+j}+\alpha {\displaystyle \sum _{j=0}^{r-1}{a}_j}={\displaystyle \sum _{j=0}^{r-1}{a}_j}{x}_{i+j}.$

因此

$g\left(z\right)={\displaystyle \sum _{i=0}^{n-1}H}\left({\displaystyle \sum _{j=0}^{r-1}{a}_j}{z}_{i+j}\right)={\displaystyle \sum _{i=0}^{n-1}H}\left({\displaystyle \sum _{j=0}^{r-1}{a}_j}{x}_{i+j}\right)=g\left(x\right).$

从而$\alpha =\frac{\gamma }{{\mu }^{\prime }}g\left(x\right)=\frac{\gamma }{{\mu }^{\prime }}g\left(z\right)$ 可由$z$ 唯一确定，并且$x=z-\frac{\gamma }{{\mu }^{\prime }}g\left(z\right)1$ 。这给出了从任意$y$ 唯一恢复$x$ 的逆映射，因此$S_F$ 可逆。证毕。

注释2 注意到当$r=2$ ，$a=\left(1,-1\right)$ ，可得到

$F\left(x\right)={\displaystyle \sum _{i=0}^{n-1}{\mu }_i}{x}_i+\gamma {\displaystyle \sum _{i=0}^{n-1}H}\left(x_i-x_{i+1}\right),$

即文献[8]中命题2给出的局部映射。我们可以取更一般的形式，当$r=4$ ，$a=\left(1,-1,1,-1\right)$ ，可得到

$F\left(x\right)={\displaystyle \sum _{i=0}^{n-1}{\mu }_i}{x}_i+\gamma {\displaystyle \sum _{i=0}^{n-1}H}\left(x_i-x_{i+1}+x_{i+2}-x_{i+3}\right).$

需要强调的是，本文关注的对象是单轮非线性层，其设计目标侧重于在大素数有限域上实现低乘法复杂度与可逆性。因为在MPC/FHE/Zk这类算数化场景中，系统开销几乎由乘法门数主导的，因此乘法复杂度决定了非线性层在证明规模、约束数、运行时间上的成本上限。下面我们给出定理1和定理2两种移位不变函数的乘法复杂度(只统计非线性乘法门数目$M(\cdot )$ )。对于定理1中的可逆移位不变函数，由其构造可知正向计算仅需要对$H$ 做一次求值。于是

$M\left(S_F\right)=M\left(H\right)$ ，$M\left(S_F^{-1}\right)=M\left(H\right)$

其中$M\left(H\right)$ 为在${\mathbb{F}}_p$ 上计算一次$H$ 所需的乘法门数。特别地，若取$H\left(t\right)=a{t}^2+b$ ，则$M\left(H\right)=1$ ；若取$H\left(t\right)=a{t}^3+b$ ，则可按$t^2$ 与$t^3=t^2\cdot t$ 计算，得到$M\left(H\right)=2$ 。并且如果$C:=\text{circ}\left(1,0,\cdots ,0\right)$ 且$H$ 为2次多项式计算$S_F$ 仅需1次${\mathbb{F}}_p$ 乘法。对于定理2，同理可以得到

$M\left(S_F\right)=nM\left(H\right)$ ，$M\left(S_F^{-1}\right)=nM\left(H\right)$

乘法复杂度与状态长度$n$ 线性相关。

因此定理1的乘法复杂度与$n$ 无关，而定理2的乘法复杂度随$n$ 线性增长。最后我们需要声明的是低乘法复杂度是以更强的代数结构为代价获取的，因此这些构造更适合作为多轮结构中低成本模块，而非单独使用的安全置换。

4. 结论

基于文献[8]中对Lai-Massey构造的推广，本文进一步给出了一类更一般的移位不变函数的构造，从而为密码算法提供更为丰富的移位不变函数。

NOTES

^*第一作者。

^#通讯作者。