Schneier on Security

A blog covering security and security technology.

« Eavesdropping Smartphone Apps | Main | UAE to Ban BlackBerrys »

August 3, 2010

Location-Based Quantum Encryption

Location-based encryption -- a system by which only a recipient in a specific location can decrypt the message -- fails because location can be spoofed. Now a group of researchers has solved the problem in a quantum cryptography setting:

The research group has recently shown that if one sends quantum bits -- the quantum equivalent of a bit -- instead of only classical bits, a secure protocol can be obtained such that the location of a device cannot be spoofed. This, in turn, leads to a key-exchange protocol based solely on location.
The core idea behind the protocol is the "no-cloning" principle of quantum mechanics. By making a device give the responses of random challenges to several verifiers, the protocol ensures that multiple colluding devices cannot falsely prove any location. This is because an adversarial device can either store the quantum state of the challenge or send it to a colluding adversary, but not both.

Don't expect this in a product anytime soon. Quantum cryptography is mostly theoretical and almost entirely laboratory-only. But as research, it's great stuff. Paper here.

Posted on August 3, 2010 at 6:25 AM • 26 Comments

To receive these entries once a month by e-mail, sign up for the Crypto-Gram Newsletter.

Comments

This is great stuff and could be potentially ground breaking.

I can see it having many uses for classified systems in the future.

Posted by: Dan at August 3, 2010 8:34 AM

See if they can find my cat.

Posted by: BF Skinner at August 3, 2010 8:58 AM

@ BF Skinner,

"See if they can find my cat"

Why has it got out of the box again?

You really should look out for it better, otherwise there's a good probability it won't last much longer.

Posted by: Clive Robinson at August 3, 2010 9:29 AM

The security of quantum encryption is based on physics, rather than on math. But this same security depends on the assumption that there are no presently-unknown principles of physics that can be used to break the encryption. This assumption can NEVER BE PROVEN. And so, unlike OTP, quantum encryption can never be said to be provably unbreakable.

Posted by: Descartes at August 3, 2010 9:32 AM

Wouldn't a location-based key have a small enough search space as to be trivially broken through a brute-force attack?

Divide the surface area of the planet (for or even better, the land area) by the resolution of the reciever (probably not much better than a few meters.

Wikipedia says 148,940,000 km2 land, assuming 5m resolution that gives you roughly 5.9 x 10^12 potential locations. If we know what country we're looking in and start checking locations in urban centers, that could narrow the keyspace even more.

Posted by: Ryan at August 3, 2010 9:42 AM

@Descartes

How is Physics not Math, or at least reliant upon mathematics? (Galileo, Assayer)

Posted by: Dan at August 3, 2010 11:15 AM

@ryan

I think the point here is that if an agent in Iran sent an encrypted text that could only be decrypted in the US Secretary of Defense's office, it might not matter that much if an attacker could figure out that the key is to be in the SecDef's office, you'ld still have to get there.

Posted by: Christopher at August 3, 2010 11:26 AM

@ryan

Christopher makes a good point. As the article suggests, the security is reliant upon the physical security and security of the perimeter of the location that the key is based from.

I don't see the DoD using this and assigning the key to a café off Pennsylvania Ave.

Posted by: Dan at August 3, 2010 11:34 AM

@descartes,

The same thing can be said of your OTP - it's only as good as the random number generator, which is based on physics. If there is something as yet unknown about radioactive breakdown or thermal noise or whatever you are using for your RNG source, then we can't say that the OTP is entirely unbreakable either.

Posted by: posedge clk at August 3, 2010 11:51 AM

@ Dan,

"How is Physics not Math, or at least reliant upon mathematics?"

I think you have the cart before the horse.

Physics happens all by it's self without any assistance from mathmatics.

Mathmatics is an intangable invention of man used to very imperfectly model the tangable physical world so that man may better understand it.

Afterall the apple fell on Newton before his mathmatics described how (and good as it was Einstien got a little closer, but not all the way).

Posted by: Clive Robinson at August 3, 2010 1:01 PM

@ Ryan,

"Wouldn't a location-based key have a smal enough search space as to be trivially broken through a brute-force attack"

It's not a "specific geographic" location but a location in time from a number of points.

From the paper the first example has to verifiers connected by the shortest path with the prover on this path at some point.

One of the verifiers sends a qbit, the other a polarisor position, if you read it carefully both of the verifiers have to know the exact distance they are from prover so that the qbit and polarizor arive simultaniously. Which means both verifiers have to know exactly how far the are from each other as well to calculate the delay in time.

There are several issues around this, one being the propagation speed of the transmission media (light only travels at 3e8M/Sec in a vacum in all other mediums it is slowed.

Also in reality no two points on the earth a reasonable distance apart are connected by a transmission medium that is only the shortest path in length. A fiber Optic cable will usually be 10 to 20% longer than the shortest path length.

Posted by: Clive Robinson at August 3, 2010 1:20 PM

So how do this fare under the imperfect-transmission and imperfect-detection stuff that allowed an attack on an instantiated QC system?

Posted by: paul at August 3, 2010 2:13 PM

When I try to view your page about the UAE and Blackberries (or its comments) I get this message (using Firefox 3.6.8):

Content Encoding Error

The page you are trying to view cannot be shown because it uses an invalid or unsupported form of compression.

Posted by: billswift at August 3, 2010 4:23 PM

@Descartes: I'd be a little more concerned that this involves applying some very tricky laws of physics properly, without leaving any implementation weaknesses to exploit.

Posted by: David Thornley at August 3, 2010 4:33 PM

@billswift - Firefox caching bug. Clear caches and restart, or try another browser

Posted by: Jay at August 3, 2010 7:45 PM

@ BF Skinner: We found your cat.

The good news is, it's alive.

The bad news is, it's dead.

Congratulations, and our condolences.

Posted by: Tom T. Schrödinger at August 3, 2010 11:13 PM

For those who are interested to learn more on Quantum Cryptography; check this:
http://www.idquantique.com/training-services/...

Posted by: Widmer Leonard at August 4, 2010 2:55 AM

thanks for all your kind regard.

It is very un-certainly my cat.

Posted by: BF Skinner at August 4, 2010 10:53 AM

I know I'm a nerd when I actually laugh at that whole exchange about the cat...

Posted by: Count0 at August 4, 2010 11:32 AM

Theres a movie plot here ... somewhere. Acme Quantum Crypto Inc is storing something really important for lots of folks at a secret location using this technology. As they prepare to move offices, they have to decrypt the data first (before they could re-encrypt it at their new location with a new super duper location aware crypto key). The unencrypted hard drives are sent by a courier truck that gets ambushed on the way. Cue the ransom demands ...... Far fetched, and impractical ... just like location aware quantum crypto!

Posted by: mooman at August 4, 2010 1:21 PM

@ BF Skinner: So, according to your theory, the cat both does and does not belong to you at the same time?

(Actually, most persons with feline housemates have known that for years, even if they know nothing of physics.)

@ Count0: That's as good a definition as any.. :-)

Posted by: Tom T. at August 4, 2010 10:11 PM

It is the most superb achievement in cryptography and security

Posted by: lava kafle at August 5, 2010 6:28 AM

Is the definition of location somehow implicit in this observation? If you have two boxes, identical in every way, why is box 1 different and in a different location than box 2? Are these two elements of quantum behavior somehow entwined to determine location? If not, any suggestions as to what does?

Posted by: Dr. Edward Kimble at August 5, 2010 2:57 PM

@Tom T. "the cat both does and does not belong to you at the same time? "

If it does I'll be in small claims court forever. The law just ain't set up for probablility.

Do I maybe own the cat or does the cat maybe own me?

Posted by: BF Skinner at August 6, 2010 6:28 AM

@Dr. Edward Kimble

There exists at least one method of encryption based upon location that uses classical physics and triangulation to establish your location. It is considered pretty solid, as I understand it. However, it has been proven that by exchanging certain information, colluding involved parties can tamper with this method, thus faking the location.

However, the colluding parties must exchange certain information. If the quantum physics-based method is used, it becomes possible to either keep the information, or send it to your colleagues in the collusion, but not both. Since that way only one of you has the information, you cannot collude. This removes the flaw from the current method based upon triangulation.

It also makes it far less practical. Ah, well.

Posted by: Geek Prophet at August 6, 2010 11:50 AM

@ BF Skinner, "Do I maybe own the cat or does the cat maybe own me?"

Yes.

Posted by: Tom T. at August 7, 2010 12:09 AM

Subscribe to comments on this entry