Paper 2019/330

Practical Supersingular Isogeny Group Key Agreement

Reza Azarderakhsh and Amir Jalali and David Jao and Vladimir Soukharev

Abstract

We present the first quantum-resistant $n$-party key agreement scheme based on supersingular elliptic curve isogenies. We show that the scheme is secure against quantum adversaries, by providing a security reduction to an intractable isogeny problem. We describe the communication and computational steps required for $n$ parties to establish a common shared secret key. Our scheme is the first non-generic quantum-resistant group key agreement protocol, and is more efficient than generic protocols, with near-optimal communication overhead. In addition, our scheme is contributory, which in some settings is a desirable security property: each party applies a function of their own private key to every further transmission. We implement the proposed protocol in portable C for the special case where three parties establish a shared secret. Moreover, we benchmark our software on two generations of Intel processors, highlighting the feasibility and efficiency of using the proposed scheme in practical settings. The proposed software computes the entire group key agreement in 994 and 1,374 millions of clock cycles on Intel Core i7-6500 Skylake and Core i7-2609 Sandy Bridge processors, respectively.

Note: The constructions described in our article have previously been published by Furukawa, Kunihiro and Takashima, "Multi-party Key Exchange Protocols from Supersingular Isogenies," doi:10.23919/ISITA.2018.8664316. Our implementation results, to our knowledge, remain novel. Our work was performed independently in 2017, but was not posted to eprint until 2019. For historical reasons we leave this article intact, as the claims therein, to our knowledge, were accurate at the time the article was written. Contemporaneous (non-refereed) references to our results include a presentation by Soukharev at ICMC 2018 (May 2018), and the PhD thesis of Jalali (Dec. 2018). It is not our intention to detract from the credit that Furukawa, Kunihiro and Takashima deserve for being first to publish the construction in peer-reviewed form.