Paper 2025/937 Original: eprint.iacr.org/2025/937 ↗
Attacking Poseidon via Graeffe-Based Root-Finding over NTT-Friendly Fields
Abstract
This paper explores the algebraic structure of the Poseidon and Poseidon2 permutations over NTT-friendly finite fields, with a focus on preimage recovery via root-finding techniques. We introduce an algorithm for efficiently identifying single roots of high-degree univariate polynomials that emerge from these constructions, based on the Graeffe transform and the tangent Graeffe method. Our approach is evaluated on reduced-round bounty instances of these permutations at various security levels, as proposed by the Ethereum Foundation, demonstrating practical effectiveness. These results yield new insights into the security of permutation-based cryptographic primitives instantiated over NTT-friendly prime fields.
Metadata
- Available format(s)
PDF- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- History
- 2025-05-23: last updated
- 2025-05-23: published
- Short URL
- https://ia.cr/2025/937
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2025/937,
author = {Antonio Sanso and Giuseppe Vitto},
title = {Attacking Poseidon via Graeffe-Based Root-Finding over NTT-Friendly Fields},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/937},
year = {2025},
url = {https://eprint.iacr.org/2025/937}
}