IBM Q , alias: say hello to cryptography? What is true, and what is not.

Just in case this news was not that popular to reach the mainstream magazines, IBM decided to enter (or better, to create) the market for quantum computers. Up to now, quantum computers were only used by entities (google, NASA, and so on) which where able to build one by themselves. There was no "standard" neither a SDK, with the only exception of D-Wave , which was the only well known company to allow a public access to their quantum computer.

If you are interested to buy one: https://www.dwavesys.com/ 

Now also IBM entered the market, which means "created a market" where there is competition. (which is a requirement to say "market", in my opinion). 

I've heard lot of people afraid of the "end of encryption", talking about "crypto apocalypse". The moment no encryption may protect you. Is it true? Is it false? 

Let's first understand what people fears more of Quantum Computing:

• There seems to be no Moore 's Law : the power of that computer is not scaling in time  as we were used with silicon ones. This means , the power of those computers are still not growing to follow up growing demand. (here some timelines: https://en.wikipedia.org/wiki/Timeline_of_quantum_computing ) .
• There price is very high: which means , is very unlikely a common person may buy one, and it will keep like that.
• The price is decreasing at a very slow rate. Compared with the first machines there was a decrease, but the decrease in price was not as high as it was, by example, when  "Personal" computers first appeared.

While we could imagine, sooner or later, a personal quantum computer would be possible, it is quite likely for the next 10 years this will technology will only be available to governments and huge corporations. Which is an issue , because of cryptography.

The concept of cryptography today is that, given a problem about number theory, your personal computer (or personal device) is able to encrypt in a way that, given the proportions, government and huge corporations cannot break it.

This requires some ratio between the power of the computer which is encrypting , and the one which is attacking your encryption. Having both system based on silicon meant , more or less, using a key with a sufficient size, it was more or less impossible, or almost too expensive, for an attacker to deploy enough power to decrypt your content.

This was due , most of time, to the fact the user's device was made (more or less) of the same technology the attacker's device is made: what the attacker can do is to stack computers which are more or less similar to the user's one, so that, the complexity of the problem translates in the amount of computers - the same power of the user's one - the attacker needed.

Now, with quantum computer we have an issue. A big issue.

• The user cannot use a quantum computer for encryption. 
• The government may deploy one for decryption.

The ratio between the amount of power the user may use to encrypt and the one the attacker may deploy to decrypt is now sliding, at the pure advantage of the attacker. 

How much is true, and how much is not in this statement?

Well, dependy by the algorithm used for encryption. This is because  a quantum computing system is not to be seen as a parallel system, just because  a qbit may have lot of values in the "uncertain" phase. It is just not like that. So what about encryption? 

Let's take the example or RSA. RSA relies a lot into the difficulty of computing prime numbers in a  large scale, (plus giving some hope in the Riemann's Zeta function conjecture). In such a case is true: Shor's algorithm can factor numbers exponentially faster than any known classical algorithm.  That is, if a quantum computer can break a 128-bit RSA encryption in one second, it only takes maybe a few seconds to break a 256-bit key.  Whereas if a classical computer, using available factoring algorithms, can break a 128-bit key in one second, don't even think about trying to break a 256-bit key.

 If the encryption scheme is not RSA, then quantum computing can still help, but probably not as dramatically.  If, for example, a private key is used, you might try to break the code by brute force, trying each key.  For N possible keys, the time for this scales like N.  In this case, Grover's algorithm can be applied if you have a quantum computer.  Grover's algorithm searches an unsorted N-element database in time that scales like sqrt(N). (You want to search the database of all possible keys for the one that turns the coded message into text.)  So you get a quadratic improvement.  Unfortunately for the codebreaker, if you can break the 128-bit key in one second, the time for the 256-bit key is ridiculously long whether you use classical brute force or Grover's algorithm.   

Likely Shor's algorithm doesn't need to be run too many times, probably on the order of the number of qubits in the system.  For something like 10^4 qubits, this would give timescales ranging from 0.01s to 3 hours.  Grover's algorithm has to be run ~sqrt(N) times, where N is the number of possible keys.  For any appreciably large N, say 2^256, this is a ridiculously long time. 

For more informations about what I'm talking about:

https://en.wikipedia.org/wiki/Shor's_algorithm

https://en.wikipedia.org/wiki/Grover's_algorithm

Now,  in the case of RSA, we adopted quite a strong statement: if a quantum computer can break a 128-bit RSA encryption in one second . 

This was not to say "it can": it was to give a proportion. Because the problem of encryption algorithms is not how hard they are: they are hard. The problem is how hard it becomes to break them, when you increase the size of numbers you use as keys. So that, saying "if you can decrypt in a second 128bit , then it takes a few seconds to break 256" , just means that the complexity of this problem is not growing so much. But... how much it takes to decrypt 128 bit, actually?

Well, here bad news: IF your encryption is based on factorization of prime numbers, a QUIP can destroy your encryption pretty easy. 

Now, the issue: how much of our encryption is using prime numbers? Well... uhm... more or less, all of them. This is surprising, because the safety of prime numbers is made out of the fact we need to factorize them ALL TIMES we have a message to decrypt. But, prime numbers database are existing since ages, so there is no need to do the factorization all the times. 

We may discuss ages on the false sense of security of this choice, anyhow, it is a fact today most of encryption relies on how hard it is to factorize prime numbers. Then yes, it is very easy for QUIP to break it. 

Is there some kind of encryption which is resistant to quantum computing and can give some privacy? There are two known:

• https://en.wikipedia.org/wiki/Lattice-based_cryptography 
• https://en.wikipedia.org/wiki/Steganography

Lattice based cryptography is a mathematical technique based on a problem which is not depending by how much power you put in "parallel": Which means, basically, QUIP is not suitable as an advantage to attack it. QUIP is a very specific solutions, and the physics of it is putting lot of limits in its application. Meaning that, with the QUIP we may think today (because of the physics we know), it is very hard to attack a Lattice-based problem.

Also check:

https://en.wikipedia.org/wiki/NTRU

and

https://en.wikipedia.org/wiki/Homomorphic_encryption

The second way to talk in private way is Steganography. steganography is based on the idea that the channel itself is not known, or hidden. To make it short: I do a call with you, talking about butterflies.  This will result in a stream of sound. Now, imagine into this digital stream of sound I can embed a text, with the instruction for an attack. 

While there are techniques to check if there are deviations from the usual noise a sound has, most of encryption techniques are producing an output which is hard to distinguish from white noise. Then, if the stream of sound contains an encrypted text, it is almost impossible to understand here you are delivering a text file. 

So, if you imagine a conference call software which can embed text files into the sound stream, then it is almost impossible to understand you are transmitting: this is "covert channel" security. 

https://en.wikipedia.org/wiki/Covert_channel 

What makes the Digital Steganography that dangerous for government agencies is that they cannot even prove you were communicating. Meaning, if you send an encrypted email to someone it could be possible to say "you are saying something I don't know to him". Which could be a legal problem into a trial.

Using steganography, the attacker is not even able to proof you sent a message, other than the one which SEEMS you sent: (i.e: talking about butterflies).

Steganography has another  huge problem, which affects quantum computing very well:

Since 90% of the traffic in the web is not even indexed, and amount is around 7 Zettabites, the search for a content doing noise floor consistency analysis is simply... unfeasible.  For a very simple reason: in such a scale. ALMOST EVERYTHING  you may communicate to another human is "noise floor".  Meaning that, your secret message could be , let's say, some kilobytes? Some megabytes? Even couple of gigabytes? Still nothing: with such a size, lost in 7 Zettabytes of data, you are into noise floor, until you remember to scramble the data (not even encrypting it).

Putting all together: yes, there are concerns about the Quantum Computing is the end of privacy.

There is something true in that, because of usage of prime numbers in cryptography, and how to end this wide adoption of a dumb problem. (dumb if related to QUIP).

Still, quantum computing is not "brute force made easy": even if you put all the particles of the universe into a quantum computer, like 2^150 QBITs , a brute force attack to a long key (=2^512)could take more than the remaining life of universe.

Which means,  Lattice Problems, most of PPAD -complex problems  and steganography are out of the Quantum Computing range. 

In practice, QUIP is likely to be the end of RSA, but not the end of Privacy at all.