# Zero-Knowledge proof of inequality

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.

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

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

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.

• Do you have a reference or the actual steps needed here so I can compare the complexity with other answers? – bobuhito Sep 29 '16 at 12:59
• 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. – Vadym Fedyukovych Sep 30 '16 at 17:42

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.