Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
    
here Section 3.2. is a straightforward way to do so. –  DrLecter Apr 10 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 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 at 12:59
2  
@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 at 13:07
1  
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 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$.

share|improve this answer
    
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 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 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 at 14:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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