22-10-2012, 12:07 PM
ZERO KNOWLEDGE PROOF
ZERO KNOWLEDGE.doc (Size: 410 KB / Downloads: 24)
Introduction:
In 1986, Manuel Blum claimed in his paper ”How to Prove a Theorem So No One Else Can Claim It” that he could apply zero-knowledgemethods to proving theorems in any proof system. He sketched a proof of this result, but gave no details. We give a background of zero knowledge proofs and examine their applicability to the propositional calculus. Wethen examine Blum’s claim, assuming the existence of a proof verifying program which can be modeled with a finite state machine, and complete the proof. However, we also show that zero knowledge proof demon-strating knowledge of a proof is no easier than actually determining a proof of a theorem from scratch.
Ever since the concept of zero-knowledge was first articulated, a large number of problems that can be exploited for their use have been identified, and a large number of applications determined. In particular, it has been determined that the entire class of NP complete problems has associated zero-knowledge proofs, subject to a few assumptions. One of the most interesting applications, however, is the idea that actual mathematical theorems are provable in zero-knowledge. This idea was first put forth by Blum in, but he goes into little detail of just how this is to be accomplished, although as Bruce Schneier points out in, Blum could have published these results without revealing them. Schneier states that the protocol involves mapping the problem onto the Hamiltonian cycles problem, where by successfully proving a theorem becomes equivalent to finding a Hamiltonian cycle in a graph although this is not clearly stated. In short, while it seems to be accepted that proving theorems in zero knowledge is possible, those who know how this is done have not seen fit to tell the rest of us.
Basic concepts of Zero Knowledge Proof:
Information is an intangible, ephemeral commodity, and virtually impossible to control. Conversations can be overheard, letters intercepted, and e-mail server shacked. Of course, good cryptography can keep the information a secret between two parties. But what is there to stop this second party from transferring that information to a third party, who can then in turn pass it to a fourth, and so on… In some cases, it is desirable to demonstrate that you possess some information, but not to reveal it. For example, some authentication schemes require you to give your private key to a trusted authority, not because the trusted authority needs to know it, but because it needs to be certain that you do, in order to prevent potential attackers from exploiting the certification process. This is where zero-knowledge comes into play.
Zero-knowledge protocols allow identification, key exchange and other basic cryptographic operations to be implemented without leaking any secret information during the conversation and with smaller computational requirements than using comparable public key protocols. Thus Zero-knowledge protocols seem very attractive especially in smart card and embedded applications.
Definition of Zero knowledge Proof:
A zero-knowledge proof is an interactive protocol between two parties, called the ”prover” and the ”verifier”. The prover claims to have some information, and the verifier would like to confirm that she actually knows it. The prover, however does not want to reveal it. In order to satisfy their respective desires for secrecy and verification, the prover and the verifier engage in an interactive proof system.
A zero-knowledge proof is a way that a “prover” can prove possession of a certain piece of information to a “verifier” without revealing it. This is done by manipulating data provided by the verifier in a way that would be impossible without the secret information in question. A third party, reviewing the transcript created, cannot be convinced that either prover or verifier knows the secret.
Zero-knowledge terminology:
The secret means some piece of information, be it a password, the private key of a public key cryptosystem, a solution to some mathematical problem or a set of credentials. With Zero-knowledge protocols, the prover can convince the verifier that she is in possession of the knowledge, the secret, without revealing the secret itself, unlike e.g. normal username-password queries.
Accreditation means the building of confidence, at each iteration of the protocol. If in one step of a zero-knowledge protocol, the chance of an impostor being able to provide the answer is 1 in 2, the chances of her passing an entire conversation are 2^-(number of accreditation rounds).