Is there a simple zero knowledge proof of $x$ for $b=x^x\pmod p$? We have a multiplicative cyclic group $G$ which is a subgroup of $(\mathbb{Z}/n\mathbb{Z})∗$. There are two parties, Alice and Bob:

If:


Alice knows: $b$ and $x$ such that $x^x = b$;
Bob knows: $b$.


Then what's the easiest non-interactive way Alice can prove to Bob the knowledge of $x$ without leaking $x$?
The original question was:

Alice knows: $a,b$ and $x$ such that $a^{(x\cdot x)} = b$
Bob knows: $a,b$

and DrLecter referenced this paper (fixed the link), which covers the question.
Now, the question was changed to

Alice knows: $b$ and $x$ such that $x^x=b$;
Bob knows: $b$.

The given structure was:

... multiplicative group $G$ which is a subgroup of  $(\mathbb{Z}/n\mathbb{Z})$

And a sub-question in the comments was, if this is easy if $n$ is prime. The answer in this case is: &quot;It depends&quot;.
As poncho pointed out, if $x&gt;n$ is allowed, you can find a $x$, if you consider the exponent and the base independently (let's call the modulus $p$ for being prime):

$x=b$ mod $p$
$x=1$ mod $p-1$
Since $p$ is prime, we can apply the Chinese Remainder Theorem to get $x= p^2 - bp + b$.

So for $x$ without restrictions, there is no need for a ZKP, because it is easy to calculate the solution from $b$ and $p$ alone.
Now the tricky part: What if $x$ is limited to $x&lt;p$?

In general, there is no solution, because there is no structure which would be preserved by a function $x\rightarrow x^x$. I can't even think of a way to check if for a given $y$ there exists a $x$, s.t. $x^x=y$.

But what we can prove is that there can be no such zero knowledge proof:

Bob knows $b$.
If $b=1$, the solution is $x=p-1$ or $x=1$, this means $x&lt;p-1$.
If the modulus is prime, he can check if $b$ is a quadratic residue.
$x$ has a factorization in $\mathbb{Z}$, and for every prime factor $x_1$ of $x$, we know that $x^{(x/x_i)}$ has to exist, because $x^a$ is well-defined for every $0\leq a\leq x$, if $0&lt;x&lt;p$.
If $b$ is a quadratic nonresidue, then there exists no quare root, and we know that $x$ does not contain a factor $2$ (in $\mathbb{Z}$).

A similar approach can be made for every prime factor of $p-1$, because the according exponentiation with this factor is a non-injective function.
This is a contradiction to ZK already, because knowledge of $b$ reveals already some information about $x$.