6
$\begingroup$

If quantum computers advance to the point where they can defeat RSA, DSA, SHA (and really all existing classical public key encryption or and authentication) then it appears that it would be impossible to make secure transactions on the internet.

It would be impossible to maintain the security of user accounts for social media, amazon, eBay, online banking, etc. It seems that the economic repercussions of this would be catastrophic on a global scale.

What measures can be taken against attacks on cryptosystems by quantum computers?

At lest for now, I see a big problem with giving an answer that involves saying we could just use quantum encryption algorithms. The main reason is that in order for the encryption to be effective the end users would have to be in possession of a quantum encrypt/decrypt device. Not a problem for a bank or Amazon on their end, but a big problem for a guy trying to order a pizza on his smart phone.

If end users were not actually in possession of a small quantum computer, and instead used a cloud based service to access a quantum device an attacker could just target the last segment of the transaction (between a cloud service and their device).

For end users to possess quantum crypto devices one would need to bring the cost down to a few hundred dollars max or the average person would not be able to afford it. Right now most quantum systems are priced in the hundreds of thousands or millions of dollars range.

Also, all of the viable quantum systems I have seen run near absolute zero. I don't know of anyone who makes a dilution refrigerator the size of a AA battery. So you couldn't perform transactions on portable devices.

Is the only option then to classify all quantum crypto research until these problems can be solved?

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
3
$\begingroup$

At least for now, I see a big problem with giving an answer that involves saying we could just use quantum encryption algorithms. The main reason is that in order for the encryption to be effective the end users would have to be in possession of a quantum encrypt/decrypt device. Not a problem for a bank or Amazon on their end, but a big problem for a guy trying to order a pizza on his smartphone.

Not really. Current day cryptosystems are mostly based on integer factorization, discrete logarithm & elliptic curve cryptography. I'd like to point out to you: Post-quantum cryptography. There are already a few cryptography algorithms which are resistant to quantum computer attacks. And you don't need necessarily "quantum computers" on the sender's or receiver's end for using such cryptography techniques.

The cryptosystems which are quantum-resistant normally use problems which lie outside BQP rather than being QMA-hard. That implies, the owners of the private key (in this case the sender and receiver) can easily decrypt the message using a classical computer, whereas since the problem is QMA-hard without the private key, even using "brute-force", it would be difficult for a quantum computer to hack. (see @DaftWullie's excellent answer) and his comment:

For example, in the normal classical case of RSA, the central function is factoring. The problem is (assumed to be) outside P making it hard for a classical computer to hack, but inside NP (NOT NP-hard) so that the rightful receiver can decrypt it on a classical computer.

To quote Wikipedia:

In contrast to the threat quantum computing poses to current public-key algorithms, most current symmetric cryptographic algorithms, and hash functions are considered to be relatively secure against attacks by quantum computers. While the quantum Grover's algorithm does speed up attacks against symmetric ciphers, doubling the key size can effectively block these attacks. Thus post-quantum symmetric cryptography does not need to differ significantly from current symmetric cryptography.

By the way, I should point out that we're still quite a long way away from having actual quantum computers which can break current-day cryptosystems. The quantum computers of today aren't capable of even factorizing very large numbers. The largest number factorized by a quantum computer till date is $291311$[1] (as far as I know). That's something even your hand PC can do in milliseconds and that is nowhere close to breaking a cryptosystem. Presumably, by the time we will have such quantum computers, cryptography will have already progressed by leaps and bounds (and we wouldn't have to worry about "quantum attacks").

Moral of the story: Even in the future, your guy can still order pizzas using his "classical" smartphone without having to worry about hungry hackers stealing his pizzas using a quantum computer! ;)

[1]: High-fidelity adiabatic quantum computation using the intrinsic Hamiltonian of a spin system: Application to the experimental factorization of 291311 Li et al. (2017)

Improve this answer
$\endgroup$
-3
$\begingroup$

We can always make larger and larger keys in RSA. If a quantum computer can factor numbers up to RSA-4096, then use RSA-131072, or better yet, some elliptic curve key big enough to be safe against the next 10 years of quantum computing hardware.

Or don't use public key cryptography but instead use standard passwords where the cost for a classical computer to break them is $M^n$ for $M$ characters and a password of length $n$, and the quantum computer's cost is at best $\mathcal{O}(M^{0.5n})$ which is not at all much better.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ The government has of course classified all kinds of research in the past when they felt it was necessary. Some of Von Neumann's early papers on computers were kept secret for years. A lot of practical research about nuclear energy was and still is kept secret. There are plenty of other examples. But you are right, eventually someone else will discover the information one way or another. $\endgroup$
    – user4574
    Jul 1, 2018 at 0:34
  • $\begingroup$ The computing power of classical computers is growing at an exponential rate over time following Moore's law. One problem I see with making larger and larger keys is that the number of q-bits in quantum computers is likely to also follow Moore's law. Since quantum computers can solve exponentially larger problems as the number of q-bits grows, the growth in computational power over time of quantum computers is likely to be an exponent of an exponent. At some point you won't be able to make a classical computer that can handle the key size you would need. $\endgroup$
    – user4574
    Jul 1, 2018 at 0:45
  • $\begingroup$ @user96037: Classifying research is different from banning it, like your title suggests. And as for a quantum version of Moore's law, I'm not worried. You can always make a key size large enough that it should stand secure for the next 50 years. It might be HUGE, but it's always possible. Furthermore, as my answer suggests, you can also abandon public key cryptography and then quantum computers just give a square root speed-up on an exponentially growing cost, which means they are not really a threat there either. $\endgroup$
    – user1271772
    Jul 1, 2018 at 1:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.