A Note on the Post-Quantum Security of the Inverse Discrete Logarithm Problem

Joshua Limbrey; Andrew Mendelsohn

Paper 2025/1417 Original: eprint.iacr.org/2025/1417 ↗

A Note on the Post-Quantum Security of the Inverse Discrete Logarithm Problem

Joshua Limbrey

Andrew Mendelsohn

Abstract

In Submission 2025/1391 to the IACR Cryptology ePrint Archive, the Inverse Discrete Logarithm Problem (IDLP) is introduced and used to build a key exchange protocol and a KEM. The author claims both classical and post-quantum security for IDLP and therefore for the proposed protocols. It is the purpose of this note to give an efficient quantum algorithm for IDLP, based on the algorithm of Shor. We give an implementation of our algorithm, replacing the use of Shor's algorithm with an oracle.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
History: 2025-08-04: last updated; 2025-08-04: published
Short URL: https://ia.cr/2025/1417
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:2025/1417,
      author = {Joshua Limbrey and Andrew Mendelsohn},
      title = {A Note on the Post-Quantum Security of the Inverse Discrete Logarithm Problem},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1417},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1417}
}