I've read this scribe that provides a public coin interactive proof for graph non-isomorphism.

In the proof, the verifier samples both a pairwise-independent hash function and a target $y$. Then it continues to show bounds for the probability that there's a pre-image of $y$ w.r.t. the hash function that's also inside a given subdomain $S$.

In all calculations carried out in page 5 (lemma 3), I couldn't find a single instance that used the fact that $y$ is random. It seems as if randomizing the hash function is enough.

This is also the case for any other source I found that shows a specific public-coin interactive proof for GNI.

Why do we need to randomize $y$?

  • $\begingroup$ I encourage you to edit your question to make it self-contained by providing relevant background and defining the notation. Also it would help to identify which part of that 7-page document you are referring to (e.g., Section number, page number, which lemma/theorem/proof). Also it might helpful to provide a proper reference in addition to the link (e.g., title of the document, author, class, semester), so we can find the document in the future if the link stops working. $\endgroup$
    – D.W.
    Commented Oct 27, 2023 at 19:53
  • $\begingroup$ Of course, thank you $\endgroup$
    – AmirD
    Commented Oct 27, 2023 at 21:16

1 Answer 1


I agree. I believe you are correct. As far as I can see, $y$ does not need to be random.


Your Answer

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

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