Cryptanalysis of Symmetric Ciphers in the Quantum Realm

Abstract

This thesis proposes a biclique attack on AES-128, with Grover’s algorithm serving as a superior search method. Bogdanov et al. previously devised and presented a classical version of such an AES-128 biclique attack at ASIACRYPT 2011. They demonstrated that with a biclique of dimension 2^{8} and length three, and 2^{112} base keys, one may mount the attack in the classical domain. This is because there was only one base key group holding the master key; therefore, a partition was created over the whole keyspace to help with the search. Thus, the time complexity is 2^{126.18}. In contrast, the quantum paradigm allows us to simultaneously superimpose all 2^{128} keys and input them to the Oracle. Using the Grover search method and simultaneous computation of independent differences, We were able to reduce the complexity of the biclique key search to 2^{64}, outperforming Grassl et al.’s attack by a factor of four. Resource estimates for the full attack were also supplied as proof of concept.