# 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 Impagliazzo & 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... Oct 8, 2010 at 18:18

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.