A Subexponential Quantum Algorithm for the Semdirect Discrete Logarithm Problem

Christopher Battarbee; Delaram Kahrobaei; Ludovic Perret; Siamak F. Shahandashti

doi:10.1007/978-3-031-62743-9_7

A Subexponential Quantum Algorithm for the Semdirect Discrete Logarithm Problem

Christopher Battarbee, Delaram Kahrobaei, Ludovic Perret, Siamak F. Shahandashti

Computer Science

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

Abstract

Group-based cryptography is a relatively unexplored family in post-quantum cryptography, and the so-called Semidirect Discrete Logarithm Problem (SDLP) is one of its most central problems. However, the complexity of SDLP and its relationship to more well-known hardness problems, particularly with respect to its security against quantum adversaries, has not been well understood and was a significant open problem for researchers in this area. In this paper we give the first dedicated security analysis of SDLP. In particular, we provide a connection between SDLP and group actions, a context in which quantum subexponential algorithms are known to apply. We are therefore able to construct a subexponential quantum algorithm for solving SDLP, thereby classifying the complexity of SDLP and its relation to known computational problems.

Original language	English
Title of host publication	Post-Quantum Cryptography 2024
Subtitle of host publication	proceedings
Pages	202–226
ISBN (Electronic)	978-3-031-62743-9
DOIs	https://doi.org/10.1007/978-3-031-62743-9_7
Publication status	Published - 14 Jun 2024
Event	Post-Quantum Cryptography 2024 - University of Oxford, Mathematical Institute, Oxford, United Kingdom Duration: 12 Jun 2024 → 14 Jun 2024 https://www.maths.ox.ac.uk/events/conferences/pqcrypto-2024

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	14771

Conference

Conference	Post-Quantum Cryptography 2024
Abbreviated title	PQCrypto 2024
Country/Territory	United Kingdom
City	Oxford
Period	12/06/24 → 14/06/24
Internet address	https://www.maths.ox.ac.uk/events/conferences/pqcrypto-2024

Bibliographical note

This is an author-produced version of the published paper. Uploaded in accordance with the University’s Research Publications and Open Access policy.

Keywords

discrete logarithm
semidirect product
group-based cryptography
semidirect-product key exchange
key exchange

Access to Document

10.1007/978-3-031-62743-9_7

A Subexponential Quantum Algorithm for the Semidirect Discrete Logarithm Problem
This is an author-produced version of the published paper. Uploaded in accordance with the University’s Research Publications and Open Access policy.
Accepted author manuscript, 324 KBLicence: CC BY

Cite this

@inproceedings{3f226c0a43df4aef9495411f4581d715,

title = "A Subexponential Quantum Algorithm for the Semdirect Discrete Logarithm Problem",

abstract = "Group-based cryptography is a relatively unexplored family in post-quantum cryptography, and the so-called Semidirect Discrete Logarithm Problem (SDLP) is one of its most central problems. However, the complexity of SDLP and its relationship to more well-known hardness problems, particularly with respect to its security against quantum adversaries, has not been well understood and was a significant open problem for researchers in this area. In this paper we give the first dedicated security analysis of SDLP. In particular, we provide a connection between SDLP and group actions, a context in which quantum subexponential algorithms are known to apply. We are therefore able to construct a subexponential quantum algorithm for solving SDLP, thereby classifying the complexity of SDLP and its relation to known computational problems.",

keywords = "discrete logarithm, semidirect product, group-based cryptography, semidirect-product key exchange, key exchange",

author = "Christopher Battarbee and Delaram Kahrobaei and Ludovic Perret and Shahandashti, {Siamak F.}",

note = "This is an author-produced version of the published paper. Uploaded in accordance with the University{\textquoteright}s Research Publications and Open Access policy. ; Post-Quantum Cryptography 2024, PQCrypto 2024 ; Conference date: 12-06-2024 Through 14-06-2024",

year = "2024",

month = jun,

day = "14",

doi = "10.1007/978-3-031-62743-9_7",

language = "English",

isbn = "978-3-031-62742-2",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "202–226",

booktitle = "Post-Quantum Cryptography 2024",

url = "https://www.maths.ox.ac.uk/events/conferences/pqcrypto-2024",

}

TY - GEN

T1 - A Subexponential Quantum Algorithm for the Semdirect Discrete Logarithm Problem

AU - Battarbee, Christopher

AU - Kahrobaei, Delaram

AU - Perret, Ludovic

AU - Shahandashti, Siamak F.

N1 - This is an author-produced version of the published paper. Uploaded in accordance with the University’s Research Publications and Open Access policy.

PY - 2024/6/14

Y1 - 2024/6/14

N2 - Group-based cryptography is a relatively unexplored family in post-quantum cryptography, and the so-called Semidirect Discrete Logarithm Problem (SDLP) is one of its most central problems. However, the complexity of SDLP and its relationship to more well-known hardness problems, particularly with respect to its security against quantum adversaries, has not been well understood and was a significant open problem for researchers in this area. In this paper we give the first dedicated security analysis of SDLP. In particular, we provide a connection between SDLP and group actions, a context in which quantum subexponential algorithms are known to apply. We are therefore able to construct a subexponential quantum algorithm for solving SDLP, thereby classifying the complexity of SDLP and its relation to known computational problems.

AB - Group-based cryptography is a relatively unexplored family in post-quantum cryptography, and the so-called Semidirect Discrete Logarithm Problem (SDLP) is one of its most central problems. However, the complexity of SDLP and its relationship to more well-known hardness problems, particularly with respect to its security against quantum adversaries, has not been well understood and was a significant open problem for researchers in this area. In this paper we give the first dedicated security analysis of SDLP. In particular, we provide a connection between SDLP and group actions, a context in which quantum subexponential algorithms are known to apply. We are therefore able to construct a subexponential quantum algorithm for solving SDLP, thereby classifying the complexity of SDLP and its relation to known computational problems.

KW - discrete logarithm

KW - semidirect product

KW - group-based cryptography

KW - semidirect-product key exchange

KW - key exchange

U2 - 10.1007/978-3-031-62743-9_7

DO - 10.1007/978-3-031-62743-9_7

M3 - Conference contribution

SN - 978-3-031-62742-2

T3 - Lecture Notes in Computer Science

SP - 202

EP - 226

BT - Post-Quantum Cryptography 2024

T2 - Post-Quantum Cryptography 2024

Y2 - 12 June 2024 through 14 June 2024

ER -