Is there a way of convincing someone on (in)validity of Diffie Hellman tuple $<g, g^u, g^v, g^{w}>$ without giving away $u,v$.

or at least solve the Decisional Diffie Hellman Problem without revealing $u,v$.

[Considering the prover knows exactly one of $u$ or $v$]?

I would appreciate references to papers (however I am avoiding Interactive Proofs for this)

  • $\begingroup$ Would you be interesting in non-interactive ZK proofs for this? $\;$ $\endgroup$ – user991 Mar 5 '14 at 7:25

That depends on the groups you are working in.

Using a $\Sigma$-protocol

If you have a group $G$ of prime order $q$ where the DDH is hard and you have a DH tuple $(g,g^u,g^v,g^w)$ with $w\equiv uv \pmod q$, then if your prover knows one of these values, say $u$, then we can write the DH tuple as $(g,g^u,h,h^u)$ and he is able to convince a verifier that this is a DH tuple by means of a standard $\Sigma$-protocol, see here (Section 5) for a concrete protocol. This proof can be made non-interactive by using the Fiat Shamir heuristic.

Gap DH Groups

If you are working in a gap Diffie Hellman group setting, i.e., a setting where the DDH is easy but the CDH is still hard, that is easy without interactive proofs. I use additive notation for groups $G_1$ and $G_2$ below as we are talking about elliptic curve groups.

For instance, take a symmetric cryptographic pairing $e:G_1\times G_1 \rightarrow G_T$ where $G_1$ is an elliptic curve group of prime order $p$ and $G_T$ a multiplicative subgroup if a finite field of the same order $p$. Then $G_1$ is a gap DH group.

Then given $(P, uP, vP, wP)\in G_1^4$ you can check if this is a DH tuple by checking if $$e(uP,vP)\stackrel{?}{=}e(wP,P).$$

Same works for an asymmetric type-2 pairing $e:G_1\times G_2\rightarrow G_T$, where you have an efficiently computable homomorphism $\psi: G_2 \rightarrow G_1$. Here $G_2$ is a gap DH group and when given a DH tuple $(P', uP', vP',wP')\in G_2^4$ you can efficiently check it by checking $$e(\psi(uP'),vP')\stackrel{?}{=}e(\psi(P'),wP').$$

Side note (which at least I find interesting)

An interesting side note is that the Chaum Pedersen signature scheme uses the first approach in DDH hard groups, where the proof is made non-interactive by using the Fiat Shamir heuristic. Here, the DH tuple to check is $(g,g^x,m,m^x)$ where $\sigma=m^x$ is a signature for $m$ w.r.t. public key $h=g^x$ and they require a non-interactive proof $\pi$ that $\log_g h=\log_m \sigma$, i.e., to prove that the signer actually knows the secret key $x$.

The BLS signature scheme essentially does the same in gap DH groups where they do not require this non-interactive proof $\pi$, but can use the pairing $e$ for checking the DH tuple. However, they have to hash the message to a group element using a secure hash function $H$, as the direct application of the Chaum Pedersen approach would make the signature scheme insecure (as otherwise one could forge signatures without the secret key). Here the DH tuple to check is $(P,xP,H(m),xH(m))$ where $xH(m)$ is a signature for $m$ w.r.t to public key $xP$.

  • $\begingroup$ I should have mentioned this before, but I am working with a type1 setting, where I basically need to verify if $e(g_1^{w},g_2) \stackrel{?}{=} e(g_1^{uv},g_2)$, both $g_1,g_2 ∈ G$ $\endgroup$ – Subhayan Mar 4 '14 at 15:28
  • $\begingroup$ @Subhayan I added also a $\Sigma$-protocol based approach. Anyways you will have to present $g^w$ as well as $g^u$ and $g^v$ to the verifier. $\endgroup$ – DrLecter Mar 4 '14 at 19:05

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.