Profile - A Prototype for
Digital Detectives
When Cynthia Dwork joined the IBM Almaden Research Center in 1985, she expected to continue the fundamental research that she had carried out before and after earning her Ph.D. in computer science. Certainly, she did not anticipate having a direct impact on products.
Dwork's research pursuits haven't changed much during her nearly 11 years at Almaden, but the direction of one of her specialties - distributed computing - has. That field has incorporated cryptography, a topic that has emerged from its academic cubbyhole to play a vital role in new and emerging products and in many areas of network services, from distributed systems to electronic commerce and intellectual property.
"When I joined IBM, people thought my field very academic," Dwork says. "But now the question of operating securely comes up in the Internet, Lotus Notes® and elsewhere. The insights we gained are just now starting to bear fruit."
It began in 1983, with a talk on the Byzantine Generals Problem, also known as Byzantine agreement, an issue relevant then and now to the design of fault-tolerant computer systems and secure distributed computation. Nancy Lynch of MIT reported that she and other researchers had proved that unanimous agreement among a group of individuals, some of whom might be traitors, was impossible in certain circumstances. "By the end of the talk," Dwork remembers, "I had improved the result."
electronic claim-check
In 1993, after completing several projects that involved cryptography, Dwork started work on the concept of an electronic claim-check for IBM's Enterprise FAX system. The idea was to add digital signatures to faxes so that individuals receiving a fax message could be sure that the message was authentic and could prove to third parties that the sender had actually sent that particular message. At the time, no practical scheme with the requisite security properties was available. Dwork and Moni Naor, a Weizmann Institute scientist visiting the Almaden Center, designed such a scheme.
The second part proved very tough, because the fax message changed from a collection of bits to printed text. Dwork and Naor came up with the idea that the sender would store the bit string, and would give the receiver a short, signed claim-check.
That project brought Dwork into contact with researchers working on the Enterprise FAX. Later, when those people began to work on digital libraries (see Research Number 1, 1996), they consulted her for input on rights-
management issues.
Rights management covers three potential security problems faced by digital libraries: personal privacy (preventing anyone from discovering what a subscriber to the library is renting); the security of material (making it impossible to alter materials, such as prescription doses, in papers stored in the library); and copyright protection, in particular the unauthorized redistribution of library materials by legitimate library users.
This third problem is extremely difficult, because a user can eventually grab whatever he or she purchases, whether it is an image on a terminal, a document or a piece of software. Some scientists have proposed indelibly "watermarking" digital content with information that identifies the recipient. However, says Dwork, such techniques do not offer security in any cryptographic sense; they require the distributor to prepare a personalized copy for each recipient; and they raise several enforcement issues, such as the lack of an automatic means of generating suspicion and the question of who will carry out and fund enforcement.
With those issues in mind, Dwork, Naor and Almaden researcher Jeffrey Lotspiech invented digital signets, a self-enforcing mechanism for protecting digital content. Under this scheme, the distributor disseminates encrypted data together with unencrypted "extrication" software. Each signet is a short string of information computed from one piece of information known only to the authorization center and one piece of "sensitive" information known to the user and revealed to the authorization center. Both pieces can be transmitted orally, over the telephone. The user combines the signet with the sensitive information to create a so-called valid signet pair. When input into the extrication software, the signet pair can decrypt the encrypted data.
The key is that the user can't give away any short string that can be used to decrypt the data without also giving away the sensitive information. More than just an ID, the sensitive information is something that causes the user real inconvenience if shared. For example, imagine how uncomfortable any individual would be about giving his or her credit card numbers to five friends. By using signets, the legitimate distributor can take advantage of mass distribution techniques to distribute encrypted data. Authorizing a user requires only a very short telephone (or e-mail) conversation. However, the pirate cannot authorize succinctly without revealing his or her sensitive information.
Nonmalleable cryptography
Other work remains at the theoretical level, although practical applications have been proposed. Nonmalleable cryptography, a term that Dwork coined after a session with a thesaurus, is one such example. She developed the theoretical technique in collaboration with Daniel Dolev, of Israel's Hebrew University, and Naor. "The work was born in the Byzantine agreement, but it has potential applications beyond it," explains Dwork.
The starting point was a form of the Byzantine agreement problem in which several individuals agree to flip a proverbial coin to decide an issue. To illustrate this, suppose two parties have access to an impartial judge, and consider the simple protocol in which each person chooses a random bit of data and sends an encrypted version of it to the judge, where the encryption is done using the judge's public key. The judge determines "heads" or "tails" according to whether the two decrypted messages are similar or different.
Although the encryption prevents each party from knowing the other's message, this is not enough to ensure that the two messages are mutually independent. A participant who sees the other participant's coded message could predetermine the result by adjusting his or her own ciphertext accordingly - for example, by simply copying the first participant's message and sending it as his or her own. Even requiring the two messages to be distinct is insufficient; in some cryptosystems it is easy, given one encryption of a bit, to compute a distinct encryption of the same bit - or, if desired, of its complement - without knowing the value of the bit. Such cryptosystems are "malleable."
Dwork and her collaborators devised a "nonmalleable cryptosystem." Used for the encryptions in the above protocol, this system ensures that the flip will be unbiased. The nonmalleable ciphertext has two parts: a simple encrypted portion and an authenticating portion. The authenticating portion is intimately related to the basic portion of the message. Any attempt to intercept the message and incorporate it into a fresh message would disrupt the balance between the two portions, making the fresh message plainly invalid.
So far, the work is almost entirely of theoretical interest. However, two former IBM researchers have proposed a simple way to implement it - in authentication servers, for example, or contract bidding. Although they have not yet proved the validity of the implementation, Dwork argues that users might want to try their system, because it requires little overhead and offers at least as much security as techniques presently in use.
Last year, Dwork undertook another form of security-busting. "When I read the Lotus Notes manual, I realized that I could forge notes and read anyone's mail," she recalls. Lotus has since assured her that, owing to a misunderstanding by a technical writer, the manual does not describe the exact mode of operation of Notes. Dwork was, in fact, the first to complain about the apparent lack of security. "You needed special training to spot it," she says. She has since discussed the issue with Lotus, and the CIA, which uses Lotus Notes, has expressed interest in her paper on the topic.
Recently, Dwork has focused on the validity of copyright protection mechanisms. She takes a skeptical view of the issue, which she publicized recently in an invited talk at the Federated Computing Research Conference in Philadelphia. Unless there's an infrastructure to support ideas for protection such as watermarking, she states, those ideas will be worthless. "There would be a need for a digital content police," she asserts. "The question is: Who are they? And even if there were a digital police force, it would incur huge search costs."
Dwork admits to having a few ideas - so far unpublicized - on how to create such a police force. If it does come into existence, Cynthia Dwork will undoubtedly work hard to keep it on its toes. n
