|
|
"Proginoskes" <CCHeckman@xxxxxxxxx> wrote in message
news:1159600856.957385.188840@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
>
> 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.
>
All interesting, thanks.
|
|