Re: [CFRG] NSA vs. hybrid

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

Following your logic, why haven’t we been using Hybrid approach for the last two decades? Are we that confident in infallibility of RSA or ECDH(E)?

Regards,
Uri

> On Dec 2, 2021, at 12:35, Natanael <[e-mail]> wrote:
> 
> 
> 
> 
> Den tors 2 dec. 2021 17:45Blumenthal, Uri - 0553 - MITLL <[e-mail]> skrev:
>> I'll use the NSA term "CRQC" - Cryptographically-Relevant Quantum Computer. I personally believe (based on my weak understanding of the incomplete scientific data - but understanding  that others have probably isn’t much better than mine) that CRQC will be built within the “relevant” (IMHO) time, aka - a matter of a decade or two. 
>> 
>> Basically, my reasoning against the Hybrid is that it is useless in the majority of cases. But it adds complexity to processing, and unnecessary ballast. 
>> 
>> Here are the possibilities and their relation to the usefulness of the Hybrid approach.
>> 
>> 1.  CRQC arrived, Classic hold against classic attacks,  PQ algorithms hold - Hybrid is useless. 
>> 2. CRQC arrived, Classic hold against classic attacks, PQ algorithms fail - Hybrid is useless. 
>> 3. CRQC arrived, Classic broken against classic attacks,  PQ algorithms hold - Hybrid is useless. 
>> 4. CRQC arrived, Classic hold against classic attacks,  PQ algorithms broken - Hybrid useless. 
>> 5. CRQC doesn’t arrive, Classic hold against classic attacks,  PQ algorithms hold - Hybrid is useless. 
>> 6. CRQC doesn’t arrive, Classic hold against classic attacks,  PQ algorithms broken - Hybrid helps. 
>> 7. CRQC doesn’t arrive, Classic broken against classic attacks,  PQ algorithms hold - Hybrid is useless. 
>> 8. CRQC doesn’t arrive, Classic broken against classic attacks,  PQ algorithms broken - Hybrid is useless. 
>> 
>> You can see from the above that Hybrid would be of benefit in only one case out of eight, one I personally consider among the least probable. 
>> 
>> Hope this explains my position?
> 
> 
> I disagree with your risk analysis. 
> 
> The main problem is that we can't predict which of these situations we will end up in. Simple enumeration doesn't help. 
> 
> The main issue is that #6 has already been seen today, multiple times, with algorithms previously expected to hold. That alone should realistically end the argument that we're ready to deploy exclusively PQ today. It's not a safe bet to make ourselves dependent on it in advance.
> 
> #5 is the only plausible case where betting on hybrid would be considered a real negative after the fact, and most would complain about performance more than complexity. And I wouldn't bet on #7 happening (even if it does you might pick the wrong candidate). 
> 
> Practically speaking we're dealing with weighing the more likely outcomes that the specific PQ of choice holds (that's a narrowed version of 1/3, also 5/7) vs a continuation of #6, that it fails while classic algorithms remain working. #8 and #4 (should be both breaks?) are IMHO less likely, I expect to see some kind of surviving asymmetric algorithms in both cases. 
> 
> #2 still protects against adversaries without quantum computing capabilities. 
> 
> Hybrid is a hedged bet, and it's a long term bet - data encrypted now can still be relevant in two decades before we even know if a CRQC is plausible at all, but we also don't know which algorithms will survive. Hybrid has a chance of surviving everything but the nightmare scenario, and is the only choice that can substantially reduce unknown risks.
> 
> Going single algorithm is not just a bet on CRQC vs none, but additionally a bet on that specific algorithm.