Ted's Home Page Get Firefox! Get Thunderbird! Tuesday, September 17, 2019, 6:57 am GMT
    Home :: Contact :: Blog :: Updates (Tue, Feb 12) :: Search :: Highlight Linux :: Apache HTTPD :: PHP :: VIM :: OCS
          email me email me
 
[Ted and a baby giraffe]
 
Contact Me
Résumé/CV
More Information
 
Faculty Job Search
Industry Job Search
Research/Graduate
Work
My Teaching Sites
 
General Posts
(including
LaTeX
templates)
 
Utilities
 
Public hg repos
Public git repos
 
Links
The Blog
 
Guestbook
 
 
 
 
   
 
 
  email me
email me
email me
email me


Quantum Encryption :: Relationship to Traditional Encryption

BACKGROUND AND PURPOSE

The following is a reproduction (with added Contents for easy navigation) of a LiquidBlur post that responded to a question about quantum computing, its impact on conventional encryption, and quantum encryption. For more background information, see the original posts in question:

(scan to the end of this post for the answer to the question; the first part is just background. The basic answer is that QUANTUM ENCRYPTION provides a SECURE WAY FOR TRASFERRING KEYS. After that, it's just standard traditional encryption. Traditional encryption is NOT convenient. Public key methods have made it more convenient, but they ALL can be broken with a finite amount of computing time. Quantum encryption gets rid of the public key methods and provides a true way to send a KEY without it ever being sniffed. After the key is transferred, the same old traditional methods are applied.)

Contents

Public Key Cryptography

Public key cryptography is a really amazing thing. You export a public key that anyone else can use to encrypt data, but not decrypt it. You then keep a private key that can decrypt that data. These two keys are coupled together, so you really are exporting information about your private key, but that information is extremely difficult to find. The coupling involves primes. Prime factorization of very large numbers is a difficult problem, so if large enough random primes are used, the private key and public keys stay "decoupled." (unless someone has a few hundred years to crunch the problem with conventional computing)

So public key cryptography ALWAYS can be cracked using a STANDARD SIMPLE METHOD. However, conventional computing would take hundreds (or even thousands) of years (ON AVERAGE) to actually run that method. Just keep in mind that public key cryptography can CERTAINLY be cracked just as long as enough computing power is tossed at it.

Simplifying the Prime Factorization Problem with Quantum Computing

Quantum computing provides a fascinating way of turning the prime factorization problem into something more reasonable for conventional computing. It doesn't make the process constant time or anything like that, but it makes it manageable in polynomial time. It's able to do this by operating on a quantum mechanical possibility wave function in such a way that correlations between possible states are not broken (the wave function doesn't "collapse") until the end of the operation. It's true parallel processing without actually having to buy parallel processors.

[ I'd like to note that there is an area of research going on right now that is investigating using the fabric of the cosmos for computing. The next generation of particle accelerator (the one they're finishing at CERN) will actually be able to create small black holes within the collider. Information theorists are coming up with ideas on how to actually dump matter into these black holes as "inputs" in such a way that the resulting radiation that is emitted from the black hole is the result of a computation. ]

So quantum computing provides a method for prime factorization that is far more tractable on modern computers. This turns the public key cryptography cracking problem into something that can be solved in a few hours rather than a few hundred years. And this is what spells doom for public key cryptography.

Traditional Encryption (A Superset of Quantum Encryption)

Before public key cryptography, parties had to agree on a key to share between them. If I was communicating with 10 people, I would have 10 keys (ciphers) for each of those 10 people, and each person would also have a copy of her respective key.

Note that when I talk of "keys," I'm actually talking about an entire method of encryption. A key is a procedure for encrypting and decrypting information. There is no standard way of using a key to encrypt information; the method IS the key. The method is the cipher. Because of that, there is no standard way to break traditional encryption. You basically have to throw a bunch of geniuses into a room and have them stare at the encrypted codes until they find patterns. They are able to guess the cipher. But this is an act of black magic. It's heuristic. There are some guidelines, but there's no one way to do it.

So traditional encryption really faces no threat from quantum computing. Quantum computing may allow for some quicker methods to chew on data, but it won't break the method like public key cryptography. The major problem with public key cryptography is that everyone already knows the METHOD, they just have to figure out exactly which numbers to plug in.

The PROBLEM with traditional encryption is that you have to have a safe way of getting the key to each of your partners. You might be able to use public key encryption, for example, to encrypt your key. This is actually how most software programs transmit cipher information today anyway. However, if someone cracks your public key encryption, then that person also can get your key and crack all of your other communications. So in the end, the best way to give someone your key is to personally HAND IT to them. Because of this problem, public key cryptography is FAR MORE convenient. But that's a tradeoff. Real encryption requires getting up and actually giving a physical key to someone, but it means that the communication will always be safe. Public key cryptography means sending the key along with the message, but with enough computing power it can ALWAYS be broken (for CERTAIN).

[ Remember in Swordfish when Hugh Jackman's character talks about encryption with a cipher that was destroyed on implementation? He's talking about true encryption. He's talking about writing software to encrypt and decrypt information and after compiling it, destroying everything that was involved in its creation. All that remains are tne encryption and decryption engines. ]

Quantum Encryption

Quantum encryption really isn't any special type of encryption. It's just a way of transmitting your key. After that, it's just standard encryption. But since quantum encryption gives us a CONVENIENT WAY of SAFELY transmitting vital information about a key, then it makes traditional encryption just as nice as public key cryptography and FAR safer.

The Simple Explanation (without talking about photons)

With quantum encryption, two people, Abby and Bill, agree on a method of encryption that requires some 1024-bit key. All they need is a way to get that key from Abby to Bill. Well, Abby has TWO WAYS of transmitting a 1 or a 0 to Bill. Likewise, Bill has TWO WAYS to receive a 1 or a 0 from Abby. (so a 1 can be sent in two ways, and a 0 can be sent in two ways; and likewise for reception) Abby generates 10,000 random bits. For each bit she sends to Bill, she randomly decides which of the two ways she can send it. Sometime she sends it method 1, and the other times she sends it method 2. Likewise, Bill randomly decides which way he's going to receive the bits. Sometimes he picks method 1 and sometimes he picks method 2. More importantly, sometimes he picks the right method, and sometimes he picks the wrong method. If he picks the wrong method, he gets a random bit that has NO CORRELATION to the one that Abby sent. If he picks the right method, he gets Abby's bit.

Now, after every one of the 10,000 bits was received, Abby and Bill call each other on a PUBLIC CHANNEL. Bill then tells Abby which methods he used to receive each bit, but HE DOES NOT advertise what bits he received. Abby just tells him when he chose the right method. They agree that the first 1024 times Bill chose CORRECTLY will be the bits that they will use for their key.

Now, let's say Eve has been listening in. Let's say that she is in between Abby and Bill intercepting each bit as it gets transmitted. She also, like Bill, can choose method 1 or method 2 to receive the bit. Every time she intercepts a bit, she records what she found, and transmits that result to Bill. Bill never even realizes that there has been a delay.

But what if Eve chooses wrong? Then the bit that she transmits to Bill is a random bit that has NO CORRELATION to the one sent by Abby.

So let's go back to that phone call between Abby and Bill. Let's say they find the first 1024+500=1524 spots that they agree on. Then let's say Bill TELLS ABBY the first 500 of those bits. If those are the same bits that Abby sent, then they simply toss them out and keep the remaining 1024 as their key. However, let's assume that Eve was listening in during the transmission. ASSUMING that Eve wasn't lucky enough to pick EVERY method EXACTLY right, then SOME of those first 500 bits will not match the ones Abby sent. In this case, Eve's presence was detected (and Eve's information is useless).

So that's all quantum encryption does. It gives an easy way to transmit KEYS. Just like with public key cryptography, after the keys are transmitted, traditional encryption can be used.

The More Detailed Explanation (with some photon talk)

The transmission of photons are often given as an example of the "methods" that Abby and Bill used to send bits from Abby to Bill. Light can be polarized horizontally, vertically, or some combination of the two. From an electromagnetics perspective, this is the direction of the transverse oscillation of the propogating wave. Picture a string. Pulling it left or right and then releasing causes horizontal oscillations. Pulling it up or down causes vertical oscillations. Pulling it up and down AND left or right causes diagonal oscillations. Note that these diagonal oscillations are actually the SUM of a horizontal oscillation and a vertical oscillation. Likewise, you could model a horizontal oscillation or a vertical oscillation as a sum of two diagonal oscillations.

When modeling a diagonal oscillation as two "rectilinear" (horizontal and vertical) oscillations, the CORRELATIONS between the two diagonal oscillations are EXTREMELY IMPORTANT. Imagine that one end of the string is fixed and you are moving the other end. As you move your hand to the right, if your hand also moves up, then you get positive sloping motion. As you move your hand to the right, if your hand also mvoes down, you get negative sloping motion. So if the VERTICAL MOTION is POSITIVELY correlated with with horizontal motion, you get postively sloping diagonal motion. Likewise, if the vertical motion is negatively correlated with horizontal motion, you get negatively sloping diagonal motion.

[ Note that in real life, light isn't always linearly polarized. Imagine that as you move your hand back and forth horizontally, vertical motion reaches its MAXIMUM when your hand is in the MIDDLE of its horizontal motion. As your hand reaches full-right, it is in the MIDDLE of its vertical motion. In this case, we say that the two directions are in quadrature, and the result is circular polarization. Your hand, and thus the string, oscillates in a circle. Note that circular modes CAN be setup in a string. Likewise, circular modes of light can be setup in a medium. There may be aspects of that medium that prevent that (like a string moving through a slot) or aspects of the medium that only allow that (like a string moving in a circular slot). This is beyond this discussion though. It's important to note that we can setup filters that only allow the passage of light polarized in a particular linear direction. With these filters we can transmit light in any diagonal or rectilinear direction. ]

Now, Abby decides that a 1 is represented by vertical (|) or positive sloping diagonal (/) light. She thus also decides that a 0 is horizontal (--) or negative sloping diagonal (\) light. At each bit she transmits, she just picks randomly one of her two options for how to transmit it.

Now, Bill (or EVE) has two filters he can use. One of them looks like an X and only allows diagonal light to pass through it. The other looks like a + and only allows rectilinear light to pass through it. Now, REMEMBER that ALL DIAGONAL LIGHT is the SUM of two CORRELATED horizontal light waves, and ALL HORIZONTAL LIGHT is the SUM of two CORRELATED vertical light waves. (keep the string example in mind) If Abby sent a diagonal light wave (/ or \) to Bill and he picks his rectilinear (+) filter, SINCE **BOTH** RECTILINEAR DIRECTIONS have been allowed to pass through, the DIAGONAL LIGHT will STILL appear on Bill's side.

NOW ENTER QUANTUM ELECTRODYNAMICS. LIGHT IS **NOT** A WAVE.

Abby did not send a wave through though. Abby sent a PHOTON that was diagonally polarized. Photons have STATES. Abby's photon's "polarization state" was set to "positively sloping diagonal (/)", for example. Now, Bill's RECTILINEAR FILTER only allows photons of RECTILINEAR POLARIZATIONS through. Bill is asking the photon "are you polarized horizontally or vertically?" From a wave point of view, we would say that the wave is actually a sum of two nearly identical horizontal and vertical waves. From a QUANTUM point of view though, things are a little hairier. The photon basically has to answer "50% of the photons passed through are horizontal, and 50% of the photons passed through are vertical, and the correlations between the two give the appearance of diagonal polarization." However, photons can't talk. So the photon just plays his role, and if you pass enough of them through, half of them will be horizontal and half of them will be vertical.

And so because Bill chose incorrectly, he learns **NOTHING** from his reading of Abby's transmission. HALF of the time his measurement is one direction and HALF of the time it's another direction, and this is the case REGARDLESS of Abby's choice. As long as Abby chooses diagonally and Bill chooses rectilinearly, then Bill's measurement is NO BETTER THAN A COIN TOSS. (this goes for Eve too)

So by asking for one photon rather than an entire wave, Bill "collapses" the wave function. He loses all information about the correlations between the two rectilinear components, and thus he loses all diagonal information.

This is what is going on **BEHIND** the Heisenberg's Uncertainty Principle (HUP). Bill CANNOT KNOW **BOTH** diagonal polarization and rectilinear polarization. It's just an ill-formed question. Something cannot be BOTH diagonally polarized AND rectilinearly polarized. Simiarly, something cannot be both in ONE POSITION *AND* have ONE MOMENTUM. This is the essense of the HUP. It's a property of WAVES. The HUP is simply a CONSEQUENCE of the fact that EVERYTHING is a probabilistic wave function underneath it all.

Conclusion (the answer to the question)
Quote from barbaricprogrammer

Quantum encryption is nearly perfect but it doesn't offer the flexibility of the public key system, if i read it correctly you would have to calibrate each optical receptor/transmitter too send the data, but if not i believe you would also have to give them the key somehow other than publicly announce part of your key?

Quantum encryption IS a transfer of keys. That's ALL it is. It really should be called quantum key transfer or something like that.

So quantum encryption MAKES traditional encryption MORE FLEXIBLE, not less flexible. Traditional encryption CURRENTLY requires physical contact. Quantum encryption gives us a SECURE COMMUNICATIONS channel on which to send our KEYS **BEFORE** encryption.

See? Isn't that beautiful? Elegant? Really wonderful?

And now you can actually BUY packaged quantum channels that play the role of Abby and Bill automatically. They are connected by means of optical fiber. Right now the length of the fiber is restricted, but it's getting longer. Eventually we might be able to do this over trans-Atlantic fiber. Now, that'd be the day...

Quote from barbaricprogrammer

I've tried to read up on the subject but I've found various different explanations of quantum encryption algorithms mostly dealing with photonics.

I hope that explanation has given you the answer to your question while also giving you an idea of what all the photonics pages were talking about.

It's a complicated subject. It can take years just to get comfortable with all the vocabularly. However, the IDEA is a simple one. The complicated thing is actually figuring out how to implement the idea in nature.


 


appalling appalling
appalling appalling
email me email me
 
1135395 hits
(82 today)
 
Terms of Use
Ted Pavlic <ted@tedpavlic.com>   appalling appalling appalling appalling email me email me GPG Public Key: D/L, View, Ubuntu, MIT, PGP (verified) (ID: E1E66F7C) This Page Last Updated on Tuesday, February 12, 2019, 6:17 pm GMT