SHealS and HealS: isogeny-based PKEs from a key validation method for SIDH

Tako Boris Fouotsa, Christophe Petit

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

Abstract

In 2016, Galbraith et al. presented an adaptive attack on the SIDH key exchange protocol. In SIKE, one applies a variant of the Fujisaki-Okamoto transform to force Bob to reveal his encryption key to Alice, which Alice then uses to re-encrypt Bob’s ciphertext and verify its validity. Therefore, Bob can not reuse his encryption keys. There have been two other proposed countermeasures enabling static-static private keys: k-SIDH and its variant by Jao and Urbanik. These countermeasures are relatively expensive since they consist in running multiple parallel instances of SIDH. In this paper, firstly, we propose a new countermeasure to the GPST adaptive attack on SIDH. Our countermeasure does not require key disclosure as in SIKE, nor multiple parallel instances as in k-SIDH. We translate our countermeasure into a key validation method for SIDH-type schmes. Secondly, we use our key validation to design HealSIDH, an efficient SIDH-type static-static key interactive exchange protocol. Thirdly, we derive a PKE scheme SHealS using HealSIDH. SHealS uses larger primes compared to SIKE, has larger keys and ciphertexts, but only 4 isogenies are computed in a full execution of the scheme, as opposed to 5 isogenies in SIKE. We prove that SHealS is IND-CPA secure relying on a new assumption we introduce and we conjecture its IND-CCA security. We suggest HealS, a variant of SHealS using a smaller prime, providing smaller keys and ciphertexts. As a result, HealSIDH is a practically efficient SIDH based (interactive) key exchange incorporating a “direct” countermeasure to the GPST adaptive attack.

Original languageEnglish
Title of host publicationAdvances in Cryptology – ASIACRYPT 2021
Subtitle of host publication27th International Conference on the Theory and Application of Cryptology and Information Security, 2021, Proceedings, Part 4
EditorsMehdi Tibouchi, Huaxiong Wang
PublisherSpringer
Pages279-307
Number of pages29
Edition1
ISBN (Electronic)9783030920685
ISBN (Print)9783030920678
DOIs
Publication statusPublished - 1 Dec 2021
Event27th International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2021 - Virtual, Online
Duration: 6 Dec 202110 Dec 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13093 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference27th International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2021
CityVirtual, Online
Period6/12/2110/12/21

Bibliographical note

Funding Information:
Acknowledgements. We would like to express our sincere gratitude to the anonymous reviewers for their helpful comments and suggestions. Christophe Petit was supported by EPSRC grant EP/S01361X/1.

Publisher Copyright:
© 2021, International Association for Cryptologic Research.

Keywords

  • Adaptive attacks
  • HealS
  • HealSIDH
  • Post-quantum cryptography
  • SHealS
  • SIDH
  • SIKE

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'SHealS and HealS: isogeny-based PKEs from a key validation method for SIDH'. Together they form a unique fingerprint.

Cite this