Trapdoor One-Way Functions

The Search for a Trapdoor One-Way Function

One crucial property of a public key cryptosystem is that the private key (D) should not be computable given the public key (E). Otherwise, an attacker could just take Bob’s public key E_{Bob} , compute the corresponding private key D_{Bob} , and use D_{Bob} to decrypt any messages sent to Bob.

All right, so we need two different keys D and E such that we can’t compute D from E, but we can use D to decrypt any message encrypted with E.

Such a function is called a “trapdoor one-way function.” It is one-way because it is very easy to compute in one direction, but very hard to compute in the other, and “trapdoor” because some piece of information can be used to make the “hard” direction much easier. This means that Bob can easily compute the encryption of his message using Alice’s public key, but it is very hard for Eve to reverse this process. Alice can use her private key as the “trapdoor” to enable her to read Bob’s message.

Diffie and Hellman included in “New Directions in Cryptography” a few candidates for one-way functions. They suggested that an NP-complete function could be used as the basis for a trapdoor one-way function, as solutions are hard to find but very easy to create and verify. Two NP-complete instances are considered in section 6 of the paper (the knapsack problem and the exponentiation mod q problem), but no definitive procedure for public-key encryption is outlined.

Instead, Diffie and Hellman created a way to exchange keys remotely over an insecure communications link. This solves part of the key exchange problem, as it means that Alice and Bob don’t have to exchange the keys in person – they can exchange them over any communications link, even if it is insecure, without compromising the security of the key itself.

The exchange is often explained by using a paint-mixing metaphor, with each party adding a secret color to a common can of paint, exchanging paint cans, and then adding their secret color to the new paint can. Each party will end up with the same new color of paint (containing both Alice’s addition and Bob’s addition) but any eavesdropper would find it difficult to figure out what Bob and Alice each added because separating paint is not an easy problem. The algorithm is explained in more detail here.

The problem with Diffie-Hellman key exchange is that it doesn’t fully solve the issue of key exchange. If Alice and Bob wish to send messages to each other, they still have to communicate beforehand to exchange the key. This could take a while if the communications system is slow, or Alice and Bob aren’t online at the same time and must wait for each other to respond. If public-key cryptography could be implemented, Bob could send Alice a secure message without ever having communicated with her before, as he could just grab her public key off of a public repository and encrypt his message with it.

The search for a trapdoor one-way function was left as an open problem in the Diffie-Hellman paper, leaving public-key encryption a fascinating theoretical discovery but unusable in practice. When three researchers at MIT read about this novel approach to cryptography, they put their minds to work on making it a reality.

 

GCHQ’s Efforts

In Simon Singh’s The Code Book (a great read on the history of cryptography), includes a subchapter on work done at Britain’s Government Communications Headquarters (abbreviated as GCHQ, it is the British signals intelligence agency). Although the work went uncredited for years due to its classified nature, researchers at GCHQ independently developed both the idea of public-key encryption and an encryption system similar to RSA. The work was done in the years spanning 1969-75, ending three years before the RSA paper was published.

James Ellis, like Diffie and Hellman, was able to create a proof of concept for public-key encryption, but was unable to discover a suitable function to use as the basis of an encryption scheme. When a coworker told mathematician Clifford Cocks about Ellis’s efforts, Cocks set to work at solving the problem and, like
Interestingly, the GCHQ team (comprised of James Ellis, Clifford Cocks, and ) made their discoveries in reverse order. While Diffie and Hellman invented their key exchange algorithm before Rivest, Shamir, and Adleman wrote RSA, GCHQ would hit upon an ecryption algorithm first, then develop the key exchange. The key exchange algorithm was discovered by Malcolm Williamson while he was trying to find a flaw with Cocks’ encryption scheme.

GCHQ gave Cocks permission to reveal GCHQ’s discoveries in 1997.

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>