“STARK-Based Signatures from the RPO Permutation” was published in IACR Communications in Cryptology, Volume 3, Issue 2, on August 3, 2026.1 The work first appeared as an IACR ePrint preprint on October 3, 2024.2
The journal authors are Shahla Atapoor of KU Leuven, Cyprien Delpech de Saint Guilhem of KU Leuven and 3MI Labs, and Al Kindi of Miden.1
Construction
The scheme proves knowledge of a pre-image of the RPO permutation using a STARK, with DEEP-ALI and the BCS transform over the Goldilocks field. It needs no trusted setup. The parameter sets provide 113 or 122 bits of average-case security, against adversaries with access to up to 2^64 signatures.1
Performance
With Blake3 as the hash, signing takes 4.6 to 7.2 milliseconds and verification 0.46 to 0.52 milliseconds. With RPO, the setting required for verification inside another proof, verification takes 5.09 to 5.79 milliseconds. The authors proved a signature verification inside the Miden zkVM.1