| Summary: | <p>This thesis refines the estimates of the costs to attack three different cryptographic
problems. To get there, I first survey some fundamental issues in quantum computing.
This narrows the scope of the capabilities of quantum computers and the engineering
costs to build and run them. I then focus on “QRAM”, a type of quantum memory.
The question with QRAM is whether quantum computers could cheaply access
memory in superposition. I argue that they could not, and that quantum computers
must pay a steep price to access memory.</p>
<p>I then analyse circuits to attack elliptic curve cryptography with Shor’s algo-
rithm. I find that even expensive QRAM improves these circuits. Next I provide
some optimisations and parallelisation strategies for Kuperberg’s algorithm. This
algorithm can attack “CSIDH”, a type of post-quantum cryptography. Again
QRAM is an effective tool: huge classical co-processing costs offset the expense
of each quantum memory access. Finally I provide an algorithm for the golden
collision problem, a generalisation of “meet-in-the-middle” attacks. If stable, error-
free memory exists, then this algorithm could acheive an exponential advantage
in total cost. However, the run-time of this algorithm is too high, so I show a
more effective use of massive arrays of quantum hardware. This second algorithm
has a higher cost but parallelises nearly perfectly.</p>
|
|---|