# Finding product of two unknown numbers each raised to a known power

Let $$G$$ be a group, and let $$a, b\in G$$, and let $$ = \{0,1,2\}$$. Let $$(x_i,y_i)$$ for $$i\in$$ be known constants. Assume that I know the elements: $$c_i = a^{x_i}b^{y_i},\quad i\in$$ Then, given $$(x', y')$$, is there a way to efficiently compute $$a^{x'}b^{y'}$$?

• Could you tell us where this is needed in Cryptography? Sep 21, 2020 at 18:55

To say more about this, you need more assumptions on $$(x_0, y_0),\dots, (x_2, y_2)$$. For example, if you write $$B = \begin{pmatrix}x_0 & x_1 & x_2 \\ y_0 & y_1 & y_2\end{pmatrix}$$ to be the $$2\times 3$$ matrix of your known constants, and let: $$\mathsf{span}_{\mathbb{Z}}(B) = \{(x', y')\in\mathbb{Z}^2 \mid \exists \vec{\alpha}\in\mathbb{Z}^3\text{ s.t. }(x', y') = B\vec{\alpha}\}$$ be the span of all of their integer linear combinations, then you can efficiently compute $$a^{x'}b^{y'}$$ for any $$(x', y')\in\mathsf{span}_{\mathbb{Z}}(B)$$ by writing: \begin{align*} \prod_{i\in}c_i^{\vec{\alpha}_i} &= \prod_{i\in}(a^{x_i}b^{y_i})^{\vec{\alpha}_i}\\ &=\prod_{i\in}a^{\vec{\alpha}_i x_i}b^{\vec{\alpha}_i y_i}\\ &=a^{x'}b^{y'},\quad (x', y') = B\vec{\alpha} \end{align*} The above technically uses the assumption that $$G$$ is abelian (commutative), but this is likely intended.
So if $$\mathsf{span}_{\mathbb{Z}}(B) = \mathbb{Z}^2$$ (which is definitely possible), you can compute your desired function for any pair of $$(x', y')$$. But if the span of $$B$$ is not all of $$\mathbb{Z}^2$$, it is not clear how to compute your desired function for $$(x', y') \in \mathbb{Z}^2\setminus\mathbb{span}_{\mathbb{Z}}(B)$$ (at least the prior technique no longer works).