Trapdoor DDH groups from pairings and isogenies

Péter Kutas; Christophe Petit; Javier  Silva

doi:10.1007/978-3-030-81652-0_17

Trapdoor DDH groups from pairings and isogenies

Péter Kutas, Christophe Petit, Javier Silva

Computer Science

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

159 Downloads (Pure)

Abstract

Trapdoor DDH groups are an appealing cryptographic primitive introduced by Dent-Galbraith (ANTS 2006), where DDH instances are hard to solve unless provided with additional information (i.e., a trapdoor). In this paper, we introduce a new trapdoor DDH group construction using pairings and isogenies of supersingular elliptic curves, and present two instantiations of it. The construction solves all shortcomings of previous constructions as identified by Seurin (RSA 2013). We also present partial attacks on a previous construction due to Dent-Galbraith, and we provide a formal security definition of the related notion of "trapdoor pairings".

Original language	English
Title of host publication	Selected Areas in Cryptography
Subtitle of host publication	27th International Conference, Halifax, NS, Canada (Virtual Event), October 21-23, 2020, Revised Selected Papers
Editors	Orr Dunkelman, Michael J. Jacobson, Jr., Colin O’Flynn
Publisher	Springer
Pages	431-450
ISBN (Electronic)	9783030816520
ISBN (Print)	9783030816513
DOIs	https://doi.org/10.1007/978-3-030-81652-0_17
Publication status	Published - 21 Jul 2021
Event	27th International Conference on Selected Areas in Cryptography, SAC 2020 - Virtual, Online Duration: 21 Oct 2020 → 23 Oct 2020

Publication series

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

Conference

Conference	27th International Conference on Selected Areas in Cryptography, SAC 2020
City	Virtual, Online
Period	21/10/20 → 23/10/20

Bibliographical note

Funding Information:
Acknowledgements. We thank Jens Groth, Steven Galbraith and Frederik Ver-cauteren for discussions related to this work. In particular, some of our applications were suggested by Jens Groth. We also thank the anonymous reviewers. Work by the first and second author was supported by an EPSRC New Investigator grant (EP/S01361X/1). The third author was supported by a PhD grant from the Spanish government, co-financed by the ESF (Ayudas para contratos predoctorales para la formación de doctores 2016). This work was partially done while the third author visited the University of Birmingham.

Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

Keywords

elliptic curve cryptography
pairings
isogenies
trapdoor DDH

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-030-81652-0_17Licence: None: All rights reserved

kutasp2021trapdoor
The final authenticated version is available online at https://doi.org/10.1007/978-3-030-81652-0_17
Accepted author manuscript, 428 KB

Cite this

Kutas, P., Petit, C., & Silva, J. (2021). Trapdoor DDH groups from pairings and isogenies. In O. Dunkelman, M. J. Jacobson, Jr., & C. O’Flynn (Eds.), Selected Areas in Cryptography: 27th International Conference, Halifax, NS, Canada (Virtual Event), October 21-23, 2020, Revised Selected Papers (pp. 431-450). (Lecture Notes in Computer Science). Springer. https://doi.org/10.1007/978-3-030-81652-0_17

Kutas, Péter ; Petit, Christophe ; Silva, Javier . / Trapdoor DDH groups from pairings and isogenies. Selected Areas in Cryptography: 27th International Conference, Halifax, NS, Canada (Virtual Event), October 21-23, 2020, Revised Selected Papers. editor / Orr Dunkelman ; Michael J. Jacobson, Jr. ; Colin O’Flynn. Springer, 2021. pp. 431-450 (Lecture Notes in Computer Science).

@inproceedings{b9db5a861a414e4a81f1cffcc8240606,

title = "Trapdoor DDH groups from pairings and isogenies",

abstract = "Trapdoor DDH groups are an appealing cryptographic primitive introduced by Dent-Galbraith (ANTS 2006), where DDH instances are hard to solve unless provided with additional information (i.e., a trapdoor). In this paper, we introduce a new trapdoor DDH group construction using pairings and isogenies of supersingular elliptic curves, and present two instantiations of it. The construction solves all shortcomings of previous constructions as identified by Seurin (RSA 2013). We also present partial attacks on a previous construction due to Dent-Galbraith, and we provide a formal security definition of the related notion of {"}trapdoor pairings{"}.",

keywords = "elliptic curve cryptography, pairings, isogenies, trapdoor DDH",

author = "P{\'e}ter Kutas and Christophe Petit and Javier Silva",

note = "Funding Information: Acknowledgements. We thank Jens Groth, Steven Galbraith and Frederik Ver-cauteren for discussions related to this work. In particular, some of our applications were suggested by Jens Groth. We also thank the anonymous reviewers. Work by the first and second author was supported by an EPSRC New Investigator grant (EP/S01361X/1). The third author was supported by a PhD grant from the Spanish government, co-financed by the ESF (Ayudas para contratos predoctorales para la formaci{\'o}n de doctores 2016). This work was partially done while the third author visited the University of Birmingham. Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 27th International Conference on Selected Areas in Cryptography, SAC 2020 ; Conference date: 21-10-2020 Through 23-10-2020",

year = "2021",

month = jul,

day = "21",

doi = "10.1007/978-3-030-81652-0_17",

language = "English",

isbn = "9783030816513",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "431--450",

editor = "Orr Dunkelman and {Jacobson, Jr.}, {Michael J.} and Colin O{\textquoteright}Flynn",

booktitle = "Selected Areas in Cryptography",

}

Kutas, P , Petit, C & Silva, J 2021, Trapdoor DDH groups from pairings and isogenies. in O Dunkelman, MJ Jacobson, Jr. & C O’Flynn (eds), Selected Areas in Cryptography: 27th International Conference, Halifax, NS, Canada (Virtual Event), October 21-23, 2020, Revised Selected Papers. Lecture Notes in Computer Science, Springer, pp. 431-450, 27th International Conference on Selected Areas in Cryptography, SAC 2020, Virtual, Online, 21/10/20. https://doi.org/10.1007/978-3-030-81652-0_17

Trapdoor DDH groups from pairings and isogenies. / Kutas, Péter ; Petit, Christophe; Silva, Javier .
Selected Areas in Cryptography: 27th International Conference, Halifax, NS, Canada (Virtual Event), October 21-23, 2020, Revised Selected Papers. ed. / Orr Dunkelman; Michael J. Jacobson, Jr.; Colin O’Flynn. Springer, 2021. p. 431-450 (Lecture Notes in Computer Science).

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

TY - GEN

T1 - Trapdoor DDH groups from pairings and isogenies

AU - Kutas, Péter

AU - Petit, Christophe

AU - Silva, Javier

N1 - Funding Information: Acknowledgements. We thank Jens Groth, Steven Galbraith and Frederik Ver-cauteren for discussions related to this work. In particular, some of our applications were suggested by Jens Groth. We also thank the anonymous reviewers. Work by the first and second author was supported by an EPSRC New Investigator grant (EP/S01361X/1). The third author was supported by a PhD grant from the Spanish government, co-financed by the ESF (Ayudas para contratos predoctorales para la formación de doctores 2016). This work was partially done while the third author visited the University of Birmingham. Publisher Copyright: © 2021, Springer Nature Switzerland AG.

PY - 2021/7/21

Y1 - 2021/7/21

N2 - Trapdoor DDH groups are an appealing cryptographic primitive introduced by Dent-Galbraith (ANTS 2006), where DDH instances are hard to solve unless provided with additional information (i.e., a trapdoor). In this paper, we introduce a new trapdoor DDH group construction using pairings and isogenies of supersingular elliptic curves, and present two instantiations of it. The construction solves all shortcomings of previous constructions as identified by Seurin (RSA 2013). We also present partial attacks on a previous construction due to Dent-Galbraith, and we provide a formal security definition of the related notion of "trapdoor pairings".

AB - Trapdoor DDH groups are an appealing cryptographic primitive introduced by Dent-Galbraith (ANTS 2006), where DDH instances are hard to solve unless provided with additional information (i.e., a trapdoor). In this paper, we introduce a new trapdoor DDH group construction using pairings and isogenies of supersingular elliptic curves, and present two instantiations of it. The construction solves all shortcomings of previous constructions as identified by Seurin (RSA 2013). We also present partial attacks on a previous construction due to Dent-Galbraith, and we provide a formal security definition of the related notion of "trapdoor pairings".

KW - elliptic curve cryptography

KW - pairings

KW - isogenies

KW - trapdoor DDH

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

U2 - 10.1007/978-3-030-81652-0_17

DO - 10.1007/978-3-030-81652-0_17

M3 - Conference contribution

AN - SCOPUS:85113496794

SN - 9783030816513

T3 - Lecture Notes in Computer Science

SP - 431

EP - 450

BT - Selected Areas in Cryptography

A2 - Dunkelman, Orr

A2 - Jacobson, Jr., Michael J.

A2 - O’Flynn, Colin

PB - Springer

T2 - 27th International Conference on Selected Areas in Cryptography, SAC 2020

Y2 - 21 October 2020 through 23 October 2020

ER -

Kutas P , Petit C, Silva J. Trapdoor DDH groups from pairings and isogenies. In Dunkelman O, Jacobson, Jr. MJ, O’Flynn C, editors, Selected Areas in Cryptography: 27th International Conference, Halifax, NS, Canada (Virtual Event), October 21-23, 2020, Revised Selected Papers. Springer. 2021. p. 431-450. (Lecture Notes in Computer Science). doi: 10.1007/978-3-030-81652-0_17

Trapdoor DDH groups from pairings and isogenies

Abstract

Publication series

Conference

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this