On Blind Signatures for Untraceable Payments
In 1983, David Chaum conceived an anonymous cryptographic electronic money, believed to be the first cryptocurrency to ever exist. This cryptocurrency relied on the use of blind signatures, which were introduced in his paper as well.
In a nutshell, it is an automation of the way we pay for goods using payment systems like banknotes and coins. It also addresses some of its problems such as lack of control, privacy, and security.
Thus, he proposed a new kind of cryptography with the following properties:
Inability of third parties to determine payee, time or amount of payments made by an individual.
Ability of individuals to provide proof of payment, or to determine the identity of the payee under exceptional circumstances.
Ability to stop use of payments media reported stolen.
In this article, I will expose the resources I used to understand blind signatures as well as give more explanations for the concepts.
Illustration
To illustrate this blind signature cryptosystem, David Chaum uses an election example based on the use of carbon paper lined envelopes. These latter is built in a way that signing them from the outside leaves a copy of the signature on a slip of paper within the envelope.
The problem statement is as follows:
Solution
Sending a vote to be signed
- The elector votes on a piece of paper.
- Puts that vote inside a carbon paper lined envelope. This means that when the trustee will sign the envelope from outside, a copy of the signature will remain on the vote.
- Wraps the vote envelope inside another envelope containing the elector’s address.
Finally, sends these nested envelopes to the trustee.
The signing process:
The trustee receives the envelope:
4. He opens the outside envelope then take out the inside envelope containing the vote.
5. He signs on the envelope containing the vote. But since it’s a carbon paper lined envelope, the signature will be also present on the vote. Thus, this is done without opening the envelope.
6. He wraps the signed envelope inside another envelope.
Then sends that envelope back to the address that was on the back of the elector’s outside envelope. The trustee should use a special signature which is only valid for this election.
The voting process:
The elector receives the signed envelope from the trustee:
7. He takes the signed envelope out of the external envelope.
8. Unwraps his vote, and he finds the signature of the trustee on top of it.
9. Sends that vote anonymously on the day of the election to be displayed during the vote.
The electors can be sure that their votes are being counted via leaving special marks on their paper votes. Marks that only them would recognize.
This way, the trustee will receive signed votes and can be sure that only the allowed electors are voting, but without knowing their identity.
Blind signatures cryptography
Blind signature schemes exist for many public key signing protocols. For example, we can build a blind signatures cryptosystem on RSA as follows:
Traditional RSA operations:
Blinded RSA can be created in the following way:
Properties
In general, the functions used should obey the following properties, as stated by David Chaum:
- A signing function s’ known only to the signer, and the corresponding publicly known inverse s, such that s(s’(x)) = x. and s give no clue about s’.
- A computing function c and its inverse c’, both know only the provider, such that c’(s’(c(x))) = s’(x), and c(x) and s’ give no clue about x.
- A redundancy checking predicate r, that checks for sufficient redundancy to make search for valid signatures impractical.
How they work
These functions are used, somehow, the same way as the carbon paper lined envelopes in the illustrated example:
- Provider chooses x at random such that r(x) (r checks for redundancy to make search for valid signatures impractical), forms c(x), and supplies c(x) to signer.
- Signer signs c(x) by applying s’ and returns the signed matter s’(c(x)) to provider.
- Provider strips signed matter by application of c’, yielding c’(s’(c(x))) = s’(x)
Anyone can check that the stripped matter s’(x) was formed by the signer, by applying the signer’s public key s and checking that r(x(s’(x))).
Nice to have:
The following security properties are desired of the blind signature system comprising the above functions and protocols:
Untraceable Payments systems
Before digging into the untraceable payment model introduced in this paper, we will first start by showing how traditional digital payments systems work.
In order to add the anonymity part, we make the following changes:
- Preparation step: Payer chooses x at random such that r(x), and forms c(x). Then, the payer forwards c(x) to bank.
- Signature step: Bank signs note s’(c(x)), and debits payer’s account. Then, bank returns the signed note, s’(c(x)) to payer.
- Signature verification step: Payer strips note by forming c’(s’(c(x))) = s’(x). Then, payer checks note by checking that s(s’(x)) = x and stops if false.
Now that the payer has a valid note, he can pay anyone with via sending s’(x).
After the Payee receives the s’(x), i.e. signed note, he goes through the following steps:
4. Local verification: Payee checks note by forming r(s(s’(x)) and stops if false. Payee then forwards note s’(x) to bank.
5. Bank verification step: Bank checks note by forming r(s(s’(x))) and stops if false. Then he, adds note to comprehensive list of cleared notes and stops if note is already on list, credits account of payee, and finally informs payee of acceptance.
So basically what happens in here, is that the Bank is able to verify that the money presented to it by the Payee is valid. However, it is not able to decide who the payer is (same as with the voting illustration) without his cooperation.
Auditability:
The model as it is can detect uncleared notes (via the verification mechanism done by the bank when receiving a note).
We can extend the current model to be auditable via the use of receipt. In fact, the payee can hand a receipt to the payer containing the details of the order as well as a copy of the note. Thus, we can have the following:
- With cooperation with the bank, know if the money was actually received by the wanted payee or there was some kind of fraud in there.
- A note supplied into the black market can be traced to know the final account it ended up in (with cooperation of the payee).
- Taxes can be calculated based on the receipts. This would make expenditures verifications possible and detection of illegal actions too.
Elaborations:
This model can be extended in various ways according to the needs. For example, periodic changes of the signing keys might increase security, auditability, and reduce uncertainty about the size of the money supply. Use of multiple banks to broaden the way notes are spent etc.
Conclusion
This scheme was actually implemented by David Chaum in 1989, under the name of Digicash, with eCash their flahship solution. It flourished for a certain period of time, was recognized by Credit Suisse in Switzerland, was available from Deutsche Bank in Germany, Bank Austria etc. However, it went bankrupt in 1998, along with ecash.
For further information check the resources below.