Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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!

share|improve this question
    
Not for the key agreement that you asked for, but for digital signatures, please see my answer to a previous related question. –  Zooko Sep 1 '11 at 3:04

4 Answers 4

up vote 4 down vote accepted

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.

share|improve this answer
    
The RFC draft was very interesting, thank you for the link! –  Nakedible Aug 25 '11 at 11:45
    
I accepted this answer because it contained more information that I didn't already know. –  Nakedible Sep 1 '11 at 13:48

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.

share|improve this answer
1  
Could you explain how to do key agreement once you have authentication? –  CodesInChaos Aug 26 '12 at 20:20
    
This answer doesn't make sense to me. Authentication can be solved, but how do you do the key agreement is the question here. –  user239558 Sep 11 '13 at 22:40
    
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. –  Nakedible Oct 13 '13 at 5:57

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.

share|improve this answer
    
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. –  Nakedible Aug 25 '11 at 11:43

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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