I'm revising some cryptographic model. To show its inadequacy, I've devised a contrived protocol based on graph isomorphism.
It is "commonplace" (yet controversial!) to assume the existence of BPP algorithms capable of generating "hard instances of the Graph Isomorphism problem." (Along with a witness of isomorphism.)
In my contrived protocol, I'm gonna assume the existence of such BPP algorithms, which satisfy one additional requirement:
- Let the generated graphs be $G_1$ and $G_2$. There's just one witness (permutation) that maps $G_1$ to $G_2$.
This implies that $G_1$ has only trivial automorphisms. In other words, I'm assuming the existence of some BPP algorithm, which works as follows:
- On input $1^n$, generate an $n$-vertex graph $G_1$, such that it has only trivial automorphisms.
- Pick a random permutation $\pi$ over $[n]=\{1,2,\ldots,n\}$, and apply it on $G_1$ to get $G_2$.
- Output $\langle G_1,G_2,\pi \rangle$.
I'm gonna assume that, in Step 1, $G_1$ can be generated as needed, and $\langle G_1,G_2 \rangle$ is a hard instance of the Graph Isomorphism problem. (Please interpret the word "hard" naturally; a formal definition is given by Abadi et al. See also the paper by Impagliazzo & Levin.)
Is my assumption reasonable? Could anyone please point me to some references?