# Leak Information?

Let a,b,c,d be selected at random from $\mathbb Z^*_q$. We pick values $r_1,r_2,r_3,z_1,z_2,z_3 \gets \mathbb Z^*_q$. Do $u_1,u_2$ that are computed as follows, leak information about values $a,b,c,d$? (a p.p.t addversary can gain information abut values a,b,c,d or these relations with non negligible probabelity؟).

$$u_1=(r_1\cdot a,r_2\cdot b,r_3\cdot c,(r_1+r_2-r_3)\cdot d)$$

$$u_2=(z_1\cdot a,z_2\cdot b,z_3\cdot c,(z_1+z_2-z_3)\cdot d)$$

Any kind of information, maybe even only under special conditions?
Sure. Just an easy one:

Since we know $(r_1 \cdot a)$ amd $(z_1 \cdot a)$, we can easily calculate
$f_1 = (r_1 \cdot a) \cdot (z_1 \cdot a)^{-1} = z_1 \cdot r_1^{-1}$
Similar for $f_2$ and $f_3$.

Lets in this easy case assume that $f_2 = f_3$.

We further know
$(r_1 + r_2 - r_3) \cdot d$ and $(z_1 + z_2 - z_3) \cdot d$
which is
$(r_1 \cdot f_1 + r_2 \cdot f_2 - r_3 \cdot f_3) \cdot d$ and with our assumption
$(r_1 \cdot f_1 + r_2 \cdot f_2 - r_3 \cdot f_2) \cdot d$

Subtracting
$(r_1 + r_2 - r_3) \cdot d \cdot f_2$ from the last line gives
$r_1 \cdot (f_1 - f_2) \cdot d$

Multiplying $(f_1 - f_2)^{-1}$ which is easily calculated, and $(a \cdot r_1)^ {-1}$ which is known,
gives the "quotient" $d \cdot a^{-1}$

Depending on what the given values are and why/how they are chosen, $f_2 = f_3$ may be very unlikely (or not). Still, the described way gives out some information in this case (which is bad for security ofc).

Other than $d \cdot a^{-1}$, $d \cdot b^{-1}$ and $d \cdot c^{-1}$ can be calculated in a similar way if $f_1 = f_3$ and/or $f_1 = f_2$.

• You may want to note that $f_2=f_3$ is extremely unlikely for a large-sized $q$ given that they are both essentially random group elements. – SEJPM Jun 2 '18 at 8:35

The answer is correct. For this aim, you can consider the following consequence:

$$f_1=r_1^{-1}\cdot z_1,~f_2=r_2^{-1}\cdot z_2,~f_3=r_3^{-1}\cdot z_3$$

Then we have from the third component $u_1$ and $u_2$:

$$(r_1+r_2-r_3)\cdot d=\alpha$$

$$(z_1+z_2-z_3)\cdot d = (r_1 \cdot f_1+r_2 \cdot f_2-r_3 \cdot f_3)\cdot d=\beta$$

Using the multiplication $f_1$, $f_2$ and $f_3$ in the above formula (first) and subtracting from the second, we obtain the following three equations:

$$r_2 \cdot d \cdot (f_1-f_2) - r_3 \cdot d \cdot (f_1 - f_3)= \alpha \cdot f_1 - \beta$$

$$r_1 \cdot d \cdot (f_2-f_1) - r_3 \cdot d \cdot (f_2 - f_3)= \alpha \cdot f_2- \beta$$

$$r_1 \cdot d \cdot (f_3-f_1) - r_2 \cdot d \cdot (f_3 - f_2)= \alpha \cdot f_3 - \beta$$

In the next step, let $x_1=r_1 \cdot d, x_2=r_2.d, x_3=r_3 \cdot d$, thus we have:

$$x_2 \cdot (f_1-f_2) - x_3 \cdot (f_1 - f_3)= \alpha \cdot f_1 - \beta$$

$$x_1 \cdot (f_2-f_1) - x_3 \cdot (f_2 - f_3)= \alpha \cdot f_2 - \beta$$

$$x_1 \cdot (f_3-f_1) - x_2 \cdot (f_3 - f_2)= \alpha \cdot f_3 - \beta$$

Finally, we solve the linear equation system. Therefore, we obtain values $x_1$, $x_2$ and $x_3$.