Multi-party Key Exchange Protocols from Supersingular Isogenies

When large-scale quantum computers are implemented, several cryptosystems based on the hardness of factoring and discrete logarithm problems will be broken. Hence, it is desirable to construct quantum-resistant cryptographic protocols. Although several candidates are introduced for hard problem, the computational hardness of finding isogenies between two supersingular elliptic curves (supersingular isogenies) is promising among them. It is strongly believed that the computation of supersingular isogenies requires exponential time even in the quantum computers. In this paper, we propose quantum-resistant multi-party key exchange protocols. First, we introduce several assumptions related to supersingular isogenies, which includes a generalization of supersingular isogeny decisional Diffie-Hellman (SSDDH) assumption which is called GSSDDH assumption. We present a construction of the n-party key exchange protocol based on the GSSDDH assumption. It is n - 1-round protocol and can be considered as a natural extension of 2-party 1-round supersingular isogeny Diffie-Hellman (SIDH) protocol, and we call it generalized SIDH (GSIDH) protocol. We then propose an n-party 2-round key exchange protocol by combining SIDH with the idea of Burmester-Desmedt (BD) key exchange, which significantly reduces the number of rounds. This protocol is called SIBD protocol and is based on the SSDDH assumption.