28
$\begingroup$

Post-quantum cryptography concentrates on cryptographic algorithms that remain secure in the face of large scale quantum computers. In general, the main focus seems to be on public-key encryption algorithms and public-key signature algorithms - but there are dozens of other constructs like hashes, block ciphers, etc. - but with a quick peek, I didn't find any key agreement algorithms.

Most of todays interactive communication is focused on key agreement via Diffie-Hellman and authentication on top of that - the goal is to set up a "secure channel". Some schemes use signatures for non-repudiable authentication, but many use Diffie-Hellman for repudiable authentication. There are many protocols for key agreement, with varying security properties, that mostly just use Diffie-Hellman in complex ways and depend on the DDH or CDH assumptions on security. As an example of the protocols I mean, I present YAK and J-PAKE.

Now, my question is, what is the post-quantum cryptography answer to establishing a secure channel? Or, specifically - anonymous key agreement, authenticated key agreement and password-authenticated key agreement?

All of the different post-quantum cryptography systems seem to have some big drawback - large signatures, large public keys, large processing requirements etc. - so I am wondering which would offer the best tradeoff for key agreement?

In general, it would seem that any public key encryption algorithm could be used pretty easily for key agreement - but are there any concrete proposals on cryptographic protocols doing key agreement for some post-quantum cryptography algorithm? What properties do these provide, such as PFS, UKS, KCI, deniability, etc? Simply encrypting a random key to the recipients public key does not achieve forward secrecy, unless the recipient public key is ephemeral (random generated each time). If it is ephemeral, the question becomes how to tie some authentication in to the ephemeral key agreement, for which there's no obvious best method but a number of tradeoffs.

I understand that post-quantum cryptography isn't ready yet for general use - and the primitives are not secure enough or standardized enough to use these kinds of protocols in the real world yet - but it feels like there should be more preliminary work done on this problem as well. If you disagree, please let me know that, too!

Improve this question
$\endgroup$
1

5 Answers 5

Reset to default
7
$\begingroup$

For authenticated/mutually authenticated key exchange, you can use that piece of TLS. TLS requires public key encryption and a key derivation function for the key exchange (plus a signature algorithm for the PKI, if necessary). There are many post-quantum encryption functions and KDFs are typically based on hashes or MACs, which are also post-quantum. There is an RFC draft for TLS using NTRU encryption and signatures (they call it NTRU_NSS). The security provided is extremely basic (no PFS or advanced properties).

I expect there is some work on more advanced exchange protocols and look forward to other answers.

Improve this answer
$\endgroup$
2
  • $\begingroup$ The RFC draft was very interesting, thank you for the link! $\endgroup$
    – Nakedible
    Commented Aug 25, 2011 at 11:45
  • $\begingroup$ I accepted this answer because it contained more information that I didn't already know. $\endgroup$
    – Nakedible
    Commented Sep 1, 2011 at 13:48
11
$\begingroup$

Answering myself...

There is now a very analogous alternative to Diffie-Hellman in post-quantum cryptography: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies

The research paper is very new, but if the results turn out to be secure, this is a very competitive key agreement scheme for post-quantum cryptography.

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ It was a big "if". More than a decade later, SIDH has been fatally broken on a 10 year old laptop. $\endgroup$
    – forest
    Commented Aug 20, 2022 at 1:56
10
$\begingroup$

You can do key agreement with asymmetric encryption. Any asymmetric encryption algorithm (post-quantum or not) can be used for key agreement: just choose a random key and encrypt it.

Password Authenticated Key Exchange looks harder, because it cannot be applied on just any key exchange or asymmetric encryption scheme. The IPAKE framework can be applied on any "trapdoor hard-to-invert group isomorphism", but application on NTRU or McEliece does not seem immediate.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Like said in the message, I know that asymmetric encryption can be used for key agreement. But "just" encrypting a random key is far from a proper cryptographic protocol enforcing PFS etc. and evaluating protocol security is not trivial either. $\endgroup$
    – Nakedible
    Commented Aug 25, 2011 at 11:43
  • $\begingroup$ I've trouble understanding the first part of this answer. Can anyone please explain why a quantum-threatened asymmetric encryption algorithm (e.g., discrete log) be also used safely for key agreement purposes? As in, if we do have a large-scale operational quantum computer, what aspect of key agreement makes it secure against quantum cryptanalysis? $\endgroup$
    – jayann
    Commented Nov 26, 2014 at 18:30
  • 3
    $\begingroup$ I am not saying that a "quantum-threatened" asymmetric encryption algorithm can be used safely for key agreement even in the presence of an attacker with a quantum computer. What I am saying is that any asymmetric encryption algorithm can be used for key agreement; so any quantum-safe asymmetric encryption algorithm is also a quantum-safe key agreement algorithm. $\endgroup$
    – Thomas Pornin
    Commented Nov 26, 2014 at 21:20
4
$\begingroup$

Douglas Stebila published:

We demonstrate the practicality of post-quantum key exchange by constructing ciphersuites for the Transport Layer Security (TLS) protocol that provide key exchange based on the ring learning with errors (R-LWE) problem

There is also a patch implementing it for OpenSSL 1.0.1f.

Improve this answer
$\endgroup$
0
0
$\begingroup$

Diffie-Hellman isn't necessary for key agreement; it's relatively rarely used in TLS, which is among the most widely used secure protocols. DH without authentication is trivially susceptible to a man in the middle, so practical systems have to have an authentication mechanism in place anyway. Once you have authentication via one of the mechanisms you described, key agreement is easy.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ Could you explain how to do key agreement once you have authentication? $\endgroup$
    – CodesInChaos
    Commented Aug 26, 2012 at 20:20
  • $\begingroup$ This answer doesn't make sense to me. Authentication can be solved, but how do you do the key agreement is the question here. $\endgroup$
    – user239558
    Commented Sep 11, 2013 at 22:40
  • 2
    $\begingroup$ If there is some secure asymmetric encryption protocol, one end can send an authenticated asymmetric encryption key and the other end can just send a random symmetric key encrypted to that key. $\endgroup$
    – Nakedible
    Commented Oct 13, 2013 at 5:57
  • 1
    $\begingroup$ In which case the party that sends the symmetric key has complete control over what the shared key is. Key Agreement (like DH) avoids this pitfall by having both parties independently contribute to the key derivation process. $\endgroup$
    – Mouse
    Commented Dec 8, 2018 at 1:22

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.