|
|
iatsonios@xxxxxxxxx wrote:
> Hello everybody.
> I am interested on the notion of Zero Knowledge Proof
Zero Knowledge Proofs are a way for someone to show that they have
proven a particular result, without having to actually give that proof.
(Maybe it's long, or maybe there are "security" issues at stake.) This
technique is named because the skeptic is convinced that the result
really has a proof, without gaining any knowledge of that proof. (Think
along the lines of nonconstructive proofs.)
In short, I can claim to have a proof of the Four Color Theorem. You
want to challenge me, so what you do is to choose a planar graph, and
then you give it to me. If I really do have a proof, I'll be able to
color the graph properly using 4 colors, and you can verify that this
is a proper coloring. (Hence, there's no way for me to "bluff" by
giving you a bad coloring and saying that it is really good.)
This suggests that I can really 4-color graphs, but is not definitive
proof, since I've only done one example. What you (as the skeptic) can
do is to create another graph for me to color.
I then will try to color this graph as well, and give you the coloring,
etc.
Aside: If you google for "James Harris" and "Surrogate Factoring",
you'll find that he claimed to be able to factor integers quickly. He
didn't want to give out the proof or algorithm, since "terrorists could
then bring down governments around the world". What people kept asking
from him was a Zero Knowledge Proof: Factor some integers. There are
some numbers called RSA numbers which have been posted, and which are
known to be the product of two prime numbers. However, Harris would
never factor any numbers given to him.
In light of what you (now) know about Zero Knowledge Proofs, what does
this suggest?
>and its
> implications in Complexity theory and more specifically through using
> the PCP theorem.Albeit combinatorial proof for the theorem is an issue
> of great interest not only as a theoretical breakthrough,but also for
> its applied facet .
> I would be grateful to anyone who can suggest me some resources in
> order to get deep unterstanding of the field via getting accustomed
> with the background,such as papers,some books ,etc.Specially as
> aforementioned i am interested on combinatorial arguments for
> PCP,because it is also highly correlated with coding theory.
Wikipedia has a page devoted to the PCP Theorem, at
http://en.wikipedia.org/wiki/PCP_Theorem . (MathWorld doesn't seem to
have any pages devoted to the PCP Theorem, or even to Zero Knowledge
Proofs.)
--- Christopher Heckman
You owe the Internet Oracle the LSD Theorem.
|
|