Full Quantum Equivalence of Group Action DLog and CDH, and More

Hart Montgomery; Mark Zhandry

Paper 2022/1135

Full Quantum Equivalence of Group Action DLog and CDH, and More

Hart Montgomery, Linux Foundation, Fujitsu Labs

Mark Zhandry

, NTT Research, Princeton University

Abstract

Cryptographic group actions are a relaxation of standard cryptographic groups that have less structure. This lack of structure allows them to be plausibly quantum resistant despite Shor's algorithm, while still having a number of applications. The most famous example of group actions are built from isogenies on elliptic curves. Our main result is that CDH for abelian group actions is quantumly *equivalent* to discrete log. Galbraith et al. (Mathematical Cryptology) previously showed *perfectly* solving CDH to be equivalent to discrete log quantumly; our result works for any non-negligible advantage. We also explore several other questions about group action and isogeny protocols.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: A major revision of an IACR publication in ASIACRYPT 2022
Keywords: group actions isogenies discrete log diffie-hellman
Contact author(s): mzhandry @ gmail com
History: 2022-09-05: approved; 2022-08-31: received; See all versions
Short URL: https://ia.cr/2022/1135
License: CC BY

BibTeX

@misc{cryptoeprint:2022/1135,
      author = {Hart Montgomery and Mark Zhandry},
      title = {Full Quantum Equivalence of Group Action DLog and CDH, and More},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1135},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1135}},
      url = {https://eprint.iacr.org/2022/1135}
}