SimS: a simplification of SiGamal

Tako Boris Fouotsa; Christophe Petit

doi:10.1007/978-3-030-81293-5_15

SimS: a simplification of SiGamal

Tako Boris Fouotsa^*, Christophe Petit

^*Corresponding author for this work

Computer Science

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

139 Downloads (Pure)

Abstract

At Asiacrypt 2020, Moriya et al. introduced two new IND-CPA secure supersingular isogeny based Public Key Encryption (PKE) protocols: SiGamal and C-SiGamal. Unlike the PKEs canonically derived from SIDH and CSIDH, the new protocols provide IND-CPA security without the use of hash functions. SiGamal and C-SiGamal are however not IND-CCA secure. Moriya et al. suggested a variant of SiGamal that could be IND-CCA secure, but left its study as an open problem. In this paper, we revisit the protocols introduced by Moriya et al. First, we show that the SiGamal variant suggested by Moriya et al. for IND-CCA security is, in fact, not IND-CCA secure. Secondly, we propose a new isogeny-based PKE protocol named SimS, obtained by simplifying SiGamal. SimS has smaller public keys and ciphertexts than (C-)SiGamal and it is more efficient. We prove that SimS is IND-CCA secure under CSIDH security assumptions and one Knowledge of Exponent-type assumption we introduce. Interestingly, SimS is also much closer to the CSIDH protocol, facilitating a comparison between SiGamal and CSIDH.

Original language	English
Title of host publication	Post-Quantum Cryptography
Subtitle of host publication	12th International Workshop, PQCrypto 2021, Daejeon, South Korea, July 20–22, 2021, Proceedings
Editors	Jung Hee Cheon, Jean-Pierre Tillich
Publisher	Springer
Pages	277-295
Number of pages	19
ISBN (Electronic)	9783030812935
ISBN (Print)	9783030812928
DOIs	https://doi.org/10.1007/978-3-030-81293-5_15
Publication status	Published - 15 Jul 2021
Event	12th International Conference on post-quantum cryptography, PQCrypto 2021 - Daejeon, Korea, Republic of Duration: 20 Jul 2021 → 22 Jul 2021

Publication series

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

Conference

Conference	12th International Conference on post-quantum cryptography, PQCrypto 2021
Country/Territory	Korea, Republic of
City	Daejeon
Period	20/07/21 → 22/07/21

Bibliographical note

Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

Keywords

CSIDH
PKE
Post-quantum cryptography
SiGamal
SimS
Supersingular isogenies

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-030-81293-5_15Licence: None: All rights reserved

FouotsaT2021SimS
The final authenticated version is available online at https://doi.org/10.1007/978-3-030-81293-5_15
Accepted author manuscript, 475 KBLicence: None: All rights reserved

Cite this

Fouotsa, T. B., & Petit, C. (2021). SimS: a simplification of SiGamal. In J. H. Cheon, & J.-P. Tillich (Eds.), Post-Quantum Cryptography: 12th International Workshop, PQCrypto 2021, Daejeon, South Korea, July 20–22, 2021, Proceedings (pp. 277-295). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12841 LNCS). Springer. https://doi.org/10.1007/978-3-030-81293-5_15

Fouotsa, Tako Boris ; Petit, Christophe. / SimS : a simplification of SiGamal. Post-Quantum Cryptography: 12th International Workshop, PQCrypto 2021, Daejeon, South Korea, July 20–22, 2021, Proceedings. editor / Jung Hee Cheon ; Jean-Pierre Tillich. Springer, 2021. pp. 277-295 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{22bb9eb9c77e4cf6bf5e5afb4a3cc1d2,

title = "SimS: a simplification of SiGamal",

abstract = "At Asiacrypt 2020, Moriya et al. introduced two new IND-CPA secure supersingular isogeny based Public Key Encryption (PKE) protocols: SiGamal and C-SiGamal. Unlike the PKEs canonically derived from SIDH and CSIDH, the new protocols provide IND-CPA security without the use of hash functions. SiGamal and C-SiGamal are however not IND-CCA secure. Moriya et al. suggested a variant of SiGamal that could be IND-CCA secure, but left its study as an open problem. In this paper, we revisit the protocols introduced by Moriya et al. First, we show that the SiGamal variant suggested by Moriya et al. for IND-CCA security is, in fact, not IND-CCA secure. Secondly, we propose a new isogeny-based PKE protocol named SimS, obtained by simplifying SiGamal. SimS has smaller public keys and ciphertexts than (C-)SiGamal and it is more efficient. We prove that SimS is IND-CCA secure under CSIDH security assumptions and one Knowledge of Exponent-type assumption we introduce. Interestingly, SimS is also much closer to the CSIDH protocol, facilitating a comparison between SiGamal and CSIDH.",

keywords = "CSIDH, PKE, Post-quantum cryptography, SiGamal, SimS, Supersingular isogenies",

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

note = "Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 12th International Conference on post-quantum cryptography, PQCrypto 2021 ; Conference date: 20-07-2021 Through 22-07-2021",

year = "2021",

month = jul,

day = "15",

doi = "10.1007/978-3-030-81293-5_15",

language = "English",

isbn = "9783030812928",

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

publisher = "Springer",

pages = "277--295",

editor = "Cheon, {Jung Hee} and Jean-Pierre Tillich",

booktitle = "Post-Quantum Cryptography",

}

Fouotsa, TB & Petit, C 2021, SimS: a simplification of SiGamal. in JH Cheon & J-P Tillich (eds), Post-Quantum Cryptography: 12th International Workshop, PQCrypto 2021, Daejeon, South Korea, July 20–22, 2021, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12841 LNCS, Springer, pp. 277-295, 12th International Conference on post-quantum cryptography, PQCrypto 2021, Daejeon, Korea, Republic of, 20/07/21. https://doi.org/10.1007/978-3-030-81293-5_15

SimS: a simplification of SiGamal. / Fouotsa, Tako Boris; Petit, Christophe.
Post-Quantum Cryptography: 12th International Workshop, PQCrypto 2021, Daejeon, South Korea, July 20–22, 2021, Proceedings. ed. / Jung Hee Cheon; Jean-Pierre Tillich. Springer, 2021. p. 277-295 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12841 LNCS).

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

TY - GEN

T1 - SimS

T2 - 12th International Conference on post-quantum cryptography, PQCrypto 2021

AU - Fouotsa, Tako Boris

AU - Petit, Christophe

PY - 2021/7/15

Y1 - 2021/7/15

N2 - At Asiacrypt 2020, Moriya et al. introduced two new IND-CPA secure supersingular isogeny based Public Key Encryption (PKE) protocols: SiGamal and C-SiGamal. Unlike the PKEs canonically derived from SIDH and CSIDH, the new protocols provide IND-CPA security without the use of hash functions. SiGamal and C-SiGamal are however not IND-CCA secure. Moriya et al. suggested a variant of SiGamal that could be IND-CCA secure, but left its study as an open problem. In this paper, we revisit the protocols introduced by Moriya et al. First, we show that the SiGamal variant suggested by Moriya et al. for IND-CCA security is, in fact, not IND-CCA secure. Secondly, we propose a new isogeny-based PKE protocol named SimS, obtained by simplifying SiGamal. SimS has smaller public keys and ciphertexts than (C-)SiGamal and it is more efficient. We prove that SimS is IND-CCA secure under CSIDH security assumptions and one Knowledge of Exponent-type assumption we introduce. Interestingly, SimS is also much closer to the CSIDH protocol, facilitating a comparison between SiGamal and CSIDH.

AB - At Asiacrypt 2020, Moriya et al. introduced two new IND-CPA secure supersingular isogeny based Public Key Encryption (PKE) protocols: SiGamal and C-SiGamal. Unlike the PKEs canonically derived from SIDH and CSIDH, the new protocols provide IND-CPA security without the use of hash functions. SiGamal and C-SiGamal are however not IND-CCA secure. Moriya et al. suggested a variant of SiGamal that could be IND-CCA secure, but left its study as an open problem. In this paper, we revisit the protocols introduced by Moriya et al. First, we show that the SiGamal variant suggested by Moriya et al. for IND-CCA security is, in fact, not IND-CCA secure. Secondly, we propose a new isogeny-based PKE protocol named SimS, obtained by simplifying SiGamal. SimS has smaller public keys and ciphertexts than (C-)SiGamal and it is more efficient. We prove that SimS is IND-CCA secure under CSIDH security assumptions and one Knowledge of Exponent-type assumption we introduce. Interestingly, SimS is also much closer to the CSIDH protocol, facilitating a comparison between SiGamal and CSIDH.

KW - CSIDH

KW - PKE

KW - Post-quantum cryptography

KW - SiGamal

KW - SimS

KW - Supersingular isogenies

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

U2 - 10.1007/978-3-030-81293-5_15

DO - 10.1007/978-3-030-81293-5_15

M3 - Conference contribution

AN - SCOPUS:85112721931

SN - 9783030812928

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

SP - 277

EP - 295

BT - Post-Quantum Cryptography

A2 - Cheon, Jung Hee

A2 - Tillich, Jean-Pierre

PB - Springer

Y2 - 20 July 2021 through 22 July 2021

ER -

Fouotsa TB, Petit C. SimS: a simplification of SiGamal. In Cheon JH, Tillich JP, editors, Post-Quantum Cryptography: 12th International Workshop, PQCrypto 2021, Daejeon, South Korea, July 20–22, 2021, Proceedings. Springer. 2021. p. 277-295. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-81293-5_15

SimS: a simplification of SiGamal

Abstract

Publication series

Conference

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this