3
$\begingroup$

I think it's neat how a person can prove that two discrete logarithms are equal without actually revealing the value.

So, conversely, is there a way for me to prove that two discrete logarithms are not equal without revealing either logarithm's value? Assume that I know (by construction or by oracle) the discrete logarithm value for any pair of elements (from the 4 given elements) and I thereby know that all are unique.

$\endgroup$
5
$\begingroup$

A zero-knowledge algorithm for proving inequality of two discrete logarithms was given e.g. by Camenisch and Shoup in Section 6 of Practical Verifiable Encryption and Decryption of Discrete Logarithms (CRYPTO'03).

Quoting from the paper:

Let $G=\langle g \rangle$ be a group of prime order $q$. The prover and verifier have common inputs $g, h, y, z \in G$ where $g, h$ are generators of $G$ and $log_g y \neq log_h z$. The prover has the additional input $x = log_g y$. The prover and the verifier then engage in the following protocol.

  1. The prover randomly chooses $r \in Z_q$, computes the auxiliary commitment $C = (h ^x/z)^r$, and sends $C$ to the verifier.

  2. The prover executes the protocol denoted $PK\left\{(\alpha, \beta) : C = h^\alpha (\frac{1}{z})^\beta \wedge 1 = g^\alpha (\frac{1}{y})^\beta \right\}$ with the verifier. (Note that this is a proof of equality, so we know how to do this).

  3. The verifier accepts if it accepts in Step 2, and if $C \neq 1$; otherwise, the verifier rejects.

This constitutes an honest-verifier proof system for proving that $log_g y \neq hog_h z$.

$\endgroup$
  • $\begingroup$ BTW. In the LNCS version of this paper, it's Section 5. $\endgroup$ – Krystian Sep 18 '16 at 13:21
  • $\begingroup$ If you have a simple procedure for step #2, please spell it out, so that I can compare the complexity with other answers. $\endgroup$ – bobuhito Sep 29 '16 at 12:55
2
$\begingroup$

It could be a proof of knowledge of some $z$ such that $z (x - y) = 1$. The idea is, such an inverse only exists for non equal $x$ and $y$ committed. It works for groups of a prime and hidden (unknown to Prover) order.

$\endgroup$
  • $\begingroup$ Do you have a reference or the actual steps needed here so I can compare the complexity with other answers? $\endgroup$ – bobuhito Sep 29 '16 at 12:59
  • $\begingroup$ This would be a self-reference. Existence of an inverse (in context of polynomial graph representation) could be found at "Zero-Knowledge Proofs via Polynomial Representations", LNCS 7464. A product of vertex color differences was proved there to be non-zero. A Schnorr-like protocol was suggested with "powers in the challenge". Thanx. $\endgroup$ – Vadym Fedyukovych Sep 30 '16 at 17:42
0
$\begingroup$

This elaborates on Krystian's answer, but looks different since I then simplified the process. Given: $g,h,y,z$ where only the prover knows the secret $x$ such that $y=g^x$

Prover chooses random secret $a,b,c$ and reveals:

$$\begin{align} t_1 &= z^a\\ t_2 &= y^a\\ t_3 &= h^{xa}\\ t_4 &= z^b\\ t_5 &= y^b\\ t_6 &= h^c\\ t_7 &= g^c\\ \end{align}$$

Verifier chooses and reveals random $k$. Prover reveals:

$$\begin{align} t_8 &= b+ak\\ t_9 &= c+xak \end{align}$$

Verifier confirms:

$$\begin{align} z^{t_8} &= t_4t_1^k\\ y^{t_8} &= t_5t_2^k\\ h^{t_9} &= t_6t_3^k\\ g^{t_9} &= t_7t_2^k\\ t_1 &\neq t_3 \end{align}$$

(If the last confirmation found equality instead, we have a long-winded zero-knowledge proof for equality of logarithms.)

I'm still hoping someone might answer with a simpler process. By the way, is there a process which transfers even less knowldege by appearing the same when either logarithm is known (i.e., when the prover instead knew $x_2$ such that $z=h^{x_2}$)? With the process here, the verifier learns that the base-g logarithm is known.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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