3
$\begingroup$

As far as I can tell we don't have any good key exchange post-quantum candidates. SIKE was broken some time ago.

It is possible to reach an authenticated shared secret by having the public key holder do PKE to send a secret to the private key holder and even have it reply with its own secret back in order to reach a unique shared secret per session where both contributed, and that can be used for regular KEX too but unlike Diffie-Hellman compromising the private key allows for decrypting all previous handshakes too.

So say a bank's private key is compromised today, if it doesn't change it all future DH can be MITMd but all previous comms are secure unless you also have a time machine. They only need to update their key. With KEX private key leak also means you can decrypt previous traffic if you've been capturing it which is way worse. You could use PKE to authenticate then have the server generate a unique key pair just for that connection to establish the shared secret but that sounds very bad computationally and traffic-wise.

Do we yet have any good post-quantum solutions to this?

$\endgroup$
1
  • $\begingroup$ There are alternatives to SIKE that are still secure. However, actual protocols will be using KEMs from the NIST 'competition' like Kyber, FrodoKEM, or Classic McEliece. Isogeny-based cryptography needs further investigation and tends to be slower. $\endgroup$ Commented Feb 15 at 8:36

1 Answer 1

5
$\begingroup$

I don't understand your concern. It sounds like you are assuming that public (and private) keys in lattice-based key exchange are static? I don't believe this is the case though. So if your bank (or whatever) ephemerally generates a new lattice-based public/private key for each connection, they are fine. This can be verified by looking at measurements. Key generation for lattice based schemes (say Kyber512) is typically in the tens of thousands of cycles. On a 3GHz machine, this is low cost by essentially any metric.

There are additionally "true DH" constructions from lattices, see Swoosh, though the efficiency is (necessairly) much worse, as there are known impossibility results for the more typical (efficient) parameter regime. Note that this does increase public key/ciphertext sizes by a factor ~100x iirc, so it comes at fairly high communication cost (operating on these larger ciphertexts is also obviously more expensive).

$\endgroup$
3
  • 1
    $\begingroup$ Actually, for TLS 1.3, it's the client (not the server) who would have the Kyber private key. If the bank owns the server, then their private key would be their signature key (the one they have a certificate for). $\endgroup$
    – poncho
    Commented Feb 15 at 19:20
  • $\begingroup$ @poncho My overall point is the lattice-based KEM itself is designed/profiled to be used ephemerally. A lot of people were wary of static schemes post LOGJAM in 2014, and the gains from static KEMs using lattices are not even particularly large in the first place. $\endgroup$
    – Mark Schultz-Wu
    Commented Feb 15 at 19:24
  • 2
    $\begingroup$ I'm not disagreeing with you. Sqoomsquoom's concern was "what if someone learned the bank's long term Kyber key"; you pointed out that there need not be a long term key; I was pointing out that the bank need not have a Kyber key at all. We're just addressing the same concern from two different directions... $\endgroup$
    – poncho
    Commented Feb 15 at 19:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.