Removing 1 modular exponentiation

[Watson Ladd]

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.
Security justification: The goal of this protocol is to authenticate
Ricky to Alice. We have 2 values that can be modified by an attacker: f
and h. If the attacker modifies f, Ricky will compute a different key
then Alice. Likewise, if the attacker modifies h then Alice will compute
 a different key then Ricky. His one option remaining is to make equal
changes to both. But if Ricky and Alice reject bad values, then it is
the same as if Alice and Ricky had picked different nonces, and the
attacker still needs to solve the same problem. If k is reveled, then
the attacker needs to break a Diffie-Hellman exchange, so forwards
secrecy is preserved. We can also reduce DDH to this problem by letting
k equal 1.

I'll keep on working on this, and comments are welcome.
Thanks,
Watson Ladd

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 249 bytes
Desc: OpenPGP digital signature
URL: <http://lists.torproject.org/pipermail/tor-talk/attachments/20070218/515197dd/attachment.pgp>