Paper 2023/1635

Oblivious issuance of proofs

Michele Orrù, French National Centre for Scientific Research
Stefano Tessaro, University of Washington
Greg Zaverucha, Microsoft Research
Chenzhi Zhu, University of Washington

We consider the problem of creating, or issuing, zero-knowledge proofs obliviously. In this setting, a prover interacts with a verifier to produce a proof, known only to the verifier. The resulting proof is transferable and can be verified non-interactively by anyone. Crucially, the actual proof cannot be linked back to the interaction that produced it. This notion generalizes common approaches to designing blind signatures, which can be seen as the special case of proving "knowledge of a signing key", and extends the seminal work of Camenisch and Stadler ('97). We propose a provably secure construction of oblivious proofs, focusing on discrete-logarithm representation equipped with AND-composition. We also give three applications of our framework. First, we give a publicly verifiable version of the classical Diffie-Hellman based Oblivious PRF. This yields new constructions of blind signatures and publicly verifiable anonymous tokens. Second, we show how to "upgrade" keyed-verification anonymous credentials (Chase et al., CCS'14) to also be concurrently secure blind signatures on the same set of attributes. Crucially, our upgrade maintains the performance and functionality of the credential in the keyed-verification setting, we only change issuance. We observe that the existing issuer proof that the credential is well-formed may be verified by anyone; creating it with our framework makes it a blind signature, adding public verifiability to the credential system. Finally, we provide a variation of the U-Prove credential system that is provably one-more unforgeable with concurrent issuance sessions. This constitutes a fix for the attack illustrated by Benhamouda et al. (EUROCRYPT'21). Beyond these example applications, as our results are quite general, we expect they may enable modular design of new primitives with concurrent security, a goal that has historically been challenging to achieve.

Available format(s)
Cryptographic protocols
Publication info
non-interactive proofsblind signaturesanonymous credentials
Contact author(s)
michele @ orru net
tessaro @ cs washington edu
gregz @ microsoft com
zhucz20 @ cs washington edu
2023-10-23: approved
2023-10-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Michele Orrù and Stefano Tessaro and Greg Zaverucha and Chenzhi Zhu},
      title = {Oblivious issuance of proofs},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1635},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.