Two faces of blind signatures

January 24, 2020

David Chaum introduced blind signatures almost four decades ago [1], as the fundamental building block to implement a form of untraceable digital cash. His proposal was to represent each digital coin as a unique serial number blindly signed by the issuing bank. The unique serial number embedded in the coin would prevent double spending, while the blind signature over the coin would guarantee both untraceability (by not knowing which coin was signed) and unforgeability (by signing the coins in the first place). Unfortunately, the way Chaum explained the blindness property has somewhat obscured the fact that it actually has two different faces.

Chaum explained blind signatures intuitively by showing how a blind signature could be implemented in a traditional, non digital, setting using carbon paper inside paper envelopes. To obtain a blind signature on a secret message, a user could send the message inside a sealed envelope to the signer, with the inside of the envelope covered with carbon paper. The carbon paper ensures that if the signer signs the envelope from the outside, the carbon paper transfers this signature to the secret message inside the envelope. When the signer returns the still sealed envelope (proving it didn't see the message) all the user needs to do is to open the envelope to obtain the blindly signed message.

This intuitive explanation clearly shows that the message stays hidden from the signer. But this by itself is not enough to prevent a bank from tracing a digital coin signed this way, even if it prevents the bank from learning its serial number. In fact, if the bank signs each envelope in a slightly different way, and remembers which way of signing it used to sign each envelope, it can link actual signatures on messages to the particular envelope on which he put the exact same signature. In other words, in order to guarantee untraceability in this particular setting (sometimes also called unlinkability), blind signatures need to guarantee two separate properties:

  1. Message hiding: The message to be signed is hidden from the signer. An adversarial signer that is engaged in a blind signature protocol involving one of two messages it previously selected itself, cannot determine which of the two messages it is currently signing.
  2. Signature unlinkability: Given a final blind signature on a message, the signer cannot determine when it generated that particular signature. An adversarial signer that previously blindly signed two messages it previously selected itself, cannot tell in which order it created the resulting signatures when given these signatures later in arbitrary order.

Perhaps due to Chaum's metaphor, blind signatures have always informally been explained as signatures where the message to be signed is hidden from the signer. In general signing messages without knowing their contents is irresponsible (who would sign a contract without knowing its terms?), but blind signatures do serve an important purpose beyond implementing digital cash. They can more generally be used to prove that a certain condition has been met, without revealing when or where that condition was met. Blind signatures can for example be used to issue a unique and unforgeable token or receipt whenever a user has performed a certain action (like paying a bill, visiting a checkpoint, entering or leaving a certain location, completing some task, or satisfying any other predetermined requirement). In fact blind signatures have been used to implement attribute based credentials.

Blind signature schemes that only offer message hiding are for instance used in the Idemix attribute based credential system to hide the master secret from the credential issuer. A trivial implementation of such a blind signature scheme in the random oracle model would be one where the message m to be signed is first hashed using a public cryptographic hash function h. To obtain a signature the resulting hash h(m) is sent to the signer, who generates a signature over this hash using an arbitrary traditional (non-blind) signature scheme. To verify the signature, the message is hashed again using the public hash function h and the result verified using the traditional signature verification function. This method hides the message to the signer (the properties of the hash function guarantee that h(m) does not reveal anything about m, but the resulting signature is still perfectly linkable.

This shows that both notions of blindness are not identical, but it is quite easy to see that the signature unlinkability property implies the message hiding property. In other words, message hiding is a strictly weaker property. Suppose we have an adversary that can break the message hiding property, we can turn it in an adversary that breaks the signature unlinkability property as follows. The idea is to let the adversary keep a history M of all messages it signed (it can do so using the adversary that breaks the message hiding property whenever it is asked to sign a message). The adversary uses this history when asked later to tell when it signed a particular message by trying each m in M in turn and see whether the signature is valid for this particular message. If it is, then this identifies when the signature was generated (provided this additional information is recorded in the history as well).

References

[1] David Chaum. “Blind Signatures for Untraceable Payments”. In: Advances in Cryptology: Proceedings of CRYPTO ’82, Santa Barbara, California, USA, August 23-25, 1982. 1982, pp. 199–203.

In case you spot any errors on this page, please notify me!
Or, leave a comment.