Which blind signature schemes exist, and how do they compare?

Question

I'm looking into blind signature schemes for use as digital cash. I have come across blinded RSA, and Lucre(DH based). Are there other schemes available, and how do they compare? I suspect there should be a elliptic curve scheme, which might have better performance than the other schemes.

In particular I'm interested in:

• Performance - how expensive is it to create/validate the signature? I mainly care about the cost for the authority(does signing and verification), and less about the performance of the client (does blinding and verification)
• Patents - Is the scheme patented? Have the patents expired?
• Simplicity - Is it easy to understand? Is it easy to make subtle mistakes which compromise anonymity or security?

My current evaluation of RSA and Lucre:

Blinded RSA

• Requires an RSA private key operation for signing. This is relatively expensive, especially if keys larger keys(say 2048 bit) are used.
• Patented by Chaum, but the patents should have expired by now
• Quite simple, even I understand it

Lucre

• Not sure about the performance, but I don't expect much better performance than with RSA.
• Paper claims it is patent free, at least in some variations
• There are some subtle points. If used incorrectly the signer might be able to abuse being able to choose k in a way that compromises anonymity. I don't really understand it (yet).

Reading the paper a few more times, it seems like most variants of lucre aren't "real" signatures that can be verified by everyone. But rather you need to perform an interactive probabilistic proof. Some variants doesn't suffer from this problem, but they might have other problems.

My subjective impression is that I don't like lucre. It seems like its only raison d'être is that is avoids Chaum's patents. But if those are expired, this shouldn't be an issue anymore.

Answer 1

Conceptually comparable to Chaums RSA blind signature scheme, is another elegant two move blind signature scheme called the blind Gap-DH signature scheme, which can be instantiated with pairing friendly elliptic curve groups.

This blind signature scheme can be based on the compact BLS-signature scheme (which is based on gap-DH groups, i.e., groups in which the DDHP is easy but the CDHP remains hard) and the blinding works similar to Chaum's RSA blind signature scheme.

Let $e: G\times G\rightarrow G_T$ be a pairing and $G$, $G_T$ groups of prime order $p$ and $H:\{0,1\}^* \rightarrow G$ a hash function and let $g$ be a generator of $G$ (I use multiplicative notation and describe here the BLS Signature for symmetric pairings, but they can also be defined for asymmetric Type 2 and Type 3 pairings, see for instance here).

In order to generate a BLS-signature, the signer with private key $x\in Z_p^*$ ($y=g^x$ is the public key) computes $\sigma=H(m)^x$ and the verifier checks whether $e(H(m),y)=e(\sigma,g)$ holds. The correctness is obvious, since $e(H(m),y)=e(H(m),g^x)=e(H(m),g)^x = e(H(m)^x,g) = e(\sigma,g)$.

Now the blind signature version is as follows:

• Receiver (blinding): Holding message $m$, choose $r\in_R \mathbb{Z}_p^*$ and compute $\overline{h}=H(m)g^r$ and send $\overline{h}$ to the signer.
• Signer: Compute $\overline{\sigma}=\overline{h}^x$ and send $\overline{\sigma}$ to the receiver.
• Receiver (unblinding): Compute $\sigma=\overline{\sigma}y^{-r}$, which is a signature for $m$.

It is easy to verify that this is correct, since $\overline{\sigma}y^{-r} = (H(m)g^r)^xy^{-r}=H(m)^xg^{rx}g^{-rx}=H(m)^x=\sigma$.

There are various other discrete log based blind signature schemes wich could be used in the elliptic curves setting, but the above blind GDH signature scheme produces short signatues, requires only two moves and all other DL schemes require more interaction (at least three moves) and are much more complicated. Nevertheless, they are typically cheaper in terms of computation. For instance, the blind version of the Schnorr protocol as proposed by Okamoto here in Appendix B from Crypto'92. Furthermore, as mentioned by Matteo there are also blind ElGamal variants.

I do not know of any patent issues with these ones, but the original patent for blind RSA signatures by David Chaum is expired.

Answer 2

I'm still a newbie in the field, but trying to learn something about it I ran into these two papers that you surely know, in case not I'll point them out:

• Blind signatures for untraceable payments, Chaum

• Provably secure blind signatures schemes, Pointcheval

By the way if you look at the introduction of the second title it seems what your looking for.

---

A specific link on Electronic Cash from RSA Laboratories:

• What is Electronic Money

---

By studying blind signatures I've read about a scheme based on ElGamal Signature Scheme, I'll provide the information I was able to glimpse.

You can find more details at the following links:

• IEEE, A blind signature scheme based on ElGamal signature

• Citeseerx, Generalized blind signature schemes

Blinded ElGamal:

• Performances:

Owner Alice needs to compute two online exponentiations modulo $p$ with a |$q$| bit exponent and one offline inverse modulo $q$.

Notary Nancy needs to compute just one online exponentiations modulo $p$ with a |$q$| bit exponent.

Verifier Victor needs to compute two exponentiations instead of the three ones required for standard ElGamal scheme.

Note: you can find further references for even more efficient variants in the links I provided.

• Patents:

I have no clue!Sorry about that...

• Simplicity:

I got it all clear, if reading the papers you have any doubts post them and we can check together!