[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.
- Re: [Cfrg] considering new topics for CFRG David McGrew
- Re: [Cfrg] considering new topics for CFRG David McGrew
- Re: [Cfrg] considering new topics for CFRG Trevor Perrin
- [Cfrg] considering new topics for CFRG David McGrew
- Re: [Cfrg] considering new topics for CFRG Sean Turner
- Re: [Cfrg] considering new topics for CFRG Henrick Hellström
- Re: [Cfrg] considering new topics for CFRG David Wagner
- Re: [Cfrg] considering new topics for CFRG Henrick Hellström
- Re: [Cfrg] considering new topics for CFRG Henrick Hellström
- Re: [Cfrg] considering new topics for CFRG Paul Lambert
- Re: [Cfrg] considering new topics for CFRG David McGrew
- Re: [Cfrg] considering new topics for CFRG Paul Lambert
- Re: [Cfrg] considering new topics for CFRG Stephen Farrell
- Re: [Cfrg] considering new topics for CFRG William Whyte
- Re: [Cfrg] considering new topics for CFRG Stephen Farrell
- Re: [Cfrg] considering new topics for CFRG Watson Ladd
- Re: [Cfrg] considering new topics for CFRG Paul Lambert
- Re: [Cfrg] considering new topics for CFRG Dan Brown
- Re: [Cfrg] considering new topics for CFRG Blumenthal, Uri - 0558 - MITLL
- Re: [Cfrg] considering new topics for CFRG Paul Lambert
- Re: [Cfrg] considering new topics for CFRG William Whyte
- Re: [Cfrg] considering new topics for CFRG Max Pritikin (pritikin)
- Re: [Cfrg] considering new topics for CFRG Watson Ladd
- Re: [Cfrg] considering new topics for CFRG Sean Turner
- Re: [Cfrg] considering new topics for CFRG Sean Turner
- Re: [Cfrg] considering new topics for CFRG Adam Back
- [Cfrg] QKD is pointless (was: Re: considering new… David McGrew
- Re: [Cfrg] considering new topics for CFRG Stephen Farrell
- Re: [Cfrg] QKD is pointless (was: Re: considering… Paterson, Kenny
- Re: [Cfrg] QKD is pointless (was: Re: considering… Sean Turner
- Re: [Cfrg] considering new topics for CFRG Sean Turner
- Re: [Cfrg] considering new topics for CFRG Max Pritikin (pritikin)
- Re: [Cfrg] considering new topics for CFRG Dan Brown
- Re: [Cfrg] considering new topics for CFRG Paul Lambert
- Re: [Cfrg] QKD is pointless (was: Re: considering… Igoe, Kevin M.
- Re: [Cfrg] QKD is pointless (was: Re: considering… Igoe, Kevin M.
- Re: [Cfrg] QKD is pointless (was: Re: considering… Watson Ladd
- [Cfrg] DANE in the IETF (was: Re: considering new… Paul Hoffman
- [Cfrg] One Key -> RE: considering new topics for … Paul Lambert
- Re: [Cfrg] QKD is pointless (was: Re: considering… Paul Lambert
- [Cfrg] ReL DANE in the IETF (was: Re: considering… Paul Hoffman
- Re: [Cfrg] QKD is pointless David McGrew
- Re: [Cfrg] QKD is pointless Hilarie Orman
- [Cfrg] likelihood that someone has a quantum comp… David McGrew
- Re: [Cfrg] considering new topics for CFRG dan
- Re: [Cfrg] likelihood that someone has a quantum … David Jacobson
- Re: [Cfrg] likelihood that someone has a quantum … William Whyte
- Re: [Cfrg] likelihood that someone has a quantum … Watson Ladd
- Re: [Cfrg] likelihood that someone has a quantum … Yoav Nir
- Re: [Cfrg] likelihood that someone has a quantum … Stephen Farrell
- Re: [Cfrg] likelihood that someone has a quantum … William Whyte
- Re: [Cfrg] likelihood that someone has a quantum … David McGrew
- Re: [Cfrg] likelihood that someone has a quantum … David McGrew
- Re: [Cfrg] likelihood that someone has a quantum … William Whyte
- Re: [Cfrg] likelihood that someone has a quantum … arne renkema-padmos
- Re: [Cfrg] likelihood that someone has a quantum … Igoe, Kevin M.
- Re: [Cfrg] QKD is pointless David Wagner
- Re: [Cfrg] likelihood that someone has a quantum … William Whyte
- Re: [Cfrg] likelihood that someone has a quantum … William Whyte
- Re: [Cfrg] likelihood that someone has a quantum … William Whyte
- Re: [Cfrg] likelihood that someone has a quantum … David McGrew
- Re: [Cfrg] likelihood that someone has a quantum … arne renkema-padmos
- Re: [Cfrg] considering new topics for CFRG Paul Lambert
- Re: [Cfrg] considering new topics for CFRG Igoe, Kevin M.
- Re: [Cfrg] considering new topics for CFRG Paul Lambert
- Re: [Cfrg] considering new topics for CFRG David McGrew
- [Cfrg] 'key centric' architecture (was: Re: consi… Rene Struik
- Re: [Cfrg] 'key centric' architecture (was: Re: c… Richard Barnes
- Re: [Cfrg] considering new topics for CFRG David McGrew