Hamiltonian Path Zero Knowledge Proof using Commitments to a Series of Edges

Question

Commonly, Zero Knowledge Proofs based on the Hamiltonian Path or Cycle problems are given as follows:

1. 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.
2. The Prover generates $G'$ which is isomorphic to $G$ via a permutation $\pi$.
3. 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.
4. 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)
5. After receiving all commitments, the Verifier makes a binary choice
6. 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
7. 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?

Answer 1

This does seem to be zero knowledge; as you say, you don't actually commit to the adjacency list. Rather, you commit to a series of edges, in random order.

Regarding the question: First, your assumption is that $n^2$ commitments, each to a single bit, is more expensive than $|E|$ commitments, each to $2\log n$ bits (to encode two numbers for the edge). This is a reasonable assumption for many commitment schemes but not necessarily for all. (Of course, it is very reasonable for sparse graphs.)

However, the main thing here is that the proof of Hamiltonicity is a theoretical proof of feasibility. Improving the concrete cost in this way is not of great interest. In any case, the protocol is unlikely to be used (applying a Karp reduction and then using Hamiltonicity will kill you in almost all cases).