6
$\begingroup$

Given two different safe primes $p_1$, $p_2$ we construct the subgroups $G_1$ of prime order $q_1 = \frac{p_1-1}{2}$ and $G_2$ of prime order $q_2 = \frac{p_2-1}{2}$. Let $g_1$ be a generator of $G_1$ and $g_2$ be a generator of $G_2$. We assume that the discrete logorithm is hard in both groups.

Alice randomly selects some secret value $ s \in \mathbb{Z}_{min\{q_1, q_2\}} $. Alice calculates $ x_1 := g_1^s \in G_1 $ and $ x_2 := g_2^s \in G_2 $ and a cryptographic hash $ H(s) $.
Alice sends $x_1$, $x_2$ and $H(s)$ to Bob via a secure channel.

Is there some pratical way that Bob can be sure that Alice indeed has sent values $ x_1 = g_1^a $ and $ x_2 = g_2^b $ such that $ a = b $? If not, can Alice provide additional data without revealing $s$ to convince Bob?

This question is somewhat related to "How can we prove that two discrete logarithms are equal?". However in our case two generators from two different groups are used instead of two generators from one group.

EDIT: Regarding the comments from poncho and Yehuda Lindell I further clarify what I mean by "discrete logarithm equality for independent groups":

I would like to use the following definition for $dlog_{g}$:
$ {dlog}_g(g^e) := $ smallest $ x \mid x \geqslant 0, g^x \equiv g^e \pmod p $

Given $ s_1 = dlog_{g_1}(g_1^s) $ and $ s_2 = dlog_{g_2}(g_2^s) $
then $ dlog_{g_1}(g_1^s) \ $ equals $ \ dlog_{g_2}(g_2^s) \ $ iff $ \ s_1 = s_2 $

$\endgroup$
  • $\begingroup$ Well, there is the generic ZK proof for every NP statement... Are you looking for something practical? $\endgroup$ – fkraiem Mar 15 '17 at 17:45
  • $\begingroup$ Yes, definitely looking for a practical solution. Based on your comment I guess that a generic ZK proof is not (yet) considered practial - is that correct? $\endgroup$ – raisyn Mar 15 '17 at 17:56
2
$\begingroup$

Let me assume for simplicity that $q_1 \leq q_2$. You want to prove that the discrete log of $x_1$ in $G_1$ is the same that the discrete log of $x_2$ in $G_2$, and that this discrete logarithm seen as an integer is smaller than $q_1$. This suggests that you should rely on a zero-knowledge proof for a relation over the integers. The most natural method to do this kind of proofs is to work over a group of unknown order, as, intuitively, if the prover does not know the order of the group he cannot reduce the exponents modulo this order - and the relation should hold over the integers.

So, let $G$ be a group of unknown order where the discrete logarithm is hard (for example, the subgroup of squares of an RSA group). Let com$(\cdot)$ be a perfectly hiding integer commitment scheme over $G$ (e.g. the Fujisaki Okamoto commitment scheme). Let $s \le q_1$ be your secret exponent. In addition to $x_1 = g_1^{s} \in G_1$ and $x_2 = g_2^s \in G_2$, the prover sends a commitment com$(s) = c$ over $G$.

Let us take the protocol suggested by professor Lindell as a basis. Consider the following modification of this protocol:

  • the answers are not computed modulo $q_1\cdot q_2$, but they are instead computed over the integers. For this not to break the zero-knowledge property, the mask $r$ should be taken, say, 160 bits longer than $s$, so as to statistically mask $e\cdot s$ over the integers.
  • The prover proves knowledge of $s$ which is the discrete log of $x_1$ and $x_2$ and the value committed in $c$
  • The prover additionally proves that the value committed in $c$ is lower than $q_1$. The classical method to do so is as follows: both players compute $c’$ from $c$ and $q_1$, a value that commits to $s’ = q_1 - s$ (the Fujisaki-Okamoto scheme is homomorphic, it is essentially com$(m;r) = g^mh^r$). Observe that $s \leq q_1$ is equivalent to $s’ \geq 0$. moreover, by a classical result of Lagrange, an integer is positive if and only if it can be written as a sum of four squares. Therefore, the prover computes this decomposition of $s’$ into a sum of four squares (via the Rabin-Shallit algorithm), commits to them, and proves that $s’$ is the sum of the squares of these committed values. Such a protocol is known as a range proof and is described in several papers, e.g. this one.

Once this protocol is complete, the verifier is convinced that the prover knows an integer $s \leq q_1$ such that $g_1^s = x_1$ and $g_2^s = x_2$. One can refine the protocol to make it more efficient, but I tried to make the answer as intuitive as possible.

$\endgroup$
1
$\begingroup$

I am pretty sure that the regular DDH sigma protocol should work here as well. In order to make things work, a few changes are needed. Specifically:

  1. Prover chooses a random $r\in\mathbb Z_{q_1\cdot q_2}$ and computes $h_1 = g_1^r \mod p_1$ and $h_2 = g_2^r \mod p_2$, and sends $h_1,h_2$ to the verifier.
  2. The verifier sends a random challenge $e\in\{0,1\}^t$.
  3. The prover replies with $z=r+es \mod q_1\cdot q_2$
  4. The verifier checks that $g_1^z = h_1 \cdot x_1^e \mod p_1$ and $g_2^z = h_2 \cdot x_2^e \mod p_2$.

This should all work easily for soundness (but needs to be checked). The only question is zero knowledge since $r$ is not chosen randomly in $\mathbb Z_q$ but in $\mathbb Z_{q_1\cdot q_2}$. In the interest of leaving you some interesting work to do, this should be checked. So, try to prove it and then let us know :-).

$\endgroup$
  • $\begingroup$ Looks promising :) I'll start with an soundness example and then work my way up. $\endgroup$ – raisyn Mar 15 '17 at 19:05
  • 1
    $\begingroup$ Lets put it this way; suppose I pick arbitrary values $s_1, s_2$, generate $x_1 = g_1^{s_1}$ and $x_2 = g_2^{s_2}$ and compute $s$ with $s \equiv s_1 \pmod{q_1}$ and $s \equiv s_2 \pmod{q_2}$ (which I can always do, as $q_1, q_2$ are relatively prime). If $s_1 \ne s_2$, what fails within the above ZKP? $\endgroup$ – poncho Mar 15 '17 at 20:53
  • 1
    $\begingroup$ @poncho I didn't see this as a problem, because I guess we have to define what it means to have the same discrete log in groups of different order. If $s=s_1 \bmod q_1$ and $s=s_2 \bmod q_2$ then the question is whether this means that the discrete log is the same. Specifically, by the above, $g_1^{s_1} = g_1^s \bmod p_1$ and $g_2^{s_2} = g_2^s \bmod p_2$. So they do have the same discrete log. $\endgroup$ – Yehuda Lindell Mar 15 '17 at 21:15
  • 1
    $\begingroup$ If you take that definition, then the problem becomes "prove that you know both the discrete log of $g_1$ and the discrete log of $g_2$". However, that's not what raisyn asked for, he specifically stated that $s \in \mathbb{Z}_{min\{q_1, q_2\}}$. $\endgroup$ – poncho Mar 15 '17 at 21:26
  • 1
    $\begingroup$ I missed the min part in the question. However, note that my interpretation is still a natural one and it's not just knowing both; it guarantees that it's the same dlog, for a certain definition of this problem. $\endgroup$ – Yehuda Lindell Mar 15 '17 at 21:29
1
$\begingroup$

If you don't mind performance too much, perhaps the following could work:

Observe that $G_1 \times G_2$ is a cyclic group of order $q_1q_2$, and that $(g_1,g_2)$ is a generator for this group.

The problem of equality of discrete logarithms as specified then reduces to showing that the logarithm of $(x_1,x_2)$ to the base $(g_1,g_2)$ is smaller than $\min\{q_1,q_2\}$.

I do not know what the state of the art is for range proofs for discrete logarithms. But the naive approach is to show that $s$ or $\min\{q_1,q_2\}-s-1$ can be written as a suitably small binary number. Which you can do as follows:

  • Commit to the bits of the number by committing to $1$ or the generator (raised to $2^i$) using a homomorphic commitment scheme.
  • Prove that each commitment is a bit commitment, using an "or"-proof.
  • Add the commitments up.
  • Open the commitment to the correct value.

There are a number of details I haven't worked out.

(If you can do significantly better than a range proof for discrete logarithms, then perhaps you have a better (but somewhat restricted) range proof for discrete logarithms...)

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