Batch Blind Signatures

Blind signatures are digital signatures where the signing process is an interactive protocol between a signer and a user. The signer provides the signing key sk and the user provides the message and receives a signature for that message. We require certain properties of this protocol. The signer should stay the only person that can sign he should not be able to associate a signing interaction with a signature.

[Fischlin] shows how to, fairly generically, construct a two round blind signature scheme. Basically the user commits to the message, the signer signs the commitment and the user proves via online extractable NIZK that he knows a commitment to the message and a signature that signs that commitment.

A bit more formally, he builds a blind signature scheme from a signature scheme sig=(KeyGen,Sign,Verify), a commitment scheme com=(Com), a public-key encryption scheme enc=(KeyGen,Enc,Dec), and a NIZK nizk=(Setup,Prove,Verify).

Now the blind signature has the following form:

Notice, the public-key encryption+NIZK combination acts as an online extractable NIZK.

What Benedikt, Rachit and I noticed is that this still works if the commitment is a vector commitment. This way, with roughly the same amount of interaction you can produce an entire batch of blind signatures. The only thing we need to make sure is that the signer not only signs the commitment but also the number of elements the commitment is allowed to contain. Else the user could generate more signatures than he is allowed to.

The full scheme looks as follows (where we now use a vector commitment scheme com=(Setup,Com,Open,Verify)):

That is the idea, I'll clean it uz and provide a proof sketch when I feel like it 😜