STARK-based Signatures from the RPO Permutation

Shahla Atapoor; Cyprien Delpech de Saint Guilhem; Al Kindi

Paper 2024/1553

STARK-based Signatures from the RPO Permutation

Shahla Atapoor

, KU Leuven

Cyprien Delpech de Saint Guilhem

, 3MI Labs

Al Kindi, Polygon Labs

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 constructed with the DEEP-ALI interactive oracle proof combined with the Ben-Sasson--Chiesa--Spooner (BCS) transformation in the random oracle model. The EUF-CMA security of the resulting signature scheme is established from the UC-friendly security properties of the BCS transformation and the pre-image hardness of the RPO permutation. The implementation of the scheme computes signatures in 13 ms and verifies them in 1 ms on a single core when the BCS transform is implemented with the Blake3 hash function. (The multi-threaded implementation signs in 9.2 ms and also verifies in 1 ms.) These speeds are obtained with parameters achieving 122 bits of average-case security for \( 2^{122} \)-bounded adversaries with access to at most \( 2^{64} \) signatures.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published by the IACR in CIC 2026
DOI: 10.62056/absgbn-3y
Keywords: signature scheme RPO STARK
Contact author(s): shahla atapoor @ kuleuven be
cyprien desaintguilhem @ 3milabs tech
al kindi @ polygon technology
History: 2026-08-20: revised; 2024-10-03: received; See all versions
Short URL: https://ia.cr/2024/1553
License: CC BY

BibTeX

@misc{cryptoeprint:2024/1553,
      author = {Shahla Atapoor and Cyprien Delpech de Saint Guilhem and Al Kindi},
      title = {{STARK}-based Signatures from the {RPO} Permutation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1553},
      year = {2024},
      doi = {10.62056/absgbn-3y},
      url = {https://eprint.iacr.org/2024/1553}
}