Spring 2020

Recent Results on Attacking Hashed Periodic Functions

Monday, Feb. 24, 2020 9:45 am10:15 am

Add to Calendar


Calvin Lab Auditorium

(joint work with Lars Schlieper and Jonathan Schwinger)

In the first part of the talk we show that quantum period finding algorithms like Simon and Shor (variants) are surprisingly robust under compression. This implies that in some cryptanalytic relevant cases we can significantly decrease the required number of qubits at the cost of only few more measurements.

In the second part we consider the error robustness of Simon period finding on noisy quantum devices, by running experiments on IBMQ-16. We show that our IBMQ-16 data can be tranformed into a problem that is equivalent to LPN. Nevertheless, we achieve quantum speedups for noisy quantum devices even for large error rates.

PDF icon lsn.pdf399.4 KB
PDF icon compression.pdf396.77 KB