[messaging] Do quantum attacks/algos also lead to compromise of PFS?

[Taylor R Campbell]

   Date: Mon, 26 Jan 2015 19:30:01 -0800
   From: Watson Ladd <watsonbladd at gmail.com>

   We have very safe encryption via McElice. The issue is key sizes are
   very large. That's where a lot of the research is focused, and why
   things like ring-RWE are interesting.

With another round-trip one can use McEliece (or any other public-key
encryption scheme) to synthesize a public-key authenticated key
exchange scheme, in order to defend against quantum cryptanalysis.

With many-kilobyte ephemeral public keys to exchange, not likely to be
useful for HTTPS, but may be useful for IM conversations, or perhaps
even for Tor with medium-term ~10-minute circuits rather than ~300 ms
HTTPS requests.


(Protocol, suggested to me by Elias Yarrkov, using public-key
encryption E_p(m) = public-key wrap under p of random k || symmetric
authenticated encryption under k of m: Alice has long-term public key
A, generates ephemeral public key a and secrets alpha, aleph; Bob has
B, b, beta, beth.

First Alice sends E_B(a || alpha) and Bob sends E_A(b || beta); Bob
receives a' || alpha' and Alice receives b' || beta'.  Next Alice
sends E_b'(aleph || beta') and Bob sends E_a'(beth || alpha'); Bob
receives aleph' || beta'' and Alice receives beth' || alpha''.  Alice
checks alpha = alpha'' and computes session key sa = H(alpha, aleph,
beta', beth'); Bob checks beta = beta'' and computes session key sb =
H(alpha', aleph', beta, beth).)


P.S.  Would be nice if McBits were released so we could use it in
applications.  I trust myself to apply public-key encryption more than
I trust myself to carefully design things not to rely on it by
exposing only symmetric ciphertext to the attacker.