💻 computer science

Automatic Teller Machines for Offline E-cash

This paper proposes a new cryptographic bearer token design for fully offline e-cash systems that enables anonymous, unforgeable, and untraceable coin withdrawals via ATMs without requiring a central bank connection during the transaction.

Original authors: Anrin Chakraborti, Qingzhao Zhang, Jingjia Peng, Morley Mao, Michael K. Reiter

Published 2026-04-15

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Anrin Chakraborti, Qingzhao Zhang, Jingjia Peng, Morley Mao, Michael K. Reiter

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Digital Cash Without the Internet

Imagine you have a digital wallet. Usually, to get money into it, you have to call the bank (the central authority) and ask for cash. The bank checks your balance, prints a digital coin, and sends it to you. This works great, but what if the internet goes down? Or what if you are in a remote area with no signal? You can't get cash.

Physical cash solves this. You go to an ATM, and it gives you money even if it's not currently talking to the bank. The ATM is just a "proxy" for the bank.

The Problem:
In the digital world, making an "ATM" that works offline is hard. If an ATM gives you a digital coin, how does the bank know it's real? And how does the bank know the ATM didn't just print a million fake coins and give them to a friend? Also, if the ATM knows who you are, it breaks your privacy.

The Solution:
This paper proposes a new way to build a digital cash system where ATMs can give you coins offline, without needing to call the bank first. It keeps your identity secret, prevents forgery, and ensures that if someone tries to cheat, the bank can catch them later.

The Core Idea: The "Magic Voucher"

To make this work, the authors invented a special tool called a "Doubly-Anonymous Voucher."

Think of it like this:
Imagine you go to a magic vending machine (the ATM). You want a chocolate bar (a coin).

The Old Way: The machine asks the factory (the Bank) for permission. The factory says, "Yes, give them a bar." The machine gives you the bar.
The New Way: The machine already has a stash of bars. You walk up, and the machine hands you a bar and a special, sealed envelope (the Voucher).

Why the envelope?
The envelope proves two things without revealing who you are:

Proof of Origin: It proves the bar came from the factory, not a counterfeiter.
Proof of Ownership: It proves the bar belongs to you specifically, but it doesn't tell the shopkeeper (the merchant) or the factory who "you" are.

If you try to spend the same bar twice, the magic envelope will burst open, revealing your name to the factory so they can punish you. But if you spend it once, your name stays hidden.

How It Works: The Three Characters

Let's break down the players in this story:

The Bank (The Factory): The only one allowed to make real money. It's "honest but curious"—it wants to stop fraud but doesn't care who spends what, as long as the rules are followed.
The ATM (The Proxy): It holds a stock of pre-made coins. It acts like a physical ATM. It can give you coins even if the internet is down.
The User (You): You withdraw coins from the ATM and spend them at a shop.

Step 1: Stocking the ATM (Offline Withdrawal)

Before you even show up, the ATM goes to the Bank (when it has internet) and asks for a big bag of coins.

The Bank signs these coins with a secret "magic ink."
The ATM puts them in its safe.
Crucial: The Bank doesn't know who will eventually buy these coins. It just knows the ATM has them.

Step 2: You Get Your Coin (The Fair Exchange)

You walk up to the ATM. You want a coin.

The Risk: What if the ATM takes your money (or promises to debit your account) but doesn't give you the coin? Or what if you get the coin but refuse to let the ATM debit your account?
The Fix: They use a "Fair Exchange" trick.
1. The ATM shows you a sealed promise (a receipt) saying, "I have a coin ready for you."
2. You sign a receipt saying, "I promise to pay if I get the coin."
3. The ATM gives you the coin and the Magic Voucher.
4. You give your signed receipt to the ATM.
5. The ATM sends your receipt to the Bank later to deduct the money.

If the ATM cheats and doesn't give you the coin, you can show the Bank your signed promise and the ATM's failed promise. The Bank will see the ATM lied and punish it.

Step 3: Spending the Coin

You go to a shop to buy coffee. You hand over the Coin and the Magic Voucher.

The shopkeeper checks the magic ink to make sure the coin is real.
The shopkeeper checks the voucher to make sure you are the one who got it from the ATM.
The Magic: The shopkeeper sees the coin and the voucher, but they cannot see your name or which ATM you used. You are anonymous.
The shopkeeper sends the transaction to the Bank.

Step 4: Catching the Cheaters

What if you try to spend the same coin twice?

The Bank receives two transactions for the same coin.
Because of the math behind the "Magic Voucher," the Bank can now solve a puzzle. The two transactions reveal your secret identity.
The Bank says, "Aha! You double-spent!" and bans you.

What if the ATM tries to give the same coin to two different people?

The ATM has a secret "double-issue token" inside the voucher.
If the Bank sees the same coin issued twice, the math reveals the ATM's identity.
The Bank says, "Aha! This ATM is printing fake money!" and shuts it down.

Why is this a Big Deal?

It's Offline: You don't need a signal to get cash. Just like a physical ATM.
It's Private: The shop doesn't know who you are. The Bank doesn't know where you spent your money. Only the ATM knows you were there, but even then, it's hard to link you to the specific coin later.
It's Secure: It prevents "double-spending" (using the same digital dollar twice) and "double-issuing" (ATMs printing fake money).
It's Fast: The authors tested this on a Raspberry Pi (a tiny, cheap computer). It took less than a second to withdraw and spend a coin. That's fast enough for real life!

The "Compact" vs. "Non-Compact" Choice

The paper offers two versions:

Non-Compact: The ATM needs to store a lot of data for every single coin. It's like carrying a physical ledger for every dollar. It's faster to withdraw but takes up more space.
Compact: The ATM uses a clever math trick to store thousands of coins in a tiny space (like a compressed zip file). It takes a tiny bit longer to withdraw, but it saves massive amounts of memory.

Summary

This paper designs a digital cash system that works like physical cash: you can get it from a machine without internet, spend it anonymously, and the system is smart enough to catch anyone who tries to cheat, all while keeping your privacy intact. It's a step toward a future where digital money is as convenient and private as a dollar bill in your pocket.

1. Problem Definition

Electronic cash (e-cash) systems typically rely on a central bank for coin issuance. This creates a single point of failure and a critical path dependency: if the network connection to the bank is disrupted, users cannot withdraw funds. While physical currency allows for decentralized withdrawal via ATMs, existing e-cash schemes struggle to replicate this securely.

The authors identify three main challenges in designing a multi-issuer e-cash system (where ATMs act as issuers):

Anonymity vs. Traceability: If coins carry the ATM's signature, the user's withdrawal location is revealed, violating anonymity. Coins must be untraceable to their specific issuer (ATM).
Malicious Actors: ATMs may be compromised or behave maliciously (e.g., double-issuing coins to debit a user's account without providing the coin). Users may also attempt to double-spend.
Fair Exchange: In an offline setting, ensuring that a user receives a coin only after the ATM is debited (and vice versa) is difficult without a trusted third party (TTP).
Efficiency: Existing "transferable e-cash" schemes (which allow arbitrary coin transfers) are too heavy for this use case. They require "coin transparency" (randomizing coins at every transfer), leading to massive storage and computational overhead (e.g., ~19KB per coin).

Goal: Design an e-cash scheme with multiple issuers (ATMs) controlled by an honest-but-curious bank that guarantees unforgeability, anonymity, untraceability (of the ATM), and fair exchange, while maintaining the efficiency of standard single-issuer e-cash.

2. Methodology and Construction

The authors propose a novel cryptographic bearer token design that decouples the coin from the ATM's identity during issuance but links them cryptographically for dispute resolution.

Core Components

Doubly-Anonymous Voucher: The central innovation is a "voucher" that records the transaction between an ATM and a user.
- It is unforgeable: Only an ATM with a bank-signed key can generate it.
- It is doubly anonymous: It hides the identities of both the ATM and the user from the merchant and the bank unless a double-spend or double-issue occurs.
- It is non-transferable: Unlike transferable e-cash, this voucher is tied to a specific user-ATM transaction and cannot be passed between users arbitrarily.
Cryptographic Primitives:
- CL Signatures (Camenisch-Lysyanskaya): Used for blind signatures, allowing the bank to sign user/ATM keys without knowing the underlying values, preserving anonymity.
- Pseudorandom Functions (PRF): Used to generate unique identifiers for coins and double-spending tokens.
- Pedersen Commitments: Used to bind values (like private keys) without revealing them.
- Non-Interactive Zero-Knowledge Proofs (NIZK): Used to prove knowledge of signatures and correct computation of tokens without revealing secrets.

Protocol Flow

Initialization: The bank issues blind signatures to ATMs and users on their identity keys.
Coin Stocking (Offline): ATMs periodically request a batch of coins from the bank. The bank blindly signs PRF keys held by the ATM. These coins are stored locally on the ATM.
Withdrawal (ATM to User):
- The ATM selects a coin from its local stock.
- The user commits to their identity and spending key.
- The ATM generates a Voucher containing:
  - A unique identifier ( $X$ ) linking the coin to the user's commitment.
  - A Double-Issuing Token ( $Y$ ) that embeds the ATM's identity but remains hidden via PRF.
  - NIZK proofs verifying that the coin was bank-signed and the tokens are correctly computed.
- Fair Exchange Mechanism: To prevent the ATM from taking the user's money without giving the coin (or vice versa), they use an Optimistic Fair Exchange:
  - The ATM signs a promise (commitment) to the coin.
  - The user signs a receipt.
  - The ATM releases the coin.
  - If the ATM fails to release the coin, the user sends an AbortWithdrawal message to the bank. The bank logs the commitment; if the ATM tries to spend that coin later, the bank detects the discrepancy and identifies the ATM.
Spending (User to Merchant):
- The user presents the Coin and the Voucher to the merchant.
- The user computes a Double-Spending Token ( $Z$ ) using their spending key and the merchant's public key.
- The merchant verifies the bank's signature on the coin, the validity of the voucher, and the NIZK proofs.
- The merchant deposits the transaction to the bank.
Bank Verification & Dispute Resolution:
- The bank checks for double-spending (two transactions with the same coin but different $Z$ values). If found, it mathematically derives the user's identity.
- The bank checks for double-issuing (two vouchers with the same coin but different $Y$ values). If found, it derives the ATM's identity.
- The bank checks against the InvList (from AbortWithdrawal messages) to ensure no invalid coins are spent.

Optimizations

Compactness: The authors offer a "compact" version where an ATM reuses the same PRF keys for $N$ coins, using a counter and range proofs to prevent reuse. This reduces storage but increases computational latency.
Fully Offline Withdrawals: To handle network disruptions, ATMs can dispense coins without checking the user's real-time balance. The bank broadcasts a Bloom filter of "low-balance" accounts. If a user is not in the filter, the ATM dispenses cash. Overdrafts are detected later via signed receipts, and penalties are enforced.

3. Key Contributions

New Security Model: Formalized the requirements for multi-issuer e-cash, introducing Untraceability (hiding the ATM's identity) and Fair Exchange (handling disputes without a TTP in the critical path).
Doubly-Anonymous Voucher: A novel primitive that links a coin to a user and an ATM for accountability without revealing identities during normal transactions.
Efficient Construction: Built upon the compact e-cash protocol of Camenisch et al. [14], adapting it for multiple issuers without the heavy overhead of transferable e-cash.
Fair Exchange Protocol: A practical mechanism using signed receipts and abort messages to ensure atomicity between ATM and user in an offline setting.
Implementation & Benchmarks: A full C++ implementation demonstrating feasibility on resource-constrained devices.

4. Results and Performance

The authors implemented the scheme (named "StreetCred") and benchmarked it on three platforms: a Server CPU, a Raspberry Pi 4, and a Cloud VM.

Coin Size: 1 KB (constant size, consisting of 3 Pedersen commitments and 1 blind signature). This is significantly smaller than transferable e-cash schemes (e.g., ~19 KB in [6]).
Voucher Size: ~55 KB (dominated by NIZK proofs).
Transaction Size: ~2 KB.
Latency (Server CPU):
- Withdrawal (User + ATM): ~74 ms.
- Spending (User + Merchant): ~72 ms.
Latency (Raspberry Pi 4):
- Withdrawal: ~508 ms.
- Spending: ~424 ms.
Conclusion: The system is efficient enough for real-time applications even on low-end hardware like the Raspberry Pi. The non-compact version is preferred for ATMs with sufficient storage, while the compact version is available for storage-constrained scenarios.

5. Significance

This work bridges the gap between the theoretical security of e-cash and the practical needs of physical currency infrastructure.

Resilience: It enables fully offline e-cash operations, making digital currency robust against network outages, a critical feature for real-world adoption.
Privacy: It achieves a level of privacy (untraceability of withdrawal location) that physical cash offers but standard digital e-cash schemes often lack when intermediaries are involved.
Scalability: By avoiding the "coin transparency" requirement of transferable e-cash, the system remains lightweight and scalable, making it viable for high-volume retail transactions.
Trust Model: It shifts the trust model from a single always-online bank to a decentralized network of ATMs, while retaining the bank's ability to detect and punish malicious behavior (double-spending/issuing) post-factum.

In summary, the paper presents a viable, efficient, and secure framework for deploying offline e-cash via ATMs, solving the critical path problem of central bank connectivity while maintaining strong anonymity and integrity guarantees.