TY - GEN

T1 - Multi-party Key Exchange Protocols from Supersingular Isogenies

AU - Furukawa, Satoshi

AU - Kunihiro, Noboru

AU - Takashima, Katsuyuki

N1 - Funding Information:
ACKNOWLEDGMENT This research was partially supported by JST CREST Grant Number JPMJCR14D6, Japan and JSPS KAKENHI Grant Number 16H02780.
Publisher Copyright:
© 2018 IEICE.

PY - 2019/3/8

Y1 - 2019/3/8

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85063917378&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85063917378&partnerID=8YFLogxK

U2 - 10.23919/ISITA.2018.8664316

DO - 10.23919/ISITA.2018.8664316

M3 - Conference contribution

AN - SCOPUS:85063917378

T3 - Proceedings of 2018 International Symposium on Information Theory and Its Applications, ISITA 2018

SP - 208

EP - 212

BT - Proceedings of 2018 International Symposium on Information Theory and Its Applications, ISITA 2018

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 15th International Symposium on Information Theory and Its Applications, ISITA 2018

Y2 - 28 October 2018 through 31 October 2018

ER -