Re: [Cfrg] likelihood that someone has a quantum computer

David McGrew <> Mon, 13 January 2014 12:03 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 2C6EA1AE08B for <>; Mon, 13 Jan 2014 04:03:20 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -15.039
X-Spam-Status: No, score=-15.039 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_HI=-5, RP_MATCHES_RCVD=-0.538, SPF_PASS=-0.001, USER_IN_DEF_DKIM_WL=-7.5] autolearn=ham
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id XFLTp-nc9ymP for <>; Mon, 13 Jan 2014 04:03:17 -0800 (PST)
Received: from ( []) by (Postfix) with ESMTP id 6957B1ADF68 for <>; Mon, 13 Jan 2014 04:03:17 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple;;; l=11404; q=dns/txt; s=iport; t=1389614587; x=1390824187; h=message-id:date:from:mime-version:to:cc:subject: references:in-reply-to:content-transfer-encoding; bh=4ynAkdXTIYIIkDyZAUbddB4b7DrgfAAoVYyxFls/4So=; b=aJpNMnA2KEDvY9uD4skrcwYcXYFMeYKokaMIvxsDvlEp219czA/ZSRv4 QJiM9Xf9WRcJTcA9znl+vBERk7gLekcYrsha7l3Bf9UPql6zv7VRImsNr gdly1pKuuDOsI5PUOq6xSd5UD+CfDLMFt3bhZqr7B0xj9GVLNeVqAbrYO 4=;
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-AV: E=Sophos;i="4.95,652,1384300800"; d="scan'208";a="296966689"
Received: from ([]) by with ESMTP; 13 Jan 2014 12:03:01 +0000
Received: from [] ( []) by (8.14.5/8.14.5) with ESMTP id s0DC309Z004271; Mon, 13 Jan 2014 12:03:00 GMT
Message-ID: <>
Date: Mon, 13 Jan 2014 07:02:59 -0500
From: David McGrew <>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20130922 Icedove/17.0.9
MIME-Version: 1.0
To: Watson Ladd <>
References: <> <> <> <> <> <>
In-Reply-To: <>
Content-Type: text/plain; charset="UTF-8"; format="flowed"
Content-Transfer-Encoding: 8bit
Cc: Dan Brown <>, "" <>, "" <>
Subject: Re: [Cfrg] likelihood that someone has a quantum computer
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Mon, 13 Jan 2014 12:03:20 -0000

Hi Watson,

On 01/12/2014 11:49 PM, Watson Ladd wrote:
> On Sun, Jan 12, 2014 at 8:16 PM, William Whyte
> <> 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.

Agreed; hash based signatures and code based encryption seem to be good 
candidates for post-quantum crypto standards, and the main issues with 
the use of those technologies will be in the amount of data that needs 
to be transported, rather than the computational cost.   I would guess 
that a key size of 100KB or so could be usable in many Internet 
applications, but not constrained devices of the Internet of Things 


>>> 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: 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 <> 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:
>>> 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
>>> 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
>> _______________________________________________
>> Cfrg mailing list