Paper 2024/250
Exploring the Six Worlds of Gröbner Basis Cryptanalysis: Application to Anemoi
Abstract
Gröbner basis cryptanalysis of hash functions and ciphers, and their underlying permutations, has seen renewed interest recently. Anemoi (Crypto'23) is a permutation-based hash function that is arithmetization-friendly, i.e., efficient for a variety of arithmetizations used in zero-knowledge proofs. In this paper, exploring both theoretical bounds as well as experimental validation, we present new complexity estimates for Gröbner basis attacks on the Anemoi permutation over prime fields. We cast our findings in what we call the six worlds of Gröbner basis cryptanalysis. As an example, keeping the same security arguments of the design, we conclude that at least $23 /45$ instead of $17 / 33$ rounds would need to be used for $128 / 256$-bit security before adding a security margin.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- Algebraic CryptanalysisArithmetization-Friendly Hash FunctionsGröbner Basis AttackAnemoiMultihomogeneous Bézout
- Contact author(s)
-
katharina koschatko @ iaik tugraz at
reinhard lueftenegger @ iaik tugraz at
christian rechberger @ iaik tugraz at - History
- 2024-02-16: approved
- 2024-02-15: received
- See all versions
- Short URL
- https://ia.cr/2024/250
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/250,
author = {Katharina Koschatko and Reinhard Lüftenegger and Christian Rechberger},
title = {Exploring the Six Worlds of Gröbner Basis Cryptanalysis: Application to Anemoi},
howpublished = {Cryptology ePrint Archive, Paper 2024/250},
year = {2024},
note = {\url{https://eprint.iacr.org/2024/250}},
url = {https://eprint.iacr.org/2024/250}
}
