Paper 2021/1596

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published by the IACR in ASIACRYPT 2021
Keywords
Post-quantum cryptographySIDHSIKEadaptive attacksHealSIDHSHealSHealS
Contact author(s)
takoboris fouotsa @ uniroma3 it
christophe f petit @ gmail com
History
2022-04-04: last of 2 revisions
2021-12-06: received
See all versions
Short URL
https://ia.cr/2021/1596
License
Creative Commons Attribution
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.