"Holy Grail" of unbreakable quantum cryptograph

flav0rflav

http://www.theregister.co.uk/content/55/31077.html

Much of the interest in quantum cryptography stems from the fact that it is fundamentally secure. This contrasts with today's code-based systems which rely on the assumed difficulty of certain mathematical operations. Ultimately, quantum cryptography seeks to deliver a method of communication whose secrecy does not depend upon any assumptions.

Quantum cryptography allows two users on an optical fibre network to form a shared key, the secrecy of which can be guaranteed. This takes advantage of the particle-like nature of light. In quantum cryptography, each transmitted bit is encoded upon a single light particle (or 'photon'). The impossibility of faithfully copying this stream of encoded photons ensures that a hacker can never determine the key without leaving detectable traces of their intervention.

I thought that the "Holy Grail" of cryptanalysis, quantum computing, would defeat all crypto, by doing a massively parallel key search?

Or is this like the Knight Rider episode when Michael and Kitt come up against the indestructable truck?

flav0rflav

Hmm, I wanted to correct my spelling mistake, but it won't let me edit?

irishgeo

You have to edit your post within a certain limit (can't remneber how long) other wise it gets locked to editing.

Capt'n Midnight

You are dealing with single quantums - it's a bit like the single atom memory bits - one cosmic ray and you are into error correction - so someone can do a limited amount of sniffing / force you to resend...

BTW: fibre links are secure - total internal reflection means that any attempt to splice the cable or bend it will be detectable if you are monitoring the receiving light level. You can also drop the transmitting level such that detecting the maximum leaked portion of it becomes more difficult. - You can use fibre coverings that are opaque and use any detected light as a sign that privacy has been lost.

In practise undoable (remember quantum effects means you can't guarantee detecting every photon !)

MiCr0

Originally posted by flav0rflav
http://www.theregister.co.uk/content/55/31077.html

I thought that the "Holy Grail" of cryptanalysis, quantum computing, would defeat all crypto, by doing a massively parallel key search?

Or is this like the Knight Rider episode when Michael and Kitt come up against the indestructable truck?

a parallel search will only find the key if its there.

the whole principle of quantum cryptography is that by attempting to break the code - you change the substance of the message.

eg
i send you a letter and it starts
"Hi flav0rflav, how are things..."

as soon as you read the letters (or decode them) they become something else

Capt'n Midnight

RE: the whole principle of quantum cryptography is that by attempting to break the code - you change the substance of the message.

So the idea is that if someone tries to intercept the message the intrusion will be detected. Again I suggest that most of this can already be done by fibre without needing quantum.

Also this system will suffer denial of service every time a cosmic ray hits the transmitter, reciver or cable - or you could retransmit the eavesdropper could pickup the mesage..

Opps forgot about natural radioactivity - eg: granite / potassium are radioactive so other ways to get photon losses

Lemming

Originally posted by MiCr0


the whole principle of quantum cryptography is that by attempting to break the code - you change the substance of the message.

eg
i send you a letter and it starts
"Hi flav0rflav, how are things..."

as soon as you read the letters (or decode them) they become something else

AFAIK, not quite MiCr0. What happens is that as soon as you intercept a part of a transmission, the quantunm state value changes, therefore the party at the other end of the transmission (receiving) knows that a 3rd party has intercepted a message.

Or something like that. I can't rightly remember. I had a guy I know with an M.Sci in Pyshics explain it to me a few years ago. Crazy ass stuff


[Edit]
hell, the more I try to recall, you're probably right MiCr0 and that the decryption is another effect.

flav0rflav

But it's only secure on the fibre? So you need one piece of fibre from source to destination, a la the bat phone?

Ah sure it's just a research proto at the min.

hego

I thought that the "Holy Grail" of cryptanalysis, quantum computing, would defeat all crypto, by doing a massively parallel key search?
[\quote]

quantum computing is not the "Holy Grail" of cryptanalysis. It's true that quantum computing can undertake massively parallel operations, but the problem lies in extracting the correct information. There are two main types of cryptographic algorithms, symmetric and assymetric. If a quantum computer were built tomorrow all assymetric algorithms based on the difficulty in factoring a composite number composed of two large prime numbers(aka RSA) would be broken. This is because of Shor's algorithm which can break the above in polynomial time. Symmetric algorithms, such as 3-DES, are invulnerable to this approach. Grover's algorithm can search an unstructured database in quadratic time, but this would probably be too slow to break a symmetric algorithm with a large key-space. It could only be used to speed up the search for keys.

flav0rflav

Thanks for that info Hego.

I see some extra detail here:
http://www.wikipedia.org/wiki/Quantum_computer

Still, if quantum computing kaiboshes public key as we know it, that would be significant.

What's the story with non-factor based asymmetric? We can't revert to only symmetric.

hego

Still, if quantum computing kaiboshes public
key as we know it, that would be significant.

What's the story with non-factor based asymmetric? We can't revert to only symmetric.

Not too sure to be honest. I would imagine elliptic curve stuff is immune, as it relies on the
difficulty of another set of problems. You can
implement RSA using elliptic curves y'know.
In any case, I'd consider it highly unlikely to
see a useful quantum computer within the
next 20 years, probably more likely in about
50 years.

Gavin

Originally posted by hego
Not too sure to be honest. I would imagine elliptic curve stuff is immune, as it relies on the
difficulty of another set of problems.

Ahh.. What exactly are those problems & why are they not vulnerable to massive parallel computing.. ?

Gav

hego

Ahh.. What exactly are those problems

Look them up on the net d00d. That's what
it's there for.

& why are they not vulnerable to massive parallel computing.. ?

*sigh*. They don't rely on the discrete logarithm problem to my knowledge, and therefore are not vulnerable to Shor's quantum algorithm.

Gavin

Originally posted by hego
Look them up on the net d00d. That's what
it's there for.

You made the statement. I assumed you know what it was about.
As they say, assumption is the mother of all ****ups.

*sigh*. They don't rely on the discrete logarithm problem to my knowledge, and therefore are not vulnerable to Shor's quantum algorithm.

I though shor's algorithm is used to factor number according this this paper here, http://www.redbrick.dcu.ie/~hego/technicalmanual/technicalmanual.pdf

What has this got to do with discrete logarithm ? correct me if i am wrong of course.

Gav

hego

You made the statement. I assumed you know what it was about.
As they say, assumption is the mother of all ****ups.

Quite. However, I am not familiar with the mathematics of elliptic curves, I know crypto based on them is based on an NP problem related to finding points on those curves or something. At no time in my post did I state I knew the exact details of elliptic curves.

I though shor's algorithm is used to factor number according this this paper here, http://www.redbrick.dcu.ie/~hego/te...nicalmanual.pdf

What has this got to do with discrete logarithm ? correct me if i am wrong of course.

Heh you bollix! Shor's algorithm also solves the discrete logarithm problem that El Gamal and Diffie Hellman are based on.

Gavin

Alright, so we don't know if quantum computing can/cannot aid in breaking elliptic curve cryptography... ( and that hego get's confused easily )

I rest my case. I am the champ. And also, I believe that mike and kitt did manage to defeat Goliath, the not so indestructible truck by kitt finding a vulnerability under it's axle. (god the internet is great)

I mean come on, naming the truck Goliath was just looking for it to get the chop.

Gav