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

Philip Lafrance <philip.lafrance92@gmail.com> Mon, 08 May 2017 18:44 UTC

Return-Path: <philip.lafrance92@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 A59ED129576 for <cfrg@ietfa.amsl.com>; Mon, 8 May 2017 11:44:29 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.449
X-Spam-Level:
X-Spam-Status: No, score=-2.449 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_ENVFROM_END_DIGIT=0.25, FREEMAIL_FROM=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 pnHpsPNMmrqJ for <cfrg@ietfa.amsl.com>; Mon, 8 May 2017 11:44:27 -0700 (PDT)
Received: from mail-io0-x234.google.com (mail-io0-x234.google.com [IPv6:2607:f8b0:4001:c06::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 7E368128B51 for <cfrg@irtf.org>; Mon, 8 May 2017 11:44:27 -0700 (PDT)
Received: by mail-io0-x234.google.com with SMTP id k91so56090390ioi.1 for <cfrg@irtf.org>; Mon, 08 May 2017 11:44:27 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=/QcOTpn+jvth3ky+i7cxnMVxSUvQWDc+1Uu9nZoRlXo=; b=ZQkCnTlxBa2DuWjwI744Fh4WPGfVZXvYb4j9kMw7ihejdDERCMDFhx5++lEwV8ApeG vUSfBXDM/C4wWoBa16vD2c/k4Xn6UFAIe+s9ImGAQ8+Uz+crqopYPyNQEgfotwdhki4z 9yak++5MnO5Y54jqjOBZXIJz/4rjx50U3vW6J24vX0Bdj6PMYQDic8sVl+sjfKXHSw17 bvu8HaX7QbQVvzd8B787Z9BLretbYYaTdP5nXi7tIwGfXrbqUnx7yRF68AcaXCUXXyJ4 OaCuho3BI7/1VeMPINVuOaXmd13KLekRUJojPXxLXN9pu0aVTtUxQSVrUAojEBCO1i1N C6cA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=/QcOTpn+jvth3ky+i7cxnMVxSUvQWDc+1Uu9nZoRlXo=; b=NE0LNY3v8ExpqbBiPtfJSr+VHqiFZ4eqqfaS02pLCdya3piQD7xjoLz+TN5YMi8/7S rNX9DsusBbSNIdFhlWUXG16JOpP8adrKmtaXCPjxWtSIhtLhPpIiPXEBu2/jioD0UiYo wBAj5OR2b8k5NQzQqdY9vy9s3wyH2dImiFMLOxN2bxnJpWbY6LUnPgwzW19iYwjD/Jd9 InJhBxXYuhZspBbfdu2dwhJvWbExyTFoXDtVzJ6/jQSgL+MLJncMWaJZ+6L4+4HD3iFB ZOQB7iaNjYfUNuHc4vXlfSexxRuRvX28VJ51nMsoiaJ2qlXqUlkfHcjo/oNAKLKrWVpr T7vw==
X-Gm-Message-State: AODbwcB5OUZAA0nw+yZhJendVIDK0k8WVmXPTbmq4aGqyAhxJDc6xVjI cUzcPiwqWUYsIh+ANuDi3rM863WnYA==
X-Received: by 10.107.128.98 with SMTP id b95mr19599840iod.25.1494269066881; Mon, 08 May 2017 11:44:26 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.107.11.212 with HTTP; Mon, 8 May 2017 11:44:26 -0700 (PDT)
In-Reply-To: <810C31990B57ED40B2062BA10D43FBF501B13ECA@XMB116CNC.rim.net>
References: <810C31990B57ED40B2062BA10D43FBF501B13ECA@XMB116CNC.rim.net>
From: Philip Lafrance <philip.lafrance92@gmail.com>
Date: Mon, 08 May 2017 14:44:26 -0400
Message-ID: <CALwqbuzErvqjbLjaOQ=EODE+tYJHLpk6KfPJ96yh_K1s7cpSBw@mail.gmail.com>
To: Dan Brown <danibrown@blackberry.com>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary="001a113dfdaeee3847054f07a0bc"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/MEmnu-5SmuXSlJrUyTsRKsQ-lcc>
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:44:30 -0000

I wanted to make a comment about the introduction of more powerful, but
classical computers.

There is a good thermodynamics argument to be made here. Even absurdly
powerful classical devices need to actually perform the bit operations.
Consider the 128 bit level of security. I'm being vague here, but I am
pretty sure if even if you assume that every operation is just a bit-flip,
then 2^{128} such operations would still take >1% of the Earth's annual
power output. Maybe I am being slightly inaccurate, but the point is that
even high powered super computers simply don't have the time or energy to
say factor secure RSA moduli (try something with 256-bits of classic
security!). This is one of the reasons that quantum computers are so
dangerous to public key crypto, they compute in a fundamentally different
way which more or less avoid the thermodynamics problem.

For this reason, I believe quantum-resistant standards are more important
for us to consider than contradictions to Moore's law. However, this is far
from the best possible argument for quantum-resistance.

-Philip Lafrance

On Mon, May 8, 2017 at 11:31 AM, Dan Brown <danibrown@blackberry.com> wrote:

> Dear CFRG,
>
> Please forgive my naivety on the matters below.
>
> 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),
>
> (b) model (1) is known [?] to affect all algorithms equally, so we must
> just give up on it,
>
> (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).
>
> Are these the established answers, or is there better answers?
>
> 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.
>
> Best regards,
>
> Dan Brown
>
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>