Subject: [Cfrg] A big, big Elliptic Curve

From: Phillip Hallam-Baker <[email-masked]>
Date: Sun, 10 Apr 2016 11:59:02 -0300

Following our discussion on QC hardening. Among the range of
responses, perhaps we should consider an Elliptic Curve with a QC
difficulty comparable to that of RSA.

As mentioned in the meeting, QC attacks don't use the same algorithms
as conventional attacks and so the difficulty of breaking Curve 25519
is considerably less than breaking RSA2048.

Interpreting the NSA advice is error prone. But the straight reading
would be 'we think it more likely that a quantum computer will be
built that can break current ECC schemes before someone works out how
to break RSA 3096.

So maybe what we need is Curve2048 or Curve3096, just to be sure. It
would be slow of course. But it could be useful.

---

From: Mike Hamburg <[email-masked]>
Date: Sun, 10 Apr 2016 10:12:39 -0700

At that point, wouldn't the multiplicative group of a prime field be a better choice?

Sent from my phone.  Please excuse brevity and typos.

> On Apr 10, 2016, at 07:59, Phillip Hallam-Baker <[email-masked]> wrote:
> 
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: Ilari Liusvaara <[email-masked]>
Date: Sun, 10 Apr 2016 20:31:48 +0300

> > built that can break current ECC schemes before someone works out how

My interpretation of NSA position & announcements is:
- QC is coming sufficently soon (and here "soon" can mean 30 years or
  so) that there is no point in transitioning to ECC anymore.
- NSA thinks that multiplicative-DH is significantly harder than what
  "open literature" considers.

> At that point, wouldn't the multiplicative group of a prime field be a better choice?

Yes, I think that if you want maximum speed for given qbit bound,
multiplicative groups are faster than ECC.

However, once one has gotten to the point where QC of hundreds of
fully-coupled gbits can be built, things are looking _very_ dire,
for both.

-Ilari

---

From: Stephen Farrell <[email-masked]>
Date: Sun, 10 Apr 2016 18:42:59 +0100

>   "open literature" considers.

That seems like a reasonable interpretation if one takes what
they say at face value.

I'm not comfortable doing that to be honest. I remain concerned
that a part of this could be an attempt to discourage deployment
of current crypto by focusing attention on the next shiny thing
(pq crypto).

I do think we should be doing preparatory work on pq crypto,
but I am frankly uneasy to see people seemingly believing what
the NSA assert with no real evidence offered. These after all
are the same people (or indistinguishable from the people) who
were happy to try pull a fast one on another part of their own
government (I mean NIST/dual-ec).

I think the very least they need to do is to offer evidence if
they expect to be believed about anything non-obvious.

The solution to this quandry I think is for us to base decisions
on whatever openly available evidence we have, but on nothing else.
(So we ought not IMO factor in press-releases from anyone.)

And yes, if we don't have that evidence, that does create a
danger that we ignore qc risks more than we ought. The blame for
that however lies clearly with those who muddied the waters.

Cheers,
S.

---

From: Tanja Lange <[email-masked]>
Date: Mon, 11 Apr 2016 05:22:20 +0200

> is considerably less than breaking RSA2048.

Could you point me to sources for this? There is an old paper by
Proos and Zalka which has claims like this, but more recent work
by Roetteler and Steinwandt properly considers reversibility and 
ends up taking longer (time & qubits) for a 160 bit curve than 
1024 bit RSA. They did detailed work for binary curves and last
I talked to them were looking into odd characteristic. The jury
is still out for larger curves and larger RSA but between a
256-bit curve DLP and a 2048 RSA; I'd be surprised if RSA was 
harder.

> built that can break current ECC schemes before someone works out how
If I take them at face value they basically say: Don't complain 
if we ask you to upgrade to new crypto soon; here, as a concession 
you may continue using the old stuff as long as it is not super 
small. 

I'd rather not speculate about their intention and whether those 
are in our interest or not.

	Tanja

---

From: Peter Gutmann <[email-masked]>
Date: Mon, 11 Apr 2016 15:13:40 +0000

Stephen Farrell <[email-masked]> writes:

>The solution to this quandry I think is for us to base decisions on whatever
>openly available evidence we have, but on nothing else. (So we ought not IMO
>factor in press-releases from anyone.)

+1.  "We have evidence of X that we can't show you, but we know you'd agree
with us if you saw it" is so 1990s crypto wars.  Go with published, proven
facts, not rumours and innuendo from an organisation with a track record of
subverting crypto.

Peter.