Another look at some isogeny hardness assumptions

Simon-Philipp Merz; Romy  Minko; Christophe Petit

doi:10.1007/978-3-030-40186-3_21

Another look at some isogeny hardness assumptions

Simon-Philipp Merz, Romy Minko, Christophe Petit

Computer Science

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

1 Citation (Scopus)

530 Downloads (Pure)

Abstract

The security proofs for isogeny-based undeniable signature schemes have been based primarily on the assumptions that the One-Sided Modified SSCDH problem and the One-More SSCDH problem are intractable. We challenge the validity of these assumptions, showing that both the decisional and computational variants of these problems can be solved in polynomial time. We further demonstrate an attack, applicable to two undeniable signature schemes, one of which was proposed at PQCrypto 2014. The attack allows to forge signatures in 2^4λ/5 steps on a classical computer. This is an improvement over the expected classical security of 2^λ , where λ denotes the chosen security parameter.

Original language	English
Title of host publication	Topics in Cryptology – CT-RSA 2020
Subtitle of host publication	The Cryptographers’ Track at the RSA Conference 2020
Editors	Stanislaw Jarecki
Publisher	Springer
Pages	496-511
Number of pages	16
ISBN (Electronic)	978-3-030-40185-6, 978-3-030-40186-3
DOIs	https://doi.org/10.1007/978-3-030-40186-3_21
Publication status	E-pub ahead of print - 14 Feb 2020
Event	The Cryptographer's Track at the RSA Conference (CT-RSA 2020) - San Francisco, United States Duration: 24 Feb 2020 → 28 Feb 2020

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	12006
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	The Cryptographer's Track at the RSA Conference (CT-RSA 2020)
Country/Territory	United States
City	San Francisco
Period	24/02/20 → 28/02/20

Keywords

elliptic curves
isogenies
undeniable signatures

Access to Document

10.1007/978-3-030-40186-3_21Licence: None: All rights reserved

Merz_et_al_Another_look_at_some_isogeny_hardness_assumptions_Topics_in_Cryptology-CT-RSA_2020
The final authenticated version is available online at https://doi.org/10.1007/978-3-030-40186-3_21
Accepted author manuscript, 435 KBLicence: None: All rights reserved

https://link.springer.com/chapter/10.1007/978-3-030-40186-3_21Licence: None: All rights reserved

Cite this

@inproceedings{cb61562dad8445a39a778b2ebd39c2c3,

title = "Another look at some isogeny hardness assumptions",

abstract = "The security proofs for isogeny-based undeniable signature schemes have been based primarily on the assumptions that the One-Sided Modified SSCDH problem and the One-More SSCDH problem are intractable. We challenge the validity of these assumptions, showing that both the decisional and computational variants of these problems can be solved in polynomial time. We further demonstrate an attack, applicable to two undeniable signature schemes, one of which was proposed at PQCrypto 2014. The attack allows to forge signatures in 24λ/5 steps on a classical computer. This is an improvement over the expected classical security of 2λ , where λ denotes the chosen security parameter.",

keywords = "elliptic curves, isogenies, undeniable signatures",

author = "Simon-Philipp Merz and Romy Minko and Christophe Petit",

year = "2020",

month = feb,

day = "14",

doi = "10.1007/978-3-030-40186-3_21",

language = "English",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "496--511",

editor = "Stanislaw Jarecki",

booktitle = "Topics in Cryptology – CT-RSA 2020",

note = "The Cryptographer's Track at the RSA Conference (CT-RSA 2020) ; Conference date: 24-02-2020 Through 28-02-2020",

}

Merz, S-P, Minko, R & Petit, C 2020, Another look at some isogeny hardness assumptions. in S Jarecki (ed.), Topics in Cryptology – CT-RSA 2020: The Cryptographers’ Track at the RSA Conference 2020. Lecture Notes in Computer Science, vol. 12006, Springer, pp. 496-511, The Cryptographer's Track at the RSA Conference (CT-RSA 2020), San Francisco, United States, 24/02/20. https://doi.org/10.1007/978-3-030-40186-3_21

Another look at some isogeny hardness assumptions. / Merz, Simon-Philipp; Minko, Romy ; Petit, Christophe.
Topics in Cryptology – CT-RSA 2020: The Cryptographers’ Track at the RSA Conference 2020. ed. / Stanislaw Jarecki. Springer, 2020. p. 496-511 (Lecture Notes in Computer Science; Vol. 12006).

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

TY - GEN

T1 - Another look at some isogeny hardness assumptions

AU - Merz, Simon-Philipp

AU - Minko, Romy

AU - Petit, Christophe

PY - 2020/2/14

Y1 - 2020/2/14

N2 - The security proofs for isogeny-based undeniable signature schemes have been based primarily on the assumptions that the One-Sided Modified SSCDH problem and the One-More SSCDH problem are intractable. We challenge the validity of these assumptions, showing that both the decisional and computational variants of these problems can be solved in polynomial time. We further demonstrate an attack, applicable to two undeniable signature schemes, one of which was proposed at PQCrypto 2014. The attack allows to forge signatures in 24λ/5 steps on a classical computer. This is an improvement over the expected classical security of 2λ , where λ denotes the chosen security parameter.

AB - The security proofs for isogeny-based undeniable signature schemes have been based primarily on the assumptions that the One-Sided Modified SSCDH problem and the One-More SSCDH problem are intractable. We challenge the validity of these assumptions, showing that both the decisional and computational variants of these problems can be solved in polynomial time. We further demonstrate an attack, applicable to two undeniable signature schemes, one of which was proposed at PQCrypto 2014. The attack allows to forge signatures in 24λ/5 steps on a classical computer. This is an improvement over the expected classical security of 2λ , where λ denotes the chosen security parameter.

KW - elliptic curves

KW - isogenies

KW - undeniable signatures

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

U2 - 10.1007/978-3-030-40186-3_21

DO - 10.1007/978-3-030-40186-3_21

M3 - Conference contribution

T3 - Lecture Notes in Computer Science

SP - 496

EP - 511

BT - Topics in Cryptology – CT-RSA 2020

A2 - Jarecki, Stanislaw

PB - Springer

T2 - The Cryptographer's Track at the RSA Conference (CT-RSA 2020)

Y2 - 24 February 2020 through 28 February 2020

ER -

Another look at some isogeny hardness assumptions

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this