Is quantum computing a threat to current encryption technology?

Linux - SecurityThis forum is for all security related questions.
Questions, tips, system compromises, firewalls, etc. are all included here.

Notices

Welcome to LinuxQuestions.org, a friendly and active Linux Community.

You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!

Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.

If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.

Having a problem logging in? Please visit this page to clear all LQ-related cookies.

Introduction to Linux - A Hands on Guide

This guide was created as an overview of the Linux Operating System, geared toward new users as an exploration tour and getting started guide, with exercises at the end of each chapter.
For more advanced trainees it can be a desktop reference, and a collection of the base knowledge needed to proceed with system and network administration. This book contains many real life examples derived from the author's experience as a Linux system and network administrator, trainer and consultant. They hope these examples will help you to get a better understanding of the Linux system and that you feel encouraged to try out things on your own.

Click Here to receive this Complete Guide absolutely free.

Is quantum computing a threat to current encryption technology?

Soooo a non-technical friend of mine recently claimed that quantum computing threatens to render encryption technology obsolete (at least for nation-states) thanks to some kind of magical ability to prime factor large numbers. I won't degrade this forum with the useless link he sent, but it occurs to me that I have no technical understanding of quantum computing whatsoever. I doubt that anyone here has access to a quantum computer or direct research with one, but what do we think? Is encryption dead? Is quantum computing really threatening the state of security?

Distribution: Debian /Jessie/Stretch/Sid, Linux Mint DE

Posts: 5,191

Rep:

If we set up this reasoning:
- any encryption can be broken by a computer with unlimited processing power
- quantum computers provide unlimited processing power
then the answer should be: "yes, encryption becomes obsolete with quantum computers"

I believe there is even a Wiki page about quantum computers. They are able to perform an infinite number of calculations at the same time because nuclear particles can have an infinite number of simultaneous positions and momentums.

The question is just when a usable quantum computer will be available. Funny things, a user would be user and root at the same time. Or logged in and logged out at the same time. Or a semaphore would be true and false at the same time. Quite exciting.

Maybe it will be in 40 years from now. Just as nuclear fusion for energy generation has been 40 years away for the part half century.

- quantum computers provide unlimited processing power
...
They are able to perform an infinite number of calculations at the same time because nuclear particles can have an infinite number of simultaneous positions and momentums.

No, quantum computers do not give infinite processing power. They can't solve NP-complete problems in polynomial time either.

There is an algorithm to factor integers in polynomial time using a quantum computer: Shor's algorithm (friendlier explanation). Note that we don't have a lower bound on integer factoring, so it might be solvable in polynomial time on a classical computer too.

This would break current public key systems but there are public key systems that are based on NP-complete problems (they are not used currently because the key sizes are quite a bit bigger), so we could move to those if quantum computers turn out to be practical.

Do you have a source for your information that we might refer to?

The "friendlier explanation" I linked to is the blog of Scott Aaronson, his thesis is about this stuff so I would consider him an expert. In his thesis summary he says:

Quote:

In the first part of the thesis, I attack the common belief that quantum computing resembles classical exponential parallelism... there is no "black-box" quantum algorithm to break cryptographic hash functions or solve the Graph Isomorphism problem in polynomial time. I also show that relative to an oracle, quantum computers could not solve NP-complete problems in polynomial time, even with the help of nonuniform "quantum advice states"...

LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.