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.

Tags: academic papers, cryptography, encryption, quantum computing, quantum cryptography, spoofing

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

Comments

Dan • August 3, 2010 8:34 AM

This is great stuff and could be potentially ground breaking.

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

BF Skinner • August 3, 2010 8:58 AM

See if they can find my cat.

Clive Robinson • August 3, 2010 9:29 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.

Descartes • August 3, 2010 9:32 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.

Ryan • August 3, 2010 9:42 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.

Dan • August 3, 2010 11:15 AM

@Descartes

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

Christopher • August 3, 2010 11:26 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.

Dan • August 3, 2010 11:34 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.

posedge clk • August 3, 2010 11:51 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.

Clive Robinson • August 3, 2010 1:01 PM

@ 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).

Clive Robinson • August 3, 2010 1:20 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.

paul • August 3, 2010 2:13 PM

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

billswift • August 3, 2010 4:23 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.

David Thornley • August 3, 2010 4:33 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.

Jay • August 3, 2010 7:45 PM

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

Tom T. Schrödinger • August 3, 2010 11:13 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.

Widmer Leonard • August 4, 2010 2:55 AM

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

BF Skinner • August 4, 2010 10:53 AM

thanks for all your kind regard.

It is very un-certainly my cat.

Count0 • August 4, 2010 11:32 AM

I know I’m a nerd when I actually laugh at that whole exchange about the cat…

mooman • August 4, 2010 1:21 PM

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!

Tom T. • August 4, 2010 10:11 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.. 🙂

lava kafle • August 5, 2010 6:28 AM

It is the most superb achievement in cryptography and security

Dr. Edward Kimble • August 5, 2010 2:57 PM

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?

BF Skinner • August 6, 2010 6:28 AM

@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?

Geek Prophet • August 6, 2010 11:50 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.

Tom T. • August 7, 2010 12:09 AM

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

Yes.

Location-Based Quantum Encryption

Comments

Leave a comment Cancel reply