Paper 2025/538
Efficient Proofs of Possession for Legacy Signatures
Abstract
Digital signatures underpin identity, authenticity, and trust in modern computer systems. Cryptography research has shown that it is possible to prove possession of a valid message and signature for some public key, without revealing the message or signature. These proofs of possession work only for specially-designed signature schemes. Though these proofs of possession have many useful applications to improving security, privacy, and anonymity, they are not currently usable for widely deployed, legacy signature schemes such as RSA, ECDSA, and Ed25519. Unlocking practical proofs of possession for these legacy signature schemes requires closing a huge efficiency gap.
This work brings proofs of possession for legacy signature schemes very close to practicality. Our design strategy is to encode the signature's verification algorithm as a rank-one constraint system (R1CS), then use a zkSNARK to prove knowledge of a solution. To do this efficiently we (1) design and analyze a new zkSNARK called Dorian that supports randomized computations, (2) introduce several new techniques for encoding hashes, elliptic curve operations, and modular arithmetic, (3) give a new approach that allows performing the most expensive parts of ECDSA and Ed25519 verifications outside R1CS, and (4) generate a novel elliptic curve that allows expressing Ed25519 curve operations very efficiently. Our techniques reduce R1CS sizes by up to 200
Metadata
- Available format(s)
-
PDF
- Category
- Applications
- Publication info
- Published elsewhere. Major revision. IEEE S&P 2025
- DOI
- 10.1109/SP61157.2025.00080
- Keywords
- applied cryptographyzero-knowledge proofssignaturesprivacy-enhancing technologies
- Contact author(s)
-
pywoo @ umich edu
aozdemir @ cs stanford edu
cmlsharp @ umich edu
thomas pornin @ nccgroup com
paulgrub @ umich edu - History
- 2025-03-25: approved
- 2025-03-24: received
- See all versions
- Short URL
- https://ia.cr/2025/538
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/538, author = {Anna P. Y. Woo and Alex Ozdemir and Chad Sharp and Thomas Pornin and Paul Grubbs}, title = {Efficient Proofs of Possession for Legacy Signatures}, howpublished = {Cryptology {ePrint} Archive, Paper 2025/538}, year = {2025}, doi = {10.1109/SP61157.2025.00080}, url = {https://eprint.iacr.org/2025/538} }