Event
Vlad Gheorghiu, Institute for Quantum Computing,University of Waterloo
Thursday, November 23, 2017 15:30to16:30
Room 3195, Pav. André-Aisenstadt, CA
Quantum Resource Estimation for Quantum Cryptanalysis (or why do constants in Ohs and Omegas matter)
Quantum computers pose a serious threat to modern cryptography: they weaken symmetric cryptography and totally break the public-key cryptography based on factoring and discrete-log. The most cryptographically relevant quantum algorithms are Grover’s searching algorithm (quadratically faster than any classical brute force searching scheme) and Shor’s factoring algorithm (exponentially faster than the best known classical factoring algorithm - the number sieve). In this talk I will describe how feasible is to run those algorithms (or variants of them) on a realistic quantum architecture, taking fault-tolerance into account, and quantify the resources (time and number of qubits) required to run them. I will show that the overhead introduced by the need for quantum error correction is significant, and has to be taken into account when analyzing the security of cryptographic schemes against quantum adversaries.
Café-biscuits à 15h
Café-biscuits à 15h