0
$\begingroup$

The FLS zero knowledge protocol for graph hamiltonicity proceeds as follows.

The prover (proving graph hamiltonicity of graph G) picks a random cycle graph C, and sends its commitment to verifier.

Verifier picks a random bit b and sends it to sender.

If b = 0, then prover decommits all the edges of graph, and verifier verifies if its a cycle graph.

If b = 1, then prover computes isomporphism between hamiltonian cycle of G and cycle graph C. It then decommits all the edges in C that are not present in the isomporphism of G.

This protocol is proven to be honest-verifier zero knowledge in many places. How can a dishonest verifier break ZK property of this scheme? A dishonest verifier can break ZK property only if he can compute bit b depending on commitment(C) and learn some info. But that would violate hiding property of commitment scheme right?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

The protocol for Hamiltonicity is by Blum and not FLS (FLS indeed use it). The protocol as you presented it is zero-knowledge for a malicious verifier as well. However, it is not known to be zero-knowledge when run in parallel (in order to get negligible soundness error). On the flip side, we also do not know how a dishonest verifier can do anything.

What do we know about the parallel repetition of Hamiltonicity?

First, we know that it is not black-box zero knowledge; see On the Composition of Zero-Knowledge Proof Systems.

Second, it is possible to prove that $log^2 n$ repetitions of the proof is actually zero knowledge in the unlikely case (not believed to be true) that Circuit-SAT on $n$ variables can be solved in time $2^{\sqrt{n}}$. This demonstrates that it would be very hard to prove that this protocol is not zero knowledge, without proving strong lower bounds on CSAT (note one could theoretically prove this under such an assumption, but no one knows how to do this). This proof can be found in Section 8 of Lower Bounds for Non-Black-Box Zero-Knowledge.

Third, we can prove that parallel Hamiltonicity is witness indistinguishable.

Finally, it is clearly honest-verifier zero knowledge.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Interesting. I was reading Canetti's recent STOC paper eprint.iacr.org/2018/1248.pdf. They mention the protocol as FLS protocol and mention in Page 25 that it satisfies honest verifier zero knowledge. If FLS protocol is only witness indistinguishable, applying Fiat Shamir on FLS does not give NIZKs right? $\endgroup$
    – satya
    Aug 7, 2019 at 22:20
  • $\begingroup$ I don't know why they would cite it as FLS, except that they're dealing with NIZK. However, once again, the parallel version is honest-verifier ZK, so it's fine to apply Fiat-Shamir. $\endgroup$
    – Yehuda Lindell
    Aug 8, 2019 at 2:22

Your Answer

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

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