| Previous | Table of Contents | Next |
Alice is a member of Cabal, Inc. Occasionally she has to meet with other members in dimly lit restaurants and whisper secrets back and forth. The problem is that the restaurants are so dimly lit that she has trouble knowing if the person across the table from her is also a member.
Cabal Inc. can choose from several solutions. Every member can carry a membership list. This has two problems. One, everyone now has to carry a large database, and two, they have to guard that membership list pretty carefully. Alternatively, a trusted secretary could issue digitally signed ID cards. This has the added advantage of allowing outsiders to verify members (for discounts at the local grocery store, for example), but it requires a trusted secretary. Nobody at Cabal, Inc. can be trusted to that degree.
A novel solution is to use something called a one-way accumulator [116]. This is sort of like a one-way hash function, except that it is commutative. That is, it is possible to hash the database of members in any order and get the same value. Moreover, it is possible to add members into the hash and get a new hash, again without regard to order.
So, here’s what Alice does. She calculates the accumulation of every member’s name other than herself. Then she saves that single value along with her own name. Bob, and every other member, does the same. Now, when Alice and Bob meet in the dimly lit restaurant, they simply trade accumulations and names with each other. Alice confirms that Bob’s name added to his accumulation is equal to Alice’s name added to her accumulation. Bob does the same. Now they both know that the other is a member. And at the same time, neither can figure out the identities of any other member.
Even better, nonmembers can be given the accumulation of everybody. Now Alice can verify her membership to a nonmember (for membership discounts at their local counterspy shop, perhaps) without the nonmember being able to figure out the entire membership list.
New members can be added just by sending around the new names. Unfortunately, the only way to delete a member is to send everyone a new list and have them recompute their accumulations. But Cabal, Inc. only has to do that if a member resigns; dead members can remain on the list. (Oddly enough, this has never been a problem.)
This is a clever idea, and has applications whenever you want the same effect as digital signatures without a centralized signer.
Imagine that Alice is a former agent of the former Soviet Union, now unemployed. In order to make money, Alice sells secrets. Anyone who is willing to pay the price can buy a secret. She even has a catalog. All her secrets are listed by number, with tantalizing titles: “Where is Jimmy Hoffa?”, “Who is secretly controlling the Trilateral Commission?”, “Why does Boris Yeltsin always look like he swallowed a live frog?”, and so on.
Alice won’t give away two secrets for the price of one or even partial information about any of the secrets. Bob, a potential buyer, doesn’t want to pay for random secrets. He also doesn’t want to tell Alice which secrets he wants. It’s none of Alice’s business, and besides, Alice could then add “what secrets Bob is interested in” to her catalog.
A poker protocol won’t work in this case, because at the end of the protocol Alice and Bob have to reveal their hands to each other. There are also tricks Bob can do to learn more than one secret.
The solution is called all-or-nothing disclosure of secrets (ANDOS) [246] because, as soon as Bob has gained any information whatsoever about one of Alice’s secrets, he has wasted his chance to learn anything about any of the other secrets.
There are several ANDOS protocols in the cryptographic literature. Some of them are discussed in Section 23.9.
This excerpt is from Silvio Micali’s introduction to the topic [1084]:
Currently, court-authorized line tapping is an effective method for securing criminals to justice. More importantly, in our opinion, it also prevents the further spread of crime by deterring the use of ordinary communication networks for unlawful purposes. Thus, there is a legitimate concern that widespread use of public-key cryptography may be a big boost for criminal and terrorist organizations. Indeed, many bills propose that a proper governmental agency, under circumstances allowed by law, should be able to obtain the clear text of any communication over a public network. At the present time, this requirement would translate into coercing citizens to either (1) using weak cryptosystems—i.e., cryptosystems that the proper authorities (but also everybody else!) could crack with a moderate effort—or (2) surrendering, a priori, their secret key to the authority. It is not surprising that such alternatives have legitimately alarmed many concerned citizens, generating as reaction the feeling that privacy should come before national security and law enforcement.
Key escrow is the heart of the U.S. government’s Clipper program and its Escrowed Encryption Standard. The challenge here is to develop a cryptosystem that both protects individual privacy but at the same time allows for court-authorized wiretaps.
| Previous | Table of Contents | Next |