@inproceedings{44106e26a4e640aa82b21e68e5511b2d,
title = "Programming Equation Systems of Arithmetization-Oriented Primitives with Constraints",
abstract = "Arithmetization-Oriented (AO) cryptographic algorithms operate on large finite fields. The most threatening attack on such designs is the Gr{\"o}bner basis attack, which solves the equation system encoded from the cryptanalysis problem. However, encoding a primitive as a system of equations is not unique, and finding the optimal one with low solving complexity is a formidable challenge. This paper presents an automated tool that transforms the problem into a Mixed-Integer Quadratic Constraint Programming (MIQCP) model. By employing integer variables and constraints, the tool tracks degree propagation and determines strategic variable introduction points. The optimal MIQCP solution yields the most efficient solving complexity, offering the lowest computational burden for the Gr{\"o}bner basis attack. We construct comprehensive models for the Griffin, Anemoi, and Ciminion permutations. Our experiments demonstrate reduced Gr{\"o}bner basis attack complexity, surpassing the designers{\textquoteright} bounds. This versatile tool can be leveraged to accurately evaluate the security of new AO designs against Gr{\"o}bner basis attacks.",
keywords = "Automatic cryptanalysis, CICO, Griffin, Gr{\"o}bner basis, MIQCP",
author = "Kexin Qiao and Mengyu Chang and Junjie Cheng and Changhai Ou and An Wang and Liehuang Zhu",
note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2026.; 21st International Conference on Information Security and Cryptology, Inscrypt 2025 ; Conference date: 19-10-2025 Through 22-10-2025",
year = "2026",
doi = "10.1007/978-981-95-6203-9\_5",
language = "English",
isbn = "9789819562022",
series = "Lecture Notes in Computer Science",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "85--106",
editor = "Rongmao Chen and Deng, \{Robert H.\} and Moti Yung",
booktitle = "Information Security and Cryptology - 21st International Conference, Inscrypt 2025, Revised Selected Papers",
address = "Germany",
}