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?


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

  • $\begingroup$ Do you know any article/book that states that "computational zero knowledge" when commitment is perfectly binding? Thank you! $\endgroup$
    – pintor
    Nov 3, 2022 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.