Einstein's theory of special relativity could help create unhackable ATMs

It's Monday morning and you're headed to grab an espresso from a corner cafe. Upon entering, you run into the dreaded "cash only" sign. "No problem," you think, wandering to the nearest ATM. You arrive at the machine, slip out your debit card, insert its worn chip and cup your hands into mini-shields while punching in your secret PIN. 

During the process, however, sly thieves might have seen past your humble security measures. They may have even preemptively hacked the cash machine to collect your code. To withdraw money for coffee, you've actually risked theft. 

Could there be a safer way to do this? A team of researchers hailing from Canada and Switzerland are determined to find out. They published a blueprint in the journal Nature earlier this month that detailed an ultra-secure cash machine that would completely reinvent the system.

"The assumption of trusting the device when you are doing anything related to identification is kind of a problem, at least at the fundamental level," said Sébastien Designolle, a physicist at the University of Geneva and co-author of the study.

"Drop all assumptions" is the motto he and fellow researchers abided by while coming up with a more secure mechanism to retrieve cash.

Anchoring their far-fetched idea with physicist Albert Einstein's theory of special relativity, they propose replacing the PIN system with what's called a zero-knowledge proof. 

Here's how it works.

Proofs in practice

Remember brain teasers? Zero-knowledge proofs are like a grownup version of such mind games. In cryptography, which is the study of secure communication, they're a method by which party A proves to party B that they know something. The catch is, party A, the prover, can't reveal the information they know to party B, the verifier.

But there's a way for party A to get around the caveat.

Suppose you have a friend named Jones who can only see in black and white, but you can see in color. Your objective is to prove to Jones you can, in fact, see color. If you were to use a zero-knowledge proof, it might go something like this:

Jones holds a red card and a blue card before you. Then, behind his back, he either swaps them or doesn't swap them. Laying them out in front of you again, he asks, "Did I swap them?"

The game could be repeated a hundred times, and you'll always have the correct answer because you can see the colors. After many iterations, Jones would eventually say, "Alright, I believe you. You can see color." At that point, you've shown him your color-identifying ability without revealing the colors you see.

"In our study," explained Designolle, "the proof is the three-colorability of a graph." 

There's some lore behind the idea. Three-colorability is a notoriously difficult mathematical problem that theorists have studied for years. It posits the question: How can you color an enormous map of shapes with three shades such that the same colors never touch? 

This wouldn't be like world maps we're used to. It'd be so huge that humans need technology to comprehend it, but even with such help, Designolle said it would take years to find a three-colorability solution.

Taking the concept to ATMs, he suggests giving everyone a device holding a uniquely colorized map with a preprogrammed three-colorability solution. To withdraw cash, you'd plug the device into an external outlet on the ATM, the verifier in this case. 

The machine would query your device, or prover, with hundreds of thousands of questions regarding sections of your map's colors. Despite the complexity of three-colorability, your device would immediately answer because it's been preprogrammed. 

Further, because every round of queries is randomized, even if the verifier asks about different edges, the ATM would never receive enough information to know the full map, Designolle explained, "which is the crucial point." 

Eventually, like in the situation with Jones, the ATM will verify your identity and roll out your cash because of your device's consistently correct answers -- like the way Jones said, "Alright, I believe you. You can see color." Ta-da.

But, remember, drop all assumptions

The invention seems solid -- to me, at least. But Designolle and his team aimed to drop all assumptions. They still didn't completely trust the security of the three-color map system.

Hypothetically, they argue, someone could record your device's sparse answers about its map and attempt to reverse calculate the full picture, enabling them to fake your identity. 

"Those functions that you can perform in one direction are very difficult, but not impossible, to compute in the other direction," Designolle said.

For example, if you multiply two prime numbers and get a very big number, it's difficult to go back to the elementary numbers. But that doesn't bar it from being done. The same applies to three-colorability.

So, how can we take these machines to a level of unconditional security? Designolle thought, well, what about invoking two devices? 

"The idea behind this is precisely the same as a policeman investigating and asking two separate suspects [questions] in different rooms, so that they can't communicate," Designolle said. "If they are telling the same version of the story, then it's a good hint they actually are telling the truth." 

Back to the cash machine. 

With two devices, you'd divide yourself into two provers, like the two suspects. Then, two verifiers, ATMs, will simultaneously ask its respective prover the usual three-colorability questions. 

Yes, you would have to plug two separate devices into two separate ATMs. At present, the researchers say the system works with the ATMs standing 60 meters (about 196 feet) apart. But they say they can get it down to a meter, or about 3 feet. It sounds overly complicated, but remember, the purpose of the experiment is to illustrate what an unconditionally secure cash machine mechanism might look like. It's theoretical -- for now, at least.

If each prover appears to hold the same, incalculable knowledge, it'd be safe to say that your identity is verified. 

And like the criminal suspects, the devices wouldn't be able to communicate with each other. Any potential hacker would need to reverse calculate not one, but two, complex maps at the exact same time, an exceptionally challenging -- if not impossible -- task.

Here's the moment you've been waiting for -- where Einstein comes in. The reason these devices wouldn't be able to communicate is they'd be bound by Einstein's theory of special relativity.

We can't travel faster than the speed of light

Einstein's theory of special relativity beautifully marries the realms of space and time. But more importantly for Designolle's team, it also leads to constraints on how fast information travels.

"With special relativity," Designolle said, "it seems quite reasonable to believe in this not computational but physical assumption ... that information cannot go faster than the speed of light."

As long as the two ATMs ask their respective plugged-in, map-filled devices questions quickly enough for lags to always remain shorter than the time needed to transfer information -- restricted by the speed of light -- we'd guard against the possibility of the devices talking to each other. 

In a sense, the provers couldn't check their "alibis" to fake an identity.

There's just one, final issue. These relativistic constraints aren't so airtight when it comes to nonconventional physics. Enter quantum computing.

Quantum loopholes and exiting a hypothetical world

Light works differently in the quantum world. Quantum mechanics allows for a fascinating principle called quantum entanglement. Put simply, when two quantum particles -- namely, light particles -- are entangled, they can instantaneously communicate. 

It's not even a matter of how fast the information travels. It's immediate. If particle A holds knowledge of something, you can be absolutely sure particle B already knows it too.

"Suppose that I do not have the coloring of a graph, but I want to pretend that I do," Designolle said, referring to a potential hacker. "I could come up with a procedure using quantum entanglement between the two chips to answer the questions correctly. In a way, I can cheat."

While Designolle's team believes their mechanism should be able to guarantee safety from quantum hackers, they're not sure. However, they're currently pondering whether the protocol could itself use quantum provers instead of standard devices.

And if you've gotten this far, you might be wondering exactly how theoretical these ultra-secure ATMs are. Is it even possible to bring them into reality? 

Right now, Designolle said, the main issue is cost. In order to create the devices needed for the mechanism, the chips can't be the same type we find on our debit cards today. They will have to be extremely powerful, which means they'll likely be very expensive. One idea he has is to invoke the system for large companies that trade secure information and can afford the pricey chips.

That would actually make the relativistic constraints looser because there would be a greater distance between each party's device and the verifying "cash machine," so light would take longer to travel. This means there'd be more room for lags before hackers can penetrate the system.

But aside from the realistic applications, Designolle said, "On a personal note, it was really interesting just to see that sometimes something very simple is actually hard to come up with. ... At some point, yes, this occurred, but it was not very clear from the beginning that it would be so simple in the end."