A Blind-Signature Protocol for Untraceable Electronic Payments
This paper presents a cryptographic framework for offline, untraceable electronic cash that preserves unconditional user anonymity while enabling reliable detection and provable attribution of double-spending through blind signatures and challenge-response protocols.
We propose a new anonymous payment scheme in which a bank issues blind-signed digital coins that users can spend untraceably. The design builds on Chaum’s classic electronic cash ideas, using RSA-based blind signatures and cut-and-choose techniques to thwart forgery while preserving payer privacy . As with earlier proposals, the central challenge remains double spending: a user might copy a coin and spend it twice. Our protocol makes double spending detectable (and optionally provable) by embedding cryptographic traps into each coin. Users withdraw coins from the bank via a blind-issuance protocol, spend them to merchants via a challenge–response subprotocol, and merchants deposit them back to the bank. We show how the bank can verify coin validity without learning who spent it, yet if a coin is deposited more than once the bank can identify the culprit. The scheme employs blind RSA signatures, bit‐commitment challenges (cut-and-choose), and one-way hash commitments. We also discuss extensions for explicitly proving double spending, issuing divisible “checks,” and adding revocable anonymity (e.g. blacklisting misbehaving users via group techniques). Our analysis demonstrates that in normal use, payer and payee anonymity hold unconditionally, while any attempt at double spending results in detection and identity linkage .
Introduction
In today’s economy, credit-card and online payment networks dominate but offer minimal privacy: each transaction links the buyer, merchant, and bank in a central ledger. By contrast, cash provides strong anonymity – no record links a spend to the spender – and hence is preferred when privacy is valued . Our goal is to bring “cash-like” privacy to the digital realm. Specifically, we seek a protocol where a user can withdraw digital coins from a bank and later spend them offline without the bank (or any observer) learning which coin came from which user, or even which merchant spent which coin. This “untraceable” property was first envisaged by Chaum .
Chaum’s pioneering work showed that blind signatures allow a bank to sign a coin token without seeing its identity . The bank thus issues a coin and deducts the user’s account, but the signature process is “blind” – the bank cannot later link that signature to the user’s account data. A merchant can later verify the signature to accept the coin as payment, and deposit it with the bank for redemption. Intuitively, this provides unconditional privacy on a single use of a coin . Indeed, Chaum proved that in such a scheme “if Alice uses a coin only once, her privacy is protected unconditionally” .
However, the double-spending problem looms large. Unlike paper money (which is hard to copy), digital coins can be trivially duplicated. As Chaum observed, “what is to prevent anyone from making several copies of an electronic coin and using them at different shops?” . One brute-force solution is to force the merchant to check with the bank (online) before every payment, but this defeats the offline convenience of cash and raises costs. In offline e-cash, the bank may only see a coin later during deposit, so if a coin appears twice it must act then. The open question is how to allow offline spending while ensuring that any double-spend reveals the cheater’s identity. Our protocol addresses this by incorporating a challenge–response step when spending, so that two different deposit transcripts for the same coin will allow the bank to recover the user’s identity.
Previous work has tackled privacy vs. double-spending in various ways. Chaum, Fiat and Naor (1988) used cut-and-choose blind signatures to build the first practical offline e-cash . They showed one can get unconditional anonymity for one-time spending, yet if a coin is reused “the bank can trace it to [the user’s] account and can prove that she has used it twice.” . Later schemes introduced a variety of accountability features: some add a trusted trustee or conditional signer to decrypt only in case of fraud , or use group signatures to revoke anonymity on abuse. Our work follows the Chaum approach but with new twists: we propose specific RSA-based algorithms (tailored for ~2005-era crypto) that achieve unconditional unlinkability under normal use, yet force a privacy breach upon any double-spending attempt, optionally even enabling a non-repudiable proof of fraud. As Chaum et al. noted, a cut-and-choose design can be “quite practical”and still let the bank produce “incontestable proof” of double spending . We elaborate this vision with original notation and detailed protocols.
Background and Related Work
Blind Signatures and E-Cash. A blind signature scheme lets a user obtain a signature on a message without revealing the message to the signer . Formally, the user picks a message $m$ and a random blinding factor $r$ and computes a blinded version $m’ = m,r^e \bmod n$ (for example in RSA). The signer computes $s’=(m’)^d \bmod n$ with its secret key. The user then unblinds $s’$, yielding $s = s’ r^{-1} \bmod n$, which is a valid signature on $m$. Importantly, the signer never sees $m$, so later cannot link $s$ back to the signing session . This unlinkability is what makes blind signatures ideal for privacy: “the signer is unable to link the blinded ballots it signs back to the un-blinded ballots…” . Digital cash schemes exploit this by letting a bank blindly sign a coin token. On withdrawal, the user gets a signed coin; on spending, anyone (including the bank) can verify the signature, but not know which account it came from.
Chaum (1982) first applied RSA blind signatures to e-cash . Fiat and Naor later refined the idea for offline coins . Typically, a coin is represented by a random serial $z$ and a signature $\sigma$ such that $\sigma^e = f(z)\ (\bmod\ n)$, where $f(\cdot)$ is a one-way function. The bank issues $(z,\sigma)$ via a blind-signing protocol, debiting the user’s account. On payment, the user gives $(z,\sigma)$ to a merchant, who checks $\sigma^e\equiv f(z)$ and then submits $(z,\sigma)$ to the bank for deposit. If $(z,\sigma)$ is fresh, the bank credits the merchant. If the bank ever sees the same $z$ twice, it detects a double-spend. However, to actually identify the cheater, the coin must somehow encode user identity in a hidden way.
Cut-and-Choose and Double-Spend Detection. Chaum et al.’s breakthrough was to embed identity ‘crumbs’ via a cut-and-choose challenge so that the bank can recover them only if the user double-spends . In their scheme, during withdrawal the user sends many blinded “candidate” coins; the bank randomly asks the user to open half of them to check consistency, and then signs the remaining ones in aggregate. The result is that the withdrawn coin contains hidden data (derived from the user’s secret account number) that will come to light if the coin is ever spent twice. Concretely, Chaum et al. note: “We use the cut-and-choose methodology … yielding quite practical constructions. The next section presents our basic scheme, which guarantees untraceability, yet allows the bank to trace a ‘repeat spender’. We then show how to modify the protocol so that the bank can supply incontestable proof that [a user] has reused her money.” . In other words, their design ensures that a single spend is anonymous, but a double spend either reveals the user’s identity (her bank account) or even provides the bank with cryptographic proof of fraud .
Later research explored similar ideas. For example, Stadler et al. introduced coin tracing mechanisms requiring an online trustee during withdrawal ; Camenisch et al., Frankel et al., and others built e-cash systems where a (possibly offline) trusted party or trapdoor could break anonymity on double spending . We adopt the underlying goal of unconditional anonymity per spend (as in Chaum’s scheme) but extend the protocol to incorporate modern blind-signature tools and to explicitly handle abuse proofs. Our system model assumes an honest-but-curious bank, users and merchants who do not collude, and anonymized communications (e.g. using mix networks) so that transaction flows cannot be trivially linked. The bank knows a user’s account ID and a counter $v$ for how many coins were withdrawn, but during issuance it learns nothing about the specific coin values being signed .
System Model and Goals
We consider three roles: Bank, Users (payers), and Merchants (payees). The bank holds an RSA key $(n,d)$, public exponent $e$, and maintains account records. Each user $A$ has a secret account number $u_A$. A user can withdraw an integer-valued coin (worth one dollar in our description) via an interactive blind-signature protocol with the bank. Later, she can present the coin to a merchant offline. The merchant will engage in a brief challenge-response with the user to verify the coin’s validity and prevent trivial forgery. Afterward the merchant contacts the bank to deposit the coin and have his account credited.
Adversary model. We assume a computationally-bounded adversary. Users and merchants follow the protocol honestly except possibly attempting to double-spend their own coins. The bank is trusted to execute its algorithms correctly but should not learn linkages: it should not be able to link a withdrawn coin to the withdrawing user, nor link a spent coin to either payer or payee, unless double spending occurs. In particular, even if the bank colludes with one party (e.g. an adversarial merchant), it should not learn additional information about honest users. We use anonymizing channels at withdrawal and payment so the bank cannot trivially correlate network addresses.
Security goals. The protocol must satisfy: Unforgeability (a user cannot create a valid coin except via withdrawing from the bank), Unlinkability/Anonymity (a withdrawn coin cannot be linked to a particular user or payment), and Double-spend detection (if the same coin is deposited twice, the bank detects it). Furthermore, we aim for conditional traceability: in case of double spending, the bank should be able to identify the offending user and optionally produce a publicly verifiable proof of the offense. This mirrors Chaum’s goal of “incontestable proof” for double spends .
Cryptographic Preliminaries
RSA and one-way functions. Let the bank publish an RSA modulus $n=pq$ of hidden factorization, and a public exponent $e$ (e.g. $e=3$ or $65537$). The private exponent $d$ satisfies $ed\equiv1\pmod{\phi(n)}$. We assume standard RSA hardness and work in the random-oracle model for hash functions. We use a one-way hash function $f(\cdot)$ or pairwise one-way functions $f,g$ to randomize coin values.
Blind signatures. Denote by $\mathit{Sign}_B(m) = m^d\bmod n$ an RSA signature by the bank on message $m$. A user can obtain $\mathit{Sign}_B(m)$ on a message $m$ without revealing $m$ by choosing random blinding factors $r$ and sending $m’ = m,r^e \bmod n$ to the bank. The bank returns $s’ = (m’)^d$, and the user unblinds $s=s’,r^{-1}\bmod n$ to get $m^d$ . By construction, $s^e = m$ mod $n$, and the bank never saw $m$. As shown in prior work, this ensures unlinkability: the bank cannot link the signature $s$ on $m$ to the blinded query it signed .
Cut-and-choose. To obtain a valid coin without cheating, the user will generate multiple blinded candidates. The bank will randomly ask the user to open some of them to verify they are well-formed (e.g. correspond to properly generated coin requests). With high probability, if the user cheats on any candidate, the bank will catch it. Only the unopened candidates are actually signed. This technique, pioneered by Rabin and used in Chaum’s e-cash, yields practical confidence that the remaining blind-signed coin is legitimate .
Protocol Definitions
We now detail the three main protocols: Withdraw (issuing a coin), Spend (paying a merchant), and Deposit (redeeming a coin at the bank). For clarity, we describe them in a step-by-step style. Let $e,d,n$ be the bank’s RSA key, and let $f,g$ be public one-way functions. Each user $A$ has an account number $u$ known only to the bank. Let $k$ be a security parameter (number of cut-choose candidates) that controls soundness.
Withdrawal (Bank $\leftrightarrow$ User)
User creates candidates: $A$ chooses random values $a_i,c_i,d_i$ and blinding factors $r_i$ for $i=1,\dots,k$. For each $i$, compute
$$ z_i = g(a_i,c_i),\qquad y_i = g(a_i;\Vert;(\mathrm{ID}| (v+i)),;d_i), $$
where $v$ is $A$’s current withdrawal counter and “$|$” denotes concatenation. Then form a blinded candidate $$ B_i = r_i^e \cdot f(z_i,y_i) \pmod n. $$
(Intuition: each pair $(z_i,y_i)$ encodes a potential coin value, with $y_i$ mixing in $A$’s ID. Blinding by $r_i^e$ hides the actual coin from the bank.)
Bank’s challenge: $A$ sends all ${B_1,\dots,B_k}$ to the bank. The bank randomly selects a subset $S$ of $k/2$ indices and asks $A$ to open those candidates. The user reveals the corresponding $(r_i,a_i,c_i,d_i)$ for $i\in S$. The bank checks that each opened $B_i$ is correctly formed, i.e. $B_i \stackrel{?}{=} r_i^e f(g(a_i,c_i),,g(a_i|(ID|(v+i)),d_i))\bmod n$. If any check fails, the bank aborts.
Bank signs remaining candidate: Let $T = {1,\dots,k}\setminus S$ be the unopened indices. The bank blindly signs each remaining $B_j$ (for $j\in T$) by computing $T_j = B_j^d \bmod n$. It also debits one dollar from $A$’s account and sets $v := v+k$ (incrementing the withdrawal counter by $k$). It returns all signed values $T_j$ to $A$.
User extracts the coin: The user picks one of the signed $T_j$ (or combines them) as the final coin. Concretely, since $T_j = (r_j^e f(z_j,y_j))^d = r_j f(z_j,y_j)^{d}\bmod n$, the user divides out $r_j$ to obtain $\sigma = f(z_j,y_j)^{d} \pmod n$. The coin is the tuple $(z_j,y_j,\sigma)$. By construction, $\sigma^e \equiv f(z_j,y_j)\pmod n$, so the bank’s signature is valid . The user records $(z_j,y_j,\sigma)$ and updates her internal counter $v:=v+k$ as well. (The counter ensures different communications will involve distinct values.)
This completes withdrawal. The bank charged the user and gave her a signed coin, but due to the blind blinding factors and unopened candidates, the bank learns nothing about $(z_j,y_j)$ beyond that the format is correct . The cut-and-choose check makes it infeasible for $A$ to withdraw a malformed coin without detection (with failure probability negligible in $k$).
Spending (User $\to$ Merchant)
To pay one dollar, the user $A$ and the merchant $M$ execute a challenge-response protocol to prove knowledge of a valid coin signature. This prevents trivial forgeries and sets up data for the bank to detect double-spends:
User gives coin: $A$ sends the coin $(z,y,\sigma)$ to $M$.
Merchant challenges: $M$ selects a random challenge bitstring $t=(t_1,\dots,t_{k/2})$, where each $t_i\in{0,1}$. He sends $t$ to $A$.
User responds: For each bit $t_i$ ($i=1,\dots,k/2$), $A$ does:
If $t_i=1$, $A$ reveals her random choice $a_i$, $c_i$, and the value $y_i$.
If $t_i=0$, $A$ reveals $z_i$, $a_i \oplus (u | (v+i))$, and $d_i$.
(These correspond to the two halves of the cut-and-choose deposit from withdrawal.)
Merchant verification: Using the responses, $M$ checks that for all $i$, the revealed values are consistent with the coin’s signature. Concretely, $M$ recomputes $g(a_i,c_i)$ or $g(a_i|(u|(v+i)),d_i)$ as needed, and verifies that $\sigma^e = f(z,y)$ remains correct and that the opened parts match the expected structure. If anything fails, $M$ rejects the coin. (Because $A$ does not know $u$ outright, she cannot convincingly answer both kinds of challenge for the same index without cheating.)
Deposit to bank: If $M$ is satisfied, he sends the full coin $(z,y,\sigma)$ and all of $A$’s responses to $t$ (both revealed values) to the bank as part of depositing the coin. The bank then proceeds to verify.
This challenge-response ensures that $A$ cannot alter the coin on the fly: she effectively must demonstrate consistency with the blind-signed data from withdrawal. Moreover, note that the challenge bits $t$ were random, so if $A$ ever spends the same coin with a different $t$, she will reveal complementary pieces of information. These pairs of transcripts will let the bank extract $u$ (her account number). The merchant itself does not learn $u$ and sees only one half of $A$’s hidden data, so $M$ gains no extra knowledge beyond verifying the signature.
Deposit (Merchant $\to$ Bank)
When $M$ presents $(z,y,\sigma)$ and the challenge transcripts to the bank, the bank does the following:
Check signature: Verify $\sigma^e \equiv f(z,y)\pmod{n}$. If not, reject. Also check that $z,y,\sigma$ follow the correct format (as would have been enforced during withdrawal).
Freshness: If this coin $(z,y)$ has never been deposited before, credit $M$’s account by one dollar and record $(z,y)$ as spent. The protocols above ensure $A$ truly had the bank’s signature on this coin (preventing forgery) and $M$ checked the structure.
Double spending detection: If $(z,y)$ is already in the spent-coin database, we have a double-spend. In this case, the bank examines the two deposit transcripts for $(z,y)$ (the one just received and the one earlier). Together, they contain two challenge responses $(a_i,c_i,y_i)$ and $(z_i,a_i\oplus(u|(v+i)),d_i)$ for each $i$ (with different challenge bits). From these, the bank recovers $a_i$ and the quantity $(u|(v+i))$ for each $i$ – hence learning the user’s account number $u$. In short, the bank identifies the culprit user. It can then optionally prove this fact by exhibiting the two transcripts and showing they are inconsistent with a single-user anonymity (this is “incontestable proof” of misbehavior ).
Thus, any reuse of a coin inevitably links back to the spender’s identity. In a normal single-spend case, the bank remains oblivious to who spent the coin, since the challenge bits and opened halves hide $u$. But a second spend leaks enough information to break anonymity . This achieves our goal: untraceability in normal use, with automatic detection and linkage of double-spends.
Security Analysis
Unlinkability (Anonymity). By construction, the bank never learns the coin’s serial $(z,y)$ during withdrawal, only signing a blinded value. Likewise, during spending, the merchant’s view is one specific challenge transcript and signature, which also hides $u$. As proven in the blind-signature literature, an RSA blind signature is unlinkable: the signature on $f(z,y)$ contains no information that the bank can correlate with the user’s account . Even the cut-and-choose protocol does not leak $u$ on a single spend, since the user answers only one branch of each challenge. In fact, Chaum et al. observed that “if Alice uses a coin only once, her privacy is protected unconditionally” . Formally, for any two honest users spending coins, the bank sees only valid signatures on random-looking hashes, so it cannot distinguish which user produced which coin. An adversary with computational power bounded by the RSA or hash assumptions cannot link a coin to its withdrawal.
Unforgeability. A valid coin $(z,y,\sigma)$ is accepted only if $\sigma^e = f(z,y)$. Since $f$ is one-way and collisions are hard, forging a new $\sigma$ for a new $(z,y)$ requires either breaking the RSA signature or finding $(z,y)$ such that $f(z,y)$ has a known cube root mod $n$. Under standard RSA assumptions, this is infeasible. Moreover, the cut-and-choose step ensures a cheating user cannot get the bank to sign an ill-formed coin without detection. Thus only coins withdrawn via the protocol can be spent.
Double-spend detection. If a user attempts to spend the same coin twice, the bank will eventually see two different deposits of $(z,y)$. As described, the two challenge transcripts reveal $u$. This detection is inevitable in our design: each coin encodes a cryptographic “tag” that ties it to the user’s account. Chaum et al. prove that this tracing is certain: “if Alice reuses a coin, the bank can trace it to her account” . In practice, the merchant must deliver transcripts faithfully. Even if a malicious merchant colludes by altering transcripts, the bank itself will still check consistency and will spot any discrepancy as a forking attempt. After detection, the bank can (and should) take action, such as blacklisting the user or initiating legal proceedings.
Proof of fraud. By including the entire transcripts in the deposit, we ensure non-repudiation: the bank can publish (or sign) the relevant data to show the two spends were from the same user. The user cannot plausibly deny the inconsistency, since both transcripts were signed by the bank. In other words, double spending is not only detected but provably attributable to a specific account, achieving incontestable proof of fraud .
Privacy trade-off. Note that this accountability comes at the cost of anonymity if a user cheats. This is by design: our policy is akin to cash with a “silk bag” – privacy is absolute unless a user breaks the rules (double-spends), in which case anonymity is revoked. Honest users enjoy unconditional unlinkability in single-spends . There is no trusted third party except the bank itself. The merchant does not learn $u$ and cannot link coin uses either.
Overall, the scheme satisfies the stated goals under the assumption that RSA and hash functions are secure, and that the bank honestly executes the algorithm (without injecting hidden watermarks or colluding with users). It aligns with known theoretical bounds: unconditional anonymity for single spends, with only cheating triggering identification .
Extensions and Variations
Several enhancements are possible:
Provable double spending: We sketched above how the bank obtains the user’s identity from two transcripts. To make this evidence public or court-admissible, the bank could sign its deposit record containing both transcripts. A zero-knowledge argument or non-interactive proof linking the transcripts to a specific account could also be constructed. In any case, by Chaum et al.’s reasoning the protocol can be augmented so the bank supplies “incontestable proof that [a user] has reused her money” .
Divisible coins / checks: A coin might be made divisible, allowing multiple sub-payments from one withdrawal (as in Brands’s divisible e-cash). For example, the bank could issue a higher-value coin which the user can then split into smaller coins by generating partial blind signatures. Alternatively, one can issue multi-use checks by embedding a spending counter or re-issuance token. These extensions complicate the protocols but follow similar principles: each sub-coin would carry a trapdoors so that if any part is double-spent, the user is caught. Designing an efficient offline divisible scheme is left for future work.
Anonymous blacklisting (group issuance): One can add revocation features by leveraging group-signature or credential techniques. For instance, at withdrawal the bank could issue the coin within a group signature or accumulator context so that if the user misbehaves, a revocation list of identities prevents further withdrawals. Concretely, the bank might maintain a blacklist of double-spenders’ account-public-keys, and require proof at withdrawal that the user is not blacklisted (using a zero-knowledge set membership proof). This would preserve anonymity for honest users while preventing known offenders from obtaining new coins. Group or ring signatures could similarly be used so that only a colluding bank and trustee could reveal a user’s identity. While detailed construction is beyond our 2005-style scope, this idea follows existing blacklistable anonymous credentialsliterature .
Higher denominations: We focused on 1-dollar coins for simplicity. Larger values or multiple denominations can be handled by parallel issuance. A user could withdraw, say, a 10-dollar coin by obtaining 10 parallel one-dollar coins (with links across them), or by an RSA signature on a composite value. Either way, double-spending any part reveals the user similarly.
Conclusion
We have presented a formal offline e-cash protocol achieving unconditional anonymity for honest users and robust double-spending accountability. By combining RSA blind signatures with cut-and-choose, our scheme lets a bank blindly issue signed tokens that users pay with privately. The novel challenge–response spending protocol ensures that any attempt to reuse a coin causes the user’s identity to surface. All operations can be described with simple mathematics (blind-signatures, hashes, XOR, etc.) and withstand standard cryptographic assumptions. This work extends the classic Chaumian e-cash paradigm with explicit proofs and attack detection mechanisms. As of 2005, it represents a state-of-the-art approach to privacy-preserving payments: fully unlinkable under one-time use, yet securely traceable on fraud .
Acknowledgments: We thank the pioneers of anonymous e-cash for their foundational ideas, and we build upon them with fresh techniques consistent with mid-2000s cryptography.
