Paper 2023/1474

Mitigation on the AIM Cryptanalysis

Seongkwang Kim, Samsung SDS
Jincheol Ha, Korea Advanced Institute of Science and Technology
Mincheol Son, Korea Advanced Institute of Science and Technology
Byeonghak Lee, Samsung SDS

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.

Note: Change constants used in the AIM2's constant addition.

Available format(s)
Secret-key cryptography
Publication info
post-quantumdigital signatureMPC-in-the-Headalgebraic cryptanalysisGröbner basis
Contact author(s)
sk39 kim @ samsung com
smilecjf @ kaist ac kr
encrypted def @ kaist ac kr
byghak lee @ samsung com
2023-11-26: revised
2023-09-25: received
See all versions
Short URL
Creative Commons Attribution


      author = {Seongkwang Kim and Jincheol Ha and Mincheol Son and Byeonghak Lee},
      title = {Mitigation on the AIM Cryptanalysis},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1474},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.