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
Abstract

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.

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
2023-11-26: revised
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 = {Mitigation on the AIM Cryptanalysis},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1474},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/1474}},
      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.