Baofeng Wu
State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China; State Key Laboratory of Cryptology, Beijing, China; School of Cybersecurity, University of Chinese Academy of Sciences, Beijing, China

Wen Kong
State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China; School of Cybersecurity, University of Chinese Academy of Sciences, Beijing, China

Dewei Kong
State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China; School of Cybersecurity, University of Chinese Academy of Sciences, Beijing, China

Hailun Yan
School of Cryptology, University of Chinese Academy of Sciences, China

Keywords: Arithmetization-oriented symmetric cipher, Rotational-add diffusion layer, MDS matrix, Circulant matrix, Determinant

Abstract

We introduce rotational-add diffusion layers aimed at the design of arithmetization-oriented symmetric ciphers, such as fully homomorphic encryption friendly ciphers. This generalizes rotational-XOR diffusion layers by working over finite fields of arbitrary prime order and enabling implementations that use only rotations together with modular additions and subtractions. The main advantage in this setting is that scalar multiplication costs are reduced because the relevant scalars are only plus or minus one. We investigate characterization and construction of the lightest rotational-add diffusion layers that are maximum distance separable, focusing on the case n = 4. We show that the minimum achievable total size of rotation offsets is 5 under the MDS constraint, specify a large class of such layers with 5 rotations, and examine all possible sign patterns for the scalars. In four cases we derive computationally tractable necessary and sufficient conditions for the MDS property, which enable explicit characterization of suitable primes for given parameters. Leveraging these results, we construct three distinct families of rotational-add MDS diffusion layers for arithmetization-oriented ciphers. To our knowledge, this is the first systematic theoretical characterization of rotational-add MDS diffusion layers together with explicit constructions.