International Association for Cryptologic Research

International Association
for Cryptologic Research


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

Kaiyi Zhang , Shanghai Jiao Tong University
Qingju Wang , Telecom Paris, Institut Polytechnique de Paris
Yu Yu , Shanghai Jiao Tong University
Chun Guo , Shandong University
Hongrui Cui , Shanghai Jiao Tong University
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2023
Abstract: 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.
  title={Algebraic Attacks on Round-Reduced Rain and Full AIM-III},
  author={Kaiyi Zhang and Qingju Wang and Yu Yu and Chun Guo and Hongrui Cui},