Re: Is this simple scheme secure?

From: NYC (name_at_company.com)
Date: 01/31/04 

Date: Sat, 31 Jan 2004 10:22:48 +0100

Tim Smith wrote:
> 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? :-)
>

Really? Does this mean that any proposition can be turned into a
question about a certain graph having a Hamiltonian circuit? Or does it
mean that once you have the proof of some proposition, then you can
create a graph in which the Hamiltonian circuit can be used to see that
the proposition must be true?

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)