Sigh, a rather major correction here...
> -----Original Message-----
> From: Scott Fluhrer (sfluhrer)
> Sent: Monday, July 30, 2018 10:46 AM
> To: 'Valery Smyslov' <[email protected]>; 'Tero Kivinen'
> <[email protected]>
> Cc: [email protected]; [email protected]
> Subject: RE: [IPsec] Modp-12288 and Modp-16384
>
>
>
> > -----Original Message-----
> > From: Valery Smyslov <[email protected]>
> > Sent: Monday, July 30, 2018 4:05 AM
> > To: Scott Fluhrer (sfluhrer) <[email protected]>; 'Tero Kivinen'
> > <[email protected]>
> > Cc: [email protected]; [email protected]
> > Subject: RE: [IPsec] Modp-12288 and Modp-16384
> >
>
> >
> > What about ECDH groups? Can you estimate how long would it take for QC
> > to break Ed448 or 521-bit groups?
>
> Well, I didn't see any papers talking about a Quantum attack of ECDH.
> However, based on what I've seen:
Oops, my analysis of ECC is broken, and should be disregarded.
One major problem is my blithe assertion that:
> - Constant time ECC algorithms would appear to translate directly into the
> Quantum realm
Nope; they rely on operations that are easy in the classical realm, but don't
directly translate into the Quantum. For one, they do operations such as:
u := u^2 mod p
A classical computer has no problem with this, however a Quantum Computer is
forbidden from doing that exact operation. The problem is that all
computations done by a Quantum Computer (other than the measurement operation,
which this is not) must be invertible. However, with this operation, if the
final u value is '1', we have no idea if the original 'u' value was either 1 or
p-1; hence it's not invertbile, and so we cannot do it.
The standard Quantum Computing way to express this is something like:
(u, v) := (u, v + (u^2 mod p))
for some reasonable meaning of '+', possibly xor, possibly modular addition.
However, just cutting/pasting this into the standard ECC algorithms would chew
up massive numbers of ancillary qubits, and so that's not an option. One
probably could restructure the ECC computations to avoid these problems
(uncomputing the ancillary qubits so they can be used in later iterations),
however I cannot guess how expensive that would be.
Sorry for the wrong answer I gave earlier.
_______________________________________________
IPsec mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/ipsec
