Score:0

When is a PQ key-exchange algorithm suitable for use with long-term static keys?

cn flag

I took a look at Cloudflare Circl because I'm curious which Post-Quantum algorithms are implemented in Go, which could be used to exchange a key.

I read this comment that SIDH is only good for ephemeral key exchange, in contrast to CSIDH.

Question 1:
Therefore, I wonder, what characteristics must a Post-Quantum algorithm have to be suitable to create a long-term static key for key exchange (like RSA or ECC)?

Question 2:
Why is SIDH only good for ephemeral key exchange but not CSIDH?

And what about

  • SIKE
  • Kyber
  • Classic McEliece
  • FrodoKEM?

Or is the answer so specific to each algorithm that it can only be determined by experts according to the current state of cryptanalysis?

ne flag
Could you try to make your question more precise: specifically, what do you mean by "when"? Because, otherwise, the only answer I have is "when they are proven secure for that specific use".
Score:1
in flag

Here's a summary of the situation:

Q1. The primary reason some key-exchange systems cannot be used with static keys are chosen-ciphertext attacks. The general theme is that malicious clients send manipulated key-exchange messages to a server, which allows them to extract partial information about the server's static secret key with each such query.

Perhaps the most well-known example are invalid-curve attacks on (badly implemented) ECDH: Here, the attacker sends a point as his public key that is not actually on the correct curve, and the result of the bogus key exchange then leaks information about the secret key (such as its residue modulo a small prime). Now in ECDH, this issue can be fixed by validating public keys prior to processing them in a key exchange (e.g., check that the given point lies on the intended curve), hence it is nowadays considered an implementation bug if this vulnerability exists in a cryptographic library.

Unfortunately, potential information leaks similar to this exist for almost all paradigms used to build post-quantum key exchange; see for instance here or here or here (§2.4), and even more unfortunately, avoiding this issue is generally not as easy as it is for ECDH. For example, one can show that distinguishing manipulated SIDH keys from honestly generated ones is as hard as breaking the scheme (and I suppose similar arguments would work for lattice- and code-based constructions, but I'm less familiar with those).

The workaround used by mainstream post-quantum key-exchange systems is the Fujisaki–Okamoto transform (or one of its variants). Basically, the first thing the client sends using the freshly negotiated key material is an encryption of their secret key that was used for the key exchange. The server then recomputes the public key corresponding to that secret key, and it immediately aborts the connection if the resulting public key does not equal the one received from the client earlier. Hence, the behaviour from a dishonest client's perspective is the same in all cases — the connection drops — thus no information can be extracted. Obviously, while this enables the server to use a static keypair, the client still needs to generate a new ephemeral keypair every time because the server gets to learn the secret. In other words, the primitive obtained from the FO transform is a CCA-secure KEM.

In summary, the answer to your question is: Keys can be reused if chosen-ciphertext attacks are not possible, either by having applied an FO-like transform or by reasoning otherwise that the system is not susceptible.

Q2. CSIDH is similar to ECDH in that it can efficiently distinguish valid from invalid public keys (and somewhat amusingly, the verification process is almost identical for ECDH and CSIDH). Hence, manipulated public keys are not an issue and we can use the "vanilla" CSIDH one-way group action with static keys.

By contrast, all of the other key-exchange schemes you listed incorporate some variant of the FO transform to achieve CCA security, which implies that one party can use a static keypair, but the other cannot. In general, the default assumption for any cryptosystem should be that chosen-ciphertext attacks are a problem unless they've been excluded.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.