# Generating Graphs with Trivial Automorphisms

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:

1. On input $1^n$, generate an $n$-vertex graph $G_1$, such that it has only trivial automorphisms.
2. Pick a random permutation $\pi$ over $[n]=\{1,2,\ldots,n\}$, and apply it on $G_1$ to get $G_2$.
3. 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 Impaliazzo & Levin.)

Is my assumption reasonable? Could anyone please point me to some references?

• Just some alternative terminology: A graph whose only automorphism is the identity is often called a rigid graph. Might help in searching... – Joseph O'Rourke Oct 8 '10 at 18:18
• @Joseph: Thanks. It will surely help! – M.S. Dousti Oct 8 '10 at 18:25

At least the first naive approach one might think of does not work. The approach I have in mind is to simply generate $G_1$ purely at random. Since almost all graphs have no symmetries (that is, the proportion of graphs on $n$ vertices with no nontrivial automorphisms approaches 1 as $n \to \infty$), $G_1$ will have no nontrivial automorphisms with high probability, which is what we want. However, the average-case version of graph isomorphism, where graphs are chosen uniformly at random, can be solved in linear time [BK], so this does not generate a distribution of hard instances.