Given a composite number $n=pq$ of primes $p$ and $q$, a secret random element $r$, and two public random elements $x_1$ and $x_2$. An adversary is given two elements, $y_1= x_1^r \mod n$ and $y_2=x_2^r \mod n$, and its goal is to correctly match $x_1$ with $y_1$ and $x_2$ with $y_2$, with probability $\frac{1}{2}+\epsilon(n)$ where $\epsilon$ is a non neglible function. Is there a security reduction that can be used to prove this?
6
-
1$\begingroup$ Is the adversary also given $x_1$ and $x_2$? $\endgroup$– MikeroNov 16 at 18:54
-
$\begingroup$ Are you asking if there is a reduction to show that this is hard for an adversary? If so, the answer is no because distinguishing is easy in roughly 1/4 of the cases. $\endgroup$– Daniel SNov 16 at 21:49
-
$\begingroup$ Yes, the adversary is also given $x_1$ and $x_2$. $\endgroup$– DoronNov 17 at 11:02
-
$\begingroup$ @DanielS can you please elaborate in which cases it is easy to distinguish between $y_1$ and $y_2$? $\endgroup$– DoronNov 17 at 20:14
-
1$\begingroup$ HINT: Jacobi symbols $\endgroup$– Daniel SNov 17 at 22:59
|
Show 1 more comment