Removing 1 modular exponentiation

[James Muir]

Mike Perry wrote:
> Thus spake Watson Ladd (watsonbladd at gmail.com):
> 
>> Hello!
>> Tor currently uses RSA encrypted DH exchanges. This requires that the
>> server and client both make 3 exponentiations: Two for DH, One for RSA.
>> But we can reduce this significantly. I've already presented this
>> before, but now I think I can justify security. Sanity checks are assumed.
>>
>> Cryptographic Personae: Anonymous Alice and Ricky the Onion Router.
>> Protocol Paramaters: A group with a "generator" g that takes on m
>> values. DDH is hard in the group. I put generator in quotes because a
>> lot of the time it's not a mathematical generator. The group is written
>> multiplicatively.
>> Setup: Ricky picks a random positive integer k less then m. Let y be
>> Ricky's public key. Then y=g^k.
>> Protocol round 1: Alice picks a random positive integer a. Let f=y^a.
>> Alice sends f to Ricky.
>> Protocol round 2: Ricky picks a random positive integer b. Let h=g^b.
>> Key calculation: Ricky computes the key as f^(b/k) where
>> (g^(k))^(1/k)=g. Alice computes the key as h^a. Note that both Ricky and
>> Alice perform 2 group exponentiations.
> 
> Well, one immediate problem is that b/k has to be an integer.. So b=rk
> for some random r and b is thus not completely random.. To clarify the
> effects of this, you should rewrite your protocol as follows from
> Round 2 on:

that's not really a problem.  all computations are done in the group 
ZZ_p. 1/k really means the inverse of k modulo the order of g in ZZ_p. 
So b/k does not have to be an integer.

putting the security of the scheme aside, one question that comes to 
mind is how Alice (the OP) is going to get an authentic copy of Ricky's 
DH public key, y.  One way to do this is to include it in the router 
descriptors.  But then we have to ask if it's worth adding a new public 
key for each OR to the Tor PKI to just save one exponentiation during 
session key agreement.

-James