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
Abstract

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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint.
Keywords
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
History
2024-02-28: last of 3 revisions
2023-09-25: received
See all versions
Short URL
https://ia.cr/2023/1474
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1474,
      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},
      url = {https://eprint.iacr.org/2023/1474}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.