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

William Whyte <wwhyte@securityinnovation.com> Mon, 13 January 2014 04:16 UTC

Return-Path: <wwhyte@securityinnovation.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 770091ACCE6 for <cfrg@ietfa.amsl.com>; Sun, 12 Jan 2014 20:16:50 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.378
X-Spam-Level:
X-Spam-Status: No, score=-1.378 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FM_FORGED_GMAIL=0.622, HTML_MESSAGE=0.001, SPF_PASS=-0.001] autolearn=no
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id y0gFNbaEh9Jq for <cfrg@ietfa.amsl.com>; Sun, 12 Jan 2014 20:16:46 -0800 (PST)
Received: from mail-qc0-x234.google.com (mail-qc0-x234.google.com [IPv6:2607:f8b0:400d:c01::234]) by ietfa.amsl.com (Postfix) with ESMTP id 5E8201A1EF9 for <cfrg@irtf.org>; Sun, 12 Jan 2014 20:16:46 -0800 (PST)
Received: by mail-qc0-f180.google.com with SMTP id i17so955966qcy.25 for <cfrg@irtf.org>; Sun, 12 Jan 2014 20:16:35 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=securityinnovation.com; s=google; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=JAT1B0O20hjT4s/SuyQTh+UvKpRxVWjnwLx0lNAz5gc=; b=Q9incPLxBaYH5naacM6/kHJuKya+A2xhx9v41knjtJw96DbRaGm4eVlbFCczXjkkf3 /9AD2/XQqz8c8M2JOtC5pmOqaIniVGAyn23iVR9CjgMhD3bOQtWvMg9EzZhuTPJGft+0 R1MXAI1GbHJcj9zTDtq0muyzj14IyqVofi/qA=
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:to:cc:content-type; bh=JAT1B0O20hjT4s/SuyQTh+UvKpRxVWjnwLx0lNAz5gc=; b=HmrdzzJ+KDS8vKMWb9ykmcweVB+OGGXYuHNtk8pGrnTtCPwYV7vfRD5lHUOUbK5vJt JnzoitKNxd5n7eiFGghbiSX6woYj3D6GQyRUkKEWkDWBadjklapl/JmQV6ZNvpWv9zUO EvTwKUyQXavkYLAsa9yjzesnJftvHyzLJ/4GOLnWLFn5f3QsQEOzWlrnFOfL3Lez77AV 6+Wrm8zQr0KWr73JIiCECYLsdBj3guImQPq6PqNo7sc9OVuv5LSUWnZSvCBO4BLCatM4 zNdc6VIN8KJPksxgSrthog38DiXmsm7S1rpje63U/N+th3xyShL/kDsFFf+vMMVLZh3X a+bA==
X-Gm-Message-State: ALoCoQmce6JYRPmqcKbL+MDO0enn3sgH27HGSETUX5mmcg0ujqGjERjPR26epN3LxnUvOfEPvn9W
MIME-Version: 1.0
X-Received: by 10.224.168.13 with SMTP id s13mr35441680qay.18.1389586595146; Sun, 12 Jan 2014 20:16:35 -0800 (PST)
Received: by 10.96.162.99 with HTTP; Sun, 12 Jan 2014 20:16:35 -0800 (PST)
In-Reply-To: <52D29B10.4030401@cisco.com>
References: <52C755AA.70200@cisco.com> <33E0BF53-A331-4646-B080-FD4F6E13916E@ieca.com> <810C31990B57ED40B2062BA10D43FBF5C1BF54@XMB116CNC.rim.net> <52D29B10.4030401@cisco.com>
Date: Sun, 12 Jan 2014 23:16:35 -0500
Message-ID: <CACz1E9rsLRwqpA0fS2RNOcpsn7DMqaN=7dcJDQqEi8HDMKKonQ@mail.gmail.com>
From: William Whyte <wwhyte@securityinnovation.com>
To: David McGrew <mcgrew@cisco.com>
Content-Type: multipart/alternative; boundary="089e01493b2a639b3804efd25743"
Cc: Dan Brown <dbrown@certicom.com>, "TurnerS@ieca.com" <TurnerS@ieca.com>, "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] likelihood that someone has a quantum computer (was: Re: considering new topics for CFRG)
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Mon, 13 Jan 2014 04:16:50 -0000

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.

> 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."

Cheers,

William


On Sun, Jan 12, 2014 at 8:39 AM, David McGrew <mcgrew@cisco.com> 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.txthttp://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
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg
>
>