Paper 2025/1544 Original: eprint.iacr.org/2025/1544 ↗

MDS Diffusion Layers for Arithmetization-Oriented Symmetric Ciphers: The Rotational-Add Construction

Abstract

We introduce the rotational-add diffusion layers aimed for applications in the design of arithmetization-oriented (AO) symmetric ciphers, such as fully homomorphic encryption (FHE)-friendly symmetric ciphers. This generalizes the rotational-XOR diffusion layers which have been utilized in the design of many important conventional symmetric ciphers like SHA-256, SM4, ZUC and Ascon. A rotational-add diffusion layer is defined over the finite field $\mathbb{F}_{p}$ for arbitrary prime $p$, enabling implementations using only rotations and modular additions/subtractions. The advantage of using such diffusion layers in AO ciphers is that, the costs of scalar multiplications can be reduced since the appearing scalars include only $\pm 1$, thus the total costs depend on sizes of the rotation offsets. In this paper, we investigate characterizations and constructions of lightest rotational-add diffusion layers over $(\mathbb{F}_{p}^{m})^{n}$ that are maximum distance separable (MDS) with a focus on the case $n=4$. It turns out that the minimum achievable size of the rotation offsets is 5 subject to the MDS property constraint. We specify a large class of rotational-add diffusion layers with 5 rotations and traverse all possible patterns of appearance of the scalars $\pm1$. In four cases we can derive computationally tractable necessary and sufficient conditions for the rotational-add diffusion layers to attain the MDS property. These conditions enable explicit characterization of suitable primes $p$ for given parameters. Leveraging these results, we construct three distinct families of rotational-add MDS diffusion layers applicable to AO ciphers. Although a rotational-add diffusion layer with 7 rotations and only additions has already been used in the design of the FHE-friendly block cipher YuX recently, to our knowledge, our work presents the first systematic theoretical characterization of rotational-add MDS diffusion layers and provides explicit constructions of them.