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?

  • 1
    $\begingroup$ Just some alternative terminology: A graph whose only automorphism is the identity is often called a rigid graph. Might help in searching... $\endgroup$ Commented Oct 8, 2010 at 18:18

1 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.

  • 1
    $\begingroup$ Thanks Joshua. I have one question. QUOTE: "worst-case regular graph isomorphism is equivalent to worst-case (general) graph isomorphism." Does it mean that, given an oracle which decides regular graph isomorphism, one can decide worst-case (general) graph isomorphism in polynomial time? Can you provide me with some pointers? $\endgroup$ Commented Oct 9, 2010 at 5:59
  • $\begingroup$ That's exactly what it means. The construction is not too difficult. Here is a reference; I do not know if it is the first: dx.doi.org/10.1016/0022-0000(79)90043-6 also available at cs.cmu.edu/~glmiller/Publications/Papers/Mi79.pdf $\endgroup$ Commented Oct 11, 2010 at 14:30

Your Answer

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

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