Re: [Cfrg] Post Quantum (was Re: Minimum required work force for additional curve)

[Simon Josefsson <[e-mail]>]

Watson Ladd <[e-mail]> writes:

> On Mon, Mar 2, 2015 at 3:25 AM, Simon Josefsson <[e-mail]> wrote:
>> Kurt Roeckx <[e-mail]> writes:
>>
>>> Since I think this hasn't been clearly asked and that it might
>>> explain the answer on the other questions asked, I'm guess I'll
>>> just ask it myself:
>>>
>>> Assuming other than the 128 WF curve we only add 1 other curve,
>>> what is the minimum WF it should have?
>>
>> I believe the focus on power-of-two work factor comparisons for
>> asymmetric schemes is harmful.  It makes people jump to the conclusion
>> that asymmetric schemes share the commonly-believed property that
>> symmetric schemes have: that adding another bit in the key space doubles
>> the work factor.  This focus also leads to confusing "algorithm pairing"
>> ideas.
>>
>> The concept of work factor is useful though.  I don't see how humans
>> will ever do > 2^100 operations using today's non-quantum-technology.
>> Thus, to me, a work-factor of 2^100 is sufficient to address our needs.
>> And at that level, I would prefer having multiple options.
>
> Why is this better? Is it so that if one goes down we have another?

I have two reasons.  The first is to enforce algorithm agility in each
of the respective areas of protocol specifications, implementations and
deployments.  If there aren't two comparable algorithms that serve a
similar purpose, people take shortcuts in each of the areas that usually
end up bites us later on.  The second is to allow for slow migration if
weaknesses is found in one of the algorithms.  Even when new
cryptographic techniques are developed, it takes time to mount them on a
particular algorithm.

>> I could live with recommending Curve25519 and some significantly larger
>> curve like Ed448-Goldilocks if we can't get consensus on anything more
>> reasonable (like two curves at 2^100-2^130 work factor), but it will
>> lead to wasting energy computing the Ed448 operations where cheaper
>> (energy-wise) alternatives would suffice.
>>
>> If we want significantly stronger alternatives to >~2^100 work factor
>> solutions, I would prefer recommending solutions that withstand quantum
>> technology attackers -- I believe there are solutions in that space.
>
> There are various proposals, some rather old and well-implemented like
> NTRU, some old and well understood like McEliece, and some exotic
> things like Ring-LWE and isogeny volcanoes. Post-Quantum cryptography
> has been brought up here a number of times, although there are some
> problems:
>
> -Most schemes have enormous public keys. Those that don't have
> structure that helps cryptanalysis, and in some cases there is some
> low-hanging fruit to pluck. Parameter choices can become trickier.
> -Implementation availability and quality. This is solvable.
> -Different problems support signatures and encryption.
>
> We can deal with the last 2, but the first one is really something
> where more research is required.

It would be useful to use some protocols that is ameanable to rapid
prototyping with good extension frameworks as guinea pigs for these
constructs -- the sooner we get some real usage, the sooner parameter
choice, algorithms and specifications will improve.  Maybe the XMPP
community wants to play with another idea for end-to-end secure chat.

/Simon