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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\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$ Commented Jan 1, 2021 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$ Commented Jan 1, 2021 at 14:01

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.