# Tag Info

6

This does seem to be zero knowledge; as you say, you don't actually commit to the adjacency list. Rather, you commit to a series of edges, in random order. Regarding the question: First, your assumption is that $n^2$ commitments, each to a single bit, is more expensive than $|E|$ commitments, each to $2\log n$ bits (to encode two numbers for the edge). This ...

0

When discussing interactive proof systems, it is important to precisely describe the proving and the verification procedures. The goals being that, for the special case of graph non-isomorphism on two input graphs $G_1$ and $G_2$: If $G_1$ and $G_2$ are not isomorphic and the prover and verifier follow their assigned procedures correctly, the verifier will ...

0

I think what confuses you is that you are mixing two types of statements. Namely, statements of the type: "$G_1$ and $G_2$ are isomorphic" (I.e., the problem of graph isomorphism) and statements of the type "$G_1$ and $G_2$ are NOT isomorphic" (this is the problem called graph non-isomorphism). These are in fact two very different problems. As you point out ...

1

No, but if the problem isn't known to be in promiseMA then we do "assume that the prover can always solve the problem". http://cstheory.stackexchange.com/questions/696/mip-with-efficient-provers Graph isomorphism is trivially in NP, so for graph isomorphism, we just "assume that the prover" has an isomorphism between the graphs. Graph non-isomorphism is ...

6

Sigma protocols as-is are secure only for honest verifiers. However, they can be easily compiled into full-blown zero knowledge protocols. If you don't want interaction, then the Fiat-Shamir transform suffices, with security in the random oracle model. With interaction, you can do the transform at little cost using commitments based on DDH. For more ...

4

I guess you are talking about Figure 5.3? It is said that the Schnorr proof (sigma protocol for discrete log relation) is insecure against cheating verifiers - it is only honest-verifier zero knowledge. Sigma protocols are always only defined in the honest-verifier zero-knowledge setting. To see why a cheating verifier is a problem in Figure 5.3 think ...

4

I have written a tutorial on how to write simulation-based proofs. I think that it should be helpful.

Top 50 recent answers are included