[tor-dev] New paper by Goldberg, Stebila, and Ostaoglu with proposed circuit handshake

[Ian Goldberg]

[+ Douglas, Berkant]

On Fri, May 06, 2011 at 10:50:05AM -0400, Nick Mathewson wrote:
> Crypto people who have been following threads about the
> circuit-establishment handshake will be interested in the new paper,
> "Anonymity and one-way authentication in key-exchange protocols", by
> Goldberg, Stebila, and Ostaoglu. Here's the version they updated
> today:
> 
> http://www.cacr.math.uwaterloo.ca/techreports/2011/cacr2011-11.pdf
> 
> If we're moving to an improved handshake, this might be a good
> candidate to consider.  The protocol itself is on page 14.
> 
> Some notes, written by a guy who knows less crypto than everybody involved:
> 
>   * It's a pure Diffie-Hellman based system, which would lend itself
> nicely to use with ECC.
> 
>   * It seems to require the same number of exponentiations as our
> current system, but Ian Goldberg notes that if you want to compute X^a
> and X^b at the same time you can do so more efficiently by taking into
> account the shared base.
> 
>   * The security proof requires that the Gap DH assumption holds over
> the group -- basically, that computing the Decisional DH problem is
> easy, but computing the Computational DH problem is hard.  This
> assumption isn't true of most basic ECC groups -- I think it means you
> need to use a pairing-based system instead for the proof to hold. I'd
> bet that the authors aren't seriously suggesting that we use
> pairing-based crypto, but I'm wondering how much they were able to
> prove in a groups where DDH is hard.

Not quite: it's saying that, if you can break the protocol (_with or
without_ the ability to solve DDH), then if you _do_ have a DDH oracle,
you can also solve CDH.  Since being able to solve CDH given a DDH
oracle (the "GDH problem") would be extremely surprising, we conclude
the protocol is secure.

>   * I haven't read over the security model closely yet; folks should
> review it for reasonableness.
> 
>   * I'm hoping to write this up as a proposed spec soon, unless Ian or
> somebody wants to give it a shot.

Please go ahead.

   - Ian