Comments about the article in Nature: Are quantum computers about to break online privacy?

Following is a discussion about this article in Nature Vol 613 12 January 2023, by Davide Castelvecchi
To study the full text select this link: https://www.nature.com/articles/d41586-023-00017-0 In the last paragraph I explain my own opinion.

Contents

Reflection

A new algorithm is probably not efficient enough to crack current encryption keys - but that's no reason for complacency, researchers say.
Picture

A quantum computer at IBM's Thomas J. Watson Research Center in New York.

My interpretation of the picture is that it shows one quantum computer with a control unit. And this four times.
The question is if all four quantum computers are identical and how the quantum logic is handled.

Introduction

A team of researchers in China has unveiled a technique that - theoretically - could crack the most common methods used to ensure digital privacy, using a rudimentary quantum computer.
Quantum Computers in principle nothing to do with privacy. Their advantage should be that they are more powerful.
Still, they warn that the paper, posted late last month on the arXiv repository https://arxiv.org/abs/2212.12372, is a reminder of the vulnerability of online privacy.
Again, in principle QC's have nothing to do with privacy.
Quantum computers are known to be a potential threat to current encryption systems, but the technology is still in its infancy.
That is true, but encryption systems will also change.
Researchers realized in the 1990s that quantum computers could exploit peculiarities of physics to perform tasks that seem to be beyond the reach of ‘classical' computers.
In principle maybe. In practice this can be a different story. Any way when you repeat the same process or calculation, the answer should be the same.
Peter Shor, a mathematician who is now at the Massachusetts Institute of Technology in Cambridge, showed in 1994 how to apply the phenomena of quantum superposition - which describes the ability of atomic-sized objects to exist in a combination of multiple states at the same time - and quantum interference, which is analogous to how waves on a pond can add to each other or cancel each other out, to factoring integer numbers into primes, the integers that cannot be further divided without a remainder.
The physical concepts used are tricky. To claim that a physical system can be in two states simultaneous is doubtful. A cat cannot physical be both alive and dead. A physical system can oscillate continuous between two states called up and down, but that does not mean that the state of that system at any moment is both: up and down.
Shor's algorithm would make a quantum computer exponentially faster than a classical one at cracking an encryption system based on large prime numbers - called Rivest-Shamir-Adleman, or RSA, after the initials of its inventors - as well as some other popular cryptography techniques, which currently protect online privacy and security.
That is only temporary.
But implementing Shor's technique would require a quantum computer much larger than the prototypes that are available. The size of a quantum computer is measured in quantum bits, or qubits. Researchers say it might take one million or more qubits to crack RSA. The largest quantum machine available today - the Osprey chip, announced in November by IBM - has 433 qubits.
That means there is currently no problem. For more information:
https://newsroom.ibm.com/2022-11-09-IBM-Unveils-400-Qubit-Plus-Quantum-Processor-and-Next-Generation-IBM-Quantum-System-Two

1. A fresh approach

Shijie Wei at the Beijing Academy of Quantum Information Sciences and collaborators took a different route to beat RSA, based not on Shor's but on Schnorr's algorithm - a process for factoring integer numbers devised by mathematician Claus Schnorr at Goethe University in Frankfurt, Germany, also in the 1990s. Schnorr's algorithm was designed to run on a classical computer, but Wei's team implemented part of the process on a quantum computer, using a procedure called the quantum approximate optimization algorithm, or QAOA.
See:
In the paper, which has not yet been peer reviewed, the authors claim that their algorithm could break strong RSA keys - numbers with more than 600 decimal digits - using just 372 qubits. In an e-mail to Nature on behalf of all the authors, Guilu Long, a physicist at Tsinghua University in China, cautioned that having many qubits is not enough, and that current quantum machines are still too error-prone to do such a large computation successfully. "Simply increasing the qubit number without reducing the error rate does not help."
That is an important honest comment, which describes the current state-of-art.
Part of the problem is:
Chao-Yang Lu, a physicist who builds quantum computers at the University of Science and Technology of China in Hefei and who was not involved in the project, says that running the QAOA algorithm on such a small machine would require each of the 372 qubits to work without errors 99.9999% of the time. State-of-the-art qubits have barely reached 99.9% accuracy.
One important issue is to what extend the quantum computer actual shows an error indication.
The team demonstrated the technique on a 10-qubit quantum computer to factor the more-manageable, 15-digit number 261,980,999,226,229. (It splits into two primes, as 15,538,213 × 16,860,433.) The researchers say this is the largest number yet to have been factored with the aid of a quantum computer - although it is much smaller than the encryption keys used by modern web browsers.
To perform factoring of the 15-digit number 261,980,999,226,229 on a classical computer, the program "VB2019 FindPrim QC" can be used. The excution time, using 1 processor is about 1500 msec. The period is 130990483413792 and the stop sign = 251446682542022. With 4 processors this time is reduced to 83 msec.
The details of how the algorithm, part of "VB2019 Findprim QC", works, is described in this document. The algorithm is based on Shor's Algorithm. See: Reflection 2 - Factoring the product of two primes.
For more detail read this: VB2019 shor-findprim-QC
The problem is that current testing of this program (identified as phase 1) shows at rare moments an error. The good news is that this error is solved. The solution is described, at this link: findprim_array_x.xls.htm .

2. Controversial paper

The trouble is, no one knows whether the QAOA makes factoring large numbers faster than just running Schnorr's classical algorithm on a laptop. "It should be pointed out that the quantum speedup of the algorithm is unclear," write the authors. In other words, although Shor's algorithm is guaranteed to break encryption efficiently when (and if) a large-enough quantum computer becomes available, the optimization-based technique could run on a much smaller machine, but it might never finish the task.
Yes, but this is speculation
Michele Mosca, a mathematician at the University of Waterloo in Canada, also points out that the QAOA is not the first quantum algorithm known to be able to factor whole numbers using a small number of qubits. He and his collaborators described one in 2017. So researchers already knew that there is nothing fundamental that requires quantum computers to be very large to factor numbers.
To understand this it is important to know what exactly a Qubit is. Also how many Qubits are required store this number: 261980999226229
Other researchers have complained that, although the latest paper could be correct, the caveat regarding speed comes only at the very end of it. "All told, this is one of the most misleading quantum computing papers I've seen in 25 years," blogged quantum-computing theorist Scott Aaronson at the University of Texas at Austin.
No comment.
In his e-mail, Long says that he and his collaborators plan to change the paper and will move the caveat higher up. "We welcome the peer review and the communication with scientists around the world," the statement added.
No comment.
Even if the Schnorr-based technique won't break the Internet, quantum computers could eventually do so by running Shor's algorithm.
Any platform used should be 100% reliable. From a physical point of view, it is a question if Quantum Computers can reach that.
Security researchers have been busy developing a number of alternative cryptographic systems that are seen as less likely to succumb to a quantum attack, called post-quantum or quantum-safe. But researchers might also discover better quantum algorithms in the future that can beat these systems, with calamitous consequences.
In some sense this is pure speculation.
"Confidence in digital infrastructures would collapse," says Mosca. "We'd suddenly switch from managing the quantum-safe migration through technology lifecycle management to crisis management," he adds. "It won't be pretty any way you slice it."
No Comment

Reflection 1 - The future of quantum computers.

IMO the future of Quantum Computers is bleak. Quantum computers use the concept of superposition. For a Qubit that means being at least in two states simultaneous. But what does that mean for a combination of 2 Qubits. When Qubit 1 is simultaneous in two states, at that same instance is then also Qubit 2 simultaneous in two states?
The final question for Quantum Computers is what types of problems can quantum computers solve? Can they be used to play chess? I doubt that.

Reflection 2 - Factoring the product of two primes.

Factoring the product of two prime numbers into its primes sounds difficult and time consuming, but with a little bit of luck it can be done rather easily.
Consider the number 143 which is the product of two primes 11 and 13. In the middle lies the number 12. Remember. 12 + 1 = 13 and 12 - 1 = 11.
Consider the number 143. 143 + 1 = 144. The square root is also 12. Now you understand part of the factoring strategy.

Now a different example: The number 187 which is the product of 11 and 17. In the middle lies the number 14 and 14 + 3 = 17 and 14 - 3 = 11.
Your strategy is calculate the sum of the two prime numbers, divided by 2, because when you know the sum you can calculate the two prime numbers. In this case this is 28/2 =14.
Consider the number 187 which we call n. The next highest square = 196, which is equal to 14^2, and 14 is the value in the middle.

Next we try 11 and 31. n = 11*31 = 341. (pm1+pm2)/2 =21. And 21+10 =31 and 21-10 =11 The next highest square = 361, which is equal to 19^2 but! 19 is not the value in the middle. So finally, this strategy is not correct. Let us follow a slightly different strategy.

  1. First calculate (n+1)/2 which is (187 + 1) / 2 = 188/2 = 94.
  2. Next calculate square root of n = 187. This is 13, rest = 187-169= 18.
  3. Next calculate a max which is the difference of these two numbers. 94 - 13 = 81
    It is important that all these calculations are a function of n and don't involve the two prime numbers,
  4. You subtract 1 (This value will be explained below) and you get the periodicity 80
To understand we are going to calculate the function x^a mod n with x = 2, or 2^a mod 187. a goes from 1 to approximate 84 and higher. This are the results: 
       X                                                       
xn  1  2  4  8 16 32 64 128 69 138 89 178 169 151 115 43 86 172 157 127 67 134 81 162 137 87 174 161 135 83 166 145 103 19 38 76 152 117 47 94
 a  0  1  2  3  4  5  6   7  8   9 10  11  12  13  14 15 16  17  18  19 20  21 22  23  24 25  26  27  28 29  30  31  32 33 34 35  36  37 38 39
      amin                                                            

xn  1  2  4  8 16 32 64 128 69 138 89 178 169 151 115 43 86 172 157 127 67 134 81 162 137 87 174 161 135 83 166 145 103 19 38 76 152 117 47 94
 a 40 41 42 43 44 45 46  47 48  49 50  51  52  53  54 55 56  57  58  59 60  61 62  63  64 65  66  67  68 69  70  71  72 73 74 75  76  77 78 79

       X
xn  1  2  4  8 16                                                                 
 a 80 81 82 83 84 
     amax
                                                                       Table 1
The above figure shows a repetition of two lines. The bottom line is the value a going from 0 to 84. The top line is the value xn, the function 2^a mod 187. At position a = 39, xn = 94. At position a = 40, xn = 1. The reason is that 2 * 94 - 187 = 1
5) At position a = 81, xn = 2. The value 81 corresponds with amax, as indicated in step 3 above. The value 2 is called the stop sign
6) At position a = 1, xn = 2. The value 2 is called the stop sign. The value 1 is called amin
See below how amin is calculated
7) In step 2 the square root of n=187 is calculated, which is 13.
13 + amin = 13 + 1 = 14, which is (pm1+pm2)/2.
8) Now we know pm1 * pm2 and (pm1 + pm2) which makes the route to victory open.

Step 5 in this strategy is the most difficult. This involves to calculate 2^amax mod 187 to calculate the stop sign 2.
Step 6 involves the same strategy in reverse order. Here your target is the stop sign, while using the function 2^a mod n, for a very small numbers of a to calculate amin. In fact, this is the most time consuming part. 

     pm1      pm2        n              (n+1)/2       sqr(n)   amax    stopsign  amin   period   (pm1+pm2)/2
      11       17       187                94           13       81        2        1       80        14
      11       31       341               171           18      153        8        3      150        21
      79      139     10823              5412          104     5308       16        4     5304       108
 3347843  3674639   12302114453677   6151057226839    3507437                      3804            3511241      103 msec
15538213 16860433  261980999226229  130990499613115  16185827                     13496            16199323     102 msec
36746137 85478221 3140994419382277 1570497209691139  56044575                   5067604            61112179    4800 msec
                                                                      Table 2
The above table 2 shows results of factorization of 6 combinations of pm1 and pm2.

Reflection 2.1 - Factoring the product of two primes. Part 2

Factoring the product of two primes mainly involves two parameters amax and amin.
  1. amax (column 6) is a function of n (=pm1*pm2) and is the difference between (n+1)/2 and sqr(n)
  2. amin (column 8) is explained in Table 1 and requires the calculation of the stopsign. See below.
  3. period (column 9) is equal to amax - amin
  4. (pm1+pm2)/2 (column 10) is equal to sqr(n) + amin.
  5. Now you have both pm1+pm2 and pm1*pm2. pm1 and pm2 are now easy to calculate.
In order to calculate the stop sign, you have to perform the function f(a,x,n) = x^a mod n for a = amax and x=2. That means you have to calculate f(a,x,n) = 2^amax mod n.
This involves very large numbers. To get an idea 2^10= 10^3, 2^20=10^6, 2^40= 10^12, 2^80=10^24
To keep the numbers smaller you can also the function in a loop with f(a,x,n) = f(a-1,x,n) * f(a-1,x,n) mod n, with a going from 1 to amax.
In any case the integer numbers become large. To solve that for large numbers, requires to use arrays. This in turn requires integer array functionality, which means: add array, subtract array, multiply array and divide array.

To calculate amin more or less goes in reverse order. In this case the stop sign is known, which is the value of the function f(a,x,n).
Now you have to calculate the smallest value of a which as result shows the stop sign. You start with a=1 etc.
However in this case you can use the multiprocessor capability of your PC. Suppose there are 4 multiprocessors or PPs. In this case PP1 can calculate: a from 1 to 1000, PP2 a from 1001 to 2000, PP3 a from 2001 to 3000 and PP4 a from 3001 to 4000.

The most important conclusion is that this always works for any combination of prime numbers, without any error !.
For more detail read these documents:
  1. shor Shor's algorithm in 6 steps.
  2. VB2019 shor-findprim-QC Explains Parallel Processing

Reflection 3 - Some thoughts about privacy

The impression of the article in Nature is that to protect our privacy a Quantum Computer is a must. More or less all our data should be encrypted, which requires a Quantum Computer and when that is the case our privacy is quaranteed. This is true for all the documents which mention my name related to all governmental, law, medical, financial, educational and insurance issues.
At the same if we want to read anything available on the internet we have to accept all cookies, other wise, as claimed, internet does not work
At the same name in order to protect us, we need a multitude of passwords, which should be strong.

What is the issue.
Generally speaking I am the only one who uses my PC, as such my PC does not require a password.
However my PC is connected to the outside world, via the Internet, and I want to maintain that capability. However under certain strict rules.
Via the Internet I want to send and receive e-mails, but here also under strict rules.
The first rule is that in general all communication goes via text messages.
The second rule is that in general no one is allowed to make any modification on my PC. That means in short: No cookies.
The exceptions are trusted links. Those trusted links are those required to update the installed software.

This raises the following question: Is there any reason why communication should be encrypted? What is it that I want to hide? Who wants to send me secret information?
That does not mean that certain organizations, for their internal operations, use secret information, but in general most communication is not. The issue is much more how do these organizations, that require secrecy, handle this secrecy internally.

If you want to give a comment you can use the following form Comment form

Created: 25 February 2023
Updated: 19 April 2023
Updated: 19 May 2023

Back to my home page Index
Back to Nature comments Nature Index