Subject: [Cfrg] naive question: QC vs RC vs Moore-blip

From: Dan Brown <[email-masked]>
Date: Mon, 8 May 2017 15:31:03 +0000

Dear CFRG,

Please forgive my naivety on the matters below.
 
If quantum computers are realistic enough to warrant standards changes (now or soon), then what about other hypothetical computers, such as:

(1) computers that can do super high-precision, as in the "real computation" model (or whatever variant of this model that can implement Shamir's algorithm to factor using super-large integers in a polynomial (even linear?) number of integer arithmetic steps),

(2) sudden (single) blips exceeding the usual Moore's law (and variants) for future computing power (e.g. are sudden and new 100x faster transistor material, superconductors, photonics, less realistic than quantum computers)?

I don't know the established answers, but would speculate:

(a) quantum computers are deemed more realistic than each of (1) and (2),

(b) model (1) is known [?] to affect all algorithms equally, so we must just give up on it,

(c) most justifications for 128-bit security already include a margin of error for risk (2),

(d) 256-bit security (and variants) are meant to deal with (2).

Are these the established answers, or is there better answers? 

As a research issue, I'd like to know more about (b), if it is correct.

I'd like to know more about (a), the why of it, but am unlikely to understand.

Best regards,

Dan Brown

---

From: "Henry B (Hank) Hotz, CISSP" <[email-masked]>
Date: Mon, 8 May 2017 10:49:19 -0700

I’m not sure how much energy this whole subject is worth, honestly. Remember that the reason the NSA started talking about post-quantum when they did was to distract us from the Dual-EC random number generator debacle.

I have absolutely no doubt that people are pouring tons of money into QC and making progress. I just don’t think we can take anything said about the maturity of the technology at face value. 

Full disclosure: my opinions are colored by the way JPLs SeaSat spacecraft met an untimely death (and the ugly politics afterward). It used off-the-shelf spy satellite components and JPL was not allowed to know what their real performance was. 

Given all of those uncertainties, wouldn’t our efforts be better spent worrying about the other things we know we don’t know? (And keep an eye out for things we don’t know we don’t know.)

(This is not intended as an attack on you Dan!! Just my opinion.)

> On May 8, 2017, at 8:31 AM, Dan Brown <[email-masked]> wrote:
> 
> Dear CFRG,
> 
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

Personal email.  [email-masked]

---

From: "Tams, Benjamin" <[email-masked]>
Date: Mon, 8 May 2017 18:09:54 +0000

> (1) computers that can do super high-precision, as in the "real computation" model (or whatever variant of this model that can implement Shamir's
> algorithm to factor using super-large integers in a polynomial (even linear?) number of integer arithmetic steps),
> 
> (2) sudden (single) blips exceeding the usual Moore's law (and variants) for future computing power (e.g. are sudden and new 100x faster transistor 
> material, superconductors, photonics, less realistic than quantum computers)?
>

I think (2) and partially (1) is more realistic than the close appearance of quantum computers 
(but I do not know).

> (b) model (1) is known [?] to affect all algorithms equally, so we must just give up on it,

Don't know if you are referring to the "real computation" model or Shamir's factoring device.
I consider it unlikely that mere improvements in factoring integers will improve on
other algorithms equally. In fact, factoring integers is not even believed to correspond
to an NP-hard problem. For (1), I do not know much about its consequences from the
scratch.

> (d) 256-bit security (and variants) are meant to deal with (2).

I hope so. :-)

> Are these the established answers, or is there better answers? 

Interested, too. 

>I'd like to know more about (a), the why of it, but am unlikely to understand.

I think sudden Moore blips are quite realistic. But a few of them won't help
much in factoring or solving discrete log problems (though a little).

Kind  regards,
Benjamin Tams

---

From: Philip Lafrance <[email-masked]>
Date: Mon, 8 May 2017 14:44:26 -0400

I wanted to make a comment about the introduction of more powerful, but
classical computers.

There is a good thermodynamics argument to be made here. Even absurdly
powerful classical devices need to actually perform the bit operations.
Consider the 128 bit level of security. I'm being vague here, but I am
pretty sure if even if you assume that every operation is just a bit-flip,
then 2^{128} such operations would still take >1% of the Earth's annual
power output. Maybe I am being slightly inaccurate, but the point is that
even high powered super computers simply don't have the time or energy to
say factor secure RSA moduli (try something with 256-bits of classic
security!). This is one of the reasons that quantum computers are so
dangerous to public key crypto, they compute in a fundamentally different
way which more or less avoid the thermodynamics problem.

For this reason, I believe quantum-resistant standards are more important
for us to consider than contradictions to Moore's law. However, this is far
from the best possible argument for quantum-resistance.

-Philip Lafrance

On Mon, May 8, 2017 at 11:31 AM, Dan Brown <[email-masked]> wrote:

> If quantum computers are realistic enough to warrant standards changes
> (now or soon), then what about other hypothetical computers, such as:
>
> (1) computers that can do super high-precision, as in the "real
> computation" model (or whatever variant of this model that can implement
> Shamir's algorithm to factor using super-large integers in a polynomial
> (even linear?) number of integer arithmetic steps),
>
> (2) sudden (single) blips exceeding the usual Moore's law (and variants)
> for future computing power (e.g. are sudden and new 100x faster transistor