Re: [Cfrg] Suggestion for open competition on PAKE -> Was Re: Dragonfly has advantages

[Feng Hao <[e-mail]>]

Hi Trevor,

On 04/01/2014 17:18, "Trevor Perrin" <[e-mail]> wrote:

>On Sat, Jan 4, 2014 at 7:23 AM, Feng Hao <[e-mail]> wrote:
>>
>> In summary, if the password element derivation in Dragonfly can be done
>> securely and efficiently, that would be a good contribution in my view.
>> That would even resolve an issue that SPEKE can't. The way that SPEKE
>> works is by requiring the use of a safe prime, but then for 1024-bit p,
>> the exponent will be 1023 bits - one modular exponentiation will be
>> equivalent to about 6 times of the exponentiation with a 160-bit
>>exponent.
>
>Hi Feng,
>
>Minor comments:  I don't agree that Dragonfly could "resolve an issue
>that SPEKE can't".
>
>It's true that SPEKE is generally described in terms of safe primes to
>avoid the problems Dragonfly is running into.
>
>But any password element derivation that works for Dragonfly would of
>course work for SPEKE.


Actually, I don't see disagreement here, but maybe I didn't express myself
clearly.

I mean if Dan manages to work out a way to derive the PE "securely and
efficiently" for Dragonfly, the same technique would also work for SPEKE.
Of course, that is a big "IF" at the moment, but I hope Dan will continue
to work on it. 


>
>
>> (Some people compare PAKEs by merely counting the number of modular
>> exponentiations, but they should also look at if the protocol readily
>> accommodates short exponents. The length of the exponent has a direct
>> impact on the cost of exponentiation.)
>
>Another important issue, particularly for EC protocols, is to
>distinguish operations with a fixed base (or fixed point) from
>operations with a random base / point.
>
>The fixed operations can be optimized to be several times faster
>(perhaps ~4x is a rule of thumb I've heard).

I guess you mean optimizing by caching the intermediate terms or saving
them in a look-up table? The amount of speed-up is not surprising. It also
applies to the exponential operation in a prime field, where one can
pre-compute all the square terms for a fixed base.

There are all sorts of similar optimizing tricks (generally involving
memory/speed trade-off and off-line pre-computation) that people can play
to make the cost in the protocol look as small as possible. But that often
raises a lot of confusion. For fairness, one should compare protocols
side-by-side under the same levels of optimization.

>
>
>Trevor