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