Paper 2025/538

Efficient Proofs of Possession for Legacy Signatures

Anna P. Y. Woo, University of Michigan–Ann Arbor
Alex Ozdemir, Stanford University
Chad Sharp, University of Michigan–Ann Arbor
Thomas Pornin, NCC Group
Paul Grubbs, University of Michigan–Ann Arbor
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 and prover times by 3-22. We can generate a 240-byte proof of possession of an RSA signature over a message the size of a typical TLS certificate (two kilobytes) in only three seconds.

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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.