Wednesday, February 1, 2023
HomeCyber SecurityPost-quantum cryptography – new algorithm “gone in 60 minutes” – Naked Security

Post-quantum cryptography – new algorithm “gone in 60 minutes” – Naked Security


We’ve written about PQC, short for post-quantum cryptography, several times before.

In case you’ve missed all the media excitement of the past few years about so-called quantum computing…

…it is (if you will pardon what some experts will probably consider a reckless oversimplification) a way of building computing devices that can keep track of multiple possible outcomes of a calculation at the same time.

With a lot of care, and perhaps a bit of luck, this means that you can rewrite some types of algorithm to home in on the right answer, or at least correctly discard a whole slew of wrong answers, without trying and testing every possible outcome one-by-one.

Two interesting cryptanalytical speedups are possible using a quantum computing device, assuming a suitably powerful and reliable one can actually be constructed:

  • Grover’s quantum search algorithm. Usually, if you want to search a randomly-ordered set of answers to see if yours is on the list, you would expect to plough through entire list, at worst, before getting a definitive answer. For example, if you wanted to find the 128-bit AES decryption key to unscramble a document, you’d need to search the list of all possible keys, starting at 000..001, ..2, ..3, and so on, all the way up to FFF..FFF (16 bytes’ worth of FF), to be certain of completing the problem. In other words, you’ve have to budget to try all 2128 possible keys before either finding the right key, or determining that there wasn’t one. Grover’s algorithm, however, given a big and powerful enough quantum computer, claims to be able to complete the same feat with the square root of the usual effort, thus cracking the code, in theory, in just 264 tries instead.
  • Shor’s quantum factorisation algorithm. Several contemporary encryption algorithms rely on the fact that multiplying two large prime numbers together can be done quickly, whereas dividing their product back into the two numbers that you started with is as good as impossible. To get a feel for this, try multiplying 59×87 using pen-and-paper. It might take a minute or so to get it out (5133 is the answer), but it’s not that hard. Now try the other way. Divide, say, 4171 back into its two factors. Much harder! (It’s 43×97.) Now imagine doing this with a number that’s 600 digits long. Loosely speaking, you’re stuck with trying to divide the 600 digit number by every possible 300 digit prime number until you hit the jackpot, or find there isn’t an answer. Shor’s algorithm, however, promises to solve this problem with the logarithm of the usual effort. Thus factoring a number of 2048 binary digits should take just twice as long as factoring a 1024-bit number, not twice as long as factoring a 2047-bit number, representing a huge speedup.


Please enter your comment!
Please enter your name here

Most Popular

Recent Comments