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 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 at 22:33
  • $\begingroup$ hard problem == Homework assingment? $\endgroup$
    – kelalaka
    Mar 8 at 11:45
  • $\begingroup$ "I do not know if it has a solution" == research. $\endgroup$
    – Turbo
    Mar 8 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 at 18:03
  • $\begingroup$ What is $C_1$ and what is $c_1$? Are they same? $\endgroup$
    – Turbo
    Mar 8 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 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 at 18:52
  • $\begingroup$ $m_1m_4-m_2m_3=0$ here and not $\lambda(p)$. $\endgroup$
    – Turbo
    Mar 9 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 at 10:53
  • $\begingroup$ What if we assume DH oracle? I think it may not be necessary though. $\endgroup$
    – Turbo
    Mar 8 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 at 18:49
  • $\begingroup$ @DanielS But DH operations are not BB.. so may be there is hope? $\endgroup$
    – Turbo
    Mar 8 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 at 19:35

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.