A Subexponential Quantum Algorithm for the Semidirect Discrete Logarithm Problem

Christopher Battarbee, Delaram Kahrobaei, Ludovic Perret, Siamak F. ShahandashtiPqcrypto 2024 · DOI

TL;DR

This paper introduces the first dedicated security analysis of the Semidirect Discrete Logarithm Problem (SDLP), a core problem in group-based cryptography. The authors establish a novel connection between SDLP and group actions, enabling them to construct a subexponential quantum algorithm for solving it, thus clarifying its complexity and relation to other hard problems.

What Problem Does This Paper Address?

Post-quantum cryptography (PQC) aims to develop cryptosystems secure against both classical and quantum computers. While NIST has standardized some PQC algorithms, the field is constantly evolving, with new attacks and the need for diverse hard problems. Group-based cryptography is a promising area for PQC, and the Semidirect Discrete Logarithm Problem (SDLP) is a central challenge within it. However, the general complexity of SDLP, especially against quantum adversaries, and its relationship to other well-known hard problems remained poorly understood. This paper addresses this gap by providing the first comprehensive security analysis of SDLP and developing a quantum algorithm for its solution.

Methods

The authors' approach involves several key steps:

  • Connecting SDLP to Group Actions: They demonstrate that SDLP can be reformulated as a problem within the context of group actions. Specifically, they show that a certain set of exponents related to SDLP forms a cycle on which an abelian group acts freely and transitively. This connection is crucial because quantum subexponential algorithms are known to apply to such group action problems.
  • Developing a Quantum Algorithm: By leveraging the group action framework, the authors construct a quantum algorithm for solving SDLP. This algorithm is built upon existing quantum techniques for related problems, such as the Group Action Discrete Logarithm Problem (GADLP) and the Abelian Hidden Shift Problem (AHSP).
  • Reduction Strategy: The core of their algorithm is a reduction from SDLP to GADLP, and then from GADLP to AHSP. They first show how to efficiently extract the necessary parameters (index and period) for the group action. Then, they use a GADLP oracle to solve SDLP. Finally, they discuss how AHSP can be solved using known quantum algorithms like Kuperberg's or Regev's.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • SDLP as a Group Action Problem: The most significant insight is the re-framing of SDLP as a problem on a group action. This connection unlocks the application of existing quantum algorithms designed for group actions.
  • Structure of Exponents: The paper reveals that the set of exponents in SDLP exhibits a cyclic structure, which is key to establishing the group action. This structure is characterized by an "index" and a "period."
  • Subexponential Quantum Complexity: The development of a quantum algorithm with subexponential time complexity for SDLP is a major result, classifying the problem's hardness against quantum adversaries.
  • Generalization: The authors' method is shown to be applicable to a broader class of structures than previously studied, including semigroups, not just groups.

Key Results

The paper presents a quantum algorithm for solving the Semidirect Discrete Logarithm Problem (SDLP) with a time and query complexity of $2^{O(\sqrt{\log p})}$, where $p$ parameterizes the size of the underlying structure. This is a subexponential complexity, which is considered acceptable for post-quantum cryptography. The algorithm relies on reducing SDLP to the Group Action Discrete Logarithm Problem (GADLP) and then to the Abelian Hidden Shift Problem (AHSP), for which efficient quantum algorithms exist.

Limitations and Future Work

  • Probabilistic Success: The algorithm's success probability is stated to be a positive constant, meaning it's not guaranteed to succeed on every run, but repeated runs can increase confidence.
  • Complexity Dependence: The subexponential complexity is dependent on the parameter $p$, which relates to the size of the "easy family of semigroups" used.
  • Renaming SDPKE: The authors propose renaming Semidirect Product Key Exchange (SDPKE) to SPDH (Semidirect Product Diffie-Hellman) to align with naming conventions for similar protocols.
  • Further Exploration: The paper suggests that this work opens avenues for further research into the algebraic machinery of SDPKE and its relation to "hard homogeneous spaces." They also mention that the presented algorithm is subexponential, which is tolerable in classical contexts, but further research might explore even more efficient solutions.

Summary updated

BibTeX
@inproceedings{battarbee2024subexponential,
  author = {Christopher Battarbee and Delaram Kahrobaei and Ludovic Perret and Siamak F. Shahandashti},
  title = {{A Subexponential Quantum Algorithm for the Semidirect Discrete Logarithm Problem}},
  booktitle = {Pqcrypto},
  year = {2024},
  doi = {10.1007/978-3-031-62743-9\_7},
}
Figure