[Cfrg] Post Quantum (was Re: Minimum required work force for additional curve)

Watson Ladd <watsonbladd@gmail.com> Mon, 02 March 2015 16:22 UTC

Return-Path: <watsonbladd@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com []) by ietfa.amsl.com (Postfix) with ESMTP id 24FC41A1A8D for <cfrg@ietfa.amsl.com>; Mon, 2 Mar 2015 08:22:04 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.101
X-Spam-Status: No, score=-0.101 tagged_above=-999 required=5 tests=[BAYES_20=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, SPF_PASS=-0.001] autolearn=ham
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id HXVfkodgCtp9 for <cfrg@ietfa.amsl.com>; Mon, 2 Mar 2015 08:22:02 -0800 (PST)
Received: from mail-yk0-x22a.google.com (mail-yk0-x22a.google.com [IPv6:2607:f8b0:4002:c07::22a]) (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 297041A1AE8 for <cfrg@irtf.org>; Mon, 2 Mar 2015 08:21:55 -0800 (PST)
Received: by ykq142 with SMTP id 142so13832761ykq.7 for <cfrg@irtf.org>; Mon, 02 Mar 2015 08:21:54 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:date:message-id:subject:from:to:cc:content-type; bh=t/UTJWCPc5NAKfNnjHqThXzhXBadkSFfjYVnnr05iJk=; b=TbusYqQ4X4RPw7zIptbB95g3fSCpDXE9pH/bKmuZNr13KRWTqQDTxpZnDSDNl28Tp7 ycQVWqPfpxkNXJE+Go7eyxMquM/hoC7wuupyhvNyKPTn6hjj3b3UbUqs4X7bK3J83FoP lIeBom+hDxxR2ZdheiDC/XVFre+PtqtWRQD1gYsLJSZbq58uoHUUKY1bWMYuzPjKYk7K RnP6+tMNtaBUxkz1E9+NgBCPCPLfgDXVvQC5WfINkHp3DM4/46/9vNwSlX3VE2lpg7xg KzM6ZLRjp78VuUUjcN6FGiNf7fFyrGe5zUGhsVLJyC/sOHpc/8Xl9i9JqdyQJQE06yPz 6y5Q==
MIME-Version: 1.0
X-Received: by with SMTP id 206mr28692377yky.34.1425313313972; Mon, 02 Mar 2015 08:21:53 -0800 (PST)
Received: by with HTTP; Mon, 2 Mar 2015 08:21:53 -0800 (PST)
Date: Mon, 2 Mar 2015 08:21:53 -0800
Message-ID: <CACsn0cmjp6oKYYC5G7J3q_u9h7PtRDMQakg2sXwt4aX-tfLU0g@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: Simon Josefsson <simon@josefsson.org>
Content-Type: text/plain; charset=UTF-8
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/cUgWwud_Z_y7pGQErMrps5MkLCA>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: [Cfrg] Post Quantum (was Re: Minimum required work force for additional curve)
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, 02 Mar 2015 16:22:04 -0000

On Mon, Mar 2, 2015 at 3:25 AM, Simon Josefsson <simon@josefsson.org> wrote:
> Kurt Roeckx <kurt@roeckx.be> writes:
>> Since I think this hasn't been clearly asked and that it might
>> explain the answer on the other questions asked, I'm guess I'll
>> just ask it myself:
>> Assuming other than the 128 WF curve we only add 1 other curve,
>> what is the minimum WF it should have?
> I believe the focus on power-of-two work factor comparisons for
> asymmetric schemes is harmful.  It makes people jump to the conclusion
> that asymmetric schemes share the commonly-believed property that
> symmetric schemes have: that adding another bit in the key space doubles
> the work factor.  This focus also leads to confusing "algorithm pairing"
> ideas.
> The concept of work factor is useful though.  I don't see how humans
> will ever do > 2^100 operations using today's non-quantum-technology.
> Thus, to me, a work-factor of 2^100 is sufficient to address our needs.
> And at that level, I would prefer having multiple options.

Why is this better? Is it so that if one goes down we have another?
> I could live with recommending Curve25519 and some significantly larger
> curve like Ed448-Goldilocks if we can't get consensus on anything more
> reasonable (like two curves at 2^100-2^130 work factor), but it will
> lead to wasting energy computing the Ed448 operations where cheaper
> (energy-wise) alternatives would suffice.
> If we want significantly stronger alternatives to >~2^100 work factor
> solutions, I would prefer recommending solutions that withstand quantum
> technology attackers -- I believe there are solutions in that space.

There are various proposals, some rather old and well-implemented like
NTRU, some old and well understood like McEliece, and some exotic
things like Ring-LWE and isogeny volcanoes. Post-Quantum cryptography
has been brought up here a number of times, although there are some

-Most schemes have enormous public keys. Those that don't have
structure that helps cryptanalysis, and in some cases there is some
low-hanging fruit to pluck. Parameter choices can become trickier.
-Implementation availability and quality. This is solvable.
-Different problems support signatures and encryption.

We can deal with the last 2, but the first one is really something
where more research is required.

Watson Ladd

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