14
$\begingroup$

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?

$\endgroup$
  • 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$ – Joseph O'Rourke Oct 8 '10 at 18:18
  • $\begingroup$ @Joseph: Thanks. It will surely help! $\endgroup$ – M.S. Dousti Oct 8 '10 at 18:25
9
$\begingroup$

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]. Laszlo Babai, Ludik Kucera, 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.

$\endgroup$
  • 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$ – M.S. Dousti Oct 9 '10 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$ – Joshua Grochow Oct 11 '10 at 14:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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