LinuxQuestions.org
Share your knowledge at the LQ Wiki.
Go Back   LinuxQuestions.org > Forums > Linux Forums > Linux - Security
User Name
Password
Linux - Security This forum is for all security related questions.
Questions, tips, system compromises, firewalls, etc. are all included here.

Notices


Reply
  Search this Thread
Old 06-10-2013, 07:45 PM   #1
sneakyimp
Senior Member
 
Registered: Dec 2004
Posts: 1,055

Rep: Reputation: 78
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?
 
Old 06-10-2013, 09:49 PM   #2
jlinkels
LQ Guru
 
Registered: Oct 2003
Location: Bonaire, Leeuwarden
Distribution: Debian /Jessie/Stretch/Sid, Linux Mint DE
Posts: 5,191

Rep: Reputation: 1039Reputation: 1039Reputation: 1039Reputation: 1039Reputation: 1039Reputation: 1039Reputation: 1039Reputation: 1039
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.

jlinkels
 
Old 06-10-2013, 11:36 PM   #3
Z038
Member
 
Registered: Jan 2006
Distribution: Slackware
Posts: 855

Rep: Reputation: 169Reputation: 169
Quote:
Originally Posted by sneakyimp View Post
Is quantum computing really threatening the state of security?
When I asked Schrödinger's cat, he confusingly said "Yes, and No."
 
Old 06-10-2013, 11:40 PM   #4
ntubski
Senior Member
 
Registered: Nov 2005
Distribution: Debian, Arch
Posts: 3,508

Rep: Reputation: 1811Reputation: 1811Reputation: 1811Reputation: 1811Reputation: 1811Reputation: 1811Reputation: 1811Reputation: 1811Reputation: 1811Reputation: 1811Reputation: 1811
Quote:
Originally Posted by jlinkels View Post
- 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.
 
1 members found this post helpful.
Old 06-11-2013, 10:48 AM   #5
sneakyimp
Senior Member
 
Registered: Dec 2004
Posts: 1,055

Original Poster
Rep: Reputation: 78
Quote:
Originally Posted by ntubski View Post
No, quantum computers do not give infinite processing power. They can't solve NP-complete problems in polynomial time either.
OK this sounds more reasonable and less like middle school hearsay. Do you have a source for your information that we might refer to?
 
Old 06-11-2013, 11:16 AM   #6
ntubski
Senior Member
 
Registered: Nov 2005
Distribution: Debian, Arch
Posts: 3,508

Rep: Reputation: 1811Reputation: 1811Reputation: 1811Reputation: 1811Reputation: 1811Reputation: 1811Reputation: 1811Reputation: 1811Reputation: 1811Reputation: 1811Reputation: 1811
Quote:
Originally Posted by sneakyimp View Post
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"...
 
2 members found this post helpful.
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
Quantum computing device hints at powerful future Jeebizz Linux - News 0 03-22-2011 12:23 PM
LXer: Quantum computing billions of times faster than conventional computing LXer Syndicated Linux News 0 11-24-2006 02:21 AM
LXer: Purdue University Expands Advanced Computing Resources With SGI Technology LXer Syndicated Linux News 0 10-18-2006 11:54 PM
LXer: Wyse Technology Extends Thin-Computing Leadership With New Linux Solutions LXer Syndicated Linux News 0 04-05-2006 02:33 PM
Will the development of quantum computing lead to faster than light communication? jschiwal General 4 01-20-2005 11:06 PM

LinuxQuestions.org > Forums > Linux Forums > Linux - Security

All times are GMT -5. The time now is 06:12 AM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration