迈向降低II型广义Feistel网络中的非线性

### 迈向降低II型广义Feistel网络中的非线性 在当今的密码学领域，随着安全多方计算（MPC）、全同态加密（FHE）和零知识证明（ZKP）等新应用的兴起，对能够最小化非线性操作的对称加密方案的需求日益凸显。线性操作成本相对较低，因此如何利用线性操作来减少非线性操作成为了研究的热点。本文将深入探讨II型广义Feistel网络（Type-II GFNs），并介绍一种新的方案——广义扩展广义Feistel网络（GEGFN），旨在降低非线性操作的同时保证安全性。 #### 1. 背景知识 - **Feistel网络与广义Feistel网络**：Feistel网络是分组密码的主要结构之一。经典的Feistel网络通过迭代Feistel置换$\Psi_F (A, B) := (B, A \oplus F(B))$进行操作，其中$F$是一个保持域不变的块函数。广义Feistel网络（GFN）是经典Feistel网络的推广形式，II型GFN是其中一种流行的版本。在II型GFN中，单轮使用块函数$F$将输入$(m_1, m_1, ..., m_w)$映射到$(c_1, c_2, ..., c_w) = [m_2, m_3 \oplus F(m_4), m_4, m_5 \oplus F(m_6), ..., m_w, m_1 \oplus F(m_2)]$，这相当于对每两个块应用Feistel置换，然后对字块进行（左）循环移位。 - **II型GFN的优缺点**：II型GFN具有许多理想的实现特性，特别是它是无逆的，即可以从具有小域的不可逆块函数构建可逆分组密码，这降低了解密的实现成本。然而，其缺点是扩散速度慢（当$w$较大时），需要许多轮才能确保安全性。 - **其他相关结构**：为了改进II型GFN的扩散问题，一系列工作研究了用更复杂的（线性）置换替换块循环移位。同时，受新应用的驱动，许多工作致力于研究有利于安全MPC等应用的对称密码结构的构造策略。例如，部分SP网络（P - SPN）、HADES设计等。 #### 2. 研究动机与目标 新应用如MPC、FHE和ZKP对对称加密方案提出了最小化非线性操作的要求。由于SPN和P - SPN使用了更强的扩散层，它们的扩散性能比II型GFN好得多。从可证明的CCA安全结果也可以看出，最佳的II型GFN变体需要10轮和$5w$次块函数应用，而SPN和P - SPN分别只需要3轮和5轮，以及$3w$和$5w/2$次块函数应用。因此，自然会想到是否可以通过利用相对便宜的线性操作（如SPN和P - SPN中的强扩散层）来减少非线性操作。 #### 3. 广义扩展广义Feistel网络（GEGFN） - **构造思路**：为了研究II型GFN中非线性的最小化，我们将（扩展）GFN进行了推广，用P - SPN中的更强线性层替换GFN中的按位洗牌，并在每一轮引入密钥。这种方案被称为广义扩展广义Feistel网络（GEGFN）。 - **与P - SPN的关系**：从另一个角度看，GEGFN与所谓的速率为1/2的部分置换网络（P - SPN）非常相似。我们也可以通过用II型GFN的非线性层替换P - SPN的非线性层来得到GEGFN。GEGFN结合了P - SPN的强扩散性和II型GFN的无逆性。 - **GEGFN的计算过程**： - 设$u_1 := k_0 + x$。 - 对于$i = 1, ..., \lambda - 1$： - $v_i := PGF_{f_i}(u_i)$，其中$PGF_{f_i}(u_i) = [u_i[1] + f_i(u_i[2])] \parallel u_i[2] \parallel ... \parallel [u_i[w - 1] + f_i(u_i[w])] \parallel u_i[w]$。 - $u_{i + 1} = k_i + T_i \cdot v_i$。 - $v_{\lambda} := PGF_{f_{\lambda}}(u_{\lambda})$。 - $u_{\lambda + 1} = k_{\lambda} + v_{\lambda}$。 - 输出$u_{\lambda + 1}$。 #### 4. 不同结构的比较 | 结构 | 轮数 | 乘法复杂度（MC） | 乘法深度（AND Depth） | 无逆性？ | | ---- | ---- | ---- | ---- | ---- | | 最优II型GFN | $2\lambda(w)$ | $w\lambda(w)$ | $2\lambda(w)$ | ✓ | | 扩展GFN | 10 | $5w$ | 10 | ✓ | | 线性SPN | 3 | $3w$ | 3 | ✗ | | HADES | 4 |