<p>So here is the right paper for my purposes:</p>

<p>Joe Kilian, "A note on efficient zero-knowledge proofs and arguments." <a href="http://people.csail.mit.edu/vinodv/6892-Fall2013/efficientargs.pdf" rel="nofollow">http://people.csail.mit.edu/vinodv/6892-Fall2013/efficientargs.pdf</a></p>

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

<p>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)$.</p>

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

CC BY-SA 3.0
2015-02-05T05:39:58.813Z
I think it is better to delete this answer and update your original one to be the correct answer.
Kaveh
CC BY-SA 3.0
2015-02-05T00:55:02.670Z
2015-02-05T00:55:02.670Z
Geoffrey Irving
<p><strong>Update</strong>: This answer is obsoleted by my other answer, with fully polylogarithmic bounds from appropriate references.</p>

<p>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</p>

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

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

<p><strong>Update:</strong>  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.</p>

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

<p><strong>Edit</strong>: Thanks to Ricky Demer for pointing out the missing factor of $e$.</p>

CC BY-SA 3.0
2015-02-01T06:43:06.960Z
How can a salted Merkle tree to be used to guess at a coloring?
Geoffrey Irving
CC BY-SA 3.0
2015-02-01T07:22:24.747Z
Oops, thought the salting was implied since it was replacing bit commitment, which is all about salting.  The length of each salt is $b$, the same as the hash security parameter.  You're probably right that I can't achieve $O(1)$ rounds with a dishonest verifier.
Geoffrey Irving
CC BY-SA 3.0
2015-02-01T09:00:26.107Z
Oh, yes: I am definitely talking about commitments to the randomizations of the colors.  Randomizing the colors is part of the original algorithm, so I didn't mention it when passing to the Merkle tree.  I will add a note to this affect.
Geoffrey Irving
CC BY-SA 3.0
2015-02-01T19:24:21.583Z
Step 2 adds $O(\log e) = O(\log n)$ communication cost, which is negligible.
Geoffrey Irving
CC BY-SA 3.0
2015-02-02T00:05:07.043Z
That is incorrect.  Step 2 happens the same number of times as step 3.  Step 2 sends one number, step 3 sends a whole bunch of them, so step 3 dominates.
Geoffrey Irving
CC BY-SA 3.0
2015-02-02T00:11:39.953Z
$O(\log (1/p))$ times.  If you want to continue the conversation, let's switch to chat.
Geoffrey Irving
CC BY-SA 3.0
2015-02-02T14:54:15.383Z
Apologies for my density: you're right of course about the extra factor of $e$.  I'm quite curious if this factor can be avoided or reduced.  I'll edit the above tomorrow to add the factor.
Geoffrey Irving
CC BY-SA 3.0
2015-02-03T04:18:30.107Z
Yes, I think the PCP machinery gives a much better result, but it should be a separate answer.  This paper is relevant, but I haven't looked through it in detail: http://www.cs.virginia.edu/~mohammad/files/papers/13%20ZKPCPs.pdf
Geoffrey Irving
CC BY-SA 3.0
2015-01-19T17:19:58.020Z
2015-02-05T00:58:41.703Z
2015-02-05T00:58:41.703Z
Geoffrey Irving
<p>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.</p>

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

CC BY-SA 3.0
2015-02-04T10:19:05.077Z
2015-02-04T10:19:05.077Z
cryptocat
<p>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</p>

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

<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)$.</p>

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

<ol>
<li><a href="http://www.wisdom.weizmann.ac.il/~oded/X/gmw1j.pdf" rel="nofollow">http://www.wisdom.weizmann.ac.il/~oded/X/gmw1j.pdf</a></li>
</ol>

<p><strong>Edit</strong>: Thanks to Ricky Demer for pointing out the missing factor of $e$.</p>

<communication-complexity><zero-knowledge>
Minimum communication cost for zero knowledge proofs of three colorability
Geoffrey Irving
# Minimum communication cost for zero knowledge proofs of three colorability

(Asked by: username_0 on 2015-01-19)

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

**Tags:** communication-complexity, zero-knowledge


---

## 3 answers

### Answer by username_0 on 2015-02-05. Score: 3 | Accepted answer

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

> **Comments:**
> **username_1**: I think it is better to delete this answer and update your original one to be the correct answer.  

---

### Answer by username_0 on 2015-01-19. Score: 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$.

> **Comments:**
> **username_0**: How can a salted Merkle tree to be used to guess at a coloring?  
> **username_0**: Oops, thought the salting was implied since it was replacing bit commitment, which is all about salting.  The length of each salt is $b$, the same as the hash security parameter.  You're probably right that I can't achieve $O(1)$ rounds with a dishonest verifier.  
> **username_0**: Oh, yes: I am definitely talking about commitments to the randomizations of the colors.  Randomizing the colors is part of the original algorithm, so I didn't mention it when passing to the Merkle tree.  I will add a note to this affect.  
> **username_0**: Step 2 adds $O(\log e) = O(\log n)$ communication cost, which is negligible.  
> **username_0**: That is incorrect.  Step 2 happens the same number of times as step 3.  Step 2 sends one number, step 3 sends a whole bunch of them, so step 3 dominates.  
> **username_0**: $O(\log (1/p))$ times.  If you want to continue the conversation, let's switch to chat.  
> **username_0**: Apologies for my density: you're right of course about the extra factor of $e$.  I'm quite curious if this factor can be avoided or reduced.  I'll edit the above tomorrow to add the factor.  
> **username_0**: Yes, I think the PCP machinery gives a much better result, but it should be a separate answer.  This paper is relevant, but I haven't looked through it in detail: http://www.cs.virginia.edu/~mohammad/files/papers/13%20ZKPCPs.pdf  

---

### Answer by username_2 on 2015-02-04. Score: 1

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


---

