Paper 2023/1474

Efficacy and Mitigation of the Cryptanalysis on AIM

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

Recent advancements in post-quantum cryptography have highlighted signature schemes based on the MPC-in-the-Head (MPCitH) framework due to their reliance only on the one-way function of the underlying primitive. This reliance offers a diverse set of assumptions regarding the difficulty of post-quantum cryptographic problems. In this context, Kim et al. proposed $\mathsf{AIM}$, an MPCitH-compatible one-way function. This function is distinguished by its large algebraic S-boxes and parallel architecture, contributing to the reduced size of signatures, as presented at CCS 2023. However, $\mathsf{AIM}$ has faced several cryptanalytic challenges, which have potentially weakened its security by up to 15 bits. This paper provides a comprehensive overview of these cryptanalytic methods and proposes $\mathsf{AIM2}$, an enhanced version that addresses these identified vulnerabilities. We conduct an extensive analysis of its resilience to algebraic attacks and detail the modifications in its efficiency.

Note: We corrected some details in the security analysis.

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
2024-02-28: last of 3 revisions
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 = {Efficacy and Mitigation of the Cryptanalysis on AIM},
      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.