discrete logarithm equality for independent groups

Question

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 $

Answer 1

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.

Answer 2

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 :-).

Answer 3

Here's a paper describing how to do it efficiently, with some concrete sizes depending on the size of $a$ and $b$: https://eprint.iacr.org/2022/1593, Fig. 1 (check table 1 for notation).
It uses the same ideas already suggested by Geoffroy and Yehuda, with the additional paradigm of Fiat-Shamir with aborts which results in a better concrete efficiency.

Answer 4

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

Answer 5

This paper provides a solution that uses zk-SNARK:

https://eprint.iacr.org/2022/1079