For The Love of Computing: “How Do I Prove That I Am Spartacus Without Showing My ID?”
February 7, 2016 • 109 Views • 12 Likes • 2 Comments
True story … I phone my bank … and my bank asks me for my password to prove that I am who I say I am, and I say “No! … I’m not giving you that”, and I say “Can you prove to me that you are my bank?” … and they say … “Well, you phoned us!” … and I say “but how do I know you are my bank?” … “We just are! Okay … give me your password” and I say “No!”, and they say “Well we can’t help you if you don’t give us your password” … and they hung up! Doh!
On the Internet, we give away so much information, and the more we give away, the more that our data can be used by others for malicious purposes. Every time we give away our date of birth, someone could use it to crack our bank account details. So how do we prove something, if we don’t want to reveal our data?
The Internet we have created uses a trust model, where we have a trusted party - Trent - which will check the information. But what if we don’t trust anyone on the Internet - how can we still check?
Oblivious Transfer (OT)
So how do we determine if someone is of a certain height or a certain age, without them giving away their height or age? One method is to use oblivious transfers, where Bob and Alice can exchange information, but not reveal their core data. The core of this is OT, which is a privacy enhancing technology (PET).
So let’s take a simple example. Let’s say that Bob is 5 feet 8 inches, and he has six boxes which he adds labels to: Box1 (5 feet); Box2 (5 feet 2 inches); Box3 (5 feet 4 inches); Box4 (5 feet 6 inches); Box5 (5 feet 8 inches); and Box6 (5 feet 10 inches). Bob then buys six padlocks and add them to each of the boxes (but does not lock them). He then throws away all the keys, apart from the one which relates to his height (5 feet 8 inches).
Bob then sends Alice all the open boxes, and she looks at the labels, and places a message in each. In boxes 1 to 5, she places “No!”, but in the box that relates to her height, she will put “Yes!”. As she is 6 feet tall, she puts “Yes!” into that box.
She then locks all the boxes with the padlocks provided by Bob, and sends them back to him. Bob can then only open one (the one that is 5 feet 8 inches), and finds the message of “No!”, and thus Bob knows he is not the same height as Alice. Eve, who has been listening, has no clue either what Bob’s height is, or Alice’s, or whether Bob and Alice are the same height.
In real-life, Bob uses public key to create six key pairs. He then sends six questions to Alice, and selects one key pair, and add the public key to the one that he wants to test for. He deletes all the other private keys, and sends the questions and associated public keys to Alice. Alice examines the questions, and answers them, and encrypts with the public keys provided, and sends them back to Bob. Bob then goes through all of the encrypted messages, and can only open one … which should reveal Alice’s answer.
The Internet we have created is flawed, and we give away too much information about our identify whenever we answer questions. If you want to find out if someone is more than 18 years old, why must they give away their age?
The revealing of passwords, for example, is so bad, and the minute you reveal your password, it is now open for those who hear it, to use it. We normally store passwords in a hashed format, where intruders cannot reverse them, but when we talk to our bank, we are expected to tell some OVER A TELEPHONE LINE … one of the most insecure methods of communication around … and to someone who we have no idea they are who they say they are. It is basically one-way authentication over an insecure channel.
We have applied OT into digital investigations, and an outline paper ishere. Our viewpoint is that an investigator should be able to investigate, without actually revealing what they are investigating.
So you have six people in your company (Bob, Alice, Eve, Trent, Carol, and Dan), and I suspect Eve, but need to know where she lives. So I generate six public keys, and send six questions to the company, asking where each of the people live. I delete five of my private keys, but send the six public keys with a question “Where does [name] live?”, and the company sends back the answers, and I can only read the one that is related to Eve… and so I have preserved the privacy of the others who are not in the investigation, and not revealed that Eve is the person I suspect.
And to show that some of the best Crypto people are from Poland, here’s Zibi’s PhD thesis here.
William BuchananProfessor at Napier University