Minimum communication cost for zero knowledge proofs of three colorability

Question

Goldreich et al.'s proof that three colorability has zero knowledge proofs uses bit commitment for an entire coloring of the graph in each round [1]. If a graph has $n$ vertices and $e$ edges, a secure hash has $b$ bits, and we seek error probability $p$, the total communication cost is

$$O(ben \log(1/p))$$

over $O(1)$ rounds. Using a gradually revealed Merkle tree, the total communication can be reduced to $O(be \log n \log (1/p))$ at the cost of increasing the number of rounds to $O(\log n)$.

Is it possible to do better than this, either in terms of total communication or number of rounds?

1. http://www.wisdom.weizmann.ac.il/~oded/X/gmw1j.pdf

Edit: Thanks to Ricky Demer for pointing out the missing factor of $e$.

Answer 1

So here is the right paper for my purposes:

Joe Kilian, "A note on efficient zero-knowledge proofs and arguments." http://people.csail.mit.edu/vinodv/6892-Fall2013/efficientargs.pdf

To get the strongest result, we need to accept zero knowledge arguments rather than proofs (computationally bounded prover); these are what I am interested in but did not know the terminology.

Assuming sufficient cryptographic assumptions, the paper gives zero knowledge arguments with total communication $O(b \log^c n \log (1/p))$ for $c = O(1)$.

This result is tightened to $O(1)$ rounds by Ishai et al., "On Efficient Zero-Knowledge PCPs", http://www.cs.virginia.edu/~mohammad/files/papers/13%20ZKPCPs.pdf.

Answer 2

Update: This answer is obsoleted by my other answer, with fully polylogarithmic bounds from appropriate references.

On second thought, there's no need to reveal the Merkle tree gradually, so the lower communication version needs no extra rounds. The communication steps are

1. The prover P randomizes its coloring, turns it into a (salted) Merkle tree, and sends the root to the verifier V.
2. V picks a random edge $e$ and sends it to P.
3. P sends the Merkle tree paths from the root to each endpoint of $e$ to V.

This gives $O(be \log n \log (1/p))$ communication over $O(1)$ rounds.

Update: Here are details of the Merkle tree construction. For simplicity, expand the graph to have exactly $2^a$ vertices by adding a few disconnected nodes (these do not effect three colorability or zero knowledge). Assume a secure hash function taking any size input and producing $b$-bit outputs. For each Merkle tree, the prover chooses $2^{a+1}-1$ random $b$-bit nonces, one for each leaf and nonleaf of the binary tree. At the leaves, we hash the color concatenated with the nonce to produce the leaf's value. At each nonleaf, we hash the two child value with the nonleaf's nonce to produce the nonleaf's value.

In the first round, the prover sends only the root value, which provides no information since it is hashed with the root's nonce. In the third round, no information is conveyed about any unexpanded node in the binary tree, since such a node was hashed with a nonce at that node. Here I am assuming the prover and verifier are both computationally bounded and cannot break the hash.

Edit: Thanks to Ricky Demer for pointing out the missing factor of $e$.

Answer 3

There is a recent surge in activity in succinct non-interactive zero knowledge arguments. It is known how for example construct an NIZK argument for Circuit-SAT where the argument length is a very small constant number of group elements (see Groth 2010, Lipmaa 2012, Gennaro, Gentry, etc, Eurocrypt 2013, etc). Based on an NP-reduction you can then clearly construct an argument for 3-colorability with the same communication.

Of course this is a different model compared to your original question - for example, in those arguments, the CRS length is linear in circuit size, and in some sense the can be thought as a part of the communication (though it can be reused in many different arguments).

Answer 4

(This doesn't fit in a comment.)

I think I now see how to show that your the salting doesn't necessarily provide
honest-verifier zero-knowledge. $\:$ Let $H_0$ be the secure hash. $\:$ If we know
that $H_0$ can already handle arbitrary-length inputs, then let $H_1$ equal $H_0$,
else let $H_1$ be the result of applying the Merkle–Damgard construction to $H_0$.
(Note that $||$ represents concatenation.) $\:$ Let $H_2$ be such that


For all 3-bit strings $x$ and $z$, for all $\; ((3\hspace{-0.05 in}\cdot \hspace{-0.05 in}b)\hspace{-0.03 in}+\hspace{-0.02 in}6)$-bit$\;$ strings $y$,
for the string $m$ such that $\;\;\;\;\; m \:\: = \:\: x\:||\:111...[b\text{ of them}].\hspace{-0.04 in}.\hspace{-0.04 in}.111\:||\:y\:||\:z \;\;\;\;\;$,
one has $\;\;\;\;\; H_2(m) \;\; = \;\; x\:||\:\:111...[b\text{ of them}].\hspace{-0.04 in}.\hspace{-0.04 in}.111\:||\:H_{\hspace{-0.02 in}1}(m)\:||\:z \;\;\;\;\;$.

and

For all 3-bit strings $x$, for all salts $r\hspace{-0.02 in}$, for the string $m$ that results from salting $x$ with $r\hspace{-0.02 in}$, if $m$ is
not of the form addressed above then $\;\;\;\;\; H_2(m) \:\: = \:\: x\:||\:\:111...[b\text{ of them}].\hspace{-0.04 in}.\hspace{-0.04 in}.111\:||\:H_{\hspace{-0.02 in}1}(m)\:||\:x \;\;\;\;\;$.

and

For all strings $m$ that are of neither of those two forms,
$H_2(m) \:\: =$
$[b\hspace{-0.04 in}+\hspace{-0.05 in}3 \text{ bits whose values don't matter}]\:||\:H_{\hspace{-0.02 in}1}(m)\:||\:[3 \text{ bits whose values don't matter}]\;\;\;\;\;$.


.

Since $H_1$ is involved in the same place in each case, any collision in $H_2$ is also a collision in $H_1$. $\:$ By Merkle-Damgard's security, any collision in $H_1$ can be efficiently transformed
into a collision in $H_0$. $\:$ Thus, if $H_0$ is collision-resistant than so is $H_2$.
However, if the number of vertices is a power of two then by checking the 3 bits
on each end of the root hash, one can determine whether or not the initial and
final vertices received the same color with error probability less than $1/(2^{(b-1)})$.