Position-based quantum cryptography theoretically proved

August 8, 2010 11:38 AM

Our results open a fascinating new direction for position-based security in cryptography where security of protocols is solely based on the laws of physics and proofs of security do not require any pre-existing infrastructure.
posted by Joe Beese (47 comments total)

I will apologize for this in advance.

So, I can only hack the Gibson in missionary then?
posted by Samizdata at 11:45 AM on August 8, 2010 [3 favorites]

actually starts reading the article
posted by Samizdata at 11:46 AM on August 8, 2010

Also you will need to be wearing rollerblades.
posted by Ouisch at 11:46 AM on August 8, 2010

It's pretty funny that "position-based quantum cryptography" basically emulates the functionality we had before communications technology. You know, like, writing shit down.
posted by mek at 11:50 AM on August 8, 2010

Anyway, the idea of not having a pre-shared key is awesome, of course. But I'm wondering how long it will take for the location itself to be infiltrated in some way in order to intercept messages.

Of course that would be difficult, far more difficult than intercepting and decrypting messages from afar, but I wouldn't put it past anyone with enough motivation and resources.

All in all, fascinating and so, so cool.
posted by Ouisch at 11:50 AM on August 8, 2010

You know, you can just link to the abstract, and then if it looks interesting, we can click on the PDF link ourselves.

Seriously.

Moreover, although this sounds nice, the security of the encryption protocol does not matter much when one can open a PDF on an iPhone can gain access to enough internals to jailbreak it, or when one can do similar things to pages in a browser, and so on.

Encryption is not the problem, our crappy software and users are.
posted by TheyCallItPeace at 11:54 AM on August 8, 2010 [3 favorites]

You know, like, writing shit down.

I'm not sure I get you. I mean, yes you can write shit down and leave it in a secure location, and then rotate interested parties in and out of the secure location to read it...but if you want to actually SEND a message from Point A to Point B, your security breaks down considerably.

Or am I totally not getting what you meant?
posted by Ouisch at 11:56 AM on August 8, 2010

anyone with enough motivation and resources

If the US government ever decides to truly serious about WikiLeaks, Julian Assange will break long before the 256-bit AES encryption of the "Insurance" file will.
posted by Joe Beese at 11:56 AM on August 8, 2010 [1 favorite]

What was that? A quantum shift in the earth time continuum did you say?
posted by infini at 11:58 AM on August 8, 2010

If the US government ever decides to truly serious about WikiLeaks, Julian Assange will break long before the 256-bit AES encryption of the "Insurance" file will.

Ah, the time-honored rubber hose method.
posted by Pope Guilty at 12:05 PM on August 8, 2010

TheyCallItPeace, I wish people would stop talking about "the problem". There is no "the problem". There are lots of problems out there; this paper proposes a kind of solution for one of them. This particular solution might not help with your problem, but it might help other people with theirs.

Also, yes, software is crap and users are stupid about security. Thus it is as it was and ever shall be, amen, until you change some fundamental aspects of human cognitive function.
posted by hackwolf at 12:06 PM on August 8, 2010

You know, you can just link to the abstract, and then if it looks interesting, we can click on the PDF link ourselves.

Seriously.

Sorry if you feel your electrons were squandered.
posted by Joe Beese at 12:08 PM on August 8, 2010 [2 favorites]

Ah, the time-honored rubber hose method.
posted by Pope Guilty at 12:05 PM on August 8 [+] [!]

Well, it's your standard brute-force attack.
posted by basicchannel at 12:08 PM on August 8, 2010 [6 favorites]

It's pretty funny that "position-based quantum cryptography" basically emulates the functionality we had before communications technology. You know, like, writing shit down.

Uh, What? Writing something down doesn't prevent it from being copied, or from being read somewhere it's not supposed to be read.

If the US government ever decides to truly serious about WikiLeaks, Julian Assange will break long before the 256-bit AES encryption of the "Insurance" file will.

The whole point of the "Insurance" file is that the government doesn't want to know, and it doesn't want anyone else to know. How will "breaking" Assange help with that?
posted by delmoi at 12:11 PM on August 8, 2010

Julian Assange will break long before the 256-bit AES encryption of the "Insurance" file will.

True, but...this is referring to a brute-force decryption, right? And not infiltrating the position that would provide the key to the encryption?

Because, if you get the key, it kind of doesn't matter how big the lock is...or am I totally misunderstanding something?
posted by Ouisch at 12:14 PM on August 8, 2010

Ah, the time-honored rubber hose method.

It's called Rubber-hose cryptanalysis, and the way around it is with Deniable encryption, where no one can prove that a certain plain text is the only one hidden in a cyphertext.

The notion of "deniable encryption" was introduced by Julian Assange & Ralf Weinmann in the Rubberhose filesystem[1] and explored in detail in a paper by Ran Canetti, Cynthia Dwork, Moni Naor, and Rafail Ostrovsky[2] in 1996.

Anyway, the whole point of the insurance file is that the government want to keep it secret from everyone else, not that they want to crack it. In fact, it would work best if the attackers already know the plaintext, and therefore the risks of it's publication.
posted by delmoi at 12:16 PM on August 8, 2010 [4 favorites]

the whole point of the insurance file is that the government want to keep it secret from everyone else, not that they want to crack it. In fact, it would work best if the attackers already know the plaintext

This is my understanding as well. So I'm getting a bit of a non-sequitur feeling with some of the comments here.
posted by Ouisch at 12:18 PM on August 8, 2010 [3 favorites]

Can someone explain this to me?
posted by Azazel Fel at 12:19 PM on August 8, 2010

Azazel: my understanding, from my strictly amateur understanding of cryptography and signals intelligence, is that, even if you are able to encrypt a message with the fanciest of encryptions, the weak link is security is the fact that the person receiving your message has to also receive the key to decrypting it.

The possibility of the encrypted message AND the key to "unlocking" it being intercepted by an outside party is, if not really high, at least extant.

However, with position-based cryptography, the key to decrypting the message is the intended receiver's LOCATION ITSELF. Which is probably a secured military site, or else some incredibly obscure, hidden and/or isolated spot where it's highly implausible that anyone except the intended recipient would be.
posted by Ouisch at 12:23 PM on August 8, 2010

There is a hilarious conversation about this and someone's cat taking place on Schneier's blog.

Thanks for the link Joe Beese this is rad.
posted by special agent conrad uno at 12:30 PM on August 8, 2010

(And, the quantum component erases the possibility of the position being spoofed by an interceptor, if I'm understanding this correctly.)
posted by Ouisch at 12:35 PM on August 8, 2010

Oh dear. Not again. Ooops.
posted by infini at 12:39 PM on August 8, 2010

Good point hackwolf.

I guess what I really meant was we are far form having quantum crypto/key distro revolutionizing computer security, especially when we consider the throughput in the current implementations (crazy low compared to any rates in modern day telecom).

Basically, I wanted to say don't get your hopes up quite yet, and work on the standard crypto stuff will go a long way before quantum crypto becomes truly practical.

(I do research in quantum info, btw, so I am not being just a naysayer.)
posted by TheyCallItPeace at 1:13 PM on August 8, 2010

hidden and/or isolated spot

Security through obscurity works!
posted by yerfatma at 1:29 PM on August 8, 2010

This sounds like a regular password system where the password is your current location. Except that the space severely restricted (since you can rule out land masses for submarines, etc.) and the whole thing is extremely inconvenient (can't go to receive your messages until you're sure no-one's watching). I also find it dubious that the issue of 100% accurate and verifiable position verification is hand-waved away since I would expect that to be the most easily breakable part.
posted by No-sword at 1:47 PM on August 8, 2010

Security through obscurity works!

Hey, I'm not saying this is how it SHOULD work. But it might be the only option in some kind of weird or sticky situation.
posted by Ouisch at 2:00 PM on August 8, 2010

The key is coming from inside the house!
posted by Babblesort at 2:14 PM on August 8, 2010 [1 favorite]

I also find it dubious that the issue of 100% accurate and verifiable position verification is hand-waved away since I would expect that to be the most easily breakable part.

I'm not sure it's exactly hand-waving if the entire paper is about solving this precise problem.
posted by Ouisch at 2:28 PM on August 8, 2010 [3 favorites]

where security of protocols is solely based on the laws of physics

Based solely on our understanding of the laws of physics not changing. What happens when our understanding changes? I just read about a new discovery of how to violate Heisenberg's Uncertainty Principle. How would that affect quantum crypto?
posted by scalefree at 2:35 PM on August 8, 2010

Based solely on our understanding of the laws of physics not changing. What happens when our understanding changes?

Another commenter brought up that same point on the Schneier blog. Someone else answered it with an analogy to One-Time Pads (which are created using random number generation):

"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."

I think it's an interesting question.
posted by Ouisch at 2:52 PM on August 8, 2010

However, with position-based cryptography, the key to decrypting the message is the intended receiver's LOCATION ITSELF.

The location plus a password would do it for me. Or a written signature. Digitalized analysis must be pretty good by now.
posted by five fresh fish at 2:55 PM on August 8, 2010

In fact, being at the right location and also having the right written password signed with a flourish would be pretty damn fine, IMO.
posted by five fresh fish at 3:00 PM on August 8, 2010

Mind, I'm still thinking doing it preshared keys would work fine in the case of credit cards.
posted by five fresh fish at 3:05 PM on August 8, 2010

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.

I'm not sure there's much in that statement, is there? We can prove the characteristics of something with the knowledge of math and technology that we have on hand. We can't say much useful about what is possible with hypothetical knowledge that we don't have.
posted by Blazecock Pileon at 3:11 PM on August 8, 2010

We can't say much useful about what is possible with hypothetical knowledge that we don't have.

I think that's what the commenter was getting at. Personally, I think that if an encryption method requires a new discovery in physics in order to decrypt it....that's pretty decent encryption.
posted by Ouisch at 3:15 PM on August 8, 2010 [1 favorite]

Only in the future, of course, -all- sophisticated public algorithms will have to be assumed to be compromised, especially quantum. Considering the average age of today's law force, it may just be possible to go back to microdo beauty marks again.

Have you seen my monograph on cigar ash? It's in that place I put that thing that time.
posted by Twang at 3:35 PM on August 8, 2010

Well, ousich, the public key cryptography only needs a new advance in mathematics to break it...

My (probably wrong*) understanding of this is that you would do something like the following:
Alice wants to send a message to Bob, and Bob goes to the Secure Location. In the secure location is a pseudo-random number generator started with a particular seed that spits out one digit every five seconds; Alice has a generator running the same algorithm. Then Bob could verify his location by reading off the digits on the number generator until sufficient certainty had been reached. Then part two of the algorithm would send the actual data for Bob to read, presumably encrypted/decrypted by the same devices doing the random number generation, so that no exchange of keys between Alice and Bob is necessary.

So basically, Alice would have a trusted relationship with a particular computer terminal, and then Bob would prove that he was at the computer terminal in order to receive the information.

(* - having been yelled at before for expressing my limited understanding of a topic in the informal setting of the Blue, I advise you not to apply the information contained in this comment in the context of heart surgery or nuclear crisis.)
posted by kaibutsu at 3:36 PM on August 8, 2010

* - having been yelled at before for expressing my limited understanding of a topic in the informal setting of the Blue

Well, I'm happy to discuss it with anyone who is actually reading the info and trying to understand it. What the hell do I know, I'm a nutrition student. It's just an interesting topic -- not like we're actually contributing to the literature on quantum cryptography here. We're all bored amateurs, until someone who works in the field shows up to enlighten us.

Anyway, my understanding of the current scheme is that, if the actual* position (*actual, meaning that, due to the non-cloning principle, the location can't be spoofed by two intercepts colluding to solve for x and successfully transmitting x back to the two separate verifiers) of the intended receiver is crucial to compiling the encryption key, then unless there is a way of two receivers existing in the same space at one time...then interception of the key is impossible.

That said, again, what the hell do I know? IS there a known way in physics for two separate bits of matter to inhabit the same space at the same time? I honestly don't know -- seems like it should be impossible, but, as we all know, shit is weird.
posted by Ouisch at 3:49 PM on August 8, 2010

I'm not sure it's exactly hand-waving if the entire paper is about solving this precise problem.

All entities can perform arbitrary quantum (and classical) operations and can communicate quantum (and classical) messages among them. For simplicity, we assume that quantum operations and communication is noise-free; however, our results generalize to the more realistic noisy case, assuming that the noise is low enough. We require that the verifiers have a private and authentic channel among themselves, which allows them to coordinate their actions by communicating before, during or after protocol execution. [...] we assume that messages to be communicated travel with the speed of light [...] We assume on the other hand that local computations take no time. [...] Finally, we assume that the verifiers have precise and synchronized clocks [...] However, we do assume that P’s clock only runs forward (i.e. P cannot be reset).

This all struck me as extremely assume-y for something that would eventually have to work in the real world, but I will admit I am not hip to the implementation of quantum cryptography. Maybe it is reasonable, or at least reasonable enough for government work. In that case, I cheerfully stand corrected. (In either case I allowed snark to override fairness to the authors, and that was unhelpful of me.)
posted by No-sword at 3:56 PM on August 8, 2010 [1 favorite]

We require that the verifiers have a private and authentic channel among themselves, which allows them to coordinate their actions by communicating before, during or after protocol execution.

Yes, I can see this, in particular, as being a potential weak point.
posted by Ouisch at 4:01 PM on August 8, 2010

I was a little skeptical before I read the paper, but wow, this is neat stuff. Unless you're a privacy buff, in which case you'll immediately be freaked out by the idea that someday providers will require unspoofable location verification on demand. If you thought DVD region coding was a pain in the ass to get around now...
posted by phooky at 4:10 PM on August 8, 2010 [1 favorite]

You know I noticed a lot of folks been getting hip to Cryptography ever since the Mathematics Illuminated" website, which contained The Primes and RSA encryption in the first chapter, was posted on the blue. I'm on the Topography chapter, where are you?
posted by Student of Man at 4:18 PM on August 8, 2010

I hadn't seen that. It's neat.
posted by Ouisch at 4:23 PM on August 8, 2010

Can I just make a plea to science article writers?

Look, I actually like LaTeX a lot, but please for all that is good and holy, don't use the default font that comes with the package! It's ugly and completely unreadable. Just use, you know, any of the other fonts that have been available for the past few decades. I'm personally fond of Palatino but knock yourself out with anything other than Computer Modern.
posted by Deathalicious at 5:31 PM on August 8, 2010

Deathalicious: Shit, with XeTeX or LuaTeX you can now use any arbitrary font. For this paper you would want one with a good math font, but that's not that hard to find.

/f*ck you, "NFSS"
posted by PsychoTherapist at 7:53 PM on August 8, 2010

It's called Rubber-hose cryptanalysis, and the way around it is with Deniable encryption, where no one can prove that a certain plain text is the only one hidden in a cyphertext. (delmoi)

The wikipedia page for this used to also point out that while deniable encryption prevents the attacker from discovering that he's been given a red herring, it also prevents the defender from proving that he's given the real message. As a result, external considerations like human rights notwithstanding, it makes as much sense to continue the interrogation indefinitely as it does to stop at any point (or never to begin).
posted by d. z. wang at 8:25 PM on August 8, 2010

Wait, I know, we'll torture them with our logic until they beg and plead for release
posted by infini at 11:02 AM on August 9, 2010