0
$\begingroup$

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?

$\endgroup$
6
  • 1
    $\begingroup$ Is the adversary also given $x_1$ and $x_2$? $\endgroup$
    – Mikero
    Nov 16, 2023 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 S
    Nov 16, 2023 at 21:49
  • $\begingroup$ Yes, the adversary is also given $x_1$ and $x_2$. $\endgroup$
    – Doron
    Nov 17, 2023 at 11:02
  • $\begingroup$ @DanielS can you please elaborate in which cases it is easy to distinguish between $y_1$ and $y_2$? $\endgroup$
    – Doron
    Nov 17, 2023 at 20:14
  • 1
    $\begingroup$ HINT: Jacobi symbols $\endgroup$
    – Daniel S
    Nov 17, 2023 at 22:59

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.