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

Joshua Limbrey; Andrew Mendelsohn

Paper 2025/1417

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

Joshua Limbrey, Imperial College London

Andrew Mendelsohn, Imperial College London

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.
Keywords: post-quantum cryptanalysis discrete logarithm Shor's algorithm
Contact author(s): j limbrey24 @ imperial ac uk
andrew mendelsohn18 @ imperial ac uk
History: 2025-08-04: approved; 2025-08-04: received; See all versions
Short URL: https://ia.cr/2025/1417
License: CC BY

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}
}