Having described the basic Diffie Hellman scheme described in the textbooks, we can use it in a lot of ways that the textbooks don't mention.
For ease of explanation, the schemes are shown using traditional Diffie-Hellman using multiplication modulo a prime. But the techniques themselves rely only on the properties of a commutative group and thus apply to any Diffie-Hellman scheme including elliptic curve variants. The only caveat being that some of the particular elliptic curve forms used for efficiency can make implementation a little challenging.
One of the things I realized in writing this document is that Diffie-Hellman is such a flexible system that in several cases there is more than one way to achieve a particular effect.
As shown in the introduction, to generate a Diffie-Hellman key, Alice
This works well for the traditional use case for public key cryptography in which Alice generates a public key pair and publishes her public key in a directory where anyone can look it up. But what if we wanted to design a cryptographic protocol in which Alice uses a different public key pair for every other person she communicates with without the need to remember the key pair she used for each one?
This particular requirement occurs in many anonymity and privacy protection protocols such as TOR and the use of public key based authentication at
A simple way that Alice can do this is to generate a master private key a and use a cryptographic digest function H(m) that has been modified to provide a number in the range 1..(p-1) rather than the usual sting of bits to create a new keypair for each party she wants to communicate with. If Alice wants to communicate with the site example.com, she calculates a new private key for that site as:
aexample.com = H(a + 'example.com')
Alternatively, we can perform the addition after the digest function:
aexample.com = a + H('example.com')
Yet another way to achieve the same result is to use the key pair addition property described below.
In the introduction, we saw that
(eb mod p)a mod p = (ea mod p)b mod p = eab mod p
We can perform a key agreement with three keys just as easily:
((ea mod p)b mod p)c mod p = eabc mod p
Again, we can do the exponentiation operations in any order we choose. Or if we happen to know more than one of the private keys, we can simply multiply them together instead:
(eb mod p)ac mod p = (ea mod p)bc mod p = eabc mod p
This particular scheme might not appear to be very useful as both the sender and the receiver have to know the value c. But if you look closely you will notice that we don't perform the private key operation with the private key, we use the private key multiplied by a random value that changes every time.
The reason this is important is that implementing an exponentiation step (or its elliptic curve equivalent) requires a processor to make a series of calculations whose pattern depends on the private key. And if the software isn't written exactly so, minute variations in the pattern of processing can reveal the private key to an attacker observing the power consumption, timing, radio emissions or even in some cases the noise made by the device. These are known as sideband attacks and a particularly effective form of sideband attack developed by Paul Kocher involves causing the device to perform a sequence of private key operations in a loop and performing sophisticated statistical analysis to uncover the private key.
Multiplying the private key by a constant factor is a form of what is known as key blinding, a powerful technique for defeating sideband attacks.
Multiplying the private key on both sides with a common constant provides us with a method of guiding protocol implementers to the use of a key blinding approach. But what if we want to use key blinding with a regular Diffie-Hellman protocol? No problem, just split the private key into two parts whose sum is the private key
a = x + y
We then perform the Diffie-Hellman key agreement separately on x and y and multiply the result together.
(eb mod p)x mod p . (eb mod p)y mod p = ebx.eby mod p = eab mod p
This approach works very well if a is large. But it is a random number is just as likely to be 1 as any other number. If a is small then we don't get as much key blinding effect as we would like. So instead we take advantage of a little piece of additional math:
ep-1 mod p = 1
Why does this work? Well 1 is the identity for modular multiplication and the order of the group is p-1. If we keep multiplying a number by itself in a group with a finite number of elements, eventually we must run out of numbers and arrive at the original number. Once this happens then the sequence must repeat. And the number of elements in the group is the order of the group by definition. Since any number multiplied by the identity is itself, the result we encounter before running out of numbers is the identity element of the group.
What this means is that we can pick any x and y provided that they satisfy:
a = x + y mod p-1
This feature of Diffie-Hellman allows us to achieve a very powerful technique called proxy re-encryption. Instead of splitting the private key, performing both Diffie-Hellman calculations on the same computer and combining the results, we split the private key and send the two (or more) parts to different computers.
Splitting the private key in this way allows us to create a system in which two (or more) parties must both participate in order to decrypt a message. For example, one of the parties might be a cloud service that has the function of monitoring how many classified documents a user is decrypting without being able to decrypt them itself and thus be a potential source of compromise.
There are many, many other applications of Proxy Re-Encryption which will be described in a companion paper.
As we saw in the example above, we can split a private key into two parts, perform the Diffie-Hellman operation on each part and combine the results. The same property allows us to do combine two key pairs to derive a third.
Given two Diffie-Hellman keys (a, ea) and (b, eb), we can create a third keypair (c, ec) where:
c = a + b
ec = ea.eb = ea+b = ec
One very important way that we can make use of this feature is in a protocol I proposed called co-operative key generation. In this protocol we are concerned with the problem of a devices whose random number generators are insufficiently random being used to generate keypairs. A party (e.g. a Certificate Authority) wants to be able to contribute randomness to the key generation process in such a way that:
The key pair combination property may also be used to provide an enhanced version of the hierarchical key generation scheme described above.