Re: Is this simple scheme secure?

From: Tim Smith (reply_in_group_at_mouse-potato.com)
Date: 01/31/04 

Date: Sat, 31 Jan 2004 08:54:59 GMT

In article <q%zSb.80748$dP1.206618@newsc.telia.net>, Foo Bar wrote:
>> Ok, but that can only be possible for some very specific kinds of secrets
>> right?
>
> It can be used for things like "I know a n-coloring of this graph" or "I
> know an isomorphism between these two graphs". I don't know the area well
> enough to comment on the case of more general secrets.

All kinds of problems (like, all the NP-complete problems) can be
transformed into problems that have ZKP procedures, so basically all secrets
of the form "I have a solution to this instance of this particular
interesting problem" can be proved using ZKP.

Furthermore, all proofs in ordinary mathematics can (in theory...the graphs
involved would probably be too large to work with) be transformed into
Hamiltonian circuits on a graph. That is, there exists a graph, G, for
example, with the property that the existence of a Hamiltonian circuit on
that graph would give a proof of, say, the Riemann hypothesis. Prove to the
world using a non-interactive ZKP that you have that Hamiltonian circuit,
and you'll have proved that you have proved the Riemann hypothesis, without
giving away anything about your proof.

I wonder if such a proof would qualify for the Millenium Prize? :-) 

-- 
--Tim Smith

Relevant Pages

  • Re: Is this simple scheme secure?
    ... >>enough to comment on the case of more general secrets. ... > interesting problem" can be proved using ZKP. ... > Hamiltonian circuits on a graph. ... with the property that the existence of a Hamiltonian circuit on ...
    (sci.crypt)
  • Re: Ideas for course on great ideas in (theoretical) CS?
    ... > testing, graph coloring ... ... construct a graph with a Hamiltonian circuit, ... how about sorting stacks of pancakes? ... you've got a stack of N pancakes, each a different size, and you'd like the ...
    (comp.theory)
  • Re: Hamiltonian path
    ... Graph Theory with Applications. ... then G has a hamiltonian circuit. ... > Harry. ...
    (sci.math)
  • Re: walks in graphs
    ... I forgot my most important correction: A Hamiltonian Circuit is ... a closed path through a graph that visits each node EXACTLY once, ...
    (sci.math)