Diffie and Hellman [1] proposed the well-known public-key distribution scheme based on the discrete logarithm problem in 1976 to enable two parties to establish a common secret session key based on their exchanged public keys. But their original scheme still needs an authentication channel to exchange the public keys. Since then, several key exchange protocols [2, 3], which utilize digital signatures of these exchanged public keys to provide authentication, to allow two parties to share a common key have been proposed. In these protocols, the Diffie-Hellman public keys have been treated as messages and one-way hash values of these public keys also need to be computed. Digital signatures need to be generated based on these one-way hash values; otherwise forgery can be easily achieved.

Since Diffie-Hellman public key is obtained by computing an exponential function and the exponential function itself is a well-known one-way function, signature schemes for Diffie-Hellman public keys without using any one-way function have been proposed recently [4]. Let us summarize the advantages of using this approach:

1. Computational speed is faster than most conventional approaches.
2. Security is easy to analyze.

Property (1) is due to the fact that this approach integrates Diffie-Hellman public-key distribution scheme into a digital signature scheme. Thus, the Diffie-Hellman public keys can be used as the random number r in the ElGamal signature scheme [5].

In most approaches, a conventional one-way function is needed in any digital signature scheme. Without using a secure one-way function, a digital signature can be easily forged. There exists a major difference of security assumptions between digital signature schemes and conventional one-way functions. The security assumption of most signature schemes are based on some well-known computational problems, such as the discrete logarithm problem, the factoring problem, etc. However, the security of most conventional one-way functions is based on the complexity of analyzing a simple iterated function. Since most computational problems are well-known and easy to understand, the security of most signature schemes can withstand quite a long time. However, a one-way function may seem very difficult to analyze at the beginning; but it may turn out to be vulnerable to some special attacks later. Thus, in general, the lifetime of one-way functions is shorter than that of signature schemes. For example, recent advancement of cryptanalytic research has found that MD5 is at the edge of risking successful cryptanalytic attack [6]. Instead of relying overall security on the weaker assumption between the signature scheme and the one-way function, the security of our proposed schemes is based on the discrete logarithm problem only. Thus, the security is easy to analyze.

The MQV key agreement protocol proposed by Menezes, Qu and Vanstone [7] in 1995 is probably the first key agreement protocol that utilized a signature for the Diffie-Hellman public key without using a one-way function. MQV key agreement protocol is currently under consideration to become a standard in the IEEE P1363 committee [8]. In this paper, we generalize MQV protocol in three aspects. First, signature variants for Diffie-Hellman public keys that were developed most recently are employed in the new protocol. Second, we allow two communication entities to establish multiple secret keys in two-pass interaction. Third, we simplify the key computations.

The Diffie-Hellman public key is r = a^k mod p, where k is a secret random integer within [1, p-2] privately selected by the signer, p is a large prime and a is a primitive number in GF(p). We can call these random parameters, k and r, as short-term private key and short-term public key, respectively. In order to sign this Diffie-Hellman public key r, the signer needs to use the long-term private key x and the long-term public key y= a^x mod p.

We list four signature variants for signing Diffie-Hellman public keys from [4]. These variants are the most efficient variants since each of them permutes four parameters {r, s, k, x} directly. The signer needs to use its short-term and long-term secret keys, k and x, to generate the signature s for the Diffie-Hellman public key r. On the other hand, the verifier can use the signer’s long-term public key y to verify the signature s for r. Interest reader can read [4] for detail discussions. We would like to point out that the MQV key agreement protocol in [8] actually used one of the variants in the listed table.

3. Key Agreement Protocols

In the following discussion we will assume that A and B want to establish secret key(s) by using the key agreement protocol. The short-term secret key and short-term public key for A are k_A and r_A, and the long-term secret key and long-term public key for A are x_A and y_A. Similarly, B has k_B, r_B, x_B and y_B. The following key agreement protocol enables A and B to establish an authenticated secret key K.

1. A generates a random short-term secret key k_A and its corresponding public key r_A, and compute the signature s_A based on any variant as listed in the table. A sends {r_A, s_A, cert(y_A)} to B, where cert(y_A) is the public-key certificate of y_A signed by a trusted party.
2. Similarly, B generates k_B, r_B, s_B, and sends {r_B, s_B, cert(y_B)} to A.
3. A verifies r_B based on the signature s_B and B’s public key y_B. Then A computes the share secret key K= r_B^kA mod p.
4. Similarly, B verifies r_A based on the signature s_A and A’s public key y_A. Then B computes the share secret key K= r_A^kB mod p.

One drawback of the above protocol is that it does not offer perfect forward secrecy [9]. That is, if an adversary learns one share secret key, the adversary can deduce all share secret keys between A and B. We illustrate this threat in the following discussion.

Assume that the protocol uses x=rk+s mod p-1 to sign each Diffie-Hellman’s public key. Then, we have following two equations:

x_A=r_A k_A +s_A mod p-1, and

x_B=r_B k_B +s_B mod p-1.

By multiplying these two equations, we obtain

x_A x_B =r_A k_A r_B k_B+ r_A k_A s_B+s_A r_B k_B+s_A s_B mod p-1.

In other words, we obtain

K_AB =(K^rA^rB)( r_A ^rA ^sB)( r_B ^rB ^sA)( a ^sA ^sB) mod p,

where K_AB= a ^xA ^xB mod p is the long-term share secret key. Assume that the adversary knows one short-term share secret key K. Then, the adversary can solve the long-term share secret key K_AB from above equation since the rest parameters are all known. Thus, the adversary can solve all other share secret keys based on the same equation.

In the two-pass MQV key agreement protocol, instead of using K=a ^kA ^kB=r_B^kA= r_A^kB mod p as the share secret key, it uses K=a ^xA ^kB^{+ x}B ^kA =y_A^kB r_A^xB=y_B^kA r_B^xA mod p as the share secret key. The MQV protocol can provide perfect forward secrecy.

Here, we want to propose an efficient protocol that enables A and B to share multiple secret keys in two passes. For the sake of simplicity, we assume that A and B want to share four secrets in two passes.

1. A generates two random short-term secret keys, k_A1 and k_A2, and two corresponding public keys, r_A1 and r_A2. A should arrange r_A1< r_A2. Then, A computes the signature s_A for {r_A1, r_A2} based on any signature variant as listed in the table by replacing r= a^rA1^rA2 and k= k_A1+k_A2. For example, A obtains s_A by solving the following equation

x_A=a^rA1^rA2(k_A1+k_A2)+s_A mod p-1.

A sends {r_A1, r_A2, s_A, cert(y_A)} to B, where cert(y_A) is the public-key certificate of y_A signed by a trusted party,

2. Similarly, B generates k_B1, k_B2, r_B1, r_B2, s_B and sends {r_B1, r_B2, s_B, cert(y_B)} to A.
3. A computes r_B=a^rB1^rB2 mod p first and then verifies {r_B1, r_B2} based on the signature s_B and B’s public key y_B by checking

The signatures, x_A and x_B, satisfy the following equations as

x_A=a^rA1^rA2(k_A1+k_A2)+s_A mod p-1, and

x_B=a^rB1^rB2(k_B1+k_B2)+s_B mod p-1.

By multiplying these two equations together, we obtain

x_A x_B= r_A r_B[ k_A1 k_B1+ k_A2 k_B1+ k_A1 k_B2+ k_A2 k_B2]+ s_A r_B(k_B1+k_B2)+s_B r_A(k_A1+k_A2)

where r_A=a^rA1^rA2 mod p and r_B=a^rB1^rB2 mod p. In other words, we have

K_AB=(K₁ K₂ K₃ K₄)^rA^rB (r_B1 r_B2) ^sA ^rB (r_A1 r_A2) ^sB ^rA (a) ^sA ^sB mod p.

If the adversary knows four consecutive share secret keys, he can solve the long-term share secret K_AB. In case the adversary knows the other three consecutive share secret keys, the adversary is able to derive the fourth share secret key. Thus, in order to achieve the perfect forward secrecy, we should limit ourselves to use only three out of the four share secret keys. Since one of the share secret keys has never been used, the adversary is impossible to recover the long-term share key K_AB.

The protocol can be generalized to enable A and B to share n²-1 secrets if each user computes and sends n Diffie-Hellman’s public keys in each pass. Since each user only needs to generate (verify) one signature for n different Diffie-Hellman public keys and enable to share n²-1 secret keys, this new protocol is very efficient.

4. Conclusion

We have proposed a key agreement protocol that utilizes a digital signature for authenticating Diffie-Hellman public keys. We summarize some features in this new protocol:

• Since we integrate the Diffie-Hellman public key in the signature scheme, this approach reduces computation.
• Since the protocol does not use any one-way function, the security assumption relies only on solving the discrete logarithm problem.
• Our protocol allows two communication parties to share multiple secret keys in two-pass interaction.
• The computation for share secret keys is simpler than the MQV protocol.