Subject: [Cfrg] Two types of quantum resistance

From: Phillip Hallam-Baker <[email-masked]>
Date: Fri, 8 Apr 2016 16:16:59 +0000 (UTC)

It occurred to me that there are two types of attack to be concerned with:
1) Someone creates a QC that can break any key of size x bits with some limitation on rate2) Someone applies the QC so that they can break every key.
Even if someone has a QC that can break thousands of keys a second, I doubt they are going to use it in ways that would risk the existence of the machine being discovered.
Yes we now know that DH in discrete log has a problem, someone can find an inverse function that allows any public key to be broken.
Questions1) Does the same attack or something similar apply to ECDH? Or is ECDH immune for the same reason that index calculus and RSA don't work?
2) Are there defenses we should be considering - like not using all the same groups all the time?

Sent from Outlook Mobile

---

From: "Paterson, Kenny" <[email-masked]>
Date: Fri, 8 Apr 2016 16:23:26 +0000

Philip,

On 08/04/2016 17:16, "Cfrg on behalf of Phillip Hallam-Baker"
<[email-masked] on behalf of [email-masked]> wrote:

>Yes we now know that DH in discrete log has a problem, someone can find
>an inverse function that allows any public key to be broken.

I'm not sure what you mean by "DH in discrete log" here. We've always
known that DH is vulnerable to discrete logarithm algorithms.

>Questions
>1) Does the same attack or something similar apply to ECDH? Or is ECDH
>immune for the same reason that index calculus and RSA don't work?

Yes, Shor also applies to ECDH.

>same groups all the time?

This is unlikely to be a robust defence against a large-scale, fully
programmable quantum computer. It might provide some very limited
mitigation if the quantum hardware technology path evolves in particular,
restricted ways, but I would not be happy betting that it will (or you'd
need to give me very generous odds).

Cheers

Kenny

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 8 Apr 2016 19:30:28 +0300

> Questions1) Does the same attack or something similar apply to ECDH? Or is ECDH immune for the same reason that index calculus and RSA don't work?

In fact, ECDH is even more vulernable to QC than (mult-group)DH. This
is because the increased qubit requirements per field bit are not enough
to balance the reduction in field bits.

IIRC, pretty much any elliptic curve in use can be cracked with ~3kqbit
QC, whereas DH2k would need ~4kqbit.

> 2) Are there defenses we should be considering - like not using all the same groups all the time?

That won't help against QC. It would help against some attacks, but
those are hopeless against prime-curve ECDH anyway.

-Ilari

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Fri, 8 Apr 2016 13:47:35 -0300

> Yes, Shor also applies to ECDH.

Does Shor allow a logjam type attack where you work out the magic key
that allows you to use a conventional computer to convert a public key
to a private?

My hunch based on my DESY/CERN experience is that the first quantum
computers are going to look like science experiments and be rather
temperamental. Like the totemak fusion experiments that would run for
a few milliseconds and then be down for weeks.

Getting from that point to being able to run one in production is
likely to take another decade of engineering.

Hence whether the math enables the general attack to solve an entire
curve or just individual points on a curve is quite significant.

> need to give me very generous odds).

I am not very happy about any of this...

Isn't it a bit odd that we have two really hard engineering problems
involving trying to maintain a particular quantum state for a
sustained period? One is very hot and offers limitless free energy.
The other is very cold and threatens to destroy the basis of the
information infrastructure.

Oh and the very cold one also has the curious property that we don't
know if the problem has been solved or not until we open up the NSA
box.

---

From: Douglas Stebila <[email-masked]>
Date: Fri, 8 Apr 2016 13:34:57 -0400

> QC, whereas DH2k would need ~4kqbit.

Do you happen to remember where those estimate came from?  Were they for logical qubits or physical qubits?

Douglas

---

From: Andy Lutomirski <[email-masked]>
Date: Fri, 8 Apr 2016 10:41:50 -0700

> Do you happen to remember where those estimate came from?  Were they for
logical qubits or physical qubits?

That number sounds like a huge overestimate for EC.  I bet it could be done
with a few hundred logical qubits.

I haven't looked at the details, but the recent paper from Chuang et al
suggests that most of the ancilla qubits aren't actually necessary.

--Andy

> Douglas
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: William Whyte <[email-masked]>
Date: Fri, 8 Apr 2016 14:30:14 -0400

It sounds like it comes from John Proos's master's thesis, specifically the
part here: http://arxiv.org/abs/quant-ph/0301141

The abstract: We show in some detail how to implement Shor's efficient
quantum algorithm for discrete logarithms for the particular case of
elliptic curve groups. It turns out that for this problem a smaller quantum
computer can solve problems further beyond current computing than for
integer factorisation. A 160 bit elliptic curve cryptographic key could be
broken on a quantum computer using around 1000 qubits while factoring the
security-wise equivalent 1024 bit RSA modulus would require about 2000
qubits.

My understanding is the number of qubits scales as the field size, but I
haven't read that paper in some time. If so, 512-bit ECC would take about
3000 qubits.

William