We have a multiplicative cyclic group $G$ which is a subgroup of $(\mathbb{Z}/n\mathbb{Z})∗$. There are two parties, Alice and Bob:


  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$?

  • $\begingroup$ here Section 3.2. is a straightforward way to do so. $\endgroup$
    – DrLecter
    Apr 10, 2014 at 11:29
  • $\begingroup$ 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. $\endgroup$
    – tylo
    Apr 10, 2014 at 12:24
  • $\begingroup$ @tylo Ah, didn't realize that the question has changed. SDL could you elaborate where you would need such a proof. $\endgroup$
    – DrLecter
    Apr 10, 2014 at 12:59
  • 2
    $\begingroup$ @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. $\endgroup$
    – DrLecter
    Apr 10, 2014 at 13:07
  • 1
    $\begingroup$ 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$. $\endgroup$
    – tylo
    Apr 11, 2014 at 15:20

1 Answer 1


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$.

  • 1
    $\begingroup$ 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. $\endgroup$
    – poncho
    Apr 15, 2014 at 17:49
  • $\begingroup$ 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). $\endgroup$
    – tylo
    Apr 16, 2014 at 14:33
  • $\begingroup$ 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. $\endgroup$
    – poncho
    Apr 16, 2014 at 14:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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