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

Tako Boris Fouotsa and Christophe Petit

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 schemes. 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.

Note: A note about the security of the schemes was added on the first page of the paper.

Available format(s)
Category
Public-key cryptography
Publication info
Keywords
Contact author(s)
takoboris fouotsa @ uniroma3 it
christophe f petit @ gmail com
History
2022-04-04: last of 2 revisions
See all versions
Short URL
https://ia.cr/2021/1596

CC BY

BibTeX

@misc{cryptoeprint:2021/1596,
author = {Tako Boris Fouotsa and Christophe Petit},
title = {SHealS and HealS: isogeny-based PKEs from akey validation method for SIDH},
howpublished = {Cryptology ePrint Archive, Paper 2021/1596},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/1596}},
url = {https://eprint.iacr.org/2021/1596}
}

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