[Cfrg] Quantum annoyance vs post-quantum preparedness

[Hugo Krawczyk <[e-mail]>]

Sorry for the long email.

The recent discussion on symmetric PAKE candidates highlights quantum
annoyance
(QA) as a differentiating property of PAKE protocols. I think the
discussion is
interesting but I wanted to express my opinion that QA should NOT be a major
consideration in judging these protocols. Instead quantum preparedness
should
be a FAR more important property to consider.

Note: It is a purpose of this email to argue that QA should not be seen as a
central property of PAKEs while preparedness for PQ adaptation and
transition is
far more important. I also argue that OPAQUE is better in that sense than
other
(augmented) schemes but my judgment of the significance of QA should be
taken
independently of my judgment of OPAQUE (where I may be suspect of bias).

If scheme A has QA and scheme B does not, all this tells us is that scheme
A may
be better at protecting your *current* password from disclosure in x years
where
x is the number of years before we have quantum machines capable of
computing
discrete logarithms over 256-bit (or more) elliptic curves in practical
ways.
For concreteness I think of x as 20 but you can use any other estimate your
crystal ball suggests.  So QA tells me that my current password may be in
danger
in 20 years - should I replace it before then? Yes, of course, you should
(and
this has nothing to do with QA).

But wait. Will my current secrets, keys, and communication be revealed in 20
years because my 20-year old password was found? NO!!
This categorical NO does not depend on the specific PAKE. Protection of past
communication in case the password is revealed is a fundamental definitional
property of PAKE. So what exactly is QA buying us?

In the context of quantum security, the question we should be asking is what
would it take to upgrade the PAKE protocol we choose today to a quantum-safe
scheme. Will we need to invent a completely new protocol? Will we be able to
keep the same design and replace some pieces? Will the quantum-safe
primitives
being developed now (e.g., via the NIST competition) be useful for the PAKE
transition to quantum safeness? How will the quantum-safe PAKE interact
with a
quantum-safe (or transitional) TLS or IKE? What will happen during a
transition
period where, for example, TLS will be using classical signatures with a
quantum-safe DH-like KEM?

Most PAKE protocols, especially the more efficient ones, build on a
combination
of techniques that are entangled together to provide PAKE security, as
opposed
to building on a  well-understood interaction between generic primitives
such as
a KEM, PKE, etc. (e.g., what is the equivalent of mapping a password to a
random
generator so central to many PAKE protocols in a generic KEM setting?).
This makes it difficult to see how these schemes evolve to the post-quantum
(and transitional) stages.

In this sense, I believe OPAQUE is better positioned for this PQ evolution.
Of the two main components that form OPAQUE: OPRF and AKE, we already have
quantum-safe AKE built out of NIST KEM candidates (see eprint 2018/928 that
builds on PQ KEMs). We can probably construct now OPRF using quantum-safe
techniques for secure two-party computation but still lack a good efficient
candidate based on lattices, for example. But such candidate is likely to
emerge in the near future given the increasing applications of OPRFs.
Moreover, since OPRF is only used for authentication, not secrecy, then the
life
span of a classic OPRF is VERY long (it is similar to the case of using
classic
digital signatures in protocols like TLS and IKE during a tranisition
period).

So we can use something like current OPAQUE with non-PQ OPRF for MANY years.
Initially with a classic AKE and, eventually, with a PQ AKE, and at some
point
in the future with a PQ OPRF too (with adaptation of the proofs to the
quantum
setting). Btw, regarding QA, once one moves to a PQ DH-replacement in TLS or
IKE, under which OPAQUE would be run (e.g., as needed to protect user
account
information) the attacker will need to run a targeted active attack against
a
victim to be able to run in the very distant future a QA attack (which as
said
assumes a powerful quantum machine and negligible gains for the attacker).

A much more significant practical attack avenue TODAY (and in the future)
is to
attack protocols that are open to pre-computation attacks. That is a
property
one should value much much much more significantly than QA.

The bottom line: QA is an interesting notion but of minimal practical
relevance
given its cost and the quite negligible gain for the attacker in the very
distant future. Preparedness for PQ evolution is much more significant as is
security against pre-computation attacks.

Hugo