Welcome to the resource topic for 2023/1397
Title:
Algebraic Attacks on Round-Reduced RAIN and Full AIM-III
Authors: Kaiyi Zhang, Qingju Wang, Yu Yu, Chun Guo, Hongrui Cui
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.
ePrint: https://eprint.iacr.org/2023/1397
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .