Paper 2024/2061
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ö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 challenge. This paper introduces an automatic tool that converts the CICO problem into a Mixed-Integer Quadratic Constraint Programming (MIQCP) model, using integer variables and constraints to track degree propagation and determine variable introduction points. The optimal MIQCP solution provides the lowest solving complexity. We build models for Griffin, Anemoi, and Ciminion permutations to cover modules comprehensively. Experiments show reduced Gröbner basis attack complexity, lower than designers’ bounds for small numbers of rounds, e.g. up to 8 rounds for Griffin.This tool can be used for security evaluation against Gröbner basis attack in new designs.
Metadata
- Available format(s)
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- Gröbner basisautomatic cryptanalysisCICOMIQCPGriffin
- Contact author(s)
-
1361587350 @ qq com
qiaokexin0327 @ 163 com
junjie cheng @ outlook com
ouchanghai @ whu ac cn
liehuangz @ bit edu cn - History
- 2024-12-23: approved
- 2024-12-23: received
- See all versions
- Short URL
- https://ia.cr/2024/2061
- License
-
CC BY-NC
BibTeX
@misc{cryptoeprint:2024/2061, author = {Mengyu Chang and Kexin Qiao and Junjie Cheng and Changhai Ou and Liehuang Zhu}, title = {Programming Equation Systems of Arithmetization-Oriented Primitives with Constraints}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/2061}, year = {2024}, url = {https://eprint.iacr.org/2024/2061} }