Hi Prof. Zeilberger -
I'm not sure we got "Option 2" right in the class today.
We decided to show the encoded graph and the Hamiltonian
cycle in that graph to the Verifier.
But I have two problems with that approach:
1. I think the Blum paper specifies that only n "boxes"
are opened for the verifier. These boxes are effectively
the Hamiltonian cycle, not the encoded graph.
2. If we give the encoded graph along with the encoded
Hamiltonian cycle, we are giving away information about
the cycle. For example, the verifier can check in the
graph to see what the degree of the nodes are in the cycle.
So, for example, the verifier would know that the Hamiltonian
cycle is:
* start at some node with degree 3 (say)
* go to an adjacent node with degree 5 (say)
* then ...
This knowledge doesn't reveal the Hamiltonian cycle
completely but it does reveal information about the
cycle which the verifier could use. Then I don't think
this is a "zero-knowledge" proof.
What do you think?
Thanks,
Phil Benjamin.