[Homepage]

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:

• Setup(1^λ):
1. Let crs←nizk.Setup(1^λ)
2. Let (pk,sk*)←enc.KeyGen(1^λ)
3. Output (crs,pk)
• KeyGen(1^λ):
1. Output (vk,sk)←sig.KeyGen(1^λ)
• Request(m;r):
1. Output c←com.Com(m;r)
• Sign(c,sk):
1. Output σ←sig.Sign(c,sk)
• Finalize(m,σ,r):
1. Let ct←enc.Enc(pk,(σ,r))
2. π←nizk.Prove(ct encrypts some (σ,r) s.t. c←com.Com(m;r) and sign.Verify(vk,c,σ)=1)
3. Output (ct,π)
• Verify(m,ct,π):
1. Output nizk.Verify(π)

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)):

• Setup(1^λ):
1. Let crs←nizk.Setup(1^λ)
2. Let crs'←com.Setup(1^λ)
3. Let (pk,sk*)←enc.KeyGen(1^λ)
4. Output (crs,crs',pk)
• KeyGen(1^λ):
1. Output (vk,sk)←sig.KeyGen(1^λ)
• Request(m):
1. Output c←com.Com(crs',m₁,...,m_n)
• Sign(c,B,sk), where B is the batchsize:
1. Output σ←sig.Sign((c,B),sk)
• Finalize(m,i,σ,c,B):
1. Let o←com.Open(c,i,m)
2. Let ct←enc.Enc(pk,(σ,o,i,B))
3. π←nizk.Prove(ct encrypts some (σ,o,i,B) s.t. com.Verify(m,c,o,i)=1, i<B, and sign.Verify(vk,(c,B),σ)=1)
4. Output (ct,π)
• Verify(m,ct,π):
1. Output nizk.Verify(π)

Blindness follows fairly easily from zero knowledge of nizk, semantic security of enc, and hiding of com. One-more unforgability is a bit harder to prove. In fact the definition is already a bit non-trivial but the strategy is roughly the following: You reduce to unforgability of the signatures by guaranteeing that the cts are encrypting (σ,o,i,B) s.t. com.Verify(m,c,o,i)=1, i<B, and sign.Verify(vk,(c,B),σ)=1. This follows from the soundness of nizk. Then you decrypt all the cts. By the precondition of one-more unforgability of the blind signature scheme or there is now either a commitment that contains more values than B (which we can rule out via binding) or there are more commitments than the signer actually signed. This would break unforgability of sig.

The proof is pretty much the same as in [Fischlin] but you need to be a little bit more careful when you count the number of signatures.

Overall, we thought this is a cute observation but not really publication worthy. We tried to make it practical by instatiating the components with schemes that work particularly well together but we couldn't find any signatures that sign vector commitments with the entire process being efficiently provable with a special purpose NIZK. If you have any idea where to take this feel free to email me about this.