Quantum Security Analysis of CSIDH

Explore the quantum security analysis of CSIDH in this 23-minute conference talk presented at Eurocrypt 2020. Delve into the intricacies of Commutative Supersingular Isogeny Diffie-Hellman (CSIDH) as a hard homogeneous space key exchange protocol. Examine CSIDH's practical implementation, security aspects, and cryptanalysis principles. Understand the cost model and quantum oracle implementation for CSIDH. Investigate the hidden shift problem, labeled qubits, and Kuperberg's first algorithm. Learn about Regev's variant and new tradeoffs in quantum attacks on CSIDH. Evaluate the implications for safe instances and draw conclusions on the quantum security of this post-quantum cryptographic scheme.

Intro
CSIDH: A Hard Homogeneous Space Key Echange
Key exchange from HHS
CSIDH in practice
CSIDH security
Cryptanalysis principles
Cost model
Implementing the CSIDH oracle
Quantum oracle cost
Hidden shift problem
Labeled qubits (in Z/(2 ))
Combining qubits
Kuperberg's first algorithm [Kup05]
Summary
Use on CSIDH
Regev's variant Reg04
Pipeline of routines
New tradeoffs
Safe instances
Conclusion