The do's and don'ts of quantum memory in cryptanalysis
<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...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | English |
| Published: |
2023
|
| Subjects: |
| _version_ | 1824458651416395776 |
|---|---|
| author | Jaques, S |
| author2 | Benjamin, S |
| author_facet | Benjamin, S Jaques, S |
| author_sort | Jaques, S |
| collection | OXFORD |
| description | <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> |
| first_indexed | 2024-03-07T08:19:29Z |
| format | Thesis |
| id | oxford-uuid:fd1412a1-2229-4b48-bbbe-95d03c79ba00 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2025-02-19T04:29:17Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | oxford-uuid:fd1412a1-2229-4b48-bbbe-95d03c79ba002024-12-12T07:58:28ZThe do's and don'ts of quantum memory in cryptanalysisThesishttp://purl.org/coar/resource_type/c_db06uuid:fd1412a1-2229-4b48-bbbe-95d03c79ba00cryptographyquantum computingEnglishHyrax Deposit2023Jaques, SBenjamin, SPetit, C<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> |
| spellingShingle | cryptography quantum computing Jaques, S The do's and don'ts of quantum memory in cryptanalysis |
| title | The do's and don'ts of quantum memory in cryptanalysis |
| title_full | The do's and don'ts of quantum memory in cryptanalysis |
| title_fullStr | The do's and don'ts of quantum memory in cryptanalysis |
| title_full_unstemmed | The do's and don'ts of quantum memory in cryptanalysis |
| title_short | The do's and don'ts of quantum memory in cryptanalysis |
| title_sort | do s and don ts of quantum memory in cryptanalysis |
| topic | cryptography quantum computing |
| work_keys_str_mv | AT jaquess thedosanddontsofquantummemoryincryptanalysis AT jaquess dosanddontsofquantummemoryincryptanalysis |