Paper 2025/061

CAPSS: A Framework for SNARK-Friendly Post-Quantum Signatures

Thibauld Feneuil, CryptoExperts (France)
Matthieu Rivain, CryptoExperts (France)
Abstract

In this paper, we present a general framework for constructing SNARK-friendly post-quantum signature schemes based on minimal assumptions, specifically the security of an arithmetization-oriented family of permutations. The term "SNARK-friendly" here refers to the efficiency of the signature verification process in terms of SNARK constraints, such as R1CS constraints. Within the CAPSS framework, signature schemes are designed as proofs of knowledge of a secret preimage of a one-way function, where the one-way function is derived from the chosen permutation family. To obtain compact signatures with SNARK-friendly verification, we rely on SmallWood, a recently proposed hash-based zero-knowledge argument scheme well suited for statements arising in this context. From this proof system which we tweak towards SNARK-friendliness, the CAPSS framework offers a generic transformation of any arithmetization-oriented permutation family into a SNARK-friendly post-quantum signature scheme. We provide concrete instances built on permutations such as Rescue-Prime, Poseidon, Griffin, and Anemoi. For the Anemoi family, achieving 128-bit security, our approach produces signatures of sizes ranging from 9 to 13.4 KB, with R1CS constraints between 19K and 29K. This represents a 4-6x reduction in signature size and a 5-8x reduction in R1CS constraints compared to Loquat (CRYPTO 2024), a SNARK-friendly post-quantum signature scheme based on the Legendre PRF.

Note: [June 2025 update] The SmallWood proof system, originally introduced in this work, has been extracted and developed as a standalone paper (https://ia.cr/2025/1085). A formal proof of EUF-CMA security has been added, and implementation benchmarks are now included.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Zero-Knowledge ProofsPost-Quantum SignaturesSNARK-FriendlinessHash-based Proof Systems
Contact author(s)
thibauld feneuil @ cryptoexperts com
matthieu rivain @ cryptoexperts com
History
2025-06-12: revised
2025-01-14: received
See all versions
Short URL
https://ia.cr/2025/061
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/061,
      author = {Thibauld Feneuil and Matthieu Rivain},
      title = {{CAPSS}: A Framework for {SNARK}-Friendly Post-Quantum Signatures},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/061},
      year = {2025},
      url = {https://eprint.iacr.org/2025/061}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.