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$

$(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$.

  • 2
    $\begingroup$ 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. $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.