Re: [Cfrg] likelihood that someone has a quantum computer
David McGrew <mcgrew@cisco.com> Mon, 13 January 2014 12:03 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 2C6EA1AE08B for <cfrg@ietfa.amsl.com>; Mon, 13 Jan 2014 04:03:20 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -15.039
X-Spam-Level:
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 mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id XFLTp-nc9ymP for <cfrg@ietfa.amsl.com>; Mon, 13 Jan 2014 04:03:17 -0800 (PST)
Received: from rcdn-iport-6.cisco.com (rcdn-iport-6.cisco.com [173.37.86.77]) by ietfa.amsl.com (Postfix) with ESMTP id 6957B1ADF68 for <cfrg@irtf.org>; Mon, 13 Jan 2014 04:03:17 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=@cisco.com; 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-Anti-Spam-Result: AiMFAK/V01KtJXG9/2dsb2JhbABagws4g1S2bYEPFnSCJQEBAQICAQEBIA8BBTMDCgEQCxgCAgUWCwICCQMCAQIBFTAGDQEFAgIFh3sNqgCabxeBKYs8gT8SAQEBSQUHgm+BSAEDiUOOVIEwhRWLUINLHoE1
X-IronPort-AV: E=Sophos;i="4.95,652,1384300800"; d="scan'208";a="296966689"
Received: from rcdn-core2-2.cisco.com ([173.37.113.189]) by rcdn-iport-6.cisco.com with ESMTP; 13 Jan 2014 12:03:01 +0000
Received: from [10.0.2.15] (rtp-mcgrew-8914.cisco.com [10.117.10.229]) by rcdn-core2-2.cisco.com (8.14.5/8.14.5) with ESMTP id s0DC309Z004271; Mon, 13 Jan 2014 12:03:00 GMT
Message-ID: <52D3D5F3.8020108@cisco.com>
Date: Mon, 13 Jan 2014 07:02:59 -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: Watson Ladd <watsonbladd@gmail.com>
References: <52C755AA.70200@cisco.com> <33E0BF53-A331-4646-B080-FD4F6E13916E@ieca.com> <810C31990B57ED40B2062BA10D43FBF5C1BF54@XMB116CNC.rim.net> <52D29B10.4030401@cisco.com> <CACz1E9rsLRwqpA0fS2RNOcpsn7DMqaN=7dcJDQqEi8HDMKKonQ@mail.gmail.com> <CACsn0c=mYv7v3fGCHCe9D5w2j+gRWWsmoUA7NQ=AsczTMP1rDw@mail.gmail.com>
In-Reply-To: <CACsn0c=mYv7v3fGCHCe9D5w2j+gRWWsmoUA7NQ=AsczTMP1rDw@mail.gmail.com>
Content-Type: text/plain; charset="UTF-8"; format="flowed"
Content-Transfer-Encoding: 8bit
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
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 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 > <wwhyte@securityinnovation.com> 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 variety. David > >>> 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 <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.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 >>> Cfrg@irtf.org >>> http://www.irtf.org/mailman/listinfo/cfrg >>> >> >> _______________________________________________ >> Cfrg mailing list >> Cfrg@irtf.org >> http://www.irtf.org/mailman/listinfo/cfrg >> > >
- 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