Efficacy and Mitigation of the Cryptanalysis on AIM

Seongkwang Kim; Jincheol Ha; Mincheol Son; Byeonghak Lee

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 , 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, 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 , 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-quantum digital signature MPC-in-the-Head algebraic cryptanalysis Grö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: 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}
}