ACHIEVING ELECTRONIC PRIVACY
_________________________________________________________________
A CRYPTOGRAPHIC INVENTION KNOWN AS A BLIND SIGNATURE PERMITS NUMBERS TO
SERVE AS ELECTRONIC CASH OR TO REPLACE CONVENTIONAL IDENTIFICATION. THE
AUTHOR HOPES IT MAY RETURN CONTROL OF PERSONAL INFORMATION TO THE
INDIVIDUAL.
by David Chaum, david@digicash.nl
This article appeared in Scientific American, August 1992, p. 96-101.
Copyright (c) 1992 by Scientific American, Inc.
_________________________________________________________________
Every time you make a telephone call, purchase goods using a credit
card, subscribe to a magazine or pay your taxes, that information goes
into a data base somewhere. Furthermore, all these records can be
linked so that they constitute in effect a single dossier on your life
not only your medical and financial history but also what you buy,
where you travel and whom you communicate with. It is almost
impossible to learn the full extent of the files that various
organizations keep on you, much less to assure their accuracy or to
control who may gain access to them.
Organizations link records from different sources for their own
protection. Certainly it is in the interest of a bank looking at a
loan application to know that John Doe has defaulted on four similar
loans in the past two years. The bank's possession of that information
also helps its other customers, to whom the bank passes on the cost of
bad loans. In addition, these records permit Jane Roe, whose payment
history is impeccable, to establish a charge account at a shop that
has never seen her before.
That same information in the wrong hands, however, provides neither
protection for businesses nor better service for consumers. Thieves
routinely use a stolen credit card number to trade on their victims'
good payment records; murderers have tracked down their targets by
consulting government-maintained address records. On another level,
the U.S. Internal Revenue Service has attempted to single out
taxpayers for audits based on estimates of household income compiled
by mailing-list companies.
The growing amounts of information that different organizations
collect about a person can be linked because all of them use the same
key in the U.S. the social security number to identify the individual
in question. This identifier-based approach perforce trades off
security against individual liberties. The more information that
organizations have (whether the intent is to protect them from fraud
or simply to target marketing efforts), the less privacy and control
people retain.
Over the past eight years, my colleagues and I at CWI (the Dutch
nationally funded Center for Mathematics and Computer Science in
Amsterdam) have developed a new approach, based on fundamental
theoretical and practical advances in cryptography, that makes this
trade-off unnecessary. Transactions employing these techniques avoid
the possibility of fraud while maintaining the privacy of those who
use them.
In our system, people would in effect give a different (but
definitively verifiable) pseudonym to every organization they do
business with and so make dossiers impossible. They could pay for
goods in untraceable electronic cash or present digital credentials
that serve the function of a banking passbook, driver's license or
voter registration card without revealing their identity. At the same
time, organizations would benefit from increased security and lower
record-keeping costs.
Recent innovations in microelectronics make this vision practical by
providing personal "representatives" that store and manage their
owners' pseudonyms, credentials and cash. Microprocessors capable of
carrying out the necessary algorithms have already been embedded in
pocket computers the size and thickness of a credit card. Such systems
have been tested on a small scale and could be in widespread use by
the middle of this decade.
_________________________________________________________________
The starting point for this approach is the digital signature, first
proposed in 1976 by Whitfield Diffie, then at Stanford University. A
digital signature transforms the message that is signed so that anyone
who reads it can be sure of who sent it [see "The Mathematics of
Public-Key Cryptography", by Martin E. Hellman; Scientific American,
August 1979]. These signatures employ a secret key used to sign
messages and a public one used to verify them. Only a message signed
with the private key can be verified by means of the public one. Thus,
if Alice wants to send a signed message to Bob (these two are the
cryptographic community's favorite hypothetical characters), she
transforms it using her private key, and he applies her public key to
make sure that it was she who sent it. The best methods known for
producing forged signatures would require many years, even using
computers billions of times faster than those now available.
To see how digital signatures can provide all manner of unforgeable
credentials and other services, consider how they might be used to
provide an electronic replacement for cash. The First Digital Bank
would offer electronic bank notes: messages signed using a particular
private key. All messages bearing one key might be worth a dollar, all
those bearing a different key five dollars, and so on for whatever
denominations were needed. These electronic bank notes could be
authenticated using the corresponding public key, which the bank has
made a matter of record. First Digital would also make public a key to
authenticate electronic documents sent from the bank to its customers.
To withdraw a dollar from the bank, Alice generates a note number
(each note bears a different number, akin to the serial number on a
bill); she chooses a 100-digit number at random so that the chance
anyone else would generate the same one is negligible. She signs the
number with the private key corresponding to her "digital pseudonym"
(the public key that she has previously established for use with her
account). The bank verifies Alice's signature and removes it from the
note number, signs the note number with its worth-one-dollar signature
and debits her account. It then returns the signed note along with a
digitally signed withdrawal receipt for Alice's records. In practice,
the creation, signing and transfer of note numbers would be carried
out by Alice's card computer. The power of the cryptographic
protocols, however, lies in the fact that they are secure regardless
of physical medium: the same transactions could be carried out using
only pencil and paper.
When Alice wants to pay for a purchase at Bob's shop, she connects her
"smart" card with his card reader and transfers one of the signed note
numbers the bank has given her. After verifying the bank's digital
signature, Bob transmits the note to the bank, much as a merchant
verifies a credit card transaction today. The bank reverifies its
signature, checks the note against a list of those already spent and
credits Bob's account. It then transmits a "deposit slip," once again
unforgeably signed with the appropriate key. Bob hands the merchandise
to Alice along with his own digitally signed receipt, completing the
transaction.
This system provides security for all three parties. The signatures at
each stage prevent any one from cheating either of the others: the
shop cannot deny that it received payment, the bank cannot deny that
it issued the notes or that it accepted them from the shop for
deposit, and the customer can neither deny withdrawing the notes from
her account nor spend them twice.
This system is secure, but it has no privacy. If the bank keeps track
of note numbers, it can link each shop's deposit to the corresponding
withdrawal and so determine precisely where and when Alice (or any
other account holder) spends her money. The resulting dossier is far
more intrusive than those now being compiled. Furthermore, records
based on digital signatures are more vulnerable to abuse than
conventional files. Not only are they self-authenticating (even if
they are copied, the information they contain can be verified by
anyone), but they also permit a person who has a particular kind of
information to prove its existence without either giving the
information away or revealing its source. For example, someone might
be able to prove incontrovertibly that Bob had telephoned Alice on 12
separate occasions without having to reveal the time and place of any
of the calls.
I have developed an extension of digital signatures, called blind
signatures, that can restore privacy. Before sending a note number to
the bank for signing, Alice in essence multiplies it by a random
factor. Consequently, the bank knows nothing about what it is signing
except that it carries Alice's digital signature. After receiving the
blinded note signed by the bank, Alice divides out the blinding factor
and uses the note as before.
The blinded note numbers are "unconditionally untraceable" that is,
even if the shop and the bank collude, they cannot determine who spent
which notes. Because the bank has no idea of the blinding factor, it
has no way of linking the note numbers that Bob deposits with Alice's
withdrawals. Whereas the security of digital signatures is dependent
on the difficulty of particular computations, the anonymity of blinded
notes is limited only by the unpredictability of Alice's random
numbers. If she wishes, however, Alice can reveal these numbers and
permit the notes to be stopped or traced.
Blinded electronic bank notes protect an individual's privacy, but
because each note is simply a number, it can be copied easily. To
prevent double spending, each note must be checked on-line against a
central list when it is spent. Such a verification procedure might be
acceptable when large amounts of money are at stake, but it is far too
expensive to use when someone is just buying a newspaper. To solve
this problem, my colleagues Amos Fiat and Moni Naor and I have
proposed a method for generating blinded notes that requires the payer
to answer a random numeric query about each note when making a
payment. Spending such a note once does not compromise unconditional
untraceability, but spending it twice reveals enough information to
make the payer's account easily traceable. In fact, it can yield a
digitally signed confession that cannot be forged even by the bank.
Cards capable of such anonymous payments already exist. Indeed,
DigiCash, a company with which I am associated, has installed
equipment in two office buildings in Amsterdam that permits copiers,
fax machines, cafeteria cash registers and even coffee vending
machines to accept digital "bank notes." We have also demonstrated a
system for automatic toll collection in which automobiles carry a card
that responds to radioed requests for payment even as they are
travelling at highway speeds.
_________________________________________________________________
My colleagues and I call a computer that handles such cryptographic
transactions a "representative." A person might use different
computers as representatives depending on which was convenient: Bob
might purchase software (transmitted to him over a network) by using
his home computer to produce the requisite digital signatures, go
shopping with a "palm-top" personal computer and carry a smart credit
card to the beach to pay for a drink or crab cakes. Any of these
machines could represent Bob in a transaction as long as the digital
signatures each generates are under his control.
Indeed, such computers can act as representatives for their owners in
virtually any kind of transaction. Bob can trust his representative
and Alice hers because they have each chosen their own machine and can
reprogram it at will (or, in principle, build it from scratch).
Organizations are protected by the cryptographic protocol and so do
not have to trust the representatives.
The prototypical representative is a smart credit-card-size computer
containing memory and a microprocessor. It also incorporates its own
keypad and display so that its owner can control the data that are
stored and exchanged. If a shop provided the keypad and display, it
could intercept passwords on their way to the card or show one price
to the customer and another to the card. Ideally, the card would
communicate with terminals in banks and shops by a short-range
communications link such as an infrared transceiver and so need never
leave its owner's hands.
When asked to make a payment, the representative would present a
summary of the particulars and await approval before releasing funds.
It would also insist on electronic receipts from organizations at each
stage of all transactions to substantiate its owner's position in case
of dispute. By requiring a password akin to the PIN (personal
identifying number) now used for bank cards, the representative could
safeguard itself from abuse by thieves. Indeed, most people would
probably keep backup copies of their keys, electronic bank notes and
other data; they could recover their funds if a representative were
lost or stolen.
Personal representatives offer excellent protection for individual
privacy, but organizations might prefer a mechanism to protect their
interests as strongly as possible. For example, a bank might want to
prevent double spending of bank notes altogether rather than simply
detecting it after the fact. Some organizations might also want to
ensure that certain digital signatures are not copied and widely
disseminated (even though the copying could be detected afterwards).
Organizations have already begun issuing tamperproof cards (in effect,
their own representatives) programmed to prevent undesirable behavior.
But these cards can act as "Little Brothers" in everyone's pocket.
We have developed a system that satisfies both sides. An observer a
tamper-resistant computer chip, issued by some entity that
organizations can trust acts like a notary and certifies the behavior
of a representative in which it is embedded. Philips Industries has
recently introduced a tamperresistant chip that has enough computing
power to generate and verify digital signatures. Since then, Siemens,
Thomson CSF and Motorola have announced plans for similar circuits,
any of which could easily serve as an observer.
The central idea behind the protocol for observers is that the
observer does not trust the representative in which it resides, nor
does the representative trust the observer. Indeed, the representative
must be able to control all data passing to or from the observer;
otherwise the tamperproof chip might be able to leak information to
the world at large.
When Alice first acquires an observer, she places it in her smart-card
representative and takes it to a validating authority. The observer
generates a batch of public and private key pairs from a combination
of its own random numbers and numbers supplied by the card. The
observer does not reveal its numbers but reveals enough information
about them so that the card can later check whether its numbers were
in fact used to produce the resulting keys. The card also produces
random data that the observer will use to blind each key.
Then the observer blinds the public keys, signs them with a special
built-in key and gives them to the card. The card verifies the
blinding and the signature and checks the keys to make sure they were
correctly generated. It passes the blinded, signed keys to the
validating authority, which recognizes the observer's built-in
signature, removes it and signs the blinded keys with its own key. The
authority passes the keys back to the card, which unblinds them. These
keys, bearing the signature of the validating authority, serve as
digital pseudonyms for future transactions; Alice can draw on them as
needed.
_________________________________________________________________
An observer could easily prevent (rather than merely detect) double
spending of electronic bank notes. When Alice withdraws money from her
bank, the observer witnesses the process and so knows what notes she
received. At Bob's shop, when Alice hands over a note from the bank,
she also hands over a digital pseudonym (which she need use only once)
signed by the validating authority. Then the observer, using the
secret key corresponding to the validated pseudonym, signs a statement
certifying that the note will be spent only once, at Bob's shop and at
this particular time and date. Alice's card verifies the signed
statement to make sure that the observer does not leak any information
and passes it to Bob. The observer is programmed to sign only one such
statement for any given note.
Many transactions do not simply require a transfer of money. Instead
they involve credentials information about an individual's
relationship to some organization. In today's identifier-based world,
all of a person's credentials are easily linked. If Alice is deciding
whether to sell Bob insurance, for example, she can use his name and
date of birth to gain access to his credit status, medical records,
motor vehicle file and criminal record, if any.
Using a representative, however, Bob would establish relationships
with different organizations under different digital pseudonyms. Each
of them can recognize him unambiguously, but none of their records can
be linked.
In order to be of use, a digital credential must serve the same
function as a paper-based credential such as a driver's license or a
credit report. It must convince someone that the person attached to it
stands in a particular relation to some issuing authority. The name,
photograph, address, physical description and code number on a
driver's license, for example, serve merely to link it to a particular
person and to the corresponding record in a data base. Just as a bank
can issue unforgeable, untraceable electronic cash, so too could a
university issue signed digital diplomas or a credit-reporting bureau
issue signatures indicating a person's ability to repay a loan.
When the young Bob graduates with honors in medieval literature, for
example, the university registrar gives his representative a digitally
signed message asserting his academic credentials. When Bob applies to
graduate school, however, he does not show the admissions committee
that message. Instead his representative asks its observer to sign a
statement that he has a B.A. cum laude and that he qualifies for
financial aid based on at least one of the university's criteria (but
without revealing which ones). The observer, which has verified and
stored each of Bob's credentials as they come in, simply checks its
memory and signs the statement if it is true.
In addition to answering just the right question and being more
reliable than paper ones, digital credentials would be both easier for
individuals to obtain and to show and cheaper for organizations to
issue and to authenticate. People would no longer need to fill out
long and revealing forms. Instead their representatives would convince
organizations that they meet particular requirements without
disclosing any more than the simple fact of qualification. Because
such credentials reveal no unnecessary information, people would be
willing to use them even in contexts where they would not willingly
show identification, thus enhancing security and giving the
organization more useful data than it would otherwise acquire.
Positive credentials, however, are not the only kind that people
acquire. They may also acquire negative credentials, which they would
prefer to conceal: felony convictions, license suspensions or
statements of pending bankruptcy. In many cases, individuals will give
organizations the right to inflict negative credentials on them in
return for some service. For instance, when Alice borrows books from a
library, her observer would be instructed to register an overdue
notice unless it had received a receipt for the books' return within
some fixed time.
Once the observer has registered a negative credential, an
organization can find out about it simply by asking the observer
(through the representative) to sign a message attesting to its
presence or absence. Although a representative could muzzle the
observer, it could not forge an assertion about the state of its
credentials. In other cases, organizations might simply take the lack
of a positive credential as a negative one. If Bob signs up for
skydiving lessons, his instructors may assume that he is medically
unfit unless they see a credential to the contrary.
For most credentials, the digital signature of an observer is
sufficient to convince anyone of its authenticity. Under some
circumstances, however, an organization might insist that an observer
demonstrate its physical presence. Otherwise, for example, any number
of people might be able to gain access to nontransferable credentials
(perhaps a health club membership) by using representatives connected
by concealed communications links to another representative containing
the desired credential.
Moreover, the observer must carry out this persuasion while its input
and output are under the control of the representative that contains
it. When Alice arrives at her gym, the card reader at the door sends
her observer a series of single-bit challenges. The observer
immediately responds to each challenge with a random bit that is
encoded by the card on its way back to the organization. The speed of
the observer's response establishes that it is inside the card (since
processing a single bit introduces almost no delay compared with the
time that signals take to traverse a wire). After a few dozen
iterations the card reveals to the observer how it encoded the
responses; the observer signs a statement including the challenges and
encoded responses only if it has been a party to that
challengeresponse sequence. This process convinces the organization of
the observer's presence without allowing the observer to leak
information.
Organizations can also issue credentials using methods that depend on
cryptography alone rather than on observers. Although currently
practical approaches can handle only relatively simple queries, Gilles
Brassard of the University of Montreal, Claude Cripeau of the Icole
Normale Supirieure and I have shown how to answer arbitrary
combinations of questions about even the most complex credentials
while maintaining unconditional unlinkability. The concealment of
purely cryptographic negative credentials could be detected by the
same kinds of techniques that detect double spending of electronic
bank notes. And a combination of these cryptographic methods with
observers would offer accountability after the fact even if the
observer chip were somehow compromised.
_________________________________________________________________
The improved security and privacy of digital pseudonyms exact a price:
responsibility. At present, for example, people can disavow credit
card purchases made over the telephone or cash withdrawals from an
automatic teller machine (ATM). The burden of proof is on the bank to
show that no one else could have made the purchase or withdrawal. If
computerized representatives become widespread, owners will establish
all their own passwords and so control access to their
representatives. They will be unable to disavow a representative's
actions.
Current tamper-resistant systems such as ATMs and their associated
cards typically rely on weak, inflexible security procedures because
they must be used by people who are neither highly competent nor
overly concerned about security. If people supply their own
representatives, they can program them for varying levels of security
as they see fit. (Those who wish to trust their assets to a single
four-digit code are free to do so, of course.) Bob might use a short
PIN (or none at all) to authorize minor transactions and a longer
password for major ones. To protect himself from a robber who might
force him to give up his passwords at gunpoint, he could use a "duress
code" that would cause the card to appear to operate normally while
hiding its more important assets or credentials or perhaps alerting
the authorities that it had been stolen.
A personal representative could also recognize its owner by methods
that most people would consider unreasonably intrusive in an
identifier-based system; a notebook computer, for example, might
verify its owner's voice or even fingerprints. A supermarket checkout
scanner capable of recognizing a person's thumbprint and debiting the
cost of groceries from their savings account is Orwellian at best. In
contrast, a smart credit card that knows its owner's touch and doles
out electronic bank notes is both anonymous and safer than cash. In
addition, incorporating some essential part of such identification
technology into the tamperproof observer would make such a card
suitable even for very high security applications.
_________________________________________________________________
Computerized transactions of all kinds are becoming ever more
pervasive. More than half a dozen countries have developed or are
testing chip cards that would replace cash. In Denmark, a consortium
of banking, utility and transport companies has announced a card that
would replace coins and small bills; in France, the telecommunications
authorities have proposed general use of the smart cards now used at
pay telephones. The government of Singapore has requested bids for a
system that would communicate with cars and charge their smart cards
as they pass various points on a road (as opposed to the simple
vehicle identification systems already in use in the U.S. and
elsewhere). And cable and satellite broadcasters are experimenting
with smart cards for delivering pay-per-view television. All these
systems, however, are based on cards that identify themselves during
every transaction.
If the trend toward identifier-based smart cards continues, personal
privacy will be increasingly eroded. But in this conflict between
organizational security and individual liberty, neither side emerges
as a clear winner. Each round of improved identification techniques,
sophisticated data analysis or extended linking can be frustrated by
widespread noncompliance or even legislated limits, which in turn may
engender attempts at further control.
Meanwhile, in a system based on representatives and observers,
organizations stand to gain competitive and political advantages from
increased public confidence (in addition to the lower costs of
pseudonymous record-keeping). And individuals, by maintaining their
own cryptographically guaranteed records and making only necessary
disclosures, will be able to protect their privacy without infringing
on the legitimate needs of those with whom they do business.
The choice between keeping information in the hands of individuals or
of organizations is being made each time any government or business
decides to automate another set of transactions. In one direction lies
unprecedented scrutiny and control of people's lives, in the other,
secure parity between individuals and organizations. The shape of
society in the next century may depend on which approach predominates.
_________________________________________________________________
Further Reading:
* Security Without Identification: Transaction Systems to Make Big
Brother Obsolete. David Chaum in Communications of the ACM, Vol.
28, No. 10, pages 1030-1044; October 1985.
* The Dining Cryptographers Problem: Unconditional Sender and
Recipient Untraceability. David Chaum in Journal of Cryptology,
Vol. 1, No. 1, pages 65-75; 1988.
* Modern Cryptology: A Tutorial. Gilles Brassard in
* Lecture Notes in Computer Science, Vol. 325. Springer-Verlag,
1988.
* Privacy Protected Payments: Unconditional Payer and/or Payee
Untraceability. David Chaum in Smart Card 2000: The Future of IC
Cards. Edited by David Chaum and Ingrid Schaumueller-Bichl.
North-Holland, 1989.
_________________________________________________________________
