Oblivious Issuance of Proofs

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.