Re: [CFRG] NSA vs. hybrid

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

Who’s to say that an Intel agency or a crime syndicate (oops, I meant “outfit” ;) hasn’t secretly developed a classic exploit against one or more of the currently used Classic asymmetric algorithms?

Regards,
Uri

> On Dec 2, 2021, at 12:15, Soatok Dreamseeker <[e-mail]> wrote:
> 
> 
> Hi Uri,
> 
>> On Thu, Dec 2, 2021 at 11:45 AM Blumenthal, Uri - 0553 - MITLL <[e-mail]> wrote:
>> 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?
>> 
>> Regards,
>> Uri 
> 
> Your setup of 8 possible outcomes is reasonable, but I don't believe your conclusion follows soundly from this premise.
> 
> The core of my disagreement is: none of us are omniscient. (If we were, most cryptography would be useless, and we wouldn't need intelligence agencies.) 
> 
> Even if we take the 8 situations you sketched in your email as a given, we'll never know which world we're in. If an intelligence agency (or significantly sophisticated computer crime syndicate) discovers a classical exploit against one of the NIST finalists (say, as a result of a novel mathematical breakthrough that permits accelerated attacks against lattices), they're strongly incentivized to keep this a secret. (NOBUS vulnerabilities, etc.)
> 
> I'm inclined to agree that, in 1/8 of the worlds, Hybrid helps, and in the other 7/8 of the other worlds, it doesn't. However, while Hybrid may not help in those cases, it isn't a clear detriment. This is because the overwhelming majority of the code needed for hybrid signatures (or, indeed, hybrid KEMs) are already implemented in cryptography libraries today, so the hit to code size, attack surface, and complexity is tractable.
> 
> Without any mechanism to distinguish between the 8 possible worlds, we cannot make a strong logical argument either way. We're forced to rely on inductive reasoning. Naturally, what we end up with is a 12.5% probability of a security improvement and a 87.5% chance of a zero-sum outcome.
> 
> My conclusion, following the premise you shared, is that Hybrid is a modest insurance policy (against a circumstance we can't guarantee that we won't fall into due to the perverse incentives of national politics), even if it's one we're not extremely likely to need.
> 
> If you wanted to pose a stronger argument against Hybrid, I think demonstrating a significant cost and/or downside to Hybrid over doing nothing would be the best way to make your case.
> 
> Regards,
> Soatok