<p>At least the first naive approach one might think of does not work.  The approach I have in mind is to simply generate <span class="math-container">$G_1$</span> purely at random.  Since almost all graphs have no symmetries (that is, the proportion of graphs on <span class="math-container">$n$</span> vertices with no nontrivial automorphisms approaches 1 as <span class="math-container">$n \to \infty$</span>), <span class="math-container">$G_1$</span> 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.</p>
<p>But a second naive approach has a chance of working: generate a random <em>regular</em> 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.)</p>
<p>[BK]. László Babai, Luděk Kučera, <a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.1979.8" rel="nofollow noreferrer">Canonical labelling of graphs in linear average time</a>. FOCS 1979, pp.39-46.</p>
<p>[KSV] Jeong Han Kim, Benny Sudakov, and Van H. Vu. <a href="http://dx.doi.org/10.1002/rsa.10054" rel="nofollow noreferrer">On the asymmetry of random regular graphs and random graphs</a>. Random Structures &amp; Algorithms, 21(3-4):216–224, 2002.  Also available <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.9769" rel="nofollow noreferrer">here</a>.</p>

CC BY-SA 2.5
2010-10-09T05:59:15.873Z
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?
Sadeq Dousti
CC BY-SA 2.5
2010-10-11T14:30:28.683Z
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: http://dx.doi.org/10.1016/0022-0000(79)90043-6 also available at http://www.cs.cmu.edu/~glmiller/Publications/Papers/Mi79.pdf
Joshua Grochow
CC BY-SA 4.0
2010-10-08T19:10:12.673Z
2022-04-22T08:16:58.473Z
2022-04-22T08:16:58.473Z
Joshua Grochow
<p>I'm revising some cryptographic model. To show its inadequacy, I've devised a contrived protocol based on graph isomorphism.</p>
<p>It is &quot;commonplace&quot; (yet controversial!) to assume the existence of BPP algorithms capable of generating &quot;hard instances of the Graph Isomorphism problem.&quot; (Along with a witness of isomorphism.)</p>
<p>In my contrived protocol, I'm gonna assume the existence of such BPP algorithms, which satisfy one additional requirement:</p>
<ul>
<li>Let the generated graphs be <span class="math-container">$G_1$</span> and <span class="math-container">$G_2$</span>. There's just one witness (permutation) that maps <span class="math-container">$G_1$</span> to <span class="math-container">$G_2$</span>.</li>
</ul>
<p>This implies that <span class="math-container">$G_1$</span> has only <strong>trivial automorphisms</strong>. In other words, I'm assuming the existence of some BPP algorithm, which works as follows:</p>
<ol>
<li>On input <span class="math-container">$1^n$</span>, generate an <span class="math-container">$n$</span>-vertex graph <span class="math-container">$G_1$</span>, such that it has only trivial automorphisms.</li>
<li>Pick a random permutation <span class="math-container">$\pi$</span> over <span class="math-container">$[n]=\{1,2,\ldots,n\}$</span>, and apply it on <span class="math-container">$G_1$</span> to get <span class="math-container">$G_2$</span>.</li>
<li>Output <span class="math-container">$\langle G_1,G_2,\pi \rangle$</span>.</li>
</ol>
<p>I'm gonna assume that, in Step 1, <span class="math-container">$G_1$</span> can be generated as needed, and
<span class="math-container">$\langle G_1,G_2 \rangle$</span> is a <em>hard</em> instance of the Graph Isomorphism problem. (Please interpret the word &quot;hard&quot; naturally; a formal definition is given by <a href="https://doi.org/10.1007/0-387-34799-2_23" rel="nofollow noreferrer">Abadi <em>et al.</em></a> See also the paper by <a href="https://dx.doi.org/10.1109/FSCS.1990.89604" rel="nofollow noreferrer">Impagliazzo &amp; Levin</a>.)</p>
<blockquote>
<p>Is my assumption reasonable? Could anyone please point me to some references?</p>
</blockquote>

CC BY-SA 2.5
2010-10-08T18:18:23.643Z
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
<graph-theory><cr.crypto-security><automorphism><graph-isomorphism><randomized-algorithms>
Generating Graphs with Trivial Automorphisms
Sadeq Dousti
# Generating Graphs with Trivial Automorphisms

(Asked by: username_0 on 2010-10-08)

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.*](https://doi.org/10.1007/0-387-34799-2_23) See also the paper by [Impagliazzo & Levin](https://dx.doi.org/10.1109/FSCS.1990.89604).)

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

**Tags:** graph-theory, cr.crypto-security, automorphism, graph-isomorphism, randomized-algorithms

> **Comments:**
> **username_1**: Just some alternative terminology: A graph whose only automorphism is the identity is often called a _rigid_ graph.  Might help in searching...  

---

## 1 answers

### Answer by username_2 on 2010-10-08. Score: 10 | Accepted answer

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](http://doi.ieeecomputersociety.org/10.1109/SFCS.1979.8). 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](http://dx.doi.org/10.1002/rsa.10054). Random Structures & Algorithms, 21(3-4):216–224, 2002. Also available [here](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.9769).

> **Comments:**
> **username_0**: 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?  
> **username_2**: 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: http://dx.doi.org/10.1016/0022-0000(79)90043-6 also available at http://www.cs.cmu.edu/~glmiller/Publications/Papers/Mi79.pdf  

---

