Cryptographic protocols do not run in a vacuum; however their behavior under composition is poorly understood. We illustrate this with an extremely simple primitive, "selective decommitment." This problem, in a somewhat different form called selective decryption, arose in Byzantine Agreement; the question is whether an adversary, who chooses, from a set of ciphertexts, certain messages to be decrypted, can then deduce something unexpected about the other, still-encrypted, messages. We view the selective decommitment problem as the composition of many instances of an underlying provably-secure block, and explain why, contrary to intuition, the proof of security fails for the composition.
We then discuss an appealing methodolgy, due to Fiat and Shamir, for converting (easy to design) identification schemes into (harder to design) digital signature schemes. The methodology requires what we term "magic functions." We show that if selective decommitment is indeed secure under composition then there is no magic function (it is not a perfect world).
The connection between selective decommitment and magic functions is made through 3-round interactive proof systems enjoying a certain useful but weakened form of zero-knowledge. If a certain well-known 3-round protocol for NP fails to enjoy this weak form of zero-knowledge, then some kind of "magic" exists, and conversely.
(Joint work with M. Naor, O. Reingold, and L. Stockmeyer.)
Cynthia Dwork received her PhD from Cornell University in 1983 under the supervision of John Hopcroft. After a two-year post-doc at MIT, she joined the IBM Almaden Research Center. Most of her research has been in cryptography and other topics in distributed computing.