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

Dan Brown <> Mon, 01 April 2019 18:30 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 4D3501204EB for <>; Mon, 1 Apr 2019 11:30:38 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2.6
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 ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id PAeZQMQW8yR3 for <>; Mon, 1 Apr 2019 11:30:35 -0700 (PDT)
Received: from ( []) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id EA3F51204CE for <>; Mon, 1 Apr 2019 11:30:34 -0700 (PDT)
Received: from ([]) by with ESMTP/TLS/DHE-RSA-AES256-SHA; 01 Apr 2019 14:30:33 -0400
Received: from ([fe80::45d:f4fe:6277:5d1b]) by ([fe80::2066:5d4f:8c45:af55%17]) with mapi id 14.03.0415.000; Mon, 1 Apr 2019 14:30:33 -0400
From: Dan Brown <>
To: "Blumenthal, Uri - 0553 - MITLL" <>, Paterson Kenneth <>, Marek Jankowski <>, "" <>
Thread-Topic: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairing-friendly-curves-01.txt
Date: Mon, 01 Apr 2019 18:30:32 +0000
Message-ID: <>
References: <> <> <> <> <> <> <> <> <> <> <> <>
In-Reply-To: <>
Accept-Language: en-US, en-CA
Content-Language: en-US
X-MS-Has-Attach: yes
x-originating-ip: []
Content-Type: multipart/signed; protocol="application/x-pkcs7-signature"; micalg="2.16.840."; boundary="----=_NextPart_000_01B0_01D4E897.75828220"
MIME-Version: 1.0
Archived-At: <>
Subject: Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairing-friendly-curves-01.txt
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-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 <> On Behalf Of Blumenthal, Uri - 0553 -
> 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

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.