# 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 ...

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 have written a tutorial on how to write simulation-based proofs. I think that it should be helpful.

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 ...

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 ...

Only top voted, non community-wiki answers of a minimum length are eligible