International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Hart Montgomery , Linux Foundation & Fujitsu Research
Mark Zhandry , NTT Research & Princeton University
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2022
Award: Best Paper Award
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.
Video from ASIACRYPT 2022
BibTeX
@inproceedings{asiacrypt-2022-32523,
  title={Full Quantum Equivalence of Group Action DLog and CDH, and More},
  publisher={Springer-Verlag},
  author={Hart Montgomery and Mark Zhandry},
  year=2022
}