Re: [Cfrg] likelihood that someone has a quantum computer
William Whyte <wwhyte@securityinnovation.com> Tue, 14 January 2014 02: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 71F671AE1B0 for <cfrg@ietfa.amsl.com>; Mon, 13 Jan 2014 18:16:13 -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 vIlGi_usr0pf for <cfrg@ietfa.amsl.com>; Mon, 13 Jan 2014 18:16:11 -0800 (PST)
Received: from mail-qe0-x22b.google.com (mail-qe0-x22b.google.com [IPv6:2607:f8b0:400d:c02::22b]) by ietfa.amsl.com (Postfix) with ESMTP id 091D01ADFE4 for <cfrg@irtf.org>; Mon, 13 Jan 2014 18:16:10 -0800 (PST)
Received: by mail-qe0-f43.google.com with SMTP id nc12so1090499qeb.16 for <cfrg@irtf.org>; Mon, 13 Jan 2014 18:15:59 -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; bh=XZs46C0gnQ6QAuRpCfWUTunX250QmMMFgPo7Yq9RT0s=; b=VfjPop3y03OkjQpMzI/XhbouTzmmOmFV3Jet5xa9dQEcL45o9WS7abxEC1TNQEwbV0 Qarc82cqjrfMQEHXK0zvlGA57MYwfbOb+HVi8BbHk/vSMwtWzOO/SKDzC9/lKtPcrHr1 iLY0hMLoqTIx5YcAcYR8oqfVfY2jgAoRUJqXU=
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; bh=XZs46C0gnQ6QAuRpCfWUTunX250QmMMFgPo7Yq9RT0s=; b=a2M3KcVydU1/OKXu+O0DaLkYHBRn4dCoQnHT1Y/ZsMviX3nZlaDhPMHXGjE4FYO5hf mkQJsdRq7BTI2J9pDGdXTId3D/oMcJtS3Mlzk1YoXAe/OfQjX3fc3EFD00awIqIwOqSU WoI+Z9/tH4m539lLXog2TspBey/FVFKpRPnqyzHFQcGYQHD5mTJd66a83ELGK0JarDSq 6o5PUTF+ncKEpbrKT6oLQIEEgr3tsbYbKXVUSVvsjpuLUqI9q8zHkpy6MCWIojGtoX09 50kJ6ppzc5CHGrVp5aIU8eIRWLGJQjpc7uWMh7ICO0nk3ObbNu5KB8IBwPNI4bxTgmws iY9A==
X-Gm-Message-State: ALoCoQkAWdiqt2+zaX9EJfk+7c0+LE0NVTfeRuYXDh34hS4a8DP0cRoiB6Bbtlm5q0lhgGbDb+vS
X-Received: by 10.49.73.135 with SMTP id l7mr45418682qev.28.1389665759710; Mon, 13 Jan 2014 18:15:59 -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> <52D3D95C.5040902@cisco.com>
In-Reply-To: <52D3D95C.5040902@cisco.com>
MIME-Version: 1.0
X-Mailer: Microsoft Outlook 14.0
Thread-Index: AQJ4x4958Z+19boV+tPFc44KqqvFgQKFSLs2AjIpROUCKyrZpgJv7XkgAgwZdQGY1RWgkA==
Date: Mon, 13 Jan 2014 21:15:57 -0500
Message-ID: <73702d62c620d7ecfd9d4f924c24d1ab@mail.gmail.com>
To: David McGrew <mcgrew@cisco.com>
Content-Type: multipart/alternative; boundary="047d7bdc0c22f701ac04efe4c53a"
Cc: Dan Brown <dbrown@certicom.com>, TurnerS@ieca.com, 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: Tue, 14 Jan 2014 02:16:13 -0000
Hi David, >> I am skeptical about the approach of combining multiple public key algorithms, especially for postquantum algorithms. This is partly because of the complexity of the specification and the implementation, but also because it would require double the amount of work from authors, reviewers, and implementers in order to be successful. I’m not sure it’s necessarily that complex. If we have an asymmetric key transport mechanism KT that transports key material k and is semantically secure, and we have a secure KDF, it seems that Transport: KT1(k1), KT2(k2), KT3(k3), … Secret k = KDF(k1, k2, k3, …) ..will also be semantically secure. Obviously this would need to be demonstrated rigorously, but rather than seeing “double the amount of work” from the standardization point of view, I see one task to define a secure combination mechanism, and then a series of tasks to standardize individual key transport mechanisms, where this series of tasks would have to be done anyway by people who wanted their algorithms adopted. For signatures, assuming we’re looking only at diversity in public key algorithms and not hash algorithms, it’s the same: the message simply takes two signatures, one from each algorithm. Again, this would have to be specified rigorously. I think diversity in signatures is less urgent than for encryption algorithms, because of the risk of an attacker storing messages for a long time and decrypting them when possible, but it’s worth considering. Similarly, implementations have one additional task rather than double the amount of tasks. Testing may be more complicated if all pairwise combinations of algorithms are to be tested, but I expect the total number of algorithms will never be too big. Finally, authenticating the public keys may require building support for new algorithms into CAs, which could be laborious (though again, I would argue that you should do this when you don’t have to). > Patents could also be a significant issue, as you note. Yes, agreed. This would need to be looked into. Cheers, William *From:* David McGrew [mailto:mcgrew@cisco.com] *Sent:* Monday, January 13, 2014 7:18 AM *To:* William Whyte *Cc:* Dan Brown; TurnerS@ieca.com; cfrg@irtf.org *Subject:* Re: [Cfrg] likelihood that someone has a quantum computer Hi William, On 01/12/2014 11:16 PM, William Whyte 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. I am skeptical about the approach of combining multiple public key algorithms, especially for postquantum algorithms. This is partly because of the complexity of the specification and the implementation, but also because it would require double the amount of work from authors, reviewers, and implementers in order to be successful. Patents could also be a significant issue, as you note. David
- 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