Let $\mathbb G$ with generator $g$, it's 256-bit prime order $q$, and the 128-bit prime $p$ be known and fixed.
Assume we get an algorithm $\mathcal A$ which on input $(h_1,h_2)\in\mathbb G^2$, with $h_1=g^{a_1}$, $h_2=g^{a_2}$ for random $a_1,a_2\in\mathbb Z_q$, outputs $h_3=g^{a_1+a_2\bmod p}$ with non-vanishing probability, as in the question.
Define algorithm $\mathcal A'$ that on input $h\in\mathbb G$ attempts to output $y$ with $g^y=h$, and towards this:
- draws $u$ random in $\mathbb Z_q$, computes $h_1=g^u\;h$, which now is random in $\mathbb G$; there's thus a unique (as yet unknown, random) $a_1\in\mathbb Z_q$ with $g^{a_1}=h_1$
- draws $a_2$ random in $\mathbb Z_q$, computes $h_2=g^{a_2}$
- runs $\mathcal A$ with input $(h_1,h_2)$, gets $h_3$ assumed to be (with non-vanishing probability) $g^{a_1+a_2\bmod p}$
- finds $x\in\mathbb Z_q$ with $0\le x<p<2^{128}$ such that $g^x=h_3$, which requires in the order of $2^{66}$ group operations using Polard's rho with distinguished points, feasibly little memory, and is easily distributed
- computes $r=x-a_2\bmod p$; it holds $a_1\equiv r\bmod p$, and $0\le a_1<q$; let the (sd yet unknown) $s\in\left[0,\left\lfloor q/p\right\rfloor\right]$ be such that $a_1=r+s\,p$, thus $g^{r+s\,p}=h_1$, thus $g^{s\,p}=h_1\,g^{q-r}$, thus $g^s=(h_1\,g^{q-r})^{p^{-1}\bmod q}$
- computes $h_4=(h_1\,g^{q-r})^{p^{-1}\bmod q}$; it holds $g^s=h_4$ and $s<2^{129}$
- finds $s$ by essentially the same method as $x$
- computes $a_1=r+s\,p$, which is thus such that $g^{a_1}=h_1$
- computes and output $y=a_1-u\bmod q$, which is such that $g^y=h$.
Our algorithm $\mathcal A'$ is thus able to computes the discrete logarithm $y$ to base $g$ of any given element $h$ in $\mathbb G$ with non-vanishing probability, and feasibly little works. This is hypothesized impossible. Hence our assumption that $\mathcal A$ exists is false.
We thus answer the question in the negative.
