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 12:58 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 5BD5D1AE134 for <cfrg@ietfa.amsl.com>; Mon, 13 Jan 2014 04:58:03 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.379
X-Spam-Level:
X-Spam-Status: No, score=-1.379 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, 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 qs4Y2LmIVi1g for <cfrg@ietfa.amsl.com>; Mon, 13 Jan 2014 04:58:01 -0800 (PST)
Received: from mail-qe0-x236.google.com (mail-qe0-x236.google.com [IPv6:2607:f8b0:400d:c02::236]) by ietfa.amsl.com (Postfix) with ESMTP id 03BCF1ADEDC for <cfrg@irtf.org>; Mon, 13 Jan 2014 04:58:00 -0800 (PST)
Received: by mail-qe0-f54.google.com with SMTP id cy10so936210qeb.41 for <cfrg@irtf.org>; Mon, 13 Jan 2014 04:57:49 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=securityinnovation.com; s=google; h=from:references:in-reply-to:mime-version:thread-index:date :message-id:subject:to:cc:content-type:content-transfer-encoding; bh=BShzOU2wxm3AEGFUQrttrMXNfKkdNQQARwVqhOR8w2s=; b=WQ0H2WOIIQ96EcQyklbifjY4D/aJF4xzbkhhbWHSE49OnHZaOVzEACMr7xlekYk4ch 5TuvtOALfa3JWDQE0hQGrpwxRsWkDdnUCnEm7MN+T7DNombeoVHZNFQWEWLKy+I413AP xy+unrUryDldPzQfPF9ywUwJfUM4uZmTMYCy4=
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:references:in-reply-to:mime-version :thread-index:date:message-id:subject:to:cc:content-type :content-transfer-encoding; bh=BShzOU2wxm3AEGFUQrttrMXNfKkdNQQARwVqhOR8w2s=; b=m8jo54fO5iYcOVXxtnhyzgEDoywUJo42gagi1eD0Jki/E5skG3Do3MQt7gdpcBZ0DO qYohFRiYitRupGR0V11T3S4f70Bk0exmvq5BxvRUxuYAvznVl4oTVvuD8EM5UmtTAd7d zoP3T+gxHtIvKzeIfl0rBuBUyFDSvgbDtzyOdORwFyGcl78VJSpmBFjMWNTxB6gcknbR 7LZvMy3SvwQhKW1IB+T/bsl0Vg7JML7ZYIZal7/vTE7bGvqAyDeyTk/JhI3DOmO4JD1k +gAigAcavLLrKlu741KPrx2b8pjOoMLLPOndSOKAbWDOEMJhsnI7H7Q3h7M7eKhEzuhR U0uA==
X-Gm-Message-State: ALoCoQlWBcOeJRgJ9EUJvqrrcdk1yjidLFIY3BxNIPsa4EDXaPURKJbfKvahR6vfvKjbSABdi5P3
X-Received: by 10.49.73.135 with SMTP id l7mr38969973qev.28.1389617869682; Mon, 13 Jan 2014 04:57:49 -0800 (PST)
From: William Whyte <wwhyte@securityinnovation.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>
MIME-Version: 1.0
X-Mailer: Microsoft Outlook 14.0
Thread-Index: AQJ4x4958Z+19boV+tPFc44KqqvFgQKFSLs2AjIpROUCKyrZpgJv7XkgAVQx05OY2dCCUA==
Date: Mon, 13 Jan 2014 05:48:48 -0500
Message-ID: <d4d82e7c3988ce4908202185921ed7bb@mail.gmail.com>
To: Watson Ladd <watsonbladd@gmail.com>
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: quoted-printable
Cc: Dan Brown <dbrown@certicom.com>, TurnerS@ieca.com, David McGrew <mcgrew@cisco.com>, 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 12:58:03 -0000

Hi Watson,

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

I wouldn't say it "depends" on it. I would say that we know that ECC and RSA
aren't postquantum
secure and that other algorithms may be, and that using two algorithms in
parallel allows us to
deploy systems that use a newer algorithm without having to rely on it 100%.
That allows
us to start making a transition before we absolutely have to, which is
always the best time to
make it.

I don't think you can say that just because there have been few
discontinuities in the
security of algorithms there will be no discontinuities in the future. There
might be,
and if it does happen unexpectedly it'll be a big problem. It's not a
problem we need
to work on right now, but, again, that makes this a really good time to
address it.

>> Moore's law for quantum computer
>> size: http://www.quantenblog.net/physics/moores-law-quantum-computer.

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

I think you're probably right and wasn't endorsing that particular page's
results, just
putting it forward as the only estimate of its type that I've seen. I agree
that it seems
more likely to be a no-later-than than a no-earlier-than estimate, but this
isn't
really my area of expertise.

Cheers,

William


-----Original Message-----
From: Watson Ladd [mailto:watsonbladd@gmail.com]
Sent: Sunday, January 12, 2014 11:50 PM
To: William Whyte
Cc: David McGrew; Dan Brown; TurnerS@ieca.com; cfrg@irtf.org
Subject: Re: [Cfrg] likelihood that someone has a quantum computer (was: Re:
considering new topics for CFRG)

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.

>
>> 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_-_Ke
>> ylength.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
>



--
"Those who would give up Essential Liberty to purchase a little Temporary
Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin