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

[Dan Brown <[e-mail]>]

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 <[e-mail]> 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.