STARK-Based Signatures from the RPO Permutation
IACR Communications in Cryptology · 03.08.2026 · 3 (2)
DOI: 10.62056/absgbn-3y ↗Kurz gefasst
Fachartikel in der Zeitschrift IACR Communications in Cryptology, online erschienen am 03.08.2026. Verfasst von Shahla Atapoor und 2 weiteren Autor:innen. Die Arbeit nennt 31 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Cybersecurity Research Program.
Abstract (Originalsprache)
This work describes a digital signature scheme constructed from a zero-knowledge proof of knowledge of a pre-image of the Rescue Prime Optimized (RPO) permutation. The proof of knowledge is instantiated using the DEEP-ALI interactive oracle proof and made non-interactive via the Ben-Sasson–Chiesa–Spooner (BCS) transformation in the random oracle model. The resulting construction yields a signature scheme with transparent setup. Our design is motivated by recursive zero-knowledge applications, in which signature verification must itself be efficiently provable inside larger proof systems. To this end, the choice of the RPO permutation, the use of a simple algebraic intermediate representation (AIR), and working over the Goldilocks field are made with the goal of enabling efficient recursive verification and aggregation. The implementation of the scheme computes signatures in 4.6–7.2 ms and verifies them in 0.46–0.52 ms when the BCS transform is implemented with Blake3. When the BCS transform is instead instantiated with the RPO permutation itself, the configuration required when signature verification is to be proven recursively inside a proof system, signing takes 20.9–30.4 ms with Metal acceleration and 59.2–229.2 ms on CPU, while verification takes 5.09–5.79 ms. We validate the recursion-friendliness claim end to end by proving one signature verification inside the Miden zkVM and reporting the recursive prover time and proof size. These speeds are obtained with parameters achieving 113 or 122 bits of average-case security, depending on the chosen preset, against adversaries that can obtain up to 2 64 signatures.
Förderung
- Cybersecurity Research Program
Zitieren
APA
Atapoor, S., Guilhem, C. D. S., & Kindi, A. (2026). STARK-Based Signatures from the RPO Permutation. IACR Communications in Cryptology, 3(2). https://doi.org/10.62056/absgbn-3y
Vancouver
Atapoor S, Guilhem CDS, Kindi A. STARK-Based Signatures from the RPO Permutation. IACR Communications in Cryptology. 2026;3(2). doi:10.62056/absgbn-3y
BibTeX
@article{Atapoor2026,
author = {Atapoor, Shahla and Guilhem, Cyprien de Saint and Kindi, Al},
title = {STARK-Based Signatures from the RPO Permutation},
journal = {IACR Communications in Cryptology},
year = {2026},
volume = {3},
number = {2},
doi = {10.62056/absgbn-3y}
}
EUVIMED