# 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:

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

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

-
here Section 3.2. is a straightforward way to do so. – DrLecter Apr 10 '14 at 11:29
The changing of the question makes DrLecter's answer seem not applicable. The original statement of $a^{(x^2)}=b$ was solved by that paper, $x^x=b$ isn't. – tylo Apr 10 '14 at 12:24
@tylo Ah, didn't realize that the question has changed. SDL could you elaborate where you would need such a proof. – DrLecter Apr 10 '14 at 12:59
@SDL could you elaborate where you would need such a proof. Exponentiation of a group element with a group element of the same group does not really make sense to me. – DrLecter Apr 10 '14 at 13:07
Ah right... I thought of Fermat, but not of throwing CRT on the problem with the coprime moduli. All I could up with involved somehow $p$ as a factor of $x$. – tylo Apr 11 '14 at 15:20

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: "It depends".

As poncho pointed out, if $x>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<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<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<x<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$.

-
I disagree; just because someone can deduce some information from $b$ doesn't disqualify a ZK proof; all it means is that the ZK proof can't reveal anything more. You can obviously put together a ZK proof by designing a circuit that computes $z^z \bmod p$ for $z<p$, and prove that you know an input $z$ that generates $b$. While this shows that a ZK proof is possible, it really doesn't answer the question; we are asked for a simple proof, and unless your definition of simple is considerably broader than mine, the circuit method wouldn't qualify. – poncho Apr 15 '14 at 17:49
I covered the basic problem for the lack of ZK too short, I guess: $f(x)=x^x$ is not a homomorphism. It does no preserve any kind of structure. So you can't find what you need in a ZKP: A sort of commitment, which is "related to $x$, but not $x$ itself", and which can be opened in multiple ways. This is similar to why there is no simple ZK proof of knowledge of a preimage of a hash function (except the circuit method). – tylo Apr 16 '14 at 14:33
I just don't trust the argument "our normal techniques cannot solve this problem, hence this problem cannot be solved". We know that a complex ZK proof is possible; the standard ways to generate a short proof do not work, however I cannot say that there isn't an alternative short way (that we haven't thought of) that would work. – poncho Apr 16 '14 at 14:57