Exploring Blind Signatures, the OG Anonymous Cryptocurrency
We’ve spent decades trying to replicate the anonymity we enjoy spending cold hard cash. With cash, the central banks are blind to what you spend your money on; Once spent, the bank can’t link the cash you’ve spent to the cash they receive.
This post will guide you through the world of blind signatures, starting from a high level, and as you continue reading further down, we’ll delve into the intricate cryptographic constructions, their relevance, impact, and promising future.
Introduction
You’re probably familiar with the concept of signatures. Write a letter, and sign it to convince the receiver that it was actually you who wrote it. Similarly in the digital world, connecting to a website with HTTPS helps build trust in the server you’re connecting to is actually who you want to be connecting to.
By 1982, Cryptographer David Chaum realised the implications of the trend towards digital finance and a future dystopia where general users lost the privacy and freedom of spending cold hard cash.
And that’s when he published his thoughts on blind signatures and how they can be used to preserve privacy in the digital world.
What are Blind Signatures?
Blind Signatures are a form of digital signature where the content of a message is disguised before it is signed. The entity signing the message can’t see its content, which is the essence of the “blind” signature. Only after the signature is applied does the message become “unblinded,” revealing the original content plus the signature. This mechanism is critical for ensuring privacy and anonymity in digital transactions, such as e-voting or cryptocurrency transactions.
The security of a blind signature scheme requires 3 critical properties:
- Blindness: the signer learns nothing about the message they’re signing
- Unforgeability: the user can’t forge a signature
- Unlinkability: the signer can’t distinguish between a signed message or a blind-signed message
A standard signature scheme involves 2 main functions — signing, and verifying. Blind signature schemes will need at-least 2 additional functions, blinding, and unblinding. Here’s a simplified analogy
1. Message: You write a absentee letter on a piece of paper with a pen 📝
Blinding the message
2. You then colour the entire paper with lead pencil 📜 hiding your letter
Signing the message
3. You ask your parents to sign the paper with their special stamp.
Their special stamp can't be rubbed off
Unblinding the signed, blind message
4. You use an eraser to remove the pencil but your parents stamp stays
5. You have the original message in pen with your parents special stamp
You can now use your stamped letter to leave school.
Your parents don't know what they signed, and the school sees their
special stamp and knows it came from your parents.Applications of Blind Signatures
David Chaum’s paper envisioned two key applications, digital cash and anonymous identity in e-voting, I’ll discuss them further below. More recently, Monero, the private anonymous cryptocurrency uses Blind Ring Signatures, a variant of blind signatures, Idemix, an anonymous credential system developed by IBM and secure voting and lottery systems.
Digital Cash
Imagine all the cash in circulation has been signed by the central bank. When I spend cash, the receiver, recognising the bank’s signature and confident that the cash wasn’t printed in my garage, trusts its value. If I were to pay digitally, however, the bank would know how much I’m spending because digital cash needs to be signed by the bank. Woolworths wouldn’t accept my digital cash unless it’s signed by an authority.
In that case, I’d make my digital cash bill, ask the bank to sign it and verify I have the balance, and then I can pay with my signed digital cash.
Here lies the privacy issue, the bank is now aware of what you do with your money.
Using blind signatures, I can blind, or obfuscate the message before sending it to the bank for signing. This blinding hides the content of the message. I can now spend digital cash without disclosing more information than I’d like.
Anonymous Identity in E-Voting
Similarly, voting systems need to ensure that the voter is authorized to vote whilst remaining anonymous. Using blind signatures, voters can blind their vote, request an authority’s signature, unblind the vote, and send it to the voting centre, ensuring their anonymity.
What do you do with a blind signature?
Unlike a physical message inside an envelope, digital messages, at a fundamental level, are a series of 1’s and 0’s. With complex mathematics and cryptographic magic, the message can be blinded, signed, and unblinded to the point the user has a signed message from an authority that looks exactly like one that was never blinded.
Why will the authority sign a blind message?
Seemingly, an authority signing a message is a liability, why would they sign? In some schemes, the content of the message isn’t important. Alternatively, protocols can build trust between the signer and the requester by convincing the authority the message is valid. A few methods to build trust between the signer and requester include:
Cut-and-choose: is an interactive protocol referring to the analogy of cutting a cake for you to share with a friend. You slice, and your friend will select the largest piece. You will naturally want to cut it fairly otherwise your friend will select the biggest piece.
In actuality, the first party presents multiple instances of a computation or task, the chooser randomly selects some of these to verify themself. The remaining are used in the computation.
The concept was first found in Michael O. Rabin’s 1979 paper where one party convinces another party they know some information; Rabin proved this with modulo arithmetic.
Challenge-Response: one party, e.g. the bank, sends a random challenge to the user who must then send a valid response back based on their knowledge of the information they have. This helps verify the responding party knows and cannot prepare answers in advance.
Zero Knowledge Proof: Undoubtedly the most popular knowledge proof framework dating back to Goldwasser, Micali, and Rackoff in their 1987 paper Knowledge Complexity of Interactive Proof-Systems the user can privately prove against knowledge of the message.
Evolution of Blind Signatures
David Chaum’s 1982 paper “Blind Signatures for Untraceable Payments” describes a signature scheme using modular arithmetic and 3 key functions — Blind & Unblind, Sign, Redundancy check.
Informally, Blind Signatures schemes are secure if observing the following properties:
Blindess — the signer should learn nothing about the message, nor the signature
Unlinkability — The signer can’t distinguish between a blindly signed and normally signed message
Unforgeability — it’s computationally infeasible for an adversary to generate a valid signature
Restrictive and Traceable Blind Signatures
Stefan Brands proposed these signatures in his 1994 thesis which both prevents double-spending and adds accountability in digital cash systems. The additional security properties Brands focused on are:
Restrictive — preventing the user from double-spending their balance prior to transacting
Traceability — if a user gets away with double-spending, the user will become traceable
Fair Blind Signatures
Realising the possible negative consequences of an anonymous payment system, one that could be used for black-mailing or money laundering, Stadler, Piveteau, and Camenisch proposed the idea of a trusted entity that could reveal the message-signature pair. Security property included:
Fair — the signer can receive information from a “judge” to efficiently recognise a message-signature pair and extract the message or efficiently recognize the sender of a message
One-More Unforgeability — Provably secure blind signatures
An additional security property proposed by Pointcheval and Stern in 1996 to ensure an adversary who has multiple signatures can’t generate a valid signature without interacting with the signer. Labelled as Existential forgery under an adaptively chosen message. They highlighted the previous security proofs were invalid and added the security property:
One More Unforgeability: an adversary who obtains n+1 signatures cannot generate n+1 valid signed messages after interacting only n times with the signer (cannot forge the +1 signed message themselves)
Partial Blind Signatures
To prevent double spending, previous blind-signature based electronic cash systems were required to keep a list of the spent coins which would ultimately grow over time. Abe and Fujisaki in 1996 set out to improve that with the additional of “partial blindness”. A partially blind signature allows a signer to include information in the signature (a tag), that could include the value of the coin and a date of issuing.
The partially blind signatures are secure if they satisfy the following properties
Partial Blindness: for multiple signatures with the same tag values, the adversary can’t distinguish between each signature, nor the session they were signed
Threshold Blind Signatures
The signature schemes discussed above entrust the security of the protocol to 1 honest signer. But a dishonest, adversary signer can abuse their power — in the e-cash example, could endlessly issue cash or even refuse to sign. To prevent this, and distribute the signing authority to more than 1 signer, Juang and Lei proposed a thresholdization of the blind signature scheme, entrusting the minimum threshold (t) of signatures from (n) nodes.
Thresholdization: control of the blind signing is distributed among a quorom, each with a partial key. The quorom signs a valid signature when the scheme’s threshold limit of signatures are combined, otherwise, the scheme isn’t successful.
Blind Signatures + Zero Knowledge Proofs
Jan Camenisch and Anna Lysyanskaya contributed to Blind Signatures and Anonymous Credentials through a series of inventions introducing zero knowledge proofs
we allow a user to prove in zero-knowledge the knowledge of a signature on a committed (or encrypted) message and to obtain a signature on a committed message. Camenisch & Lysyanskaya, 2005, Signature Schemes and Anonymous Credentials from Bilinear Maps
Let’s say I wanted to buy a concert ticket to a special concert and I’d rather not share my details with the concert organiser. But the concert requires I’m over 18 with a certain membership status.
With Blind Signatures, I can commit to my personal attributes, blind them, and ask the government as an authority to sign off on my attributes.
With Zero Knowledge Proof, I can use the blinded signature to prove aspects of my attributes without revealing information on identity
Attribute-Based Blind Signatures
Khader’s 2007 paper was the first paper to mention attribute-based blind signatures; Each private key in Khaders scheme contains the users attributes which they can use to verify their attributes.
Weak, Strong, Weak partially, Strong partially
A 2023 paper by Doerner, Kondi, Lee, and Shelat built upon Camenisch and Lysyanskaya’s works, as well as many other cryptographers working on Anonymous Credentials. Notably, the paper defined 4 properties that explain the protocols behaviour and properties when combining Blind Signatures and Zero Knowledge Proofs
Weakly-blind - only the message is hidden from the signer
Strongly-blind - the message and signature is hidden from the signer
Weak partially-blind - message is hidden from the signer + signer receives proof the message satisfies some predicate
Strong partially-blind - the message and signature is hidden from the signer + signer receives proof the message satisfies some predicate
Non-interactive Blind Signatures for Random Messages
Lucjan Hanzlik in 2023 proposed the issuance of pre-signed random message that recipients can use anonymously. An example of how this works:
Let’s think of a scenario where the bank wants to pay their depositors $100 for being good customers. Hanzlik’s protocol enables the bank to issue a pre-signed “voucher” to a users public key which they can then use blindly.
Non-interactive - a signer issues a pre-signed random message that the recipient can use as a blind signature
Illustrated below, the bank first issues the pre-signed randomized message with their secret key, the recipients public key, and a random nonce. The user then finalizes the signature with their own secret key. The result is a signed unblinded message that can be used anonymously anywhere a bank-issued voucher is accepted. The bank can’t link the voucher back to the user.
Post-Quantum Blind Signatures
Lattice-based signature schemes are a part of post-quantum cryptography, believed to be secure against an attack by a quantum computer. Lattice-based and blind signature schemes are a current hot topic with recent advances.
Cryptographic Constructions
Many prominent digital signature schemes support blind signatures. The essential quality needed is a kind of homomorphic property that enables performing operations on the blinded, signed message that correspond to operations on the original message. Several signature schemes supporting blinding include RSA, BBS, Pointcheval-Stern, Okamoto-Schnorr, and ECC (Eliptic Curve Cryptography)
RSA
RSA encryption showcases a multiplicatively homomorphic property, signifying the product of two encrypted messages is equivalent to the encryption of the product of the original messages, represented as:
E(m1) * E(m2) = E(m1 * m2)A (simplified version) of the RSA blind signature scheme can be illustrated with emojis:
You start with a message 💬
The signer has a public/private key pair (🔑,🔐)
Start with your message
1. Blind your message 💬
Multiply 💬 with a random factor 🎲 raised to the power of the public key 🔑
💬 * 🎲 ^ 🔑 -> 🗨️
This creates a blind message 🗨️
2. Get the blind message signed
The signer applies their private key 🔐 to the blind message,
resulting in a signed blind message (🗨️,🔐)
3. Unblind the signed message (🗨️,🔐)
You unblind the message by reversing your blinding factor calculation
(🔑√🗨️/🎲),🔐)️ -> (💬,🔐)
resulting in a signed, unblinded message (🔐, 💬)
4. Verify
apply the public key 🔑 to the signed message 💬,🔐
(💬,🔐) ^ 🔑 -> 📦 (valid) / ❌ (invalid)Modular multiplicative homomorphism in RSA is demonstrated through a simple arithmetic operation mod 7.
Let's use Mod 7 in our example.
1. A quick refresh
- 8 mod 7 = 1 (because 7*1 + 1 = 8)
- 14 mod 7 = 0 (because 7*2 + 0 = 14)
2. Comparison
- Multiply 8 * 14 (2 numbers from above) = 112
- 112 mod 7 = 0
3. Using modular residues from section 1.
- Multiply 1 * 0 (because (8 mod 7) * (14 mod 7) === (1 * 0)
This is the modular multiplicative homomorphic property in RSA Bilinear Map Blind Signatures
The core idea behind blinding is similar between RSA and Bilinear Maps, the difference is in their mathematical structures. Bilinear Maps use their inherent properties i.e. e:G x G -> GT the map between bilinear groups to perform blinding and unblinding
Setup
- You start with a message 💬
- The system picks a bilinear group of prime order p, and generators G1,G2
- The signer has a pk/sk pair, pk in G1, sk in G2 (🔑G1,🔐G2)
- User picks a random number 🎲 in G1
1. Blind the message in G1💬 with the random number 🎲
The message in G1💬 is mapped to a blinded message in G2🗨️
This is some operation in the bilinear group, e.g.
Raise 💬 to the power of the random number 🎲
💬 ^ 🎲 -> 🗨️
2. Sign the blinded message
Signing occurs in G2
Signer uses their private key 🔐
This is some operation, e.g. raise 🗨️ to the power of the private key 🔐
🗨️ ^ 🔐 -> 🖋
3. Unblind the signed blind message 🖋 with the random number 🎲
Unblinding occurs in G1
This is the opposite of the blinding function, e.g.
Raise 🖋 to the power of the inverse random number 🎲
🖋 ^ (1/🎲) -> (💬🔐) where 💬🔐 is the signed unblind message in G1
note: this is a simplified/normalised explanation and may not resemble a true schemeOkamoto-Schnorr Eliptic Curve
Elliptic Curve Signatures uses the properties of the bilinear map associated to the elliptic curve but with the operations on elliptic curve.
Setup
- Elliptic curve generator point 🌈
- Signer has pk,sk (🔑,🔐) a point on the elliptic curve. 🔑=🔐*🌈
- User selects random blinding factor 🎲 on the curve
- n is the order of the elliptic curve group
1. Blind your message 💬
- Calculate R = 🎲 * 🌈
- Calculate S = 🎲 * 🔑
- h = Hash(m||R||S)
- blind h by computing h' = h + 🎲 mod(n) -> 🗨️
2. Sign the message
Signer receives the blind message 🗨️ and signs with sk 🔐
🗨️ * 🔐 mod(n) -> (🗨️,🔐)
3. Unblind the message
(🗨️,🔐) - 🎲 mod(n) -> (💬,🔐)Schemes that don’t support blinding
The ECDSA signature scheme does not support blinding because of 2 properties, 1) it uses a random secret (nonce) and 2) the hash function it uses to hash the message.
1. The scheme creates a unique, random secret 🎲:
It's needed for signature creation. We will call it 🎲
2. The scheme hashes your message 💬:
The hased message is a random number representing the message, without revealing information about it
Hash(💬) -> 📦
3. Generate the signature:
Use the signer's private key 🔐,
the random secret 🎲,
and the hashed message 📦
(🔐, 🎲, 📦) -> (📝1, 📝2)
The signature is a pair of values, 📝1 and 📝2.- Random secret (nonce): as you can see in step 1. ECDSA needs to generate a random secret number 🎲 that it uses in the signature generation in step 3. (🔐, 🎲, 📦) -> (📝1, 📝2). This random number isn’t known by the user — if the user tried to blind, sign, then unblind the unblind the message, the generated signature wouldn’t correspond to the original message when unblinded.
- Hash of the message: in step 2 we see the message being hashed. Hash functions are special one-way functions, easy to compute but hard or impossible to reverse. Hash functions destroy the structural or mathematical relationship with the original message, breaking any homomorphic properties needed to unblind the signed message.
While some cryptographic schemes like RSA support blind signatures due to their homomorphic properties, others like ECDSA do not. Understanding the underlying principles and limitations of these cryptographic schemes is essential for creating secure, anonymous digital systems.
Summary
The article provides an in-depth look at blind signatures and their role in cryptography. Blind signatures, a concept introduced by David Chaum, help ensure privacy in digital transactions. Like standard digital signatures, blind signatures offer integrity, non-repudiation, and authenticity, but with the added advantage of maintaining the sender’s anonymity.
Thanks!
Thanks for reading. If you find anything that needs revising, is incorrect or general feedback, please leave a comment on Medium or message me on Twitter
Resources
