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

David McGrew <mcgrew@cisco.com> Sun, 12 January 2014 13:39 UTC

Return-Path: <mcgrew@cisco.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 8965B1ADFC5 for <cfrg@ietfa.amsl.com>; Sun, 12 Jan 2014 05:39:44 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -8.139
X-Spam-Level:
X-Spam-Status: No, score=-8.139 tagged_above=-999 required=5 tests=[BAYES_40=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, RP_MATCHES_RCVD=-0.538, SPF_PASS=-0.001, USER_IN_DEF_DKIM_WL=-7.5] autolearn=ham
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 bvF30lEGHVZx for <cfrg@ietfa.amsl.com>; Sun, 12 Jan 2014 05:39:41 -0800 (PST)
Received: from alln-iport-6.cisco.com (alln-iport-6.cisco.com [173.37.142.93]) by ietfa.amsl.com (Postfix) with ESMTP id 21A571AD7BE for <cfrg@irtf.org>; Sun, 12 Jan 2014 05:39:41 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=@cisco.com; l=16725; q=dns/txt; s=iport; t=1389533970; x=1390743570; h=message-id:date:from:mime-version:to:cc:subject: references:in-reply-to; bh=K0M7XRuXAcAiP0IrzuRt+titQpSdCJDJpx/bKDKaUeI=; b=fxT9SmRFOZFj2kpLLWdVo+i67GV5fnPmcHayfxBiXJGoduoVhBkce0Du kLcr7GvcWof0uc78perHdAwKK0b7dWmOrrPYPuAAS1blDSon3rpBcn/rT EwNiPnVnAKxsFyH+zU2opOIYZ5WyrH5GJhrp3VEl/qelWzR7bQKqRambN I=;
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AiIFAISa0lKtJV2c/2dsb2JhbABagws4g1S2aYEHFnSCJQEBAQIBASNIDQEFCxkKCRYLAgIJAwIBAgFFBg0BBwKHeAgNqUWaTheOJBVJBQeCb4FIBIlDjlSBMIUVi1CBb4FcHg
X-IronPort-AV: E=Sophos; i="4.95,647,1384300800"; d="scan'208,217"; a="12268755"
Received: from rcdn-core-5.cisco.com ([173.37.93.156]) by alln-iport-6.cisco.com with ESMTP; 12 Jan 2014 13:39:29 +0000
Received: from [10.0.2.15] (rtp-mcgrew-8914.cisco.com [10.117.10.229]) by rcdn-core-5.cisco.com (8.14.5/8.14.5) with ESMTP id s0CDdSB5010564; Sun, 12 Jan 2014 13:39:29 GMT
Message-ID: <52D29B10.4030401@cisco.com>
Date: Sun, 12 Jan 2014 08:39:28 -0500
From: David McGrew <mcgrew@cisco.com>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20130922 Icedove/17.0.9
MIME-Version: 1.0
To: Dan Brown <dbrown@certicom.com>
References: <52C755AA.70200@cisco.com> <33E0BF53-A331-4646-B080-FD4F6E13916E@ieca.com> <810C31990B57ED40B2062BA10D43FBF5C1BF54@XMB116CNC.rim.net>
In-Reply-To: <810C31990B57ED40B2062BA10D43FBF5C1BF54@XMB116CNC.rim.net>
Content-Type: multipart/alternative; boundary="------------000607020406010306060706"
Cc: "'TurnerS@ieca.com'" <TurnerS@ieca.com>, "'cfrg@irtf.org'" <cfrg@irtf.org>
Subject: [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: Sun, 12 Jan 2014 13:39:44 -0000

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.