Cryptanalysis

An adversary armed with a quantum computer has algorithms[66, 33, 34] at their disposal, which are capable of breaking our current methods of encryption. Even with the birth of post-quantum cryptography[52, 62, 61], some of best cryptanalytic algorithms are still quantum [45, 8]. This thesis contains several experiments on the efficacy of lattice reduction algorithms, BKZ and LLL. In particular, the difficulty of solving Learning With Errors is assessed by reducing the problem to an instance of the Unique Shortest Vector Problem. The results are used to predict the behavior these algorithms may have on actual cryptographic schemes with security based on hard lattice problems. Lattice reduction algorithms require several floating-point operations including multiplication. In this thesis, I consider the resource requirements of a quantum circuit designed to simulate floating-point multiplication with high precision.

Quantum computers and quantum computing is a reality of the near feature. Companies
such as Google and IBM have already declared they have built a quantum computer
and tend to increase their size and capacity moving forward. Quantum computers have
the ability to be exponentially more powerful than classical computers today. With this
power modeling behavior of atoms or chemical reactions in unusual conditions, improving
weather forecasts and traffic conditions become possible. Also, their ability to exponentially
speed up some computations makes the security of todays data and items a major
concern and interest. In the area of cryptography, some encryption schemes (such as RSA)
are already deemed broken by the onset of quantum computing. Some encryption algorithms
have already been created to be quantum secure and still more are being created
each day. While these algorithms in use today are considered quantum-safe not much is
known of what a quantum attack would look like on these algorithms. Specifically, this
paper discusses how many quantum bits, quantum gates and even the depth of these gates
that would be needed for such an attack. The research below was completed to shed light
on these areas and offer some concrete numbers of such an attack.