Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairing-friendly-curves-01.txt

Dan Brown <danibrown@blackberry.com> Mon, 01 April 2019 18:30 UTC

Return-Path: <danibrown@blackberry.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 4D3501204EB for <cfrg@ietfa.amsl.com>; Mon, 1 Apr 2019 11:30:38 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.6
X-Spam-Level:
X-Spam-Status: No, score=-2.6 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001, URIBL_BLOCKED=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 PAeZQMQW8yR3 for <cfrg@ietfa.amsl.com>; Mon, 1 Apr 2019 11:30:35 -0700 (PDT)
Received: from smtp-p02.blackberry.com (smtp-p02.blackberry.com [208.65.78.89]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id EA3F51204CE for <cfrg@irtf.org>; Mon, 1 Apr 2019 11:30:34 -0700 (PDT)
Received: from xct102cnc.rim.net ([10.65.161.202]) by mhs214cnc.rim.net with ESMTP/TLS/DHE-RSA-AES256-SHA; 01 Apr 2019 14:30:33 -0400
Received: from XMB116CNC.rim.net ([fe80::45d:f4fe:6277:5d1b]) by XCT102CNC.rim.net ([fe80::2066:5d4f:8c45:af55%17]) with mapi id 14.03.0415.000; Mon, 1 Apr 2019 14:30:33 -0400
From: Dan Brown <danibrown@blackberry.com>
To: "Blumenthal, Uri - 0553 - MITLL" <uri@ll.mit.edu>, "Paterson Kenneth" <kenny.paterson@inf.ethz.ch>, Marek Jankowski <mjankowski309@gmail.com>, "yonezawa@lepidum.co.jp" <yonezawa@lepidum.co.jp>
CC: CFRG <cfrg@irtf.org>
Thread-Topic: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairing-friendly-curves-01.txt
Thread-Index: AQHU2Yg9d9ockWZnDkeyn6LWng9bQKYLg1EAgAA63ACABtxrAIACXiwAgAwGegCAAD6YAP//creAgADJWQCAAabZAIAAENIAgARbhvA=
Date: Mon, 1 Apr 2019 18:30:32 +0000
Message-ID: <810C31990B57ED40B2062BA10D43FBF501DB4A31@XMB116CNC.rim.net>
References: <155231848866.23086.9976784460361189399@ietfa.amsl.com> <737ea2b3-74e3-d02e-a44d-c44cca5db036@lepidum.co.jp> <CAEseHRrSiJ72tQepyTiL=pSBcRRLGXhnJyy_QzOubWax+v=Ntw@mail.gmail.com> <CAEseHRqh4d0VaeSaj4CWr_ZxJbbpm33ZaLF-aYGBjVowFNLFeQ@mail.gmail.com> <c57bbf7b-3177-eb64-a3c0-26842fccbb89@lepidum.co.jp> <CAEseHRrVomCo6KD7gidCRBzKJDzFZRQ+q0+PjfBr8tQT4dVpMQ@mail.gmail.com> <b016d1f6-68e4-9728-c738-ab72c593dfd1@lepidum.co.jp> <CAEseHRoLGFbf74HT9n2beryc9Liqf2Hz+_rh-yo6Q8hNqwCvNQ@mail.gmail.com> <CAMCcN7RTQU=a+SYVkGUHZ4enOhkA9j9i6ivMRDUwb+aXPZ9hBg@mail.gmail.com> <7AE82BE8-768D-4B70-B7F1-EAF6894E428E@ll.mit.edu> <9CABDAD4-AAB7-46BF-BED7-6A917F828F11@inf.ethz.ch> <27F5D9B6-A44D-4A12-B81D-C4FB01052113@ll.mit.edu>
In-Reply-To: <27F5D9B6-A44D-4A12-B81D-C4FB01052113@ll.mit.edu>
Accept-Language: en-US, en-CA
Content-Language: en-US
X-MS-Has-Attach: yes
X-MS-TNEF-Correlator:
x-originating-ip: [10.65.160.251]
Content-Type: multipart/signed; protocol="application/x-pkcs7-signature"; micalg=2.16.840.1.101.3.4.2.1; boundary="----=_NextPart_000_01B0_01D4E897.75828220"
MIME-Version: 1.0
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/7yzYLqt1z_-wva9VlMxJsbNZ3MM>
Subject: Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairing-friendly-curves-01.txt
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
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, 01 Apr 2019 18:30:39 -0000

The topic of non-PQ crypto's value applies to other CFRG drafts, such as PAKEs, VRFs, Oblivious functions, etc., so maybe this discussion should be taken outside this thread?

Non-PQ crypto still seems worthwhile to me, mainly because I estimate the chance of a practical ECC-breaking quantum computer to be low, e.g. 2^(-10), yet still high enough to warrant a hybrid of PQ and non-PQ crypto, e.g. McEliece + ECC. (See further below.)

> -----Original Message-----
> From: Cfrg <cfrg-bounces@irtf.org> On Behalf Of Blumenthal, Uri - 0553 -
> MITLL
> 
> It doesn’t but we did already discuss that, and good arguments were put forth
> for continuing the work despite this. (See the mail archive, I guess.)
> 
> So far I’ve found this (which IMHO doesn't look like a set of good arguments):
> 
> >  1) Pairing-based crypto threw open the doors to lots of nice new crypto
> possibilities, enabling stuff that we couldn't do before
> >  2) Gradually post-quantum crypto is catching up and demonstrating
> capabilities that mirror some (but not all) of these achievements
> >  3) Post-quantum crypto depends on hard problems that it will take time to
> develop full confidence in, even in regard to attacks from non-
> quantum computers
> >  4) In the meantime (and that could be quite a long time) it makes perfect
> sense to proceed with the development and standardization
> >       of non-quantum safe methods.
> >  5) In the year x out pops a quantum computer. However in the year x-1 out
> popped well-developed and well-understood
> >       post-quantum crypto replacements in which we can have complete
> confidence.
> 
> Re. (1): sure, it would do great stuff, but for how long? What’s the expected
> lifetime of an algorithm/protocol/approach that would justify efforts spent on
> formalizing, implementing, and deploying it? What application field or use case
> would support it?
> 
> Re. (2) and (3): sure, but irrelevant with regard to the main question - is it
> worth developing (for deploying later, as there's an inevitable lag) non-
> quantum-resistant crypto now?

It would be smart to answer these types questions with quantified support, but all I get so far is the naïve estimates below. (Presumably, experts have already documented more sophisticated reasoning, maybe see ia.cr/2015/1018).

For simplicity, consider any crypto as broken or not (at some attack cost and success rate), and then compare 3 alteratnives: ECC, McEliece (McC), and their hybrid (in the strongest link sense).

Define five event probabilities, but please replace my personal (ultra-low-confidence) estimates with your own:

Break ECC classically: e  ~  2^-40
Break ECC quantumly: E = 1 [Shor]
Build quantum computer: Q ~ 2^-10 [(Mosca's estimate = 1/2) ^ (my_grain_of_salt ~ see also cold fusion:)]
Break McC classically: m ~ 2^-20 
Break McC quantumly: M ~ 2^-20

Assuming e,E,Q,m,M independent (in the usual sense that their products are the probabilities of intersection of corresponding events), deduce 3 event probabilities:

Break ECC:  X = e+Q-eQ.
Break McC: Y = m+MQ-mMQ.
Break hybrid ECC+McC: Z = mX+Y-m  = em+mQ+MQ-emQ-mMQ.

For brevity, I omit the tedious derivations.  Assuming X,Y,Z correct:

If Q=1, then X=1 and Z=Y, so ECC is essentially redundant (out with old...).

If Q=0, then X=e and Z=XY, which means that hybrid is generally better (see * below) than either individual crypto, and the lower of X and Y (ECC in my estimation) can be considered as the main contributor to the lowness of Z.

(*) Assume 0 < X,Y < 1. Ignore the issue of declining returns for very low probabilities, e.g. X=2^-128 might be just as good as Z=2^-256 (who needs new?).

For 0 < Q < 1, then the conclusions smoothly vary between the two extremes (Q=0) and (Q=1) above.  

My (e,Q,m,M) estimates lead to an estimate (X,Y,Z) ~ 2^-(10,-20,-30).  I admit to using my (biased?) intuition for the ordering X<Y<Z to cook my (e,Q,m,M) estimates.  

Anyway, with my estimates and (circular?) reasoning, hybrid is usually worthwhile (for protecting high-value data), except as Q gets too close to 1.  

If there is a fancy security goal that McC lacks, e.g. some kind of identity-based forward secrecy, then put m=1 relative to this goal.   (Perhaps replace ECC by pairing-ECC to meet this goal.)  If m=1 and Q=1, then we have Z=1, so we might as well abandon the fancy goal.  If Q<1, then Z=X, and (pairing-)ECC is our only hope to meet the fancy goal.