International Association
for Cryptologic Research

Post-quantum signature schemes based on the MPC-in-the-Head (MPCitH) paradigm are recently attracting significant attention as their security solely depends on the one-wayness of the underlying primitive, providing diversity for the hardness assumption in post-quantum cryptography. Kim et al. proposed AIM as an MPCitH-friendly one-way function characterized by large algebraic S-boxes and parallel design, which lead to short signature size (CCS 2023).

Recently, Liu et al. proposed a fast exhaustive search attack on AIM (ePrint 2023), which degrades the security of AIM by up to 13 bits. While communicating with the authors, they pointed out another possible vulnerability on AIM. In this paper, we propose AIM2 which mitigates all the vulnerabilities, and analyze its security against algebraic attacks.