Oblivious issuance of proofs

We consider the problem of 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 cannot be linked back to the interaction that produced it, and can be verified non-interactively by anyone. 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 two provably-secure constructions of oblivious proofs, and 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. Our upgrade maintains the performance and functionality of the credential in the keyed-verification setting, we only change issuance. 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.