Blind Signatures

You did “not” see such a good introduction coming

The author thanks Unsplash and Osarugue Igbinoba for this image

Basic definitions and proposals

Blind signatures are an extension of digital signatures which provide privacy by allowing a user to obtain a signature from a signer on a message without the signer being able to see the contents of the blinded message. If the signer is later presented with the signed document he cannot relate it neither to the signing session nor to the user on behalf of whom he has signed the message.

A blind signature scheme is a tuple of polynomial-time algorithms {KeyGen, Sign, Verify} such that:

• KeyGen is an algorithm that on the input of a security parameter, outputs a pair of keys pk and sk.
• Sign is an interactive protocol between a signer S and a user U. The input of S is a secret key sk, whereas the input of U is a public key pk and a message m ∈ M from a message space M. The output of S is a view 𝜈 (seen as a random variable) and the output of U is a signature 𝜎.
• Verify is a verification algorithm that outputs 1 if 𝜎 is a valid signature and 0 otherwise.

Security in blind signatures is captured by two concepts: blindness and unforgeability. Blindness prevents a malicious signer from learning information about a user’s message. On the other hand, unforgeability ensures that each completed Sign execution yields at most k signatures after k interactions between S and U.

Blindness is defined through the following game:

• An adversarial signer S* runs KeyGen to get a key pair (pk, sk).
• S* generates messages m₀ and m₁.
• A random bit b ∈ {0, 1} is selected and messages m[b] and m[1-b] are sent to users U₀ and U₁.
• Sign is executed between S* and U₀ and between S* and U₁ and outputs signatures 𝜎[b] or 𝜎[1-b] respectively.
• U₀ and U₁ send 𝜎[b] and 𝜎[1-b] to S*.
• S* gets 𝜎[b] and 𝜎[1-b] and outputs a bit b*.
• The game outputs 1 if b = b*, or 0 otherwise.

For a small enough 𝜀 > 0, a blind signature scheme BS is called (t, 𝜀)-blind if the game, run by any adversarial signer S* in time at most t, outputs 1 with probability 1/2+𝜀.

Unforgeability is also defined through a game where an adversarial user U* tries to output k + 1 valid pairs (m[i], 𝜎[i]), for 1 ≤ i ≤ k + 1 after at most k successful interactions with an honest signer S. In this case, U* wins the game.

For a small enough 𝜀 > 0, a blind signature scheme BS is called (t, q_sign, 𝜀)-unforgeable if for any adversarial user U*, running in time t (at most) the previous game and making q_sign signing interactions, wins the game with probability lower or equal than 𝜀.

Chaum’s scheme

David Chaum created the concept of blind signature and introduced the first scheme from the modification of an RSA digital signature, so one assumes that the public key is of the form (n, e), for n = p · q the product of two large primes. The secret key is an integer d such that e · d = 1 (mod (p-1) · (q -1)), as follows:

• U takes a random invertible r ∈ ℤn and sends m’ = m · rᵉ (mod n) to S.
• S signs m’ with his private key by computing s’= m’ᵈ (mod n) and sends s’ to U.
• U unblinds s’ to get the signature on m by computing:

Schnorr’s blind signature

In this scheme, system parameters and involved keys are the same as for the DSA and Chaum’s proposals but include a hash function H. When a user U wants a signer S to sign a message m ∈ ℤp blindly, he follows the steps below:

• S takes a random invertible k ∈ ℤq, computes r = gᵏ (mod p) and sends it to U.
• U takes a random pair of invertible a, b ∈ ℤq and computes

and sends e to S.

• S computes s = k — e · x (mod q) and sends it to U.
• U computes s’=s — a (mod q) and obtains a valid signature (r’, s’).

An ECDSA-based proposal

This is a proposal based on ECDSA, therefore with potential applications to Bitcoin. It is based on a modified version of Paillier’s cryptosystem, which follows:

• Key generation requires three large primes p, q and t such that gcd(p — 1, q) = 1 = gcd(t — 1, q). The public key is given by the pair (N, g) for N = p · q · t and g = (1 + N) · p · t mod N². Concerning the secret key, it is given by the pair (p, t).
• Encryption takes a message m ∈ ℤq, m ≥ 0, a random invertible r ∈ ℤN² and outputs c = gᵐ · r^N mod N².
• Decryption takes a ciphertext and outputs

The blind signature proposal follows:

• The signer S takes a random k₁ ∈ ℤq and computes K₁ = k₁ · g for g an element of the elliptic curve E used in ECDSA (assumed to have primer order q). S sends K₁ to the user U.
• After receiving K₁ from S, U takes a random invertible k₂ ∈ ℤq and computes K = (Kₓ, K_y) = k₂ · K₁. U now follows the modified Paillier scheme and takes large primes p and t, computes the public key (N, g) and takes random invertible r₁, r₂ ∈ ℤN² for encryption (q is assumed public).

U encrypts h, the hash of the message m, by computing

and sends c₁, c₂ to S. U needs to send also a proof that encryptions were computed correctly using a protocol that will be described below.

• After receiving c₁, c₂ and checking that they were computed correctly, S takes a random 1 < r ≤ N and computes

for sk the secret key used by S in the ECDSA. S sends c to U.

U computes s = k₂ — 1 · Dec(c, (p,t)) (mod q), for Dec the Paillier’s decryption mechanism. The blind ECDSA signature is (Kₓ, s).

In order for U to prove that the ciphertext has the form c=gᵐ · r^N mod N²:

• U takes random m’ ∈ ℤq and r’ ∈ ℤN², computes c’ = gᵐ’ · r’^N mod N² and sends it to S.
• S takes a random bit b ∈ {0,1} and sends it to U.
• If b = 0, then U sends m’, r’ to S, who checks whether c’ = gᵐ’ · r’^N mod N².
• If b = 1, then U sends m’’ = m + m’ (mod q) and r’’ = r · r’ mod N² to S, who checks whether c · c’ = gᵐ’’ · r’’^N mod N².

One repeats this interaction l times. If U replied to all queries correctly, then S is sure that c was constructed correctly with probability 1 — 1/2ˡ.

Okamoto’s blind signature scheme

It is important to note that many of the proposals for blind signatures have security proofs which rely on the random oracle model. It is well known that this model offers security proofs that are weaker than those obtained from the so-called standard model. Two facts need to be highlighted:

• Obtaining proofs in the standard model is not easy and comes at the price of considering assumptions that make the cryptographic protocol inefficient. For this reason, many security proofs are in the weaker random oracle model, without implying that the protocol is insecure (unless an attack is discovered).
• Fischlin and Schröder (Fischlin and Schröder) proved that it is hard to find this kind of security proof (in the standard model) for blind signatures of “three moves” such as Chaum’s proposal.

The key point in Fischlin — Schröder’s result is that schemes must satisfy some technical conditions such as reduction in unforgeability proofs are efficient, and this is something satisfied by many three-move blind signatures.

Soon after the appearance of Fischlin — Schröder’s paper, Garg et al. proposed an optimal blind signature: a two-move scheme, proven secure in the standard model. The authors managed to bypass the technical conditions concerning unforgeability to obtain a feasible scheme, which unfortunately is far from being efficient.

The best-known proposal in blind signatures, in terms of round complexity, proven secure in the standard model is due to Okamoto (Okamoto ) and has four rounds.

The security of Okamoto’s proposals, both the signature scheme and the derived blind version, relies on the hardness of the 2-variable strong Diffie-Hellman problem. Both proposals are based on pairings over cyclic groups of prime orders.

Partially blind signatures

One of the problems that blind signatures face is that the signer has no control over the attributes he is signing except for those coming from public information. To solve this problem some authors introduced partially blind signatures, where the user and the signer have an agreement to explicitly include common information in the blind signature.

Concerning definitions, partially blind signatures are introduced in a very similar way when compared to ordinary blind signatures. The main difference is a piece of information, called “info”, that is included in the input of both the user and the signer. When dealing with blindness and unforgeability, one needs to carry “info” in the input details of the user and the signer; the rest of the definition or proof remains unchanged.

Among the proposals that one can find in the literature, we highlight Okamoto’s proposal (Okamoto ), a partially blind scheme derived from his signature scheme, and the ECDSA-based proposal due to Huang, Liu and Tso (Huang et al.) which combines Yi — Lam (Yi and Lam ) blind signatures and Bellare — Micciancio incremental hash functions (Bellare and Micciancio).

Use cases

Blind signatures were developed with anonymous transactions in mind. Nevertheless, there are a few other use cases that deserve to be explored. This section discusses some of the proposals.

Anonymous transactions

There are several proposals, for instance, Ladd (Ladd) or Yi — Lam, where blind signatures are used to allow sender anonymity. The use of blind signatures in those proposals indicates that using blind signatures would not require particular modifications besides the obvious substitution of the digital signature scheme: both Ladd and Yi — Lam — Gollmann simply substitute ECDSA with the blind analogue scheme.

It is important to note that Ladd’s proposal relies on a blind signature which does not have a proof of security, in fact, the proposal comes from a community discussion. Therefore it would be advisable to follow Ladd’s ideas but change the signature mechanism with a proven secure proposal.

Another interesting point to keep in mind is that blind signatures do not enjoy particular good fame due to the fact that the signer has no control over the contents of the message. A good option would be to use partially blind digital signatures instead in order to incentivize or increase the level of confidence of signers when involved in this blind signing.

Anonymous mixing services

Similarly to anonymous transactions, blind signatures, in combination with mixers, led Valenta and Rowan to introduce Blindcoin (Valenta and Rowan) built upon Mixcoin with a modification of the protocol in order to provide anonymity by using blind signatures. Blindcoin guarantees that the input-output connection is kept secret from the mixing service.

As happens with the case of anonymous transactions, Blindcoin does not need major modifications to Mixcoin to get the objective. In step 1 the sender sends the mixer a set of parameters with a blind token (an output address and a nonce). If the mixer accepts, the protocol runs in a very similar fashion as happens in Mixcoin. At some point, the sender unblinds the token containing the output address, which has been blindly signed by the mixer. Observe that now the mixer is not able to establish a connection between the unblind output address and the input address of the sender.

References

1. Bellare, Mihir, and Daniele Micciancio. “A New Paradigm for Collision-Free Hashing: Incrementality at Reduced Cost.” EUROCRYPT 1997: Advances in Cryptology — EUROCRYPT ’97, 1997, pp. 163–192.
2. Fischlin, Marc, and Dominique Schröder. “On the Impossibility of Three-Move Blind Signature Schemes.” EUROCRYPT 2010: Advances in Cryptology — EUROCRYPT 2010, 2010, pp. 197–215.
3. Huang, Hongxun, et al. “Partially Blind ECDSA Scheme and Its Application to Bitcoin.” 2021 IEEE Conference on Dependable and Secure Computing, 2021, pp. 1–8.
4. Ladd, Watson. “Blind Signatures for Bitcoin Transaction Anonymity.” 2012.
5. Okamoto, Tatsuaki. “Efficient Blind and Partially Blind Signatures Without Random Oracles.” Cryptology ePrint Archive, 2006.
6. Valenta, Luke, and Brendan Rowan. “Blindcoin: Blinded, Accountable Mixes for Bitcoin.” FC 2015: Financial Cryptography and Data Security, 2015, pp. 112–126.
7. Yi, Xun, and Kowk-Yan Lam. “A New Blind ECDSA Scheme for Bitcoin Transaction Anonymity.” Asia CCS ’19: Proceedings of the 2019 ACM Asia Conference on Computer and Communications Security, 2019, pp. 613–620.