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

Tako Boris Fouotsa; Christophe Petit

doi:10.1007/978-3-030-92068-5_10

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

Tako Boris Fouotsa^*, Christophe Petit

^*Corresponding author for this work

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

24 Downloads (Pure)

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 language	English
Title of host publication	Advances in Cryptology – ASIACRYPT 2021
Subtitle of host publication	27th International Conference on the Theory and Application of Cryptology and Information Security, 2021, Proceedings, Part 4
Editors	Mehdi Tibouchi, Huaxiong Wang
Publisher	Springer
Pages	279-307
Number of pages	29
Edition	1
ISBN (Electronic)	9783030920685
ISBN (Print)	9783030920678
DOIs	https://doi.org/10.1007/978-3-030-92068-5_10
Publication status	Published - 1 Dec 2021
Event	27th International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2021 - Virtual, Online Duration: 6 Dec 2021 → 10 Dec 2021

Publication series

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

Conference

Conference	27th International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2021
City	Virtual, Online
Period	6/12/21 → 10/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)

Access to Document

10.1007/978-3-030-92068-5_10

FouotsaT2021SHealS
This version of the contribution has been accepted for publication, after peer review (when applicable) but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: http://dx.doi.org/10.1007/978-3-030-92068-5_10. Use of this Accepted Version is subject to the publisher’s Accepted Manuscript terms of use https://www.springernature.com/gp/open-research/policies/accepted-manuscript-terms
Accepted author manuscript, 476 KBLicence: Other (please specify with Rights Statement)

Cite this

Fouotsa, T. B., & Petit, C. (2021). SHealS and HealS: isogeny-based PKEs from a key validation method for SIDH. In M. Tibouchi, & H. Wang (Eds.), Advances in Cryptology – ASIACRYPT 2021: 27th International Conference on the Theory and Application of Cryptology and Information Security, 2021, Proceedings, Part 4 (1 ed., pp. 279-307). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13093 LNCS). Springer. https://doi.org/10.1007/978-3-030-92068-5_10

Fouotsa, Tako Boris ; Petit, Christophe. / SHealS and HealS : isogeny-based PKEs from a key validation method for SIDH. Advances in Cryptology – ASIACRYPT 2021: 27th International Conference on the Theory and Application of Cryptology and Information Security, 2021, Proceedings, Part 4. editor / Mehdi Tibouchi ; Huaxiong Wang. 1. ed. Springer, 2021. pp. 279-307 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{620298befb5b4d9694dae0ee8e0f9981,

title = "SHealS and HealS: isogeny-based PKEs from a key validation method for SIDH",

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{\textquoteright}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.",

keywords = "Adaptive attacks, HealS, HealSIDH, Post-quantum cryptography, SHealS, SIDH, SIKE",

author = "Fouotsa, {Tako Boris} and Christophe Petit",

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: {\textcopyright} 2021, International Association for Cryptologic Research.; 27th International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2021 ; Conference date: 06-12-2021 Through 10-12-2021",

year = "2021",

month = dec,

day = "1",

doi = "10.1007/978-3-030-92068-5_10",

language = "English",

isbn = "9783030920678",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "279--307",

editor = "Mehdi Tibouchi and Huaxiong Wang",

booktitle = "Advances in Cryptology – ASIACRYPT 2021",

edition = "1",

}

Fouotsa, TB & Petit, C 2021, SHealS and HealS: isogeny-based PKEs from a key validation method for SIDH. in M Tibouchi & H Wang (eds), Advances in Cryptology – ASIACRYPT 2021: 27th International Conference on the Theory and Application of Cryptology and Information Security, 2021, Proceedings, Part 4. 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13093 LNCS, Springer, pp. 279-307, 27th International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2021, Virtual, Online, 6/12/21. https://doi.org/10.1007/978-3-030-92068-5_10

SHealS and HealS: isogeny-based PKEs from a key validation method for SIDH. / Fouotsa, Tako Boris; Petit, Christophe.
Advances in Cryptology – ASIACRYPT 2021: 27th International Conference on the Theory and Application of Cryptology and Information Security, 2021, Proceedings, Part 4. ed. / Mehdi Tibouchi; Huaxiong Wang. 1. ed. Springer, 2021. p. 279-307 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13093 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - SHealS and HealS

T2 - 27th International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2021

AU - Fouotsa, Tako Boris

AU - Petit, Christophe

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

PY - 2021/12/1

Y1 - 2021/12/1

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

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

KW - Adaptive attacks

KW - HealS

KW - HealSIDH

KW - Post-quantum cryptography

KW - SHealS

KW - SIDH

KW - SIKE

UR - http://www.scopus.com/inward/record.url?scp=85121910639&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-92068-5_10

DO - 10.1007/978-3-030-92068-5_10

M3 - Conference contribution

AN - SCOPUS:85121910639

SN - 9783030920678

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 279

EP - 307

BT - Advances in Cryptology – ASIACRYPT 2021

A2 - Tibouchi, Mehdi

A2 - Wang, Huaxiong

PB - Springer

Y2 - 6 December 2021 through 10 December 2021

ER -

Fouotsa TB, Petit C. SHealS and HealS: isogeny-based PKEs from a key validation method for SIDH. In Tibouchi M, Wang H, editors, Advances in Cryptology – ASIACRYPT 2021: 27th International Conference on the Theory and Application of Cryptology and Information Security, 2021, Proceedings, Part 4. 1 ed. Springer. 2021. p. 279-307. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-92068-5_10