Commonly, Zero Knowledge Proofs based on the Hamiltonian Path or Cycle problems are given as follows:
- The Prover has a graph $G$, for which he knows a Hamiltonian Path (or Cycle). $G$ is also known to the Verifier and constitutes the public key.
- The Prover generates $G'$ which is isomorphic to $G$ via a permutation $\pi$.
- The adjacency matrix of $G'$ is individually committed, i.e. a cryptographic commitment for every possible edge is created which holds $1$ if the edge is in $G'$ and $0$ otherwise.
- The Prover also sends a commitment to $\pi$ (it could be argued that this step is obsolete due to a recent improvement in graph isomorphy solving)
- After receiving all commitments, the Verifier makes a binary choice
- When choosing 0: The prover opens all the commitments for all edges that are part of the Hamiltonian path in $G'$ so that the Verifier sees a Hamiltonian path (or cycle) exists
- When choosing 1: The prover opens all commitments so that the Verifier can see that the commitments indeed refer to $G'$ and that $G'$ is isomorph to $G$
The biggest problem with this Zero Knowledge Proof is that $O(n^2)$ individual commitments are required. We have recently been wondering if this could not be worked around by committing to a series of edges (in the spirit of adjacency lists) instead would not be more efficient with the same security guarantees.
This would create $|E|$ commitments of 2-tuples of two points each instead of $n^2$ commitments of single bits. (Plus one for $\pi$ in either case.)
For Example: "(commit(1,2), commit(1,3), commit(2,3)" is a valid set of commitments for the 3-Clique
It should be noted that the commitments must not only be for some random permutation $G'$ of the original Graph $G$, but also in random order, or one could potentially derive knowledge about the degree of nodes from the position of the opened commitment (and therefore identify individual nodes when only opening those corresponding to the Hamiltonian path/cycle).
We believe that this should still constitute a Zero Knowledge Proof, as a trivial simulator can be given:
When Prover will choose 0: Create a "Hamiltonian Path" commitment tuple "commit(1,2), commit(2,3), ..." and enough bogus commitments to have $|E|$ commitments in total. Randomly permutate everything. Reveal the "Hamiltonian Path" when Prover asks for it.
When Prover will choose 1: Just follow the protocol, as no knowledge of a Hamiltonian Path is required.
Are there any reasons (beyond tradition) why the literature would always use a version with adjacency matrices?