Generating Graphs with Trivial Automorphisms

Question

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?

Answer 1

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.

But a second naive approach has a chance of working: generate a random regular graph (of non-constant degree, since constant-degree graph isomorphism is in P). This also has no nontrivial automorphisms with high probability [KSV], but the Babai-Kucera result does not apply (as they point out in the paper). Proving that this is an invulnerable generator obviously requires some assumptions, but one could imagine proving unconditionally that average-case regular graph isomorphism is as hard as worst-case graph isomorphism, though I don't know how likely this is. (Note that worst-case regular graph isomorphism is equivalent to worst-case (general) graph isomorphism.)

[BK]. László Babai, Luděk Kučera, Canonical labelling of graphs in linear average time. FOCS 1979, pp.39-46.

[KSV] Jeong Han Kim, Benny Sudakov, and Van H. Vu. On the asymmetry of random regular graphs and random graphs. Random Structures & Algorithms, 21(3-4):216–224, 2002. Also available here.