# How to attack Oblivious Transfer from a malicious sender that can deviate from the protocol

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.

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.

• Thanks! Could you clarify why the correct one will be an $e$th root, and the wrong one will likely not be? Jan 1, 2021 at 11:54
• @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'$ Jan 1, 2021 at 14:01