Les Bell

Welcome to today's daily briefing on security news relevant to our CISSP (and other) courses. Links within stories may lead to further details in the course notes of some of our courses, and will only be accessible if you are enrolled in the corresponding course - this is a shallow ploy to encourage ongoing study. However, each item ends with a link to the original source.

News Stories

New Scheme Could Improve on Shor's Algorithm

Back in the mid-1990's, mathematician Peter Shor came up with an algorithm for factoring composite numbers much faster than was possible with previous methods. This would, of course, break the RSA public-key cryptosystem, which relies upon the difficulty of factoring large composite numbers; in fact, the RSA key-generation algorithm starts by generating two large probably-prime numbers, \(p\) and \(q\), and then multiplying them to create a modulus, \(N\), which forms part of the public key and is therefore known to any attacker. If an attacker can quickly figure out \(p\) and \(q\) by factoring \(N\), it's game over, and they can easily derive the private key. And since RSA is widely used for exchange of the secret session keys used by symmetric cryptoprimitives like AES, this would break a lot of Internet communications.

But there's one problem: Shor's algorithm specifically needs a quantum computer to run. Specifically, it uses a quantum circuit to effectively perform a Fourier transform, in order to find the period of a function; a function is said to be periodic when it repeatedly returns the same value as the input value is incremented - something that must happen when performing the modular arithmetic that underlies public-key cryptograpy (remember, \(N\) is a modulus).

To date, the development of quantum computers has been beset by difficulties, such as noise causing errors in the calculation, which have only gradually been overcome by a variety of techniques, such as using additional qubits (quantum bits) for error correction. To date, only relatively small numbers have been factored; for example, the factoring of 143 (11 x 13) using a 4-qubit nuclear magnetic resonance quantum computer in 2012 was considered quite a breakthrough, although later analysis, by other researchers, of the raw data they released indicated that they had simultaneously factored several much large numbers such as 3,599, 11,663 and 56, 153.

As of early 2023, the largest number to be factored using quantum computing is the 48-bit number 261980999226229, which still falls well short of the 2048-bit (617 decimal digit) moduli commonly used for RSA keys today, which by some estimates would require a quantum computer with 20 million qubits.

However, a new variant of Shor's algorithm, developed by NYU computer scientist Oded Regev, massively reduces the number of quantum operations required to factor a number. Ironically, Regev based his technique in what he had learned while trying to find attacks on the lattice-based algorithms and learning-with-errors algorithms which provide one approach to post-quantum, or quantum-resistant, cryptography.

A lattice is a multi-dimensional vector space with integer coordinates; you could think about the integers modulo \N\) as being a one-dimensional lattice, and the fourier transform stage of Shor's algorithm effectively amounts to finding the shortest vector - the period of the function - in that one-dimensional lattice. The post-quantum algorithms, such as NTRU, are based on a similar shortest vector problem, only in a space with hundreds of dimensions, which makes the problem intractably hard - including, it is believed, for quantum computers.

What Regev did was to start by generalizing the algorithm from one dimension to, first two dimensions, and ultimately many dimensions. Rather than repeatedly multiplying a single number, \(g\) with itself, he would try two numbers, \(g_1\) and \(g_2\) and repeatedly mutliply them with themselves and each other in a two-dimensional space, and then \(g_1, g_2, \ldots, g_n\) in an \(n\)-dimensional space. The problem was that although each \(g_i\) did not need to be multiplied as many times, this needed to be repeated for \(n\) different \(g_i\)'s, providing no advantage over Shor's original algorithm.

But musing while waiting for a lift one morning, the solution struck him - with a small number of dimensions, the numbers involved were large, so the algorithm could not benefit from the speedup of multiplying small numbers, but with a large number of dimensions, the quantum part was fast, but the remaining calculations, which have to be performed using a classical computer, required solving a very hard lattice problem. The trick is to find a sweet spot between these two extremes, modifying the algorithm to make it run fast in just a relatively small number of dimensions.

The result is a significant improvement; while Shor's algorithm for factoring an \(n\)-bit number requires \(\tilde{O}(n^2)\) qubits, Regev's requires only \(\tilde{O}(n^{3/2})\).

But wait - there's more. Just two weeks ago, Seyoon Ragavan and Vinod Vaikuntanathan at MIT published a further refinement of Regev's algorithm which reduces the number of qubits required to \(\tilde{O}(n \log{n})\) qubits.

If these results are correct, this makes quantum factorization of RSA keys closer than ever before, and the need for crypographic agility and the replacement of RSA, etc. with post-quantum algorithms more urgent than ever.

Brubaker, Ben, Thirty Years Later, a Speed Boost for Quantum Factoring, Quanta Magazine, 17 October 2023. Available online at https://www.quantamagazine.org/thirty-years-later-a-speed-boost-for-quantum-factoring-20231017/.

Ragavan, Seyoon, and Vinod Vaikuntanathan, Optimizing Space in Regev’s Factoring Algorithm, arXiv preprint, 2 October 2023. Available online at https://arxiv.org/abs/2310.00899.

Regev, Oded, An Efficient Quantum Factoring Algorithm, arXiv preprint, 17 August 2023. Available online at https://arxiv.org/abs/2308.06572.

Upcoming Courses

• SE221 CISSP Fast Track Review, Virtual/Online, 13 - 17 November 2023
• SE221 CISSP Fast Track Review, Sydney, 4 - 8 December 2023
• SE221 CISSP Fast Track Review, Sydney, 11 - 15 March 2024
• SE221 CISSP Fast Track Review, Virtual/Online, 13 - 17 May 2024
• SE221 CISSP Fast Track Review, Virtual/Online, 17 - 21 June 2024
• SE221 CISSP Fast Track Review, Sydney, 22 - 26 July 2024
  

These news brief blog articles are collected at https://www.lesbell.com.au/blog/index.php?courseid=1. If you would prefer an RSS feed for your reader, the feed can be found at https://www.lesbell.com.au/rss/file.php/1/dd977d83ae51998b0b79799c822ac0a1/blog/user/3/rss.xml.

Copyright to linked articles is held by their individual authors or publishers. Our commentary is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License and is labeled TLP:CLEAR.