Quantum Cryptanalysis
summary
Presents two concrete results: a quantum FLT-based inversion framework that lets inversion follow arbitrary addition chains and yields a Basic algorithm and Extended algorithm which cut resource costs — e.g., for n=571 Basic uses 74% of PWLK’s qubits and 94% of its CNOTs, Extended uses 80% of BBHL’s CNOTs and 82% of its depth — by choosing addition chains with fewer doubled terms; and a rigorous ECVRF analysis that defines non-malleability, proves (strong) non-malleability under DDH in the ROM, proves binding from collision resistance, and shows full uniqueness in the QROM via relative indifferentiability.
AI-written summary · about
chapters (16)
- 0:00Introduction
- 1:10Quantum attacks on ECDLP
- 3:01Binary elliptic curves basics
- 6:24FLT-based inversion overview
- 8:31PWLK FLT algorithm details
- 15:40Basic algorithm concept
- 17:32General Basic algorithm
- 20:51BBHL FLT and Extended algorithm
- 21:38Quantum resource comparison
- 23:27Detailed results for n=163
- 23:49Q&A session
- 26:01Introduction to ECVRF
- 31:48ECVRF security gaps
- 36:38Non-malleability of ECVRF
- 41:44Quantum uniqueness analysis
- 46:25Summary and conclusions
