Fast Exhaustive Search on AIM2

Debnath, Arka; Mahzoun, Mohammad

doi:10.22042/isecure.2026.243623

Fast Exhaustive Search on AIM2

Articles in Press

Document Type : Research Article

Authors

Arka Debnath ¹

Mohammad Mahzoun ²

¹ Department of Electrical Engineering, KU Leuven, Leuven, Belgium

² Mohammad Mahzoun, 3MI Labs, Leuven, Belgium

10.22042/isecure.2026.243623

Abstract

This paper describes a fast exhaustive search preimage attack on AIM2, an improved version of the one-way function AIM, proposed to address algebraic vulnerabilities found in its predecessor. Our attack transforms the polynomial system describing AIM2 over F2λ to a boolean polynomial system over F2, allowing for an exhaustive search by guessing input bits and solving a resulting linear system. Solving the whole system is not necessary for most incorrect guesses, and use of Gray code helps optimizing the iteration over all possible guesses. Our results show that the complexity of exhaustive search on AIM2, especially AIM2-I and AIM2-III is lower than previously estimated, though still higher than that of AES.

Keywords

AIM2

Cryptanalysis

Fast Exhaustive Search

[1] Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai. Zero-knowledge from secure multiparty computation. In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC ’07, page 21–30, New York, NY, USA, 2007. Association for Computing Machinery. ISBN 9781595936318. . URL https://doi.org/10.1145/1250790.1250794.

[2] Seongkwang Kim, Jincheol Ha, Mincheol Son, ByeongHak Lee, Dukjae Moon, Joohee Lee, Sangyub Lee, Jihoon Kwon, Jihoon Cho, Hyojin Yoon, and Jooyoung Lee. AIM: symmetric primitive for shorter signatures with stronger security. In Weizhi Meng, Christian Damsgaard Jensen, Cas Cremers, and Engin Kirda, editors, Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, CCS 2023, Copenhagen, Denmark, November 2630, 2023, pages 401–415. ACM, 2023. . URL https://doi.org/10.1145/3576915.3616579.

[3] Daniel Kales and Greg Zaverucha. Efficient lifting for shorter zero-knowledge proofs and postquantum signatures. Cryptology ePrint Archive, Paper 2022/588, 2022. URL https://eprint. iacr.org/2022/588.

[4] Kaiyi Zhang, Qingju Wang, Yu Yu, Chun Guo, and Hongrui Cui. Algebraic attacks on roundreduced rain and full aim-iii. In Jian Guo and Ron Steinfeld, editors, Advances in Cryptology – ASIACRYPT 2023, pages 285–310, Singapore, 2023. Springer Nature Singapore. ISBN 978-98199-8727-6.

[5] Fukang Liu, Mohammad Mahzoun, Morten Øygarden, and Willi Meier. Algebraic attacks on rain and aim using equivalent representations. IACR Transactions on Symmetric Cryptology, 2023(4): 166–186, December 2023. ISSN 2519-173X.

[6] Seongkwang Kim, Jincheol Ha, Mincheol Son, and Byeonghak Lee. Efficacy and mitigation of the cryptanalysis on AIM. Cryptology ePrint Archive, Paper 2023/1474, 2023. URL https://eprint. iacr.org/2023/1474.

[7] C. Bouillaguet, H.-C. Chen, C.-M. Cheng, T. Chou, R. F. Niederhagen, A. Shamir, and B.Y. Yang. Fast exhaustive search for polynomial systems in F2. In Proceedings of the 12th International Workshop on Cryptographic Hardware and Embedded Systems (CHES 2010), volume 6225 of Lecture Notes in Computer Science, pages 203– 218. Springer, 2010.

[8] Markku-Juhani O. Saarinen. Round 1 (additional signatures) official comment: Aimer, September 2023. URL https://groups.google.com/a/ list.nist.gov/g/pqc-forum/c/BI2ilXblNy0. Google Groups post in the PQC-forum.