Principal Investigator Silvio Micali
A public-key encryption scheme is plaintext-aware if, whenever an adversary creates a ciphertext, he must “know” its corresponding plaintext. Although this turns out to be the strongest known definition of security, plaintext-aware encryption has been remained controversial for two primary reasons: 1. Plaintext awareness fundamentally relies on random oracles: a third party that provides a random mapping from all possible inputs to strings. Not only does every implementation of plaintext-aware encryption use the random oracle, but the very definition requires it. Thus, plaintext awareness can seemingly only be achieved if one is willing to invoke a trusted third party for every encryption. 2. Plaintext awareness has found no important and novel applications. The primary application to plaintext-awareness has been to construct schemes secure against chosen-ciphertext attacks. (If the adversary already “knows” the answer that it will receive from a decryption oracle, then the oracle gives him no additional power.) However, schemes achieving this level of security were already known. Thus, genuinely new applications of PA encryption have been somewhat scarce. In this research, we are addressing these drawbacks by redefining plaintext-aware encryption and finding new applications.
1. We have introduced a new definition of PA encryption that does not use the random oracle. To be sure, we still need to access a trusted third party: a key registration authority. In our model, encryption is available only between users who have properly registered their public keys with the registration authority. Plaintext-awareness is guaranteed if this authority is honest. If the authority is not honest, on the other hand, then nothing is lost: the encryption remains secure against chosen-ciphertext attack. A registration authority is a natural third party to use in our model because it must be present anyway. To be implemented, a public-key cryptosystem requires a correct association between users and keys, which is produced by having public keys certified. It is a natural extension to have the certification authority fill an additional function. Hence, the use of a registration authority does not degrade security and adds no additional parties to the model. Furthermore, we insist that the registration authority be unneeded after the registration process. Thus, we replace the per-encryption use of the random oracle with a one-time use of a registration authority. 2. We have designed an implementation of the new definition by modifying the scheme of Sahai (which refined that of Naor and Yung). Instead of encrypting the same message in two keys, however, we encrypt in three: two of the receiver and one of the sender. A proof that all three encryptions contain the same plaintext ensures that the plaintext can be understood by both sender and receiver. The registration process ensures that the registrant knows the decryption key to the registered one. Hence, if the adversary properly registers its key, it must know the decryption to any ciphertext it creates. 3. Lastly, we applied this definition to a new and natural application which requires its full power. The Dolev-Yao model is a framework for protocol analysis developed in the formal methods community. Unlike the more general computational models, the Dolev-Yao model has the advantage of extreme simplicity and ease of use. In fact, in this model the security of a given protocol can be successfully determined by automated tools. However, these successes are qualified by their reliance on extremely strong assumptions. In particular, the Dolev-Yao model assumes an extremely weak adversary. Instead of performing arbitrary computations, it is limited to selecting its actions from a small number of predetermined operations. (For example, it cannot decrypt or modify a ciphertext unless it possesses the right key, or create a ciphertext unless it possesses the plaintext.)
These restrictions raise serious doubts about the meaningfulness of the Dolev-Yao model. After all, these restrictions might not be obeyed by a real-world adversary. We show, however, that plaintext awareness ensures that the Dolev-Yao restrictions can be actually enforced in the real world. (It is here that the naturalness of our model and implementation matters crucially. Were plaintext awareness to require random oracles, we would simply be reducing one abstraction to another. However, since our model is concrete, it follows that the Dolev-Yao adversary can be made concrete also.)
This work looks likely to continue into the future. Research continues on several fronts. In particular, we would like to find a more efficient implementation of plaintext-aware encryption. Our current scheme uses only general assumptions, but is woefully inefficient. Recent work using the Cramer-Shoup scheme has yielded a more efficient scheme, but under specific assumptions and requiring a more complex setup process. We would also like to continue work on the Dolev-Yao model. It is possible that our current results can be strengthened. They also do not entirely justify the model, since the makes additional assumptions that we have not addressed. In particular, the model assumes that honest participants leak no useful information when error conditions arise. Recent work has shown that error codes and behavior can be used to break cryptographic implementations, and so this assumption of the Dolev-Yao model must be addressed.