Re: [Cfrg] likelihood that someone has a quantum computer (was: Re: considering new topics for CFRG)

[Watson Ladd <[e-mail]>]

On Sun, Jan 12, 2014 at 8:16 PM, William Whyte
<[e-mail]> wrote:
> Hi all,
>
> Sorry again for top-posting, that's gmail for you.
>
>> I would put it more positively as: let's figure out how to use
>> post-quantum cryptography in practice, because if there is a breakthrough in
>> quantum computing, the mad rush will be ugly.
>
> As I mentioned in a previous mail, I think the best way to do this is to
> figure out how to avoid depending on a single public key algorithm in any
> context, because all public key algorithms are potentially vulnerable to
> technological and algorithmic breakthroughs. So combining public key
> algorithms seems like a prudent approach. I know there are Certicom patents
> on this but it seems that this shouldn't be insuperable.

But that depends on at least one algorithm being postquantum secure,
and historically
we've not had any real surprises in the public key world.
Algorithms exist that do this, we just need to be ahead of the game in
specifying them. I'll see if McBits is amenable to standardization. Worst
case we wait for NTRU patents to expire, and adopt it. Yeah, we lose some
nice stuff in the post-quantum world, but most IETF protocols will survive
no problem. Signatures are a bit nasty in the present state of knowledge,
and there is protocol review work to do. Key sizes get massively bigger:
a lot of hardcoded limits will have to be revised.

However, McBits is slightly faster than existing techniques including ECC,
so the big issue is really size, not speed.

>
>> I don't think it would be fruitful to attempt to estimate the probability
>> that a quantum computer can be built.   If someone did try to make such an
>> estimate, it would make interesting reading, but I doubt that I would trust
>> it, because the likelihood of new scientific advances cannot reliably be
>> estimated.
>
> I would say the question isn't so much "can a quantum computer be built?" as
> "what size quantum computer can be built?" There's an interesting 2011 blog
> post on that subject that tries to derive a Moore's law for quantum computer
> size: http://www.quantenblog.net/physics/moores-law-quantum-computer. I
> don't know how well reviewed this has been, but it's a start: key lines are
> "The blue line is a fit to the data, indicating a doubling of the number of
> qubits every 5.7±0.4 years." and "If you are bold enough to believe that the
> same scaling continues even further, 2048-bit RSA keys would come under
> attack somewhere between 2052 and 2059."

That's a serious underestimate because it ignores the possibility of a
breakthrough
in making qubits. Once you get a method that scales up, it is likely
to be a large jump
rather than incremental increase.

>
> Cheers,
>
> William
>
>
> On Sun, Jan 12, 2014 at 8:39 AM, David McGrew <[e-mail]> wrote:
>>
>> Hi Dan,
>>
>> some further thoughts on things quantum:
>>
>> On 01/08/2014 12:32 PM, Dan Brown wrote:
>>
>>
>> 2) Is QKD something we need to start considering:
>> http://tools.ietf.org/id/draft-nagayama-ipsecme-ipsec-with-qkd-00.txt
>> http://tools.ietf.org/id/draft-ghernaouti-sfaxi-ppp-qkd-00.txt
>>
>> I am more interested in the issue of whether quantum computing (for Shor's
>> algorithm) will, or even has, become feasible? I am not an expert in the
>> area, but am interested.
>>
>>
>> this is not an area that I actively follow, but I think the following
>> description is accurate: quantum computing is an active area of research,
>> and those working in the area believe that it can become a viable technology
>> in the not-to-distant future, though there are also skeptics who feel that
>> quantum decoherence may make it impossible to ever build a quantum computer
>> that would be able to solve problems of cryptographic interest.   (An
>> important side note: the D-Wave computer is not a real quantum computer in
>> the Peter Shor sense; it does something more like simulated annealing).
>>
>> Of course, we can just go ahead and get prepared with proposals for
>> postquantum algs.  That's great to do, but still doesn't address the
>> question. I expect some may argue that asking this whole question just
>> begs
>> pointless speculation, on the grounds that if your adversary (soon) has a
>> QC, then you should have spent your time switching to PQ rather than
>> thinking about whether the adversary had a QC.  In other words, I'm
>> expecting some may say that consideration of postquantum crypto is
>> perfectly
>> reasonable, but asking about the existence of a quantum computer is
>> pointless.
>>
>>
>> This is my thinking, more or less.   I would put it more positively as:
>> let's figure out how to use post-quantum cryptography in practice, because
>> if there is a breakthrough in quantum computing, the mad rush will be ugly,
>> and besides, we don't really know what capabilities our adversaries have
>> now, or will have in a decade.
>>
>> But I think it is okay for CFRG to consider it, and, nay, even try to
>> boldly
>> quantify these, say with likelihood 2^(-64) of some well-defined claim,
>> calculated via a series of estimates.  The status quo is to just claim
>> that
>> algorithm X with key size provides 128 bit security, whatever that means,
>> perhaps adding the exclusion against quantum computers.  Adding an
>> estimated
>> likelihood of a quantum computer gives a more meaning of what kind of
>> security is being claimed.  Maybe the postquantum researchers already have
>> made such an estimate, as part of an effort to justify a switch to
>> postquantum.
>>
>>
>> I don't think it would be fruitful to attempt to estimate the probability
>> that a quantum computer can be built.   If someone did try to make such an
>> estimate, it would make interesting reading, but I doubt that I would trust
>> it, because the likelihood of new scientific advances cannot reliably be
>> estimated.   The scenario here recalls that of the prominent physicists in
>> the 1920s and 1930s who scorned H.G. Wells' predictions about nuclear power.
>> It is unlikely that those physicists would have done a better job with their
>> prognostications if they had attempted to use a formal model for Bayesian
>> inference, or some other framework for computing an exact probability.
>> (The model would just mathematically formalize their beliefs, which turned
>> out to be wrong.)
>>
>> As an aside, if it were possible to come up with accurate estimates for
>> the likelihood of scientific advances, it would be reasonable to apply that
>> methodology to other cryptographic questions.   By way of example, one could
>> ask: are we more likely to see advances in the cryptanalysis of
>> lattice-based cryptography, or code-based cryptography?    It is interesting
>> to think about, but it does not seem like we should expect this sort of
>> analysis to provide us with much concrete guidance on future standards.
>>
>> Lenstra did consider the possibility of progress in cryptanalytic
>> capabilities in his very thorough study of key lengths, and he noted that
>> one must model advances for different cryptosystems differently.   But he
>> does not attempt anything as detailed as a probability estimate for a
>> quantum computer; he says that "a clearly discernable and well-established
>> past pattern in practical cryptanalytic progress is no guarantee that the
>> future pattern will be the same or that there will not be any surprising
>> breakthroughs with immediate practical consequences."   (The quote is from
>> the handbook contribution online at
>> http://www.keylength.com/biblio/Handbook_of_Information_Security_-_Keylength.pdf)
>>
>> I would understand if the CFRG chairs deem this out of scope for CFRG.  If
>> so, I hope that somebody could suggest to me off-list an alternative
>> forum.
>>
>> An informal, perhaps dubious, argument that comes to my mind is the
>> following.  The most likely party to have a quantum computer is a large
>> nation.
>>
>>
>> Agreed.
>>
>> If they had such a thing, then they could break almost all IETF
>> crypto, except pre-shared key based stuff, and wouldn't have to resort to
>> any other chicanery.  But reports are now suggesting the latter.  Well,
>> the
>> chicanery could all be just a cover-up ruse.  Or more realistically, maybe
>> the quantum computer is kept on reserve, and more mundane cryptanalysis is
>> used on a daily basis, maybe because it is cheaper.  Still, why not just
>> lay
>> little lower, if a QC is available? Anyway, the loose inference I'm
>> drawing
>> is that a quantum computer does not yet exist, and further that the most
>> likely parties to have one do not anticipate being able to have one in the
>> near future.
>>
>>
>> I agree with some of the logic, but not the conclusion, because
>> intelligence agencies for large nations are likely to pursue all avenues
>> that are available to them.   To continue the nuclear analogy from above,
>> the vast arsenal of conventional bombs that the U.S. built in 1944 should
>> not have been taken as evidence that there was not an active and successful
>> effort to build a nuclear weapon that was proceeding concurrently.
>>
>> Thanks for the interesting discussion!
>>
>> David
>>
>> Well, this argument does not give any kind of quantified
>> likelihood. If I had to dead-reckon a likelihood, I'd make a wildly
>> different number every time, but most of them would be above 2^(-128),
>> unfortunately.
>>
>> I wonder if others have more substantial arguments.
>>
>>
>>
>>
>> ---------------------------------------------------------------------
>> This transmission (including any attachments) may contain confidential
>> information, privileged material (including material protected by the
>> solicitor-client or other applicable privileges), or constitute non-public
>> information. Any use of this information by anyone other than the intended
>> recipient is prohibited. If you have received this transmission in error,
>> please immediately reply to the sender and delete this information from your
>> system. Use, dissemination, distribution, or reproduction of this
>> transmission by unintended recipients is not authorized and may be unlawful.
>>
>>
>>
>> _______________________________________________
>> Cfrg mailing list
>> [e-mail]
>> http://www.irtf.org/mailman/listinfo/cfrg
>>
>
>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg
>



-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin