Is the following protocol perfect zero knowledge or computational zero knowledge?

Question

So I have this protocol for the hamiltonian cycle:

repeat t times:

1. Peggy chooses a random permutation $\pi$ on $V$, and computes $G_1=\pi(G)$
2. For each of the $\frac{|V|(|V|-1)}{2}$ possible edges of $G_1$ Peggy computes a different commitment and sends the commitnet to Victor. ($\forall v_1,v_2\in \pi(V)$ if $(v_1,v_2)\in \pi(E)$ then the commitment is on 1, and 0 otherwise)
3. Victor chooses a random $i\in {1,2}$ and sends it to Peggy
4. If $i=1$ the Peggy sends $\pi$ to Victor and reveals all the commitments on $G_1$. Otherwise, Peggy revelas the commitments on $|V|$ edges which form a hamiltonian cycle on $G$.
5. Victor checks Peggy's answer

So it's pretty easy to see that this is a zero knowledge protocol. How do I show if it's perfect zero knowledge or computational zero knowledge?

Answer 1

This is Blum's protocol for Hamiltonicity. The answer to your question depends on the commitments. There are two possibilities:

1. The commitments are perfectly hiding: in this case, the proof is perfect zero knowledge, but is only an argument (meaning that soundness is computational, and so only holds against a polynomial-time cheating prover).
2. The commitments are perfectly binding: in this case, the proof is only computational zero knowledge, but is a proof (meaning that soundness is unconditional).

Note that no commitment scheme can be both perfectly binding and hiding. In addition, the class of perfect zero knowledge proofs (unconditional soundness) is contained in $AM \cap co-AM$ and so is very unlikely to contain an $NP$-complete problem.