I am looking for an interactive proof for the language $AUTO^C= \{𝐺∣\text{𝐺 is an undirected graph that has no non-trivial automorphisms} \}$.
I am interested in a method similar to the interactive proof for Graph Non-Isomorphism (GNI).
Any insights or references to relevant literature would be greatly appreciated.
For a permutation $ \pi$ and a graph $G = (V,E)$ denote $\pi(G) = (V, \pi(E))$ under this notation, an automorphism $ \sigma $ will hold the following property:
$ \sigma(G)=G $
The protocol for a verifier $V$ and a prover $P$ will go as follows:
1.) $V$ selects a random permutation $\pi$ and sends $P$ $\pi(G)$
2.) $P$ sends back a permutation $g$
3.) $V$ accepts iff $g = \pi^{-1}$
the idea here is that if $G$ has only the trivial automorphism, $P$ can just iterate over all possible permutations until he will find one to reverse $\pi$ and he can be sure this is $\pi^{-1}$
However, if $G$ has a non-trivial automorphism $\sigma$, then both $\pi^{-1}$ and $\sigma \circ \pi^{-1}$ will give us back $G$, that is:
$ \pi^{-1} \circ \pi (G) = G $
$ \sigma \circ \pi^{-1} \circ \pi (G) = \sigma (G) = G $
but since $\sigma$ is non-trivial, we will get $ \pi^{-1} \neq \sigma \circ \pi^{-1} $
so any prover could never distinguish between those two given $ \pi(G)$, and will have at best a probability of $\frac{1}{2} $ to trick the verifier
