Paper 2023/1397

Algebraic Attacks on Round-Reduced RAIN and Full AIM-III

Kaiyi Zhang, Shanghai Jiao Tong University
Qingju Wang, Telecom Paris, Institut Polytechnique de Paris, France
Yu Yu, Shanghai Jiao Tong University
Chun Guo, Shandong University
Hongrui Cui, Shanghai Jiao Tong University

Picnic is a NIST PQC Round 3 Alternate signature candidate that builds upon symmetric primitives following the MPC-in-the-head paradigm. Recently, researchers have been exploring more secure/efficient signature schemes from conservative one-way functions based on AES, or new low complexity one-way functions like Rain (CCS 2022) and AIM (CCS 2023). The signature schemes based on Rain and AIM are currently the most efficient among MPC-in-the-head-based schemes, making them promising post-quantum digital signature candidates. However, the exact hardness of these new one-way functions deserves further study and scrutiny. This work presents algebraic attacks on RAIN and AIM for certain instances, where one-round Rain can be compromised in $2^{n/2}$ for security parameter $n\in \{128,192,256\}$, and two-round Rain can be broken in $2^{120.3}$, $2^{180.4}$, and $2^{243.1}$ encryptions, respectively. Additionally, we demonstrate an attack on AIM-III (which aims at 192-bit security) with a complexity of $2^{186.5}$ encryptions. These attacks exploit the algebraic structure of the power function over fields with characteristic 2, which provides potential insights into the algebraic structures of some symmetric primitives and thus might be of independent interest.

Available format(s)
Attacks and cryptanalysis
Publication info
Published by the IACR in ASIACRYPT 2023
Algebraic AttacksPower MappingArithmetization Oriented PrimitivesRAINAIM
Contact author(s)
kzoacn @ sjtu edu cn
qingju wang @ telecom-paris fr
yyuu @ sjtu edu cn
chun guo sc @ gmail com
rickfreeman @ sjtu edu cn
2023-09-21: approved
2023-09-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Kaiyi Zhang and Qingju Wang and Yu Yu and Chun Guo and Hongrui Cui},
      title = {Algebraic Attacks on Round-Reduced {RAIN} and Full {AIM}-{III}},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1397},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.