Algebraic Attacks on RAIN and AIM Using Equivalent Representations

Abstract

Designing novel symmetric-key primitives for advanced protocols like secure multiparty computation (MPC), fully homomorphic encryption (FHE) and zero-knowledge proof systems (ZK), has been an important research topic in recent years. Many such existing primitives adopt quite different design strategies from conventional block ciphers. Notable features include that many of these ciphers are defined over a large finite field, and that a power map is commonly used to construct the nonlinear component due to its efficiency in these applications as well as its strong resistance against the differential and linear cryptanalysis. In this paper, we target the MPC-friendly ciphers AIM and RAIN used for the post-quantum signature schemes AIMer (CCS 2023 and NIST PQC Round 1 Additional Signatures) and Rainier (CCS 2022), respectively. Specifically, we can find equivalent representations of 2-round RAIN and full-round AIM, respectively, which make them vulnerable to either the polynomial method, or the crossbred algorithm, or the fast exhaustive search attack. Consequently, we can break 2-round RAIN with the 128/192/256-bit key in only 2¹¹¹/2¹⁷⁰/2²²⁵ bit operations. For full-round AIM with the 128/192/256-bit key, we could break them in 2^136.2/2^200.7/2²⁶⁵ bit operations, which are equivalent to about 2¹¹⁵/2¹⁷⁸/2²⁴¹ calls of the underlying primitives. In particular, our analysis indicates that AIM does not reach the required security levels by the NIST competition.