Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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$.
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$.
