3
$\begingroup$

Let $g$ be a generator of multiplicative group mod $p$ a prime.

Suppose we know $$g^{a+km_1}\bmod p$$ $$g^{b-km_2}\bmod p$$ $$g^{a+k'm_3}\bmod p$$ $$g^{b-k'm_4}\bmod p$$ where $m_2m_3-m_4m_1=\phi(p)$ where $\phi$ is Totient and $a,b,k,k'$ are the only unknown and all of $a$ through $m_4$ are of size $\sqrt p$ (we know $m_1$ through $m_4$ over $\mathbb Z$) can we identify $g^a$, $g^b$ in polynomial time?

We are allowed to assume a Diffie Hellman oracle?

$\endgroup$
4
  • $\begingroup$ Is this a homework assignment? Or, is this a 'hard problem' you came up with when analyzing a crypto protocol? $\endgroup$
    – poncho
    Mar 7, 2022 at 22:30
  • $\begingroup$ It is a hard problem... I am unable to make progress. I do not know if it has a solution. $\endgroup$
    – Turbo
    Mar 7, 2022 at 22:33
  • $\begingroup$ hard problem == Homework assingment? $\endgroup$
    – kelalaka
    Mar 8, 2022 at 11:45
  • $\begingroup$ "I do not know if it has a solution" == research. $\endgroup$
    – Turbo
    Mar 8, 2022 at 11:46

2 Answers 2

1
$\begingroup$

I think not. If we could extend such a construction to black box group, it would give a $q^{1/4}$ method for solving discrete logarithms in that group. Also note that if the size constraint on $a$, $b$, $k$ and $k'$ is removed, the problem is not well-defined (there may be multiple solutions even in the constrained case; I'm not sure).

Multiple solutions if size constraints are ignored

Generically we can consider this isomorphic to a linear algebra problem in the exponents. We write $c_1=a+km_1$, $C_i=g^c_i\mod p$ and so forth. By multiplying terms $C_iC_j$ or exponentiating terms $C_i^d$ we can add $c_i+c_j$ or multiply our unknown exponents by constants $dc_i$, so that we can find $g^x$ where $x$ is an arbitrary linear combinations of these $c_i$ (a Diffie-Hellman oracle would allow us to form $g^y$ where $y$ is an arbitrary polynomial expressions in the $c_i$). Restricting ourselves to such linear combinations (as would be the case for a black box group), the problem becomes to find a linear combination of our $c_i$ that is equal to $a$ or $b$.

We have the system $$\left(\matrix{1&0&m_1&0\\ 0&1&0&-m_2\\ 1&0&m_3&0\\ 0&1&0&-m_4}\right)\left(\matrix{a\\ b\\ k\\ k'}\right)=\left(\matrix{c_1\\ c_2\\c_3\\c_4}\right)\pmod{\phi(p)}$$ if we write $M$ for the 4x4 matrix and $\mathbf c$ for the right hand vector, we might hope to find our linear combination from $M^{-1}\mathbf c$. However we see that $$\mathrm{det}(M)=m_1m_4-m_2m_3\equiv 0\pmod{\phi(p)}$$ so that our matrix is not invertible.

High school linear algebra now tells us that we either have no solutions or many solutions. The fact that our construction defines one solution tells us that there are many solutions. A little row reduction tells us that $m_2c_1+m_1c_2-m_3c_3-m_1c_4\equiv 0\pmod{\phi(p)}$. In particular then if e.g. $m_1$ is coprime to $\phi(p)$, we can determine $C_4$ given $C_1$, $C_2$ and $C_3$ and so the 4th equation grants us no additional information. In the absence of further degeneracy, it follows that we can, for example, choose an arbitrary $g^a$ and then find $g^k\equiv(C_1/g^a)^{1/m_1}\pmod p$, $g^b\equiv C_2(g^k)^{m_2}\pmod p$ and $g^{k'}\equiv(C_3/g^a)^{1/m_3}$ that produce the $C_1$, $C_2$, $C_3$ and $C_4$ that we are presented with. However, the $a$, $b$, $k$ and $k'$ associated with these will not necessarily meet the size constraints.

A no-go in the black box model

Now suppose that we can extended such a solver to a black box multiplicative group. Suppose that we are given a discrete logarithm problem for the generator $g$ of order $q$ and the element $C_1$ is such a group. We choose an arbitrary $m_1$ and by a counting argument there is a strong probability that $c_1$ can be written in the form $c_1\equiv a+km_1\pmod q$ with $a,k\le q^{1/2}$. Write $d=[q^{1/2}]$. We now call our solver with $C_1=C_1$, $C_2=g^d/C_1$, $C_3=C_1g^{m_1}$ and $C_4=g^d/C_3$ and $m_1=m_2=m_3=m_4$ (corresponding to the values $b=d-a$ and $k'=k+1$ which satisfy the size constraints). Our solver will return $g^a$ from which we can recover $a$ using the baby-steps/giant-steps method in $O(\root 4\of q)$ steps. Similarly we can recover $g^k=(C_1/g^a)^{1/m_1}$ and $k$ in another $O(\root 4\of q)$ steps. This allows us to compute $c_1$ with $O(\root 4\of q)$ group operations which is not possible for a black box group.

$\endgroup$
16
  • $\begingroup$ Yes, $\sqrt q$ is possible to compute $c_1$, but $\root 4\of q$ is not. Recall that $c_1$ is arbitrary and we have a contradiction. $\endgroup$
    – Daniel S
    Mar 8, 2022 at 18:03
  • $\begingroup$ What is $C_1$ and what is $c_1$? Are they same? $\endgroup$
    – Turbo
    Mar 8, 2022 at 18:31
  • $\begingroup$ @Turbo as in the first part $C_1=g^c_1\mod p$. The argument does not preclude some use of the structure of $\mathbb Z/p\mathbb Z$, but does mean that to recover $g^a$ we must do something other than raise the $C_i$ to powers and multiply. $\endgroup$
    – Daniel S
    Mar 8, 2022 at 18:46
  • $\begingroup$ You could use the general number field sieve to recover $c_1$ (not polynomial time, but certainly subexponential) and then use lattice basis reduction to find $a, k\approx\sqrt p$ such that $a+km_1\equiv c_1\pmod p$. $\endgroup$
    – Daniel S
    Mar 8, 2022 at 18:52
  • $\begingroup$ $m_1m_4-m_2m_3=0$ here and not $\lambda(p)$. $\endgroup$
    – Turbo
    Mar 9, 2022 at 14:08
2
$\begingroup$

Well, one obvious observation is that, if we call the four revealed values $C_1, C_2, C_3, C_4$ (so $C_1 = g^{a+km_1}$), then:

$$C_1^{-m_4} \cdot C_2^{m_3} \cdot C_3^{m_2} \cdot C_4^{-m_1} = (g^a)^{m_2-m_4} \cdot (g^b)^{m_3-m_1}$$

This can be used to distinguish a guess of $g_a, g_b$ from the correct values; hence if "can we identify" means "distinguish", then yes, we can do that.

I don't know if there is a way to add a second observation which would allow you to recover the $g^a, g^b$ values.

$\endgroup$
12
  • $\begingroup$ That's a necessary condition on $g^a$ and $g^b$, but not a sufficient one. For example the pair $g^{a+m_3-m_1}$ and $g^{b-m_2+m_4}$ would also pass this test. $\endgroup$
    – Daniel S
    Mar 8, 2022 at 10:53
  • $\begingroup$ What if we assume DH oracle? I think it may not be necessary though. $\endgroup$
    – Turbo
    Mar 8, 2022 at 11:02
  • $\begingroup$ @Turbo A DH oracle will not change the fact that there is a large family of solutions that pass poncho's test and any other test that relies on exponentiating and multiplying the $C_i$. Indeed this family allows us to take any arbitrary value for $g^a$ and find putative values for $g^b$, $g^k$ and $g^{k'}$ that pass all such tests. $\endgroup$
    – Daniel S
    Mar 8, 2022 at 18:49
  • $\begingroup$ @DanielS But DH operations are not BB.. so may be there is hope? $\endgroup$
    – Turbo
    Mar 8, 2022 at 18:50
  • $\begingroup$ I think it should be $C_1^{m_4} \cdot C_2^{m_3} \cdot C_3^{m_2} \cdot C_4^{m_1} = (g^a)^{m_2+m_4} \cdot (g^b)^{m_3+m_1}$ in Poncho's approach. Or else the problem gets trivially solved. $\endgroup$
    – Turbo
    Mar 8, 2022 at 19:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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