15461

Video URL

https://simons.berkeley.edu/talks/overview-attacks-code-based-public-key-cryptography-and-recent-re…

Recent Results on Attacking Hashed Periodic Functions

(2020). Recent Results on Attacking Hashed Periodic Functions. The Simons Institute for the Theory of Computing. https://simons.berkeley.edu/talks/overview-attacks-code-based-public-key-cryptography-and-recent-results-attacking-hashed

Recent Results on Attacking Hashed Periodic Functions. The Simons Institute for the Theory of Computing, Feb. 24, 2020, https://simons.berkeley.edu/talks/overview-attacks-code-based-public-key-cryptography-and-recent-results-attacking-hashed 

          @misc{ scivideos_15461,
            doi = {},
            url = {https://simons.berkeley.edu/talks/overview-attacks-code-based-public-key-cryptography-and-recent-results-attacking-hashed},
            author = {},
            keywords = {},
            language = {en},
            title = {Recent Results on Attacking Hashed Periodic Functions},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2020},
            month = {feb},
            note = {15461 see, \url{https://scivideos.org/index.php/Simons-Institute/15461}}
          }
Alexander May, Ruhr-Universität Bochum
Talk number15461
Source RepositorySimons Institute
Subject

Abstract

(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.