On the security of supersingular isogeny cryptosystems

Steven D. Galbraith, Christophe Petit, Barak Shani, Yan Bo Ti

Research output: Chapter in Book/Report/Conference proceedingConference contribution

63 Citations (Scopus)

Abstract

We study cryptosystems based on supersingular isogenies. This is an active area of research in post-quantum cryptography. Our first contribution is to give a very powerful active attack on the supersingular isogeny encryption scheme. This attack can only be prevented by using a (relatively expensive) countermeasure. Our second contribution is to show that the security of all schemes of this type depends on the difficulty of computing the endomorphism ring of a supersingular elliptic curve. This result gives significant insight into the difficulty of the isogeny problem that underlies the security of these schemes. Our third contribution is to give a reduction that uses partial knowledge of shared keys to determine an entire shared key. This can be used to retrieve the secret key, given information leaked from a side-channel attack on the key exchange protocol. A corollary of this work is the first bit security result for the supersingular isogeny key exchange: Computing any component of the j-invariant is as hard as computing the whole j-invariant.

Our paper therefore provides an improved understanding of the security of these cryptosystems. We stress that our work does not imply that these systems are insecure, or that they should not be used. However, it highlights that implementations of these schemes will need to take account of the risks associated with various active and side-channel attacks.
Original languageEnglish
Title of host publicationAdvances in Cryptology – ASIACRYPT 2016
Subtitle of host publication22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4-8, 2016, Proceedings, Part I
EditorsJung Hee Cheon, Tsuyoshi Takagi
PublisherSpringer
Pages63-91
ISBN (Electronic)9783662538876
ISBN (Print)9783662538869
DOIs
Publication statusPublished - 9 Nov 2016
Event22nd International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2016) - Hanoi, Viet Nam
Duration: 4 Dec 20168 Dec 2016

Publication series

NameLecture Notes in Computer Science (LNCS)
Volume10031
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference22nd International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2016)
Country/TerritoryViet Nam
CityHanoi
Period4/12/168/12/16

Keywords

  • isogenies
  • supersingular elliptic curves

Fingerprint

Dive into the research topics of 'On the security of supersingular isogeny cryptosystems'. Together they form a unique fingerprint.

Cite this