2
$\begingroup$

I am looking at at the $1–2 \space \text{oblivious transfer}$ that is described here: https://en.wikipedia.org/wiki/Oblivious_transfer#:~:text=In%20cryptography%2C%20an%20oblivious%20transfer,Rabin.

I want to show that a malicious sender (Alice) can attack this protocol if it can deviate from it, namely, send a wrong RSA key pair, and learn the secret bit $b$.

If the sender (Alice) sends $e$ such that $gcd(e, \phi(N)) \neq 1$, then the RSA key is not valid, but the receiver (Bob) can't efficiently know this without the factorization of $N$.

However, I don't exactly understand how sending such an invalid input $e$ helps.

Since $e$ and $\phi(N)$ aren't coprime, then $k^e$ from the protocol that the receiver sends is not exactly random. But how does it help to understand who is $b$?

Help would be appreciated.

$\endgroup$
2
$\begingroup$

I want to show that a malicious sender (Alice) can attack this protocol if it can deviate from it, namely, send a wrong RSA key pair, and learn the secret bit $b$.

You can, in fact, show this (or, rather, the OT would require a ZK proof by Alice that $\gcd(e, \phi(N)) = 1$)

However, I don't exactly understand how sending such an invalid input $e$ helps.

If $\gcd(e, \phi(N)) > 1$, then not all values $z$ have $e$th roots, that is, sometimes there won't be a value $y$ with $y^e = z$. And, if you know the factorization, this is easy to test.

So, when Alice gets the value $v = (x_b + k^e) \bmod N$, she can compute $v - x_0$ and $v - x_1$. The correct one will be an $e$th root; the wrong one will likely not be - if it is not, then she will then know $b$.

One issue that Alice will run into is that, in this case, she would not be able to unambiguously recover $k$; this would prevent her from being able to complete the protocol. However, the damage has already been done.

$\endgroup$
2
  • $\begingroup$ Thanks! Could you clarify why the correct one will be an $e$th root, and the wrong one will likely not be? $\endgroup$
    – Gabi G
    Jan 1 at 11:54
  • $\begingroup$ @GabiG: well, if $b=0$, then $v - x_0 = k^e$, Alice doesn't know what $k$ is, but it will exist, and hence $v - x_0$ will have a $e$th root. In contrast, $v - x_1$ is effectively a random value, and random values have an aproximately $1/e$ probability (if $e$ is prime and $e$ is a factor of only one of $p-1, q-1$; otherwise, it's more complicated) of having an $e$th root, that is, being $k'^e$ for some value $k'$ $\endgroup$
    – poncho
    Jan 1 at 14:01

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.