TransWikia.com

Paper references on how quantum algorithms have an impact on cryptography?

Quantum Computing Asked by Azhar Hossen on July 20, 2021

Could you please help me in finding some research paper references on the impact of Quantum algorithms on symmetric and asymmetric cryptography ?

Also, I request if I can get some references or notes demonstrating the impact on cryptography with particular algorithms as shown below:

  • Bernstein–Vazirani algorithm
  • Simon’s algorithm
  • Quantum phase estimation algorithm
  • Shor’s algorithm Hidden subgroup problem
  • Grover’s algorithm Quantum counting

One Answer

Disclaimer: I've mainly worked on Symmetric Cryptography. Hence, not only is my answer likely to be incomplete, but an answer concerning assymetric cryptography would be appreciated.

Most of the attacks giving an exponential speedup on symmetric cryptosystems use Simon's algorithm. Such attacks have been observed for instance on:

  • the Even-Mansour scheme (key recovery)
  • the 3-round Feistel scheme (distinguisher)
  • Encrypt-last-block CBC-MAC (EUF-qCMA violation)
  • GMAC (EUF-qCMA violation)

All of these have been summarized/found out in Breaking Symmetric Cryptosystems using Quantum Period Finding. Note that the Bernstein-Vazirani's algorithm can also be used for the first two. Another team from INRIA also studied in depth the impact of QC on Symmetric cryptography. You can read for instance Xavier Bonnetain's PhD, where he studies, amongst many other things, the current state of the art attacks on AES. This has lead to a paper from this team where thy develop a generic framework whose goal is to speedup known attacks using Grover's algorithm. This only gives, in my opinion, quite disappoiting results concerning AES though: these quantum-enhanced attacks only lead to a very small gain when compared with naive bruteforce search using Grover's algorithm, not to mention these attacks target reduced rounds version of AES.

I don't know if this is on point, but Simon's algorithm is also used in (in)security proofs. For instance, it has been used to show that CBC and CFB are not necessarily IND-qCPA secure when used with a block cipher that is not a qPRF. In order to show this, they construct a very specific block cipher which is a PRF but which can be broken using Simon's algorithm.

Concerning hash functions, QC has not been proven really useful for now. The best generic algorithms we know for attacking hash functions are exponential at best (doing barely better than birthday bound). Some interesting work has still been performed to perform attacks that are better than the birthday bound using QC (because of the Grover's algorithm speedup), but it is important to remember that because of the proven optimality of the BHT/Grover's algorithms, the only hope we have for exponential speedups for attacks on hash functions is that we find a flaw in their design that would allow QC to attack them. Needless to say, such a flaw is still to be found for hash functions like SHA-256 or SHA-3.

As a final note, Shor's algorithm for HSP has been considered when designing countermeasures to attacks which use Simon's algorithm, so this might be an interesting article for you. Note however that these countermeasures have some severe drawbacks, as mentioned in Xavier Bonnetain's PhD.

Answered by Tristan Nemoz on July 20, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP