Re: [Cfrg] naive question: QC vs RC vs Moore-blip

"Tams, Benjamin" <Benjamin.Tams@secunet.com> Mon, 08 May 2017 18:09 UTC

Return-Path: <Benjamin.Tams@secunet.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 28DAF12896F for <cfrg@ietfa.amsl.com>; Mon, 8 May 2017 11:09:59 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.901
X-Spam-Level:
X-Spam-Status: No, score=-1.901 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_NONE=-0.0001, RP_MATCHES_RCVD=-0.001] autolearn=ham autolearn_force=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 LDJeDRBiHXqo for <cfrg@ietfa.amsl.com>; Mon, 8 May 2017 11:09:57 -0700 (PDT)
Received: from a.mx.secunet.com (a.mx.secunet.com [62.96.220.36]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 752AE128656 for <cfrg@irtf.org>; Mon, 8 May 2017 11:09:57 -0700 (PDT)
Received: from localhost (localhost [127.0.0.1]) by a.mx.secunet.com (Postfix) with ESMTP id A8A15201C7; Mon, 8 May 2017 20:09:55 +0200 (CEST)
X-Virus-Scanned: by secunet
Received: from a.mx.secunet.com ([127.0.0.1]) by localhost (a.mx.secunet.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 8VMttRSd1ZYJ; Mon, 8 May 2017 20:09:55 +0200 (CEST)
Received: from mail-essen-02.secunet.de (mail-essen-02.secunet.de [10.53.40.205]) (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by a.mx.secunet.com (Postfix) with ESMTPS id 1EC1D2008B; Mon, 8 May 2017 20:09:55 +0200 (CEST)
Received: from MAIL-ESSEN-01.secunet.de ([fe80::1c79:38b7:821e:46b4]) by mail-essen-02.secunet.de ([fe80::4431:e661:14d0:41ce%16]) with mapi id 14.03.0319.002; Mon, 8 May 2017 20:09:54 +0200
From: "Tams, Benjamin" <Benjamin.Tams@secunet.com>
To: Dan Brown <danibrown@blackberry.com>, "cfrg@irtf.org" <cfrg@irtf.org>
Thread-Topic: naive question: QC vs RC vs Moore-blip
Thread-Index: AdLIDxLailn8AM7oS6K3HHWy2z/EagAFNQ5Q
Date: Mon, 8 May 2017 18:09:54 +0000
Message-ID: <78B0B91A8FEB2E43B20BCCE1326131813992A221@mail-essen-01.secunet.de>
References: <810C31990B57ED40B2062BA10D43FBF501B13ECA@XMB116CNC.rim.net>
In-Reply-To: <810C31990B57ED40B2062BA10D43FBF501B13ECA@XMB116CNC.rim.net>
Accept-Language: de-DE, en-US
Content-Language: de-DE
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-originating-ip: [172.18.9.76]
x-exclaimer-md-config: 2c86f778-e09b-4440-8b15-867914633a10
x-g-data-mailsecurity-for-exchange-state: 0
x-g-data-mailsecurity-for-exchange-error: 0
x-g-data-mailsecurity-for-exchange-sender: 23
x-g-data-mailsecurity-for-exchange-server: cbe3d3f7-b9e3-4256-b890-f24c4306a01c
x-g-data-mailsecurity-for-exchange-guid: F5DCF1E7-87CF-4290-82F1-7D1E52811BEB
Content-Type: text/plain; charset="Windows-1252"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/iSwwPI-MzKFQpFAnJXhrap_7H18>
Subject: Re: [Cfrg] naive question: QC vs RC vs Moore-blip
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.22
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: Mon, 08 May 2017 18:09:59 -0000

> If quantum computers are realistic enough to warrant standards changes (now or soon), then what about other hypothetical computers, such as:
> 
> (1) computers that can do super high-precision, as in the "real computation" model (or whatever variant of this model that can implement Shamir's
> algorithm to factor using super-large integers in a polynomial (even linear?) number of integer arithmetic steps),
> 
> (2) sudden (single) blips exceeding the usual Moore's law (and variants) for future computing power (e.g. are sudden and new 100x faster transistor 
> material, superconductors, photonics, less realistic than quantum computers)?
>
> I don't know the established answers, but would speculate:
> 
> (a) quantum computers are deemed more realistic than each of (1) and (2),
>

I think (2) and partially (1) is more realistic than the close appearance of quantum computers 
(but I do not know).

> (b) model (1) is known [?] to affect all algorithms equally, so we must just give up on it,

Don't know if you are referring to the "real computation" model or Shamir's factoring device.
I consider it unlikely that mere improvements in factoring integers will improve on
other algorithms equally. In fact, factoring integers is not even believed to correspond
to an NP-hard problem. For (1), I do not know much about its consequences from the
scratch.

> (c) most justifications for 128-bit security already include a margin of error for risk (2),
> (d) 256-bit security (and variants) are meant to deal with (2).

I hope so. :-)

> Are these the established answers, or is there better answers? 

Interested, too. 

> As a research issue, I'd like to know more about (b), if it is correct.
>
>I'd like to know more about (a), the why of it, but am unlikely to understand.

I think sudden Moore blips are quite realistic. But a few of them won't help
much in factoring or solving discrete log problems (though a little).

Kind  regards,
Benjamin Tams