[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 [127.0.0.1]) 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-Level:
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 ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (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 10.170.56.215 with SMTP id 206mr28692377yky.34.1425313313972; Mon, 02 Mar 2015 08:21:53 -0800 (PST)
Received: by 10.170.126.210 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
problems:

-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.

Sincerely,
Watson Ladd




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