International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Tako Boris Fouotsa , Università degli Studi Roma Tre
Christophe Petit , Université libre de Bruxelles
Download:
DOI: 10.1007/978-3-030-92068-5_10
Search ePrint
Search Google
Conference: ASIACRYPT 2021
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.
Video from ASIACRYPT 2021
BibTeX
@inproceedings{asiacrypt-2021-31465,
  title={SHealS and HealS: isogeny-based PKEs from a key validation method for SIDH},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-030-92068-5_10},
  author={Tako Boris Fouotsa and Christophe Petit},
  year=2021
}