Authenticated key exchange from supersingular isogeny

Abstract

This paper studies the supersingular isogeny cryptosystem, a new promising post-quantum cryptosystem, and proposes a provably secure two-pass authenticated key exchange protocol over supersingular isogeny cryptosystems inspired by twin Diffie-Hellman problems. The proposed protocol is also an MQV-style protocol, hence it inherits sound properties of (H)MQV protocol. The security of the proposed protocol is based on the hardness of computing isogenies between supersingular elliptic curves. This paper gives heuristic arguments about the security properties, and formally proves its security in the authenticated-links adversarial model of Canetti-Krawczyk. To prove the security, a twin version of supersingular isogeny assumption is proposed. Compared with the lattice-based schemes, the proposed protocol has smaller keys and larger computation.