STARK-Based Signatures from the RPO Permutation

Shahla Atapoor; Cyprien Delpech de Saint Guilhem; Al Kindi

doi:10.62056/absgbn-3y

STARK-Based Signatures from the RPO Permutation

Authors

Shahla Atapoor, Cyprien Delpech de Saint Guilhem, Al Kindi

Shahla Atapoor

COSIC, KU Leuven, Leuven, Belgium
shahla dot atapoor at kuleuven dot be

Cyprien Delpech de Saint Guilhem

COSIC, KU Leuven, Leuven, Belgium
3MI Labs, Leuven, Belgium
cyprien dot desaintguilhem at 3milabs dot tech

Al Kindi

Miden, UAE
al dot kindi at miden dot team

Keywords: STARK RPO Post-Quantum Cryptography Digital Signatures

Abstract

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.

References

[AKM⁺22]

Tomer Ashur, Al Kindi, Willi Meier, Alan Szepieniec, and Bobbin Threadbare. Rescue-Prime Optimized. Cryptology ePrint Archive, Paper 2022/1577. 2022.

Google Scholar ePrint

[BBdSG⁺23]

Carsten Baum, Lennart Braun, Cyprien Delpech de Saint Guilhem, Michael Klooß, Emmanuela Orsini, Lawrence Roy, and Peter Scholl. Publicly Verifiable Zero-Knowledge and Post-Quantum Signatures from VOLE-in-the-Head. In Helena Handschuh and Anna Lysyanskaya, editors, Advances in Cryptology - CRYPTO 2023, Part V, volume 14085 of Lecture Notes in Computer Science, pages 581–615. 2023. Springer. DOI: 10.1007/978-3-031-38554-4_19

Google Scholar ePrint

[BCCT13]

Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer. Recursive composition and bootstrapping for SNARKS and proof-carrying data. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC'13, pages 111–120. 2013. ACM. DOI: 10.1145/2488608.2488623

Google Scholar ePrint

[BCI⁺20]

Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, and Shubhangi Saraf. Proximity Gaps for Reed-Solomon Codes. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 900–909. 2020. IEEE. DOI: 10.1109/FOCS46700.2020.00088

Google Scholar ePrint

[BCR⁺19]

Eli Ben-Sasson, Alessandro Chiesa, Michael Riabzev, Nicholas Spooner, Madars Virza, and Nicholas P. Ward. Aurora: Transparent Succinct Arguments for R1CS. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology - EUROCRYPT 2019, Part I, volume 11476 of Lecture Notes in Computer Science, pages 103–128. 2019. Springer. DOI: 10.1007/978-3-030-17653-2_4

Google Scholar ePrint

[BCS16]

Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner. Interactive Oracle Proofs. In Martin Hirt and Adam D. Smith, editors, Theory of Cryptography - 14th International Conference, TCC 2016-B, Part II, volume 9986 of Lecture Notes in Computer Science, pages 31–60. 2016. DOI: 10.1007/978-3-662-53644-5_2

Google Scholar ePrint

[BDPVA11]

Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche. Cryptographic sponge functions. Keccak Team Website. 2011.

Google Scholar ePrint

[BGK⁺23]

Alexander R. Block, Albert Garreta, Jonathan Katz, Justin Thaler, Pratyush Ranjan Tiwari, and Michal Zajac. Fiat-Shamir Security of FRI and Related SNARKs. In Jian Guo and Ron Steinfeld, editors, Advances in Cryptology - ASIACRYPT 2023, volume 14439 of Lecture Notes in Computer Science, pages 3–40. 2023. Springer. DOI: 10.1007/978-981-99-8724-5_1

Google Scholar ePrint

[BGKS20]

Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, and Shubhangi Saraf. DEEP-FRI: Sampling Outside the Box Improves Soundness. In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, volume 151 of LIPIcs, pages 5:1–5:32. 2020. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. DOI: 10.4230/LIPICS.ITCS.2020.5

Google Scholar ePrint

[BHK⁺19]

Daniel J. Bernstein, Andreas Hülsing, Stefan Kölbl, Ruben Niederhagen, Joost Rijneveld, and Peter Schwabe. The SPHINCS\({}^{\mbox{+}}\) Signature Framework. In Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, editors, Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, CCS 2019, pages 2129–2146. 2019. ACM. DOI: 10.1145/3319535.3363229

Google Scholar ePrint

[BSBHR18]

Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. Scalable, transparent, and post-quantum secure computational integrity. Cryptology ePrint Archive, Paper 2018/046. 2018.

Google Scholar ePrint

[BSBSofS20]

Michal Ben-Sasson, Eli Ben-Sasson, and others from StarkWare. Ziggy - a ZK-STARK based post-quantum secure signature scheme. StarkWare Git. 2020.

Google Scholar ePrint

[Can01]

Ran Canetti. Universally Composable Security: A New Paradigm for Cryptographic Protocols. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, pages 136–145. 2001. IEEE Computer Society. DOI: 10.1109/SFCS.2001.959888

Google Scholar ePrint

[CF24]

Alessandro Chiesa and Giacomo Fenzi. zkSNARKs in the ROM with Unconditional UC-Security. In Elette Boyle and Mohammad Mahmoody, editors, Theory of Cryptography - 22nd International Conference, TCC 2024 Part I, volume 15364 of Lecture Notes in Computer Science, pages 67–89. 2024. Springer. DOI: 10.1007/978-3-031-78011-0_3

Google Scholar ePrint

[CY24]

Alessandro Chiesa and Eylon Yogev. Building Cryptographic Proofs from Hash Functions. Self published 2024.

Google Scholar ePrint

[DHLW10]

Yevgeniy Dodis, Kristiyan Haralambiev, Adriana López-Alt, and Daniel Wichs. Efficient Public-Key Cryptography in the Presence of Key Leakage. In Masayuki Abe, editor, Advances in Cryptology - ASIACRYPT 2010, volume 6477 of Lecture Notes in Computer Science, pages 613–631. 2010. Springer. DOI: 10.1007/978-3-642-17373-8_35

Google Scholar ePrint

[DKKW25]

Justin Drake, Dmitry Khovratovich, Mikhail A. Kudinov, and Benedikt Wagner. Hash-Based Multi-Signatures for Post-Quantum Ethereum. IACR Commun. Cryptol., 2(1):13, 2025. DOI: 10.62056/AEY7QJP10

Google Scholar ePrint

[DKL⁺18]

Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler, and Damien Stehlé. CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2018(1):238–268, 2018. DOI: 10.13154/TCHES.V2018.I1.238-268

Google Scholar ePrint

[{Do }24]

Jérémi Do Dinh. Simulation Security in the Random Oracle Model. Master's thesis. School of Computer and Communication Science, EPFL, August 2024.

Google Scholar ePrint

[FKMV12]

Sebastian Faust, Markulf Kohlweiss, Giorgia Azzurra Marson, and Daniele Venturi. On the Non-malleability of the Fiat-Shamir Transform. In Steven D. Galbraith and Mridul Nandi, editors, Progress in Cryptology - INDOCRYPT 2012, volume 7668 of Lecture Notes in Computer Science, pages 60–79. 2012. Springer. DOI: 10.1007/978-3-642-34931-7_5

Google Scholar ePrint

[FR25]

Thibauld Feneuil and Matthieu Rivain. CAPSS: A Framework for SNARK-Friendly Post-Quantum Signatures. IACR Cryptol. ePrint Arch., 2025:61, 2025.

Google Scholar ePrint

[GHR⁺23]

Lorenzo Grassi, Yonglin Hao, Christian Rechberger, Markus Schofnegger, Roman Walch, and Qingju Wang. Horst Meets Fluid-SPN: Griffin for Zero-Knowledge Applications. In Helena Handschuh and Anna Lysyanskaya, editors, Advances in Cryptology - CRYPTO 2023, Part III, pages 573–606. 2023. Springer. DOI: 10.1007/978-3-031-38548-3_19

Google Scholar ePrint

[Hab22]

Ulrich Haböck. A summary on the FRI low degree test. Cryptology ePrint Archive, Paper 2022/1216. 2022.

Google Scholar ePrint

[HK24]

Ulrich Haboeck and Al Kindi. A note on adding zero-knowledge to STARKs. Cryptology ePrint Archive, Paper 2024/1037. 2024.

Google Scholar ePrint

[KV09]

Jonathan Katz and Vinod Vaikuntanathan. Signature Schemes with Bounded Leakage Resilience. In Mitsuru Matsui, editor, Advances in Cryptology - ASIACRYPT 2009, volume 5912 of Lecture Notes in Computer Science, pages 703–720. 2009. Springer. DOI: 10.1007/978-3-642-10366-7_41

Google Scholar ePrint

[KZ20]

Daniel Kales and Greg Zaverucha. Improving the Performance of the Picnic Signature Scheme. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2020(4):154–188, 2020. DOI: 10.13154/TCHES.V2020.I4.154-188

Google Scholar ePrint

[{Nat}24]

National Institute of Standards and Technology. Stateless Hash-Based Digital Signature Standard (SLH-DSA, FIPS 205). Technical report number FIPS 205, U.S. Department of Commerce. https://doi.org/10.6028/NIST.FIPS.205. 2024.

Google Scholar ePrint

[Pre23]

Team Preon. Preon, a zk-SNARK based Signature Scheme. Preon Team Website. 2023.

Google Scholar ePrint

[SGJ⁺24]

Vikas Srivastava, Naina Gupta, Arpan Jati, Anubhab Baksi, Jakub Breier, Anupam Chattopadhyay, Sumit Kumar Debnath, and Xiaolu Hou. Ascon-Sign Submission to the NIST Post-quantum Project. 2024.

Google Scholar ePrint

[{Sta}21]

StarkWare Team. ethSTARK Documentation. Technical report, StarkWare. 2021.

Google Scholar ePrint

[ZSE⁺24]

Xinyu Zhang, Ron Steinfeld, Muhammed F. Esgin, Joseph K. Liu, Dongxi Liu, and Sushmita Ruj. Loquat: A SNARK-Friendly Post-quantum Signature Based on the Legendre PRF with Applications in Ring and Aggregate Signatures. In Leonid Reyzin and Douglas Stebila, editors, Advances in Cryptology - CRYPTO 2024, Part I, pages 3–38. 2024. Springer. DOI: 10.1007/978-3-031-68376-3_1

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/absgbn-3y

History

Submitted: 2026-05-04
Accepted: 2026-06-30
Published: 2026-08-03

How to cite

Shahla Atapoor, Cyprien Delpech de Saint Guilhem, and Al Kindi, STARK-Based Signatures from the RPO Permutation. IACR Communications in Cryptology, vol. 3, no. 2, Aug 03, 2026, doi: 10.62056/absgbn-3y.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{10.62056/absgbn-3y,
         author={Shahla Atapoor and Cyprien Delpech de Saint Guilhem and Al Kindi},
         title={{STARK}-Based Signatures from the {RPO} Permutation},
         volume={3},
         number={2},
         year={2026},
         date={2026-08-03},
         issn={3006-5496},
         doi={10.62056/absgbn-3y},
         journal={{IACR} Communications in Cryptology},
         publisher={International Association for Cryptologic Research}
}

TY  - JOUR
AU  - Shahla Atapoor
AU  - Cyprien Delpech de Saint Guilhem
AU  - Al Kindi
PY  - 2026
TI  - STARK-Based Signatures from the RPO Permutation
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 3
IS  - 2
DO  - 10.62056/absgbn-3y
UR  - https://doi.org/10.62056/absgbn-3y
AB  - <p>  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. </p>
ER  -

Shahla Atapoor, Cyprien Delpech de Saint Guilhem, and Al Kindi, STARK-Based Signatures from the RPO Permutation. IACR Communications in Cryptology, vol. 3, no. 2, Aug 03, 2026, doi: 10.62056/absgbn-3y.