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.

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. APKC 2018
DOI
10.1145/3197507.3197516
Keywords
isogeny-based cryptographypost-quantum cryptographySIDHtorsion pointssupersingular elliptic curvesequivalence theorems
Contact author(s)
dburbani @ uwaterloo ca
History
Short URL
https://ia.cr/2018/336

CC BY

BibTeX

@misc{cryptoeprint:2018/336,
author = {David Urbanik and David Jao},
title = {SoK: The Problem Landscape of SIDH},
howpublished = {Cryptology ePrint Archive, Paper 2018/336},
year = {2018},
doi = {10.1145/3197507.3197516},
note = {\url{https://eprint.iacr.org/2018/336}},
url = {https://eprint.iacr.org/2018/336}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.