In recent years a new class of symmetric-key primitives over $\mathbb{F}_p$ that are essential to Multi-Party Computation and Zero-Knowledge Proofs based protocols have emerged. Towards improving the efficiency of such primitives, a number of new block ciphers and hash functions over $\mathbb{F}_p$ were proposed. These new primitives also showed that following alternative design strategies to the classical Substitution-Permutation Network (SPN) and Feistel Networks leads to more efficient cipher and hash function designs over $\mathbb{F}_p$ specifically for large odd primes $p$. In view of these efforts, in this work we build an \emph{algebraic framework} that allows the systematic exploration of viable and efficient design strategies for constructing symmetric-key (iterative) permutations over $\mathbb{F}_p$. We first identify iterative polynomial dynamical systems over finite fields as the central building block of almost all block cipher design strategies. We propose a generalized triangular polynomial dynamical system (GTDS), and based on the GTDS we provide a generic definition of an iterative (keyed) permutation over $\mathbb{F}_p^n$. Our GTDS-based generic definition is able to describe the three most well-known design strategies, namely SPNs, Feistel networks and Lai--Massey. Consequently, the block ciphers that are constructed following these design strategies can also be instantiated from our generic definition. Moreover, we find that the recently proposed \texttt{Griffin} design, which neither follows the Feistel nor the SPN design, can be described using the generic GTDS-based definition. We also show that a new generalized Lai--Massey construction can be instantiated from the GTDS-based definition. We further provide generic analysis of the GTDS including an upper bound on the differential uniformity and the correlation.
翻译:近年来,出现了一类对于多方计算和基于零知识证明协议至关重要的$\mathbb{F}_p$对称密钥原语。为了改进这类原语的效率,提出了许多新的$\mathbb{F}_p$块密码和哈希函数。这些新的原语也表明,跟随替换-置换网络(SPN)和 Feistel 网络之外的替代设计策略,可以指导构建相对于大奇素数$p$的更有效的密码和哈希函数设计。鉴于这些努力,本文建立了一个代数框架,可以系统地探索构建$\mathbb{F}_p$上对称密钥(迭代)置换的可行且有效的设计策略。我们首先将迭代多项式动力系统作为几乎所有块密码设计策略的核心构建块。我们提出了一个广义三角形多项式动力系统(GTDS),并基于 GTDS 提供了一个关于$\mathbb{F}_p^n$的迭代(有密钥)置换的通用定义。我们基于 GTDS 提供的通用定义能够描述三个最为著名的设计策略,即SPN,Feistel网络和Lai-Massey。因此,按照这些设计策略构建的块密码也可以从我们的通用定义中实例化。此外,我们发现最近提出的 Griffin 设计既不遵循 Feistel 也不遵循 SPN设计,但其可以使用通用的 GTDS-based 定义来描述。我们还展示了一个新的广义 Lai-Massey 构造可以从 GTDS-based 定义中实例化。我们进一步提供了 GTDS 的通用分析,包括微分均匀性和相关性的上界。