Quantum Cost Models for Cryptanalysis of Isogenies

quantum computation;cryptanalysis;isogenies

Jaques, Samueladvisor:Mosca, Michele ; advisor:Menezes, Alfred ; affiliation1:Faculty of Mathematics ; Menezes, Alfred ; Mosca, Michele ;

University of Waterloo

关键词: Master Thesis;    cryptanalysis;    quantum computation;    isogenies;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/14612/1/Jaques_Samuel.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

Isogeny-based cryptography uses keys large enough to resist a far-future attack fromTani’s algorithm, a quantum random walk on Johnson graphs. The key size is based on ananalysis in the query model. Queries do not reflect the full cost of an algorithm, and thisthesis considers other cost models. These models fit in a memory peripheral framework,which focuses on the classical control costs of a quantum computer. Rather than queries,we use the costs of individual gates, error correction, and latency. Primarily, these costsmake quantum memory access expensive and thus Tani’s memory-intensive algorithm isno longer the best attack against isogeny-based cryptography. A classical algorithm due tovan Oorschot and Wiener can be faster and cheaper, depending on the model used and theavailability of time and hardware. This means that isogeny-based cryptography is moresecure than previously thought.