Paper 2023/1474
Mitigation on the AIM Cryptanalysis
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
-
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} }