1
$\begingroup$

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$?

Improve this question
$\endgroup$
2
  • $\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. ♦
    Oct 27 at 19:53
  • $\begingroup$ Of course, thank you $\endgroup$
    – AmirD
    Oct 27 at 21:16

1 Answer 1

Reset to default
0
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

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

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