Re: [CFRG] NSA vs. hybrid

[Natanael <[e-mail]>]

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.

>