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.