Posted on 09/03/2013 9:35:49 AM PDT by null and void
In the age of the Internet, it’s getting harder and harder to keep secrets. When you type in your password, there’s no telling who might be watching it go by. However, new research at Cornell may offer a pathway to more secure communications.
The answer is to not send sensitive information at all. Rafael Pass, associate professor of computer science, has developed a new protocol, or set of rules, to create what computer scientists call a “zero knowledge proof.”
“I think zero knowledge proofs are one of the most amazing notions in computer science,” Pass said. “What we have done is to combine it with another notion — that it’s easier to prove that a computation can be done correctly than it is to actually compute it.”
The result is a way to prove that you know something without saying out loud what it is you know. Instead of insecurely typing the password for your bank account, you just prove to the bank that you know the password. You could pass an exam by proving that you know the answer, without actually writing the answer down so the person sitting next to you can’t copy it.
Applications include password authentication, cryptography, auctions, financial transactions and online voting. “At this point it’s purely theoretical,” Pass cautioned, “but it is teaching us a lot more about how zero knowledge works. That’s what makes me excited.” Pass and colleagues will describe their work at the 54th Annual IEEE Symposium on Foundations of Computer Science, October 27 to 29 in Berkeley, CA.
In its simplest form, such a proof consists of answering questions that depend on having the secret knowledge. To prove you have been in my house, I might ask you what color my cat is. The idea has been around since 1985, and there are already many ways to do it. Early versions required only a few messages being passed back and forth, but were insecure if an attacker participated in many proofs at the same time, as can easily be done on the Internet. An attacker could pick up a little bit of information from each exchange, piecing together the whole secret. Some newer methods will remain secure over many simultaneous exchanges, but instead require many messages being passed back and forth. The new protocol gets the job done with as few as 10 exchanges, Pass said, while remaining secure over many simultaneous exchanges. The researchers supply a rigorous mathematical proof that the protocol is a true zero-knowledge system, and that it works with just a small number of exchanges.
The proof that a zero-knowledge protocol works is the ability to construct a “simulator” that generates a fake conversation indistinguishable from a real one using the protocol, showing that whatever attack the intruder uses against the real conversation produces the same result as attacking the simulation. In other words, the intruder can learn nothing from the real conversation that he couldn’t have learned for himself by running the simulator. But running the simulator requires a lot of computer time, especially if there are many exchanges. The new protocol instead sends a “P-certificate,” certifying that the simulator has been proven to work. A computer program is just a series of logical steps; that it generates a particular output can be proven like any other mathematical statement.
The next step, Pass said, will be to apply the idea to the “man-in-the-middle” attack, where an intruder slips in between two parties to a conversation, making them think they’re talking directly to each other, not only to listen in but sometimes to change the messages as they pass through.
The idea of a zero knowledge proof was introduced by Shafi Goldwasser, Silvio Micali and Charles Rackoff at MIT. This year Goldwasser and Micali received the Turing Award (the equivalent of a Nobel Prize in computer science) for this and related discoveries.
Although I am always a little skeptical about any claim to uncrackability.
“...Turing Award (the equivalent of a Nobel Prize in computer science)...”
Given the completely besmirched reputation of the word “Nobel”, ‘twould be better for the Nobel prizes actually requiring intellect and achievement (physics, medicine, etc) to be renamed. The peace and literature prizes have reduced the reputation of the present name to the equivalent of “Yugo” in the automotive world.
Slightly off topic, see tagline...
Zero Knowledge Proof sounds like a Zero-Sum Gain, IMO...
The Internet is consistent proof of the existence of Zero Knowledge...
Making an attacker have to intercept multiple tests, would definitely make it harder.
The downside is that now when I forget my password, and don’t realize I forgot my password, I’ll be sitting through multiple tests before I realize what I no longer know.
Making an attacker have to intercept multiple tests, would definitely make it harder.
The downside is that now when I forget my password, and don’t realize I forgot my password, I’ll be sitting through multiple tests before I realize what I no longer know.
This isn't new. algore used this method in the eighties to prove global warming.
Agreed, but many of the Nobel Prizes wimped out on the revolutionary, or controversial science things. When they gave it to Einstein, it was for the photo-electric effect, not relativity, either special or general.
Meta questions for authentication have been used for years. One of the prime problems with passwords is currently requiring passwords that cannot be remembered, even with “security” hints. More than seven letters, upper and lower case, with a number and a symbol...If it is a password that is used infrequently or lost good luck! Writing them down is becoming a necessity, violating the physical security of the password in favor of the electronic security.
This is interesting stuff.
DK
So in a sense, wouldn’t this be like directly using those “secret” questions to gain site access instead of simply to retrieve or reset p/w’s?
It’s Tuesday.
You don’t have to know your password. You just have to prove that you should know it.
Sounds like ‘20 Questions’.
Is it animal, vegetable or mineral?
Is it bigger than a breadbox?
Can you put it in your pocket?.......
I think this is just a personalized version of the Eliza idea. Can a computer hold a conversion with a person that is indistinguishable from another person? Can you think of something about a piece of information about a person that does not require disclosing the original info? Oddly enough that is the prime question in reincarnation, because once you disclose the type of information you will seek, people that want to deceive will target that type of info.
The bottom line is always from that great line...three people can keep a secret...if two are dead.
DK
what they are saying could maybe be said as the following
it might be more secure for your bank to NOT ask for a “password” but to somehow crypticly ask, and you cryptically answer, your “security questions” - the ones you set up with them for the questions they would ask to confirm it was you who was admitting your forgot your password
Ref. my point ;)
It's not going to ask you for your password, but it's going to ask you about your password. And if I've forgotten it again, I'll be answering the questions wrong.
It's not going to ask you for your password, but it's going to ask you about your password. And if I've forgotten it again, I'll be answering the questions wrong.
“Instead of insecurely typing the password for your bank account, you just prove to the bank that you know the password.”
And how does my bank KNOW I’m right? It has to KNOW my password.
So if my password is “0bama is a jerk”
will it ask me what the 4th word is? And I type ‘jerk’?
Will it ask me how many A’s in the password? and I type 3?
Splain some more.
Disclaimer: Opinions posted on Free Republic are those of the individual posters and do not necessarily represent the opinion of Free Republic or its management. All materials posted herein are protected by copyright law and the exemption for fair use of copyrighted works.