Paper 2023/1474
Efficacy and Mitigation of the Cryptanalysis on AIM
, Samsung SDS, Korea Advanced Institute of Science and Technology, Korea Advanced Institute of Science and Technology, Samsung SDSAbstract
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
-
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},
note = {\url{https://eprint.iacr.org/2023/1474}},
url = {https://eprint.iacr.org/2023/1474}
}
