[Cfrg] Two types of quantum resistance

Phillip Hallam-Baker <phill@hallambaker.com> Fri, 08 April 2016 16:17 UTC

Return-Path: <hallam@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 1933B12D547 for <cfrg@ietfa.amsl.com>; Fri, 8 Apr 2016 09:17:06 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.399
X-Spam-Level:
X-Spam-Status: No, score=-2.399 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, FREEMAIL_FORGED_FROMDOMAIN=0.199, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
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 t6ww1cR-vkdA for <cfrg@ietfa.amsl.com>; Fri, 8 Apr 2016 09:17:04 -0700 (PDT)
Received: from mail-pf0-x234.google.com (mail-pf0-x234.google.com [IPv6:2607:f8b0:400e:c00::234]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 408EC12D1AC for <cfrg@irtf.org>; Fri, 8 Apr 2016 09:17:03 -0700 (PDT)
Received: by mail-pf0-x234.google.com with SMTP id e128so78570013pfe.3 for <cfrg@irtf.org>; Fri, 08 Apr 2016 09:17:03 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=sender:date:from:to:message-id:subject:mime-version; bh=qNxq7Pubr3Yvxvit0wsULoXi7s5/DEnmnln98y3wi3E=; b=fCVwfIj77IxtmJ7ueETomG2erLpxHtWyS7U2loPHrcTROBYFSRCu3/et39z+RcON0s WSdF8c4h/QknLsJq0I2dI11C9kkoqRfuPmDE1s+Rg9uoon6CyMpYhOLn2g4eiXcoSS1f ftmyDyiS3XuqDL/e9HyPiIRdJLbm6nqlmqE8eZoP0ubEzmYq0ekTmNfIJS1uTa3POfH7 Hl6KBOcXrVQB7wJsjs/12L1BKUxN5VdIH1H1HXv1YYdfmUHYZbpyOOdRrSIZ6ROe3V/o 9I78uZOfL//Zaw0qR8CxQc0Buxub1OGT1fiUqABgEtHikOp/TyEUeBByQROWdxBeEPZy 0n2A==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:sender:date:from:to:message-id:subject :mime-version; bh=qNxq7Pubr3Yvxvit0wsULoXi7s5/DEnmnln98y3wi3E=; b=XKiGw9OaBWQClNN9SK/x0E0CM7DWIaYIWUcA/yn0vaEn5QQrVmcXCJme8sYPJvrJMe gh3BptXP3Mod2VjMAHXNvDK6a4fp0prG9yIs1EZji87lU6/CT7SuVi0QsJL8R4sxfw7D HXy5vvmr3YildakYlhv7UP2rQ+OCtgysOYEnmq4LZ3/FxwJhof44ruhhjmgRIAATIiVa aqR9RzAoxWaIkzTUSOVnqcvxgkMMoM4GhzDYTRa4DxQwu4exfXhX+UenRLbOGZlcnogo Zzm96lrRwLF+lgcv0NaxQS9Vseb791KynrapN5Vh66Pj2s/yiyQ9MWEYxsp1BaJsfiKS Hwxw==
X-Gm-Message-State: AD7BkJJZEDie2yz5Cr362lqXCms4JB1A1tjQPeY7eFYzVI03sXkdwpZ3gZyCcgGozSEzYQ==
X-Received: by 10.98.7.153 with SMTP id 25mr13951842pfh.38.1460132222794; Fri, 08 Apr 2016 09:17:02 -0700 (PDT)
Received: from mail.outlook.com (ec2-52-24-139-88.us-west-2.compute.amazonaws.com. [52.24.139.88]) by smtp.gmail.com with ESMTPSA id to9sm19788050pab.27.2016.04.08.09.17.00 for <cfrg@irtf.org> (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 08 Apr 2016 09:17:00 -0700 (PDT)
Sender: Phillip Hallam-Baker <hallam@gmail.com>
Date: Fri, 08 Apr 2016 16:16:59 +0000
From: Phillip Hallam-Baker <phill@hallambaker.com>
To: IRTF CFRG <cfrg@irtf.org>
Message-ID: <994C5976EA09B556.C00F2996-803A-4815-814F-69865ECFCC39@mail.outlook.com>
MIME-Version: 1.0
Content-Type: multipart/alternative; boundary="----=_Part_4878_831816746.1460132219649"
X-Mailer: Outlook for iOS and Android
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/26q41AyfpnbmroKeMoorvCIOE_Y>
Subject: [Cfrg] Two types of quantum resistance
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.17
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Fri, 08 Apr 2016 16:17:06 -0000

It occurred to me that there are two types of attack to be concerned with:
1) Someone creates a QC that can break any key of size x bits with some limitation on rate2) Someone applies the QC so that they can break every key.
Even if someone has a QC that can break thousands of keys a second, I doubt they are going to use it in ways that would risk the existence of the machine being discovered.
Yes we now know that DH in discrete log has a problem, someone can find an inverse function that allows any public key to be broken.
Questions1) Does the same attack or something similar apply to ECDH? Or is ECDH immune for the same reason that index calculus and RSA don't work?
2) Are there defenses we should be considering - like not using all the same groups all the time?

Sent from Outlook Mobile