Paper 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.
- Keywords
- Poseidon · Poseidon2CryptanalysisRoot-findingGraeffeInterpolationCICOZero-KnowledgeHash Break
- Contact author(s)
-
antonio sanso @ ethereum org
giuseppe @ zircuit com - History
- 2025-05-23: approved
- 2025-05-23: received
- See all versions
- Short URL
- https://ia.cr/2025/937
- License
-
CC BY
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}
}
