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

["Blumenthal, Uri - 0553 - MITLL" <[e-mail]>]

Marek,

Thank you for your comments. Please see inline.

From: Marek Jankowski <[e-mail]>


  1.  As Mike says, we don't know much about current post-quantum schemes, even against a classical attacker. Due to their theoretical complexity, it may take dozens of years to develop considerable trust in such schemes. In the meantime, it is worthwhile to develop (classically-)strong PK schemes with cryptographic advantages. What I mean is - until PQ schemes are made secure, we will use classical schemes; I think the capabilities pairings offer (e.g. IBE, short and aggregateable signatures) are appealing enough to justify standardization.

I think we differ in how much we do or do not know about security of post-quantum schemes. I think all of the NIST PQC submissions came with security proofs, so – no offense meant – I think the “we don’t know much about PQ …” part is a bit disingenuous. If I’m wrong here, or am missing something, or you see problems with the proofs of, e.g., SIKE  – please feel free to post here and/or let me know.

Regardless of how sure/unsure we are of the PQ schemes, we’d probably agree that we are sure that all the “classical” asymmetric crypto (factoring-based, DL-based, etc.) is completely broken with quantum computers. That means – the question is how much time we have before all the classical asymmetric is dead, and how that maps onto the required security lifetime for our data.

I agree that some data won’t need to live that long, and could be fine with “classic” protection, whatever it is. Who/how is going to ensure that only the appropriate data is protected by this mechanism?

Research, implementation, standardization, commercialization of implementation, deployment in the field all take time. It is quite possible that by the time this (or other non-quantum-resistant) approach becomes deployable technology, it gets life-time of zero or only a couple of (or a few) years. If/when, e.g., a hash-function is broken – you simply replace it with a new one as a field upgrade (and even that turned out to be a big hurdle in the field, one wonders why).  As you and Mike pointed out, there is no PQ-secure analog for BLS. Once it is broken, it will stay broken for good, until a new discovery is made. Is it a risk you’re willing to accept? If so, may I ask why?


  1.  > data produced in year x-k (encrypted by good and intercepted by bad players) may still have value in year x, x+1, etc.


I agree; yet, given the choice to encrypt data using a provably (classically-)secure scheme, and a non proven PQ scheme, I would prefer the former: we don't know if current PQ schemes may be broken by a classical computer before year x. Classical computers are available today to millions of potential bad guys, while even when quantum computers are built, it makes sense that for some time very few people will have access to one. It is also worth mentioning that pairing based crypto offers signature schemes with nice qualities (see the recent I-D by Boneh et al.); for signatures it is perfectly acceptable to use quantum-vulnerable schemes today. (But not in year x.)

As I said above, most/all of the NIST PQC submissions came with security proofs. There’s no need to resort to “non-proven PQ scheme”. Unless you’re not happy with the proofs…? In which case, please share what makes you happy with “pre-quantum” proofs and unhappy with PQ ones.

For the second part, it depends on whether the data signed today needs to stay secure in and after year x. One problem is – we do not know how soon (or far away) that year x is. But we do know that it is not a Sci-Fi any more. Quantum computers are built today, they just aren’t a direct threat yet.


  1.  Post quantum crypto is generally much more resource intensive than classical crypto (including pairings), in both complexity and traffic. Therefore pairing based cryptography works better for lightweight processors. Data encrypted by such devices is likely to be irrelevant in 20-30 years after transmission (e.g. IoT, smart cars). So it is OK to use classical crypto there.

You are probably correct here. I.e., if I authenticate to a remote Web site today with a smartcard, somebody’s ability to break my smartcard’s key several years from now is probably not very important. Except that there’s a chance that I logged in to a secure web site to fill out some sensitive form, disclosure of which even several years from now would be highly undesirable.

As you see, it may be hard to draw a line apriori between OK and Not OK.


  1.  Pairings are getting into practical use. Examples are several RFCs (5091, 6508, 6539, 6509), Cloudflare's GeoKey Manager and more, as listed in the I-D. The rising popularity strengthens the need for a well thought out standard/set of standards.

There is a difference between getting an RFC and getting into practical use. But I concede your point.

To conclude, I believe that developing PQ crypto and classical PK crypto should be done in parallel, and not one instead of the other. While using non quantum secure chemes will threaten one's data once a quantum computer is built, I think it should not slow down research of new crypto capabilities.

My concern here is that the life window of the non-quantum is shrinking, maybe shrinking rapidly (and alas, I don’t know how fast). So, with every year and every day there is less and less sense to invest time and efforts into non-quantum crypto. Are we already at the point when it already doesn’t make …? I personally think we are.

Dan Brown made a good point about hybrid approaches. Offhand, I concur with him. Perhaps we need to invest more efforts there.



On Fri, Mar 29, 2019 at 5:59 PM Blumenthal, Uri - 0553 - MITLL <[e-mail]<mailto:[e-mail]>> wrote:
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?

Re. (4): I see no logic in that statement. We don't have full confidence in post-quantum hard problems, therefore we should standardize methods that we know are not quantum-resistant?

Re. (5): It's only true for data that loses value rapidly. It may work for, e.g., throw-away TLS sessions, but not for, e.g., sensitive email. It seems to ignore the fact that data produced in year x-k (encrypted by good and intercepted by bad players) may still have value in year x, x+1, etc.

I cannot (nor do I want to) tell people what to research or experiment with, and what not to. But common sense suggests that systems/algorithms that do not offer long-term protection won't see large-scale commercial deployment, IRTF draft or not.