Re: [TLS] Before we PQC... Re: PQC key exchange sizes

["Scott Fluhrer (sfluhrer)" <[e-mail]>]

> -----Original Message-----
> From: TLS <[e-mail]> On Behalf Of Blumenthal, Uri - 0553 -
> MITLL
> Sent: Sunday, August 7, 2022 1:32 PM
> To: Phillip Hallam-Baker <[e-mail]>
> Cc: [e-mail]
> Subject: Re: [TLS] Before we PQC... Re: PQC key exchange sizes
> 
> > > I thought a Quantum Annoyance was someone who keeps banging on
> about
> > > imaginary attacks that don't exist as a means of avoiding having to
> > > deal with actual attacks that have been happening for years without
> being addressed.
> >
> > That is a little unfair but only a little.
> 
> I don't think Quantum "Annoyance" makes any sense at all. It's only
> annoying to implementers.

Actually, we came up with the concept while evaluating PAKEs for the CFRG, and in the that context, it makes sense.  For some PAKEs, if we assume that the adversary has the ability to compute one discrete log, all that would gain him is the ability to check of one particular password was being used for a recorded exchange (and hence if computing a discrete log is costly, which is likely to be the case for the first generation of Quantum Computers), you're still "mostly safe".

In contrast, with other PAKEs, computing one discrete log would allow you to break any implementation of that PAKE parameter set globally - that is about is 'un-annoying' as you can possibly get.

We say this disparity, and the term 'Quantum Annoyance' was coined to express it.

Now, with key exchanges, it is somewhat less applicable.  However, if computing a few thousand discrete logs allows you to put together a usable factor base, well, perhaps that would indicate that 'finite field DH with a common modulus' is less 'quantum annoying' (in the above sense) than (say) ECC...

> 
> > I have seen references to a 'NIST' slide insisting that we should not
> > use hybrid schemes and I completely disagree with them.

(The above comment was by PHP)

Hmmm, I had thought I tracked just about everything NIST said about postquantum, and I don't recall that.  In any case, I don't believe that anyone is taking that advice; initially, just about everyone is suggesting to combine postquantum with classical (ECC or RSA).  And, since this is the TLS working group, I would point out that the current TLS postquantum draft does do hybrid.

> 
> > First, do no harm: At this point it is very clear that the risk of a
> > Laptop on a Weekend breaking Kyber is rather higher than anyone
> > building a QCC capable computer in the next decade.
> > So, what is not going to happen is a system in which a break of Kyber
> > results in a break of TLS.

Again, that's why we're planning on hybrid; to break the privacy of TLS, you would need to break both Kyber (or NTRU; I'll spout off on that if you're interested) and (say) X25519.  Hence, what we are proposing is no less secure than what we are currently doing now.