5.1 Shor 'Nuff

(See the top of this set of postings.)

Obviously, the main thing we're talking about here is Shor's algorithm.  I have not been privy to the conversations of cryptographers in creating post-quantum crypto, though we'll take a short look at that below.  But there are very few people in the world who understand better than I do what it takes to actually run the full version of Shor's algorithm on a potentially real machine.

A full implementation of Shor's algorithm consists of two quantum phases: modular exponentiation, followed by the quantum Fourier transform.  (I'm assuming you're familiar with the main ideas behind Shor, how it uses interference to build patterns in the quantum register that can reveal the period of a function that allows us to find the factors of a large semi-prime number.)

The key insight may be the behavior of the QFT, but the bulk of the execution time will be in the modular exponentiation phase.  This is actually one of the areas that I worked on in my Ph.D. thesis.

https://arxiv.org/abs/quant-ph/0607065

Some of the important parts of this were published in Physical Review A.

In my thesis there is a plot that I think is useful, which we updated and published in our Communications of the ACM article:

https://m-cacm.acm.org/magazines/2013/10/168172-a-blueprint-for-building-a-quantum-computer/fulltext

We worked out detailed performance estimates, including hardware requirements and quantum error correction, in some of our papers:

https://journals.aps.org/prx/abstract/10.1103/PhysRevX.2.031007

and

https://www.worldscientific.com/doi/abs/10.1142/S0219749910006435

https://arxiv.org/abs/0906.2686

There were other, contemporary important papers on how to implement Shor, including Fowler et al.,  https://arxiv.org/abs/quant-ph/0402196 who discussed Shor on a linear array, a few months ahead of my own Phys. Rev. A paper on the same topic.

We both built on important, early work by Vedral, Barenco and Ekert (VBE) and by Beckman, Chari, Devabhaktuni and Preskill (BCDP).

https://arxiv.org/abs/quant-ph/9511018

https://journals.aps.org/pra/abstract/10.1103/PhysRevA.54.147

https://arxiv.org/abs/quant-ph/9602016

https://journals.aps.org/pra/abstract/10.1103/PhysRevA.54.1034

If you are looking to broaden your reading on implementations of Shor’s algorithm, the following are useful:

Pavlidis and Gizopoulous found an efficient division algorithm, accelerating the math.

https://arxiv.org/abs/1207.0511

https://dl.acm.org/citation.cfm?id=2638682.2638690

Roetteler, Steinwandt focused on the applicability of Shor's algorithm to elliptic curve. I like the paper, except I think their survey of related research could have been better.

https://arxiv.org/abs/1306.1161

and Roetteler, Naehrig, Svore, Lauter:

https://arxiv.org/abs/1706.06752

Gidney and Ekera submitted to the arXiv a paper on factoring a 2048-bit number using 20 million noisy quibits.  In this paper, one of their techniques is arithmetic "windowing" which is essentially identical to one of the techniques I proposed in my 2005 Phys. Rev. A paper.  https://arxiv.org/abs/1905.09749

May and Schliper also recently uploaded a paper on period finding with a single qubit.

https://arxiv.org/abs/1905.10074

Ekeraa and Hastad also proposed a new period-finding algorithm variant, in 2017.

https://link.springer.com/chapter/10.1007/978-3-319-59879-6_20

https://arxiv.org/abs/1702.00249

Smolin, Smith, Vargo wrote something of a warning about inferring too much from very simple demonstrations on a few qubits.

https://www.nature.com/articles/nature12290

Here is one early paper on how to assess errors in Shor’s algorithm, by Miquel, Paz and Perazzo:

https://arxiv.org/abs/quant-ph/9601021

https://journals.aps.org/pra/abstract/10.1103/PhysRevA.54.2605

Chuang et al., also published an early examination of decoherence in factoring.

https://science.sciencemag.org/content/270/5242/1633

Among random things, there is Dridi and Alghassi, factoring on D-Wave; I don’t think this paper tells us very much about factoring at scale.

https://www.nature.com/articles/srep43048

That's more than enough for now, since it isn't really the focus of what we're after here, anyway.

5. Attacking classical cryptography using quantum computers

Naturally, my own interest in writing these notes stems from my experience in quantum computing and quantum networking.  The previous sections dealt primarily with classical attacks, with a little bit of quantum networking can be integrated with classical thrown into each section.  Here, let's look at the attacks on classical cryptography using quantum computers.

4.5 Notes & References

To be filled in eventually.

4.4 TLS and QKD

Alan Mink, Sheila Frankel and Ray Perlner worked on integrating TLS with QKD, a full decade ago.

https://arxiv.org/abs/1004.0605

4.3 Other Attacks on TLS

One startling and potentially useful document is RFC7457, "Summarizing Known Attacks on Transport Layer Security (TLS) and Datagram TLS (DTLS)".  It details a couple of dozen attacks on TLS, most having to do with protocol implementation issues such as failing to correctly verify all of the information you are given.  Some of them leak information or allow a connection to be take over, others allow an attacker to downgrade the security negotiation so that a later attack on the cipher has a higher chance of success.

One attack this RFC points out is http://www.openssl./~bodo/tls-cbc.txt, which (among other things) describes a flaw in how TLS Record Protocol records are concatenated. Originally, TLS kept the ciphertext of the last block of a record to use as the initialization vector (IV) of the first block of a new record, but this allows an attacker who can adaptively choose plaintexts to more completely choose the text being encrypted.  The fix is straightforward (toss in an extra block of nonsense data before starting the new record), and current versions of TLS aren't vulnerable.

4.2 Keying and Rekeying

(To be filled in.)

<>

<sure that an attacker can't cause a downgrade of security relative to
what both ends really want.>>

<>

4.1 TLS Records and Basic Limits

TLS consists of one primary protocol: the TLS Record Protocol.  On top of the TLS Record Protocol sit four protocols, one of which (the application data protocol) is used for the bulk data encryption, and the TLS Handshake Protocol, which utilizes public key cryptography to establish identity, securely creates a shared secret to be used for the bulk data encryption, and makes sure that this part of the process can't be modified by an attacker.  A third one of interest to us is the change cipher spec protocol.

A record in the record layer has a maximum size of 16KB ($2^{14}$).

There is, as best I can tell, no official limit on the key lifetime or on the number of bytes that can be pushed through a single TLS except the limit on record sequence numbers of $2^{64}-1$.  Combined with the max record size, that's $2^{78}$ bytes, or 256 exabytes, which is a bloody lot of data.  So, if the lifetime of a session needs to be limited, it has to be done by breaking the connection and renegotiating. Apparently, adding a key renegotiate feature was considered for TLS 1.3, but doesn't seem to have been included.

Luykx and Paterson wrote up a short (8 page) summary recommending limits for TLS with different cryptosystems. (My copy is dated Aug. 2017, but the paper was referred to in Apr. 2016.) http://www.isg.rhul.ac.uk/~kp/TLS-AEbounds.pdf
Unfortunately, that paper has good references but doesn't go through the complete reasoning, so going one level deeper in the reading is really necessary.

In April 2016, Mozilla moved to limit the length of a connection, based on those results:
https://bugzilla.mozilla.org/show_bug.cgi?id=1268745
They set AES-CBC to about $2^{34.5}$, or about 24 billion records, about 400 terabytes max.  That should give a probability of $2^{-57}$ of "ciphertext integrity [being] breached", though I'm a little unclear on exactly what that means here -- is this just birthday bound leaking some plaintext, or is this compromise of the entire session key? Figuring that out will take more digging, since they express things differently than most of the resources I used above.

4. TLS/SSL and cryptography

(Back to the top of this sequence of postings.)

Here we want to answer the same three questions we had above about IPSec:

1. What are the technical mechanisms in place for rekeying and effective use of encryption?
2. What was known, at the time these protocols were developed, about the best practices for rekeying?
3. What are best practices today?

but this section will be much shorter, as I know so much less about TLS (despite the fact that it is the most important use of encryption on the Internet today).

The current standard for Transport Layer Security, or TLS, is RFC8446, published in 2018.  It specifies version 1.3 of the protocol.  The main document itself is only 160 pages, not bad for something so complex and important.

...oh, what is TLS?  It's the protocol that HTTPS runs over.  It's the successor to SSL, the Secure Sockets Layer, which was the first way to encrypt web browsing.  TLS originally built on top of a reliable transport protocol, such as TCP, though a later adaptation (RFC6347) lets it run over a datagram protocol.  We'll only worry about running it over TCP here.  TLS provides privacy, by encrypting all of your web browsing traffic for a particular connection.  It also provides data integrity, using a MAC (message authentication code) when necessary. (IPsec also does both, but we ignored that above.)

3.5 Notes & References

To be filled in eventually.