'Zero knowledge' may answer computer security question

Aug 29, 2013 by Bill Steele

(Phys.org) —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. 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 , has developed a new protocol, or set of rules, to create what 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 , cryptography, auctions, 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, Oct. 27-29 in Berkeley, Calif.

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

Explore further: Quantum measurement carries information even when the measurement outcome is unread

Related Stories

Air Force grant to tighten online encryption

Dec 14, 2009

(PhysOrg.com) -- Computer scientist Rafael Pass is seeking new approaches to cryptographic security with a $600,000, five-year grant from the Air Force Office of Scientific Research.

Encryption is less secure than we thought

Aug 14, 2013

Information theory—the discipline that gave us digital communication and data compression—also put cryptography on a secure mathematical foundation. Since 1948, when the paper that created information theory first appear ...

Recommended for you

Fired Yahoo exec gets $58M for 15 months of work

9 minutes ago

Yahoo's recently fired chief operating officer, Henrique de Castro, left the Internet company with a severance package of $58 million even though he lasted just 15 months on the job.

Simplicity is key to co-operative robots

8 hours ago

A way of making hundreds—or even thousands—of tiny robots cluster to carry out tasks without using any memory or processing power has been developed by engineers at the University of Sheffield, UK.

Freight train industry to miss safety deadline

8 hours ago

The U.S. freight railroad industry says only one-fifth of its track will be equipped with mandatory safety technology to prevent most collisions and derailments by the deadline set by Congress.

IBM posts lower 1Q earnings amid hardware slump (Update)

9 hours ago

IBM's first-quarter earnings fell and revenue came in below Wall Street's expectations amid an ongoing decline in its hardware business, one that was exacerbated by weaker demand in China and emerging markets.

User comments : 0

More news stories

Simplicity is key to co-operative robots

A way of making hundreds—or even thousands—of tiny robots cluster to carry out tasks without using any memory or processing power has been developed by engineers at the University of Sheffield, UK.

Microsoft CEO is driving data-culture mindset

(Phys.org) —Microsoft's future strategy: is all about leveraging data, from different sources, coming together using one cohesive Microsoft architecture. Microsoft CEO Satya Nadella on Tuesday, both in ...

Floating nuclear plants could ride out tsunamis

When an earthquake and tsunami struck the Fukushima Daiichi nuclear plant complex in 2011, neither the quake nor the inundation caused the ensuing contamination. Rather, it was the aftereffects—specifically, ...

New clinical trial launched for advance lung cancer

Cancer Research UK is partnering with pharmaceutical companies AstraZeneca and Pfizer to create a pioneering clinical trial for patients with advanced lung cancer – marking a new era of research into personalised medicines ...

More vets turn to prosthetics to help legless pets

A 9-month-old boxer pup named Duncan barreled down a beach in Oregon, running full tilt on soft sand into YouTube history and showing more than 4 million viewers that he can revel in a good romp despite lacking ...