I was trying to look into weather or not it would be possible to build a post-quantum version of the signal protocol. The double ratchet algorithm is trivial to modify, replacing the ECDH key exchanges with SIDH key exchanges appears to be enough (since you only have to publish E, ϕ(P) and ϕ(Q) once) provided that there is a shared secret between all parties at the start. But the key exchange that signal uses to derive that shared secret, X3DH, is a problem. In the protocol there is a signed ECDH pre-key and the way the protocol specifies signing it is by using the identity key with XEdDSA which is based on EdDSA (which can be broken by quantum computers) and the fact that Montgomery Eliptic curves are birationally equivalent to twisted Edwards curves. I can't figure out a way around this without wrecking some of the protocol properties. The most promising lead I could find is figuring out a way to do something similar with RLWE-SIG and RLWE-KEX but I'm by no means an expert with lattice problems so anything I come up with would probably be bad and easily breakable. So is there a way to construct a post-quantum X3DH key exchange?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
I don't know very much about X3DH specifically, but Ben Smith's recent preprint is about isogeny-based cryptography and mentions X3DH on page 2. Unfortunately, that may be all it does, since I don't see any further discussion of X3DH. But it may be worth looking at.
As far as key signing goes, there is no good way to do isogeny-based signatures. If you only need one other party to validate the signature, you can use designated verifier signatures, which do work well with isogenies. Otherwise you're probably stuck building your own thing, which as you mentioned is not something suitable for the non-expert.
