2
$\begingroup$

I'm trying to implement a simple 1-out-of-2 Oblivious Transfer with RSA. I was checking the code and tried to work it step by step. The 2 messages by Alice, let's say, are $m_0 = 7$ and $m_1 = 9$. Bob's decryption turns out to be -8. Can you please help me understand what I'm doing incorrectly? Am I missing $\bmod N$ somewhere?

  • $m_0 = 7$, $m_1 = 9$
  • $p: 3$, $q: 5$, $\phi: 8$, $N: 15$
  • coprime $e: 3$
  • $d: 3$
  • Public and private keys: $(3, 15)$
  • $X_0, X_1: 8, 5$
  • Bob's choice: $b=0$, random $k: 22$
  • $x_b: 8$
  • $v = (8+22^3) \bmod 15 = 6$
  • $v: 6$, $k_0: (6-8)^3 \bmod 15 = 7$, $k_1: (6-5)^3 \bmod 15 = 1$
  • $m_0+k_0: 7+7= 14=M_0$
  • $m_1+k_1: 9+1= 10=M_1$
  • $M_b: 14$
  • Bob decrypts: Chosen Message: $17-22 = -8$
$\endgroup$
2
  • 1
    $\begingroup$ Yes, the question (and the wikipedia page it now links to) are missing a final reduction modulo $N$. $\endgroup$
    – fgrieu
    Dec 9, 2023 at 15:57
  • $\begingroup$ That is M0 and M1 that Alice sends to Bob should be computed as modulo N, and in the last step Bob also must do modulo N? $\endgroup$
    – Guest
    Dec 9, 2023 at 20:48

1 Answer 1

1
$\begingroup$

Yes, reductions modulo $N$ are missing in the question, for $m_0+k_0$, $m_1+k_1$ (even though they do nothing for the parameters used), and the final $17−22=−8$, which after reduction modulo $N=15$ yields the expected $m_b=7$.

Except for the public key $(e,N)$, everything that's exchanged, and the final decryption, is to be reduced modulo $N$. The final reduction is necessary to consistently get the correct result. The other reductions are necessary to avoid information leak.

The wikipedia description of RSA-based 1-out-of-2 Oblivious transfer is now hopefully fixed.

Notice that $p$ and $q$ in the question are way too small for security. They should be like 1000-bit (300 decimal digits), rather than 2 or 3-bit (1 decimal digit).


1-out-of-2 Oblivious Transfer with RSA

$A$ has two secrets $m_0$ and $m_1$. The protocols sends one of the two to $B$, as decided by $B$, over a public channel, with $A$ not knowing ("oblivious to") which secret $B$ decided to receive. Some passive observer does not learn the secrets, or $B$'s choice.

We assimilate bitstrings to non-negative integers per some convention, e.g. big-endian binary.

  1. Key setup: $A$ generates (or reuses) an RSA key pair with public key $(e,N)$ and private key $(d,N)$, and makes $(e,N)$ known to $B$. We assume $N$ large enough for security, and $N>\max(m_0,m_1)$.
  2. $A$ generates random $x_0$ and $x_1$ uniformly at random in $[0,N)$ and sends $(x_0,x_1)$ to $B$.
  3. $B$ secretly chooses $b\in\{0,1\}$, generates random $k$ uniformly at random in $[0,N)$, computes and sends $v=((k^e\bmod N)+x_b)\bmod N$ to $A$.
  4. $A$ computes ${m'}_0=(((v-x_0)^d\bmod N)+m_0)\bmod N$, ${m'}_1=(((v-x_1)^d\bmod N)+m_1)\bmod N$, and sends $({m'}_0,{m'}_1)$ to $B$.
  5. $B$ computes $m_b=({m'}_b-k)\bmod N$

The protocol is sound (that is, $B$ faithfully gets the desired secret) because in step 4 it holds $(v-x_b)^d\bmod N=k$.

The protocol keeps $b$ perfectly secret from $A$ or an observer because the distribution of $v$ (the only thing sent by $B$) is undistinguishable from a uniformly distributed random over $[0,N)$ even with knowledge of $(e,d,N)$ and $(x_0,x_1)$, because $k$ has this distribution and $k\mapsto k^e\bmod N$ is a bijection.

It looks like if $B$ could learn the other secret $m_{1-b}$, or if an adversary could learn either secret, they could break RSA. However I do not know if we need the hypothesis that $m_0$ and $m_1$ are random and independent (which we could get with random padding as in RSA encryption). Addition of such (or other) info/argument/proof in this community wiki is welcome!

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.