Cryptology ePrint Archive: Report 2018/336

SoK: The Problem Landscape of SIDH

David Urbanik and David Jao

Abstract: The Supersingular Isogeny Diffie-Hellman protocol (SIDH) has recently been the subject of increased attention in the cryptography community. Conjecturally quantum-resistant, SIDH has the feature that it shares the same data flow as ordinary Diffie-Hellman: two parties exchange a pair of public keys, each generated from a private key, and combine them to form a shared secret. To create a potentially quantum-resistant scheme, SIDH depends on a new family of computational assumptions involving isogenies between supersingular elliptic curves which replace both the discrete logarithm problem and the computational and decisional Diffie-Hellman problems. Like in the case of ordinary Diffie-Hellman, one is interested in knowing if these problems are related. In fact, more is true: there is a rich network of reductions between the isogeny problems securing the private keys of the participants in the SIDH protocol, the computational and decisional SIDH problems, and the problem of validating SIDH public keys. In this article we explain these relationships, which do not appear elsewhere in the literature, in hopes of providing a clearer picture of the SIDH problem landscape to the cryptography community at large.

Category / Keywords: public-key cryptography / isogeny-based cryptography, post-quantum cryptography, SIDH, torsion points, supersingular elliptic curves, equivalence theorems

Original Publication (in the same form): APKC 2018
DOI:
10.1145/3197507.3197516

Date: received 11 Apr 2018

Contact author: dburbani at uwaterloo ca

Available format(s): PDF | BibTeX Citation

Version: 20180411:202714 (All versions of this report)

Short URL: ia.cr/2018/336

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]