Cryptography
- encryption randomness semantic-security probabilistic-encryption
- Updated Fri, 15 Jul 2022 02:23:05 GMT
-
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)$$
Solution
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$.