Subject: Re: [Cfrg] matching AES security

From: Andy Lutomirski <[email-masked]>
Date: Wed, 30 Jul 2014 12:42:40 -0700

On Wed, Jul 30, 2014 at 12:26 PM, Andrey Jivsov <[email-masked]> wrote:
> On 07/30/2014 11:47 AM, Michael Hamburg wrote:
>>
>> * Quantum computation.  More bits of AES buys you more resistance, but
>> more bits of ECC does not.
>
>
> Wouldn't more qubits mean substantially higher cost and it will take some
> time (decades?) to get from 5 (?) to 256 qubits and beyond?

Good luck.  In my view, either you have a scalable quantum computer or
you don't.  If it's scalable, then you can spend a bunch of money and
scale it.  If it's not scalable (and the current things that factor 15
aren't), you can throw as many fancy refrigerators and copies of the
machine at it as you want, and you won't get anywhere.

The asymptotic complexity of Shor's algorithm is *really* good.

>
> If so, higher bit curves have an advantage, esp. for persistent structures
> like CA certificates that cannot count on fast crypto upgrade.
>

When someone has a quantum computer, I will consider all crypto based
on Abelian groups to be dead, full stop.  (There's some reason to
believe that crypto based on elliptic curve isogenies might survive a
little bit longer, but the quantum algorithms there haven't been all
that well studied, and IIRC they're already decent.)

--Andy