Paper 2023/1133

Algebraic Attacks on RAIN and AIM Using Equivalent Representations

Fukang Liu, Tokyo Institute of Technology
Mohammad Mahzoun, Eindhoven University of Technology
Morten Øygarden, Simula UiB
Willi Meier, FHNW

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^{111}/2^{170}/2^{224}$ 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^{265}$ bit operations, which are equivalent to about $2^{115}/2^{178}/2^{241}$ calls of the underlying primitives. In particular, our analysis indicates that AIM does not reach the required security levels by the NIST competition.

Note: This is the version accepted by FSE 2024.

Available format(s)
Attacks and cryptanalysis
Publication info
Published by the IACR in TOSC 2024
RAINAIMequivalent representationoverdefined systemalgebraic attack
Contact author(s)
liufukangs @ gmail com
m mahzoun @ tue nl
morten oygarden @ simula no
willimeier48 @ gmail com
2023-11-22: last of 4 revisions
2023-07-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Fukang Liu and Mohammad Mahzoun and Morten Øygarden and Willi Meier},
      title = {Algebraic Attacks on RAIN and AIM Using Equivalent Representations},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1133},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.