Quantum Ciphers and Human Ingenuity

Schtask

Schtask

Limp Gawd
Joined
Nov 29, 2011
Messages
436
Quantum Computers have cryptographers worried that our concepts of modern cryptography will soon become obsolete. We've mentioned this before. Quantum computers like the D Wave X2 utilize bits that exist in superposition. In other words, bits of 1 or 0 are not just 1 or 0. They can also be 1 AND 0. The quantum midichlorians are strong with that droid. So strong, in fact, that modern cryptography was given a shelf life back in the 1990's when Peter Shore wrote a quantum algorithm that single-handedly cracked encryption based on integer factorization and discrete logarithms. Like Lord Vader versus the last remaining Jedi, the RSA and the Diffie-Hellman key exchange were destroyed in a single tactical strike. Since then, other algorithms have emerged that improve upon his work. In 2012, through adiabatic quantum computation, researchers were able to modify an algorithm and successfully factor numbers as large as 56k. It would seem that with the advent of Quantum Computing, cryptography's days are numbered.
 
Last edited:
So about encryption, unless I didn't understand it. If you're using 512bit now, to a quantum computer this would be like 256bit. So if you're using 256bit now, you'd want to switch to 512bit if quantum computers came out, that right?
 
Quantum computers would make breaking modern encryption more or less trivial, true, but my expectation is that electronic devices in the future will all have quantum coprocessors dedicated to encryption (quantum cryptography) and non-classical operations.
 
I remember reading somewhere about using photons in encryption some how. Something about how observing the photon would destroy it. Man now I'm going to have to dig up that article.
 
Rev Lemmon said:
I remember reading somewhere about using photons in encryption some how. Something about how observing the photon would destroy it. Man now I'm going to have to dig up that article.
Click to expand...

Yes. Photonic QuiBits were used in 2001 as a method to increase factorization. Maybe a PiC based system. Probably laser based. Gain region, grating mirror etc..
 
Maybe I'm missing the mark with this, but isn't quantum computing supposed to only obliterate asymmetric encryption since it is dependent on increasingly long prime numbers that are currently time intensive to factor out, but will be no match for quantum computing which can essentially factor instantly? If so, won't symmetric, password based, encryption still be fine since it's more guess and check rather than a function of lots of just straight math?
 
Extra-Titanian said:
Maybe I'm missing the mark with this, but isn't quantum computing supposed to only obliterate asymmetric encryption since it is dependent on increasingly long prime numbers that are currently time intensive to factor out, but will be no match for quantum computing which can essentially factor instantly? If so, won't symmetric, password based, encryption still be fine since it's more guess and check rather than a function of lots of just straight math?
Click to expand...

The jury is out on that one. Brute forcing the hash on a password that's 20 characters long can take like...a septillion years (without OCL Hashcat, intelligent guessing and rainbow tables). There is not enough computing power on planet earth to make that go any faster. Quantum computing definitely changes that. How quickly? I have no idea. Still trying to wrap my head around the concepts.

However... We can hypothesize from what has occurred in the past and look to the specs of these devices as they exist now. Before I answer this, please keep in mind that I'm a lowly infosec slug with a trade skill level of knowledge regarding encryption algorithms.

Regarding Symmetric Encryption and Hashes:
Symmetric encryption probably fares better than asymmetric. Since a quantum computer can search through a space of size 2n in 2n/2 time space ( space time? :yawn:) I believe that your bit keys are halved thus reducing strength. Note that these search areas are for quantum computing specifications for current devices. Larger search sizes and speeds reduce strength exponentially. That being said.. The cost of these devices increases exponentially with performance.

Hashes are most likely in the same boat as Symmetric Encryption. SHA -256 will probably fare as well as SHA 1 since preimages and collisions exist in the 2n/2 space as well.

Regarding what's been done before with RSA and DH:

RSA and like algorithms that utilize integer factorization like Rabin, are obsolete. Peter Shor has been there and done that.

Discrete Logarithms are also obliterated. There goes Diffie-Hellman and it's family members. Again, also proven by the research complementing Peter Shor's work.

Quibits might have something. Then again..They might not. The box is still closed and we don't know if the cat drank the poison or not. Hell... we don't even know if they could afford a real cat or if they had to settle for a crayon drawing of the Nyan Cat.
 
Last edited:
Galvin said:
So about encryption, unless I didn't understand it. If you're using 512bit now, to a quantum computer this would be like 256bit. So if you're using 256bit now, you'd want to switch to 512bit if quantum computers came out, that right?
Click to expand...

Current non-symmetric encryption techniques will not stand a chance verses quantum computers. For example RSA 128 encryption can be cracked by a quantum computer in a second. Maybe a few seconds if it's RSA 256. RSA 1024 is probably in the minutes range. Symmetric encryption is weakened by about half the time (2^(n/2) as opposed to 2^n)

It'll take a quantum computer with more than a thousand qubits to be powerful enough to perform decryption. Current quantum computers and even near future are in the 5-50 qubit range. Y2Q (yes this appears to be what they're calling it) will happen around 2030 (estimated time for 1000+ qubit quantum computers to exist). At this point all encryption, on the internet and everywhere else, must use quantum cryptography otherwise the message that's being sent/received can be assumed to have been cracked by the time it's received.

http://www.cambridgewireless.co.uk/Presentation/CWTEC16-Mike_Brown-ISARA.pdf

The first part is a good basic explanation of the coming problem.
 
Last edited:
Crixus, I've taken Intro to Cryptography, so I recognize some of the words you used. That post, sir, was more densely packed than most of the lectures. I curled up in the fetal position about the time you got to adiabatic.
 
Huh? I hear a lot of 'will' and 'can' future tense, but no HAVE DONE X in reference to this Quantum Computer shit. Is this for real or just another path of hype, smoke, and mirrors on the part of techno-con artists in academia self-justifying their bullshit grants?

The whole thing makes me want to stuff Schrödinger's Cat in Box and strange it.
 
You must log in or register to reply here.
Back
Top