Encryption which quantum computers cannot break?

The link below goes to an article from a very respectable newspaper in Israel, but written by a journalist, not a scientist, and with a headline that sounds like click bait.

The article is fairly long, and a bit boring, mostly about the need for Israeli politicians to provide more funding for quantum computing, before the “apocalypse”(click bait?) occurs —and enemies with quantum computers will be able to break into any computer in the world .

The journalist interviews several businessmen heading commercial companies in Israel that deal with quantum computers.(These men are CEO’s, and so of course have a bias for their companies, but they apparently also have solid scientific training.)
I’m wondering how much of it is accurate.

The article mentions the ability of quantum computers to break RSA encryption and SSL security protocols, thus making the whole internet and all military computers vulnerable. But it claims that soon it will be possible to replace these security problems with new, quantum-based systems.

One of the CEO’s states that there now exists “post-quantum encryption”, which is more advanced that quantum computing, and will produce a “new revolution in encryption that quantum computers cannot break”. The algorithms to do this are being studied at a level called “stage three” (no explanation given) by the Israeli National Institute of Standards and Technology, and “will be approved by 2023 or 2024.”

My questions are basically "Is this all true?
More specifically:
1.How serious a threat exists right now from quantum computers to the current encryption systems which we all use for our banking, and which armies rely on?
2. Is it possible to replace these encryption systems with quantum computers? (I can’t imagine that I’ll be using a laptop quantum computer in my bedroom to access my bank accounts any time soon.Or that a platoon sergeant in the field will use quantum encryption to send a message back to headquarters )
3. Will governments, banks, and armies soon be using quantum computers for practical,useful, daily operations?
If not, what use it there for this new, unbreakable quantum-encryption?

First off: Yes, quantum computers could, in principle, break RSA, the most commonly-used encryption algorithm. It hasn’t been done on a practical scale yet, but the technology is advancing, and eventually, it will.

Second, there are other known encryption schemes, already developed, which are believed to be as secure as RSA, and for which there is no known quantum algorithm to crack them. It’s just a matter of implementing them, which, since RSA is used all over the place, is a nontrivial task.

Third, there is also such a thing as quantum encryption, but its purpose is not to defeat quantum cracking. It helps to protect against various other sorts of attacks, based on the fact that quantum states can’t be copied non-destructively.

Fourth, “no algorithm is known” is not the same thing as “there is known to be no algorithm”. We don’t even know for sure that there’s not a practical classical algorithm to crack any given sort of encryption. We’d be really surprised if there were, but we don’t know for sure.

There is no way to encode meaning in such a way that it cannot be understood.

A related question: whenever anyone mentions quantum computers, all they ever talk about is encryption and decryption. Is that all they do, or does quantum computing have any other applications?

As far as I understand it, they may have applications in any sort of ‘needle in a haystack’ type of operation, where there is a ‘right’ answer, but it’s time/computation expensive to find it. I only have an armchair understanding of the ideas, but I think it’s more or less accurate to say that whereas with traditional computing methods, you would have to iterate a whole series of calculations, trawling through a whole load of wrong answers until you hit the right answer, quantum computing can (sort of) try them all simultaneously, as long as you can define the problem in such a way that the wrong answers (sort of) destroy themselves by being wrong, and the right answer is all that remains.

That’s an oversimplification to the point of being basically wrong. There is a class of problems that it’s known that quantum computers can do much more quickly than classical computers, but that class doesn’t remotely encompass all needle-in-haystack problems. As I mentioned before, there are even other two-key encryption systems, functionally similar to RSA, that are not in that class of problems. Factoring large numbers, the fundamental operation behind RSA cracking, just happens to be one of them.

As for what else quantum computers can do, the most obvious one is simulate other quantum systems. But as for classical applications of quantum computing, yeah, factoring is the big one. There doubtless are other applications, but the field is still in its infancy, and very few people can grok it enough to make any real progress in it.

That is true as long as you don’t include “scramble at random” in “encode”, but there are plenty of ways to encode messages so that there is no realistic way to decode them without having the algorithm and the key. They may not be practical in most situation, but they’re possible.

It depends a bit on what one means by ‘needle in a haystack’, but for searching through an unsorted database, Grover’s algorithm gives a general speedup compared to classical algorithms. In fact, in this case, it’s even provable that the quantum algorithm is faster than the classical one—although the speedup is ‘only’ quadratic, not exponential.

It doesn’t have anything to do with trying all possibilities simultaneously, though.

OK, I apologise. I thought I had a tentative grasp of the possibilities, but perhaps not.

The standard term for these schemes is post-quantum cryptography or post-quantum encryption as can be seen in Post-quantum cryptography - Wikipedia.

Ah, OK, I’d never encountered that name for them. Still, it’s not that they’re “more advanced than quantum computing”-- It’s just that they happen not to fall into the category of problems that quantum computers help with. In fact, I think some of these “post-quantum” algorithms actually predate quantum computing.

Post-quantum encryption doesn’t mean “encryption that’s scientifically more advanced than quantum computing”. It means “encryption that will be necessary to avoid one’s messages being broken if quantum computers reach the point where they can break the standard encryption systems used today”. It’s better not to use the term “quantum algorithm”, since that seems to imply that it’s necessary to know quantum physics to understand the algorithm.

Sorry if that seemed snippish, it wasn’t my intention. It’s just that the idea of ‘quantum parallelism’ is one of the worst failures of science communication, and has led to any number of misconceptions about the power and means of operation of quantum devices. Plus, these days, you have to take extra care what you say:

:smiley:

There’s a good explanation of Grover’s algorithm here, if you’re interested. The gist of it is, you think of the item you’re looking for as one for which a certain function returns True, while it returns False for all others. Then, you put all the possible inputs in a superposition (which is where the idea of ‘quantum parallelism’ comes from), and act on the whole superposition in such a way that the amplitude (the probability of finding a state in a measurement) of the ‘right’ item increases, while the probability of all others decreases. This is best thought of as rotating the state you have towards the state you want—an operation on the whole state (i. e. the superposition of all possible inputs, initially) rather than on each of its components.

I’m not sure exactly what is meant here, but from the point of view of encryption a one time pad is unbreakable no matter what attack is attempted.
There are however significant downsides to using a pure one time pad. The pad must be the same length as the message and cannot ever be used again. And both ends of the communication need a copy of the pad.
Addressing these limitations are in many ways core drivers of modern cryptography.
The problem of key exchange is one of the core problems. One time pads are subject to interception. You can send the pads by courier with an attaché case handcuffed to their wrist. But nothing is sure. The allure of quantum cryptography is that it solves the key exchange problem. We hope. That is a big deal.
But public key cryptography is never going away.

Well every one thinks quantum computing is the next major thing because Moore’s law is ending very soon. But I’m not so sure how quantum computing can work because computers we have now operate on electric charge being recorded as 1 and no charge being recorded as 0 and by operations of 1s and 0s they can represent data.

But by looking at quantum mechanics it says quantum computing should operate on 0s and 1s and being both at the same time. So this opens up big problem how could data be both there and not there.

IS it 1 or 0 ? Well how can it be 1 and a 0 or both or 1 and O at the same time.

Other big problem I don’t buy into this quantum computing is sensitivity effect. Where just a truck driving down the street can cause interface.

I just don’t know why engineers take quantum computing seriously it is all research and development at this stage.

There not going to be any quantum computer any time soon.

I don’t know what happen to optical computers they where pushing in the late 90s being 50 years out but optical computers have much better and faster at replacing silicon computers by year 2050 than quantum computer that is way beyond level of understanding and technology we have today.

But everyone is racing to replace silicon computers because of transistors getting so close now you are going to start to get quantum interference.

It just pop media like the likes of popular science that seem to paint we will have quantum computers soon and that not the case. We are no where close to a quantum computer be it now or in 20 years from now or by the year 2050.

It will probably be other 100 years or more if ever and there is still major problems with quantum mechanics that science cannot explain.

@Jillwood77, it sounds like you’re saying that, because you don’t understand quantum mechanics, it can’t work. The fact is, no human really understands quantum mechanics. Richard Feynman, who won the Nobel Prize for his contributions to extending quantum mechanics, said that anyone who thinks they understand quantum mechanics, doesn’t understand quantum mechanics. But this fact, that we don’t understand quantum mechanics, reflects a limitation of our brains, not a limitation of quantum mechanics.

And there you answer your own question in the same sentence you asked it. Engineers take quantum computing seriously because it’s in research and development at this stage. How could it be otherwise?

As for the claim that there won’t be one any time soon, that’s demonstrably false. Quantum computers exist now. The ones that exist now are still small, too small to be practical, but they exist, they work, and they’re getting bigger (because that’s what research and development do).

Will a quantum computer be able to mine BitCoin very quickly?

Not at all. I welcome the correction!

You can buy one right now if you have have $10M burning a hole in your pocket.

There are plenty of applications such as modelling things like the weather or nuclear explosions but they won’t be good at getting you 120fps when playing PUBg.