# Minimum communication cost for zero knowledge proofs of three colorability

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

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

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.

• I think it is better to delete this answer and update your original one to be the correct answer. – Kaveh Feb 5 '15 at 5:39

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

• Step 1 would give the verifier a high-accuracy way to test any guess at the prover's coloring, using only 6 times the prover's step-1 work per guess. $\:$ Also, I don't see any way to use a Merkle tree computed by the prover without going from a proof to an argument. $\;\;\;\;$ – user6973 Feb 1 '15 at 2:53
• How can a salted Merkle tree to be used to guess at a coloring? – Geoffrey Irving Feb 1 '15 at 6:43
• I posted an answer saying why I think the salted Merkle Tree idea doesn't work. $\:$ You should instead turn commitments to the randomizations of the colors into a Merkle tree. $\:$ I also notice that you seem to be missing a number_of_edges factor in the communication complexity. $\hspace{.48 in}$ – user6973 Feb 1 '15 at 8:40
• Well, one can consider the promise that the assignment is either a valid 3-coloring or [at least $\: \delta \cdot \hspace{-0.02 in}e\:$ edges have same-colored vertices]. $\;\;\;$ That drops the communication complexity to $\: O\hspace{.02 in}(((b\hspace{-0.04 in}\cdot \hspace{-0.04 in}n)/\delta) \cdot \log(n))\;$. $\;\;\;$ (continued ...) – user6973 Feb 3 '15 at 3:31
• (... continued) $\;\;\;$ Next, one can apply PCP machinery to reduce the standard 3-coloring relation to that promise-relation. $\;\;\;$ Then, taking that idea to its extreme gives zero-knowledge universal arguments. $\;\;\;\;\;\;\;\;$ – user6973 Feb 3 '15 at 3:31

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

(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)})$.

• I'm not sure I follow your notation, but it seems like you're arguing that you can take my sketch and fill in the details in an obviously silly way, thus producing an insecure system. I'll add the cleaner secure version of the details to my answer. – Geoffrey Irving Feb 1 '15 at 8:47
• The only silliness was my transformation to $H_2$. $\:$ Everything else was $\hspace{1.71 in}$ what I honestly thought you meant. $\;\;\;\;$ – user6973 Feb 1 '15 at 8:52
• Please let me know whether the detailed added to my answer make it clear. It's quite possible that I'm missing something and my construction is indeed broken. – Geoffrey Irving Feb 1 '15 at 8:58