A Formal Treatment of Remotely Keyed Encryption

Joan Feingenbaum, AT&T Labs- Research

No cryptographic protocol is stronger than the mechanism protecting its secret keys. However, in many computing and communication systems, there is no “safe place” in which secret keys can be stored and cryptographic computations can be performed. This is especially true of modern networked computers: In some sense, every computer that communicates extensively with the world is bound at some point to be partly controlled by an unfriendly entity. Therefore, it is natural to consider adding an external, special-purpose device, such as a smart-card or a PCMCIA card, for storing cryptographic keys and computing cryptographic functions. Unfortunately, because such devices have limited bandwidth, memory, and processor speed, it is not feasible to rely on them to perform all of the cryptographic computation that a host computer may need for a high-bandwidth application (e.g., a private video conference).

This talk addresses “the remotely keyed encryption problem”: how to do bulk encryption and decryption for high-bandwidth applications in a way that takes advantage of both the superior power of the host and the superpior security of the smart-card? We review the network threats and the emerging services that motivate the development of secure smart-cards and remotely keyed encryption schemes. We then present a formal framework in which to study the security of these schemes, along with two specific schemes that satisfy our formal criteria. In addition to being “provably secure”, these schemes are efficient enough for use in high-speed, high-bandwidth services.

This is joint work with Matt Blaze (AT&T Labs - Research) and Moni Naor (Weizmann Institute of Science).