STARK-Based Signatures from the RPO Permutation

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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow> <mml:mn>64</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> signatures.