A Simpler and More Efficient Reduction of DLog to CDH for Abelian Group Actions

Steven Galbraith; Yi-Fu Lai; Hart Montgomery

Paper 2024/191

A Simpler and More Efficient Reduction of DLog to CDH for Abelian Group Actions

Steven Galbraith

, University of Auckland

Yi-Fu Lai

, Ruhr-University Bochum

Hart Montgomery

, Linux Foundation

Abstract

Abelian group actions appear in several areas of cryptography, especially isogeny-based post-quantum cryptography. A natural problem is to relate the analogues of the computational Diffie-Hellman (CDH) and discrete logarithm (DLog) problems for abelian group actions. Galbraith, Panny, Smith and Vercauteren (Mathematical Cryptology '21) gave a quantum reduction of DLog to CDH, assuming a CDH oracle with perfect correctness. Montgomery and Zhandry (Asiacrypt '22, best paper award) showed how to convert an unreliable CDH oracle into one that is correct with overwhelming probability. However, while a theoretical breakthrough, their reduction is quite inefficient: if the CDH oracle is correct with probability $\epsilon$ then their algorithm to amplify the success requires on the order of $1/\epsilon^{21}$ calls to the CDH oracle. We revisit this line of work and give a much simpler and tighter algorithm. Our method only takes on the order of $1/\epsilon^{4}$ CDH oracle calls and is conceptually simpler than the Montgomery-Zhandry reduction. Our algorithm is also fully black-box, whereas the Montgomery-Zhandry algorithm is slightly non-black-box. Our main tool is a thresholding technique that replaces the comparison of distributions in Montgomery-Zhandry with testing equality of thresholded sets.

Note: Update Feb 9: Edit the contact information.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: A minor revision of an IACR publication in PKC 2024
Keywords: group actions isogenies isogeny-based cryptography discrete log CDH
Contact author(s): s galbraith @ auckland ac nz
Yi-Fu Lai @ ruhr-uni-bochum de
hart montgomery @ gmail com
History: 2024-02-09: revised; 2024-02-08: received; See all versions
Short URL: https://ia.cr/2024/191
License: CC BY

BibTeX

@misc{cryptoeprint:2024/191,
      author = {Steven Galbraith and Yi-Fu Lai and Hart Montgomery},
      title = {A Simpler and More Efficient Reduction of DLog to CDH for Abelian Group Actions},
      howpublished = {Cryptology ePrint Archive, Paper 2024/191},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/191}},
      url = {https://eprint.iacr.org/2024/191}
}