不经意传输

不经意传输(Oblivious Transfer, OT)是一种可保护隐私的双方通信协议、接受者的隐私不被发送者所知道,使通信双方以一种选择模糊化的方式传送消息。抽象地讲,就是A给B发消息,A却不知道B收到的是啥,一般的思路就是A要多发一些消息然后让B去选择有需要的,如果是这样的话,同时还应该保证B不会多知道他本不应该知道的消息。不经意传输可以分为1选1、2选1、n选1、n选k多种不经意传输协议。

1选1

A给B发送一条消息,B只有 $\frac{1}{2}$ 的概率能够接受到真正的消息,且A不知道B是否真正接受了消息。

  1. A取两个素数 $p,q$,计算 $n=pq$,将 $n$ 发送给B;

  2. B任取 $x,x \in (0,n),\gcd(x,n)=1$,计算 $a=x^2 \bmod n$,将 $a$ 发送给A;

  3. A知道 $p,q$,可以计算 $a=x^2 \bmod n$ 的四个根 $(x,n-x,y,n-y)$,从中随机挑选一个送给B;

  4. B若收到 $y$ 或 $n-y$,则可计算 $p,q$:$\gcd(x+y,n)=p$ 或 $\gcd(x+y,n)=q$;

    B若收到 $x$ 或 $n-x$,则B什么也得不到。

2选1

A给B发送两条消息 $(m_0, m_1)$,B能够在不知道另外一条消息的内容的情况下得知其中一条消息的内容,且A不知道B选择的哪条消息。

  • RSA实现

    1. A有两个秘密消息 $m_0,m_1$;

    2. A使用RSA算法,生成公钥 $(N,e)$ 对公开,私钥 $d$ 自己留着。公钥 $(N,e)$ 告知B;

      (每次通信的时候RSA都要重新生成一对公钥私钥)

    3. A产生两个随机数 $x_0,x_1$,并且将这两个随机数传输给B;

    4. B决定要获取的数字编号 $b={0,1}$,以及产生一个随机数 $k$;

    5. B计算一个数字 $v=(x_b+k^e) \bmod N$,并且将这个 $v$ 发送给A;

    6. A计算多个 $k_i$,其中一个 $k_i$ 将会等于 $k$:

      $k_0=(v-x_0)^d \bmod N \ k_1=(v-x_1)^d \bmod N$

      由于此时 $v$ 并不是A产生的,所以此时的A并不知道哪一个 $k$ 是B需要的;

    7. A将生成的值与自己手上的信息进行相加,得到全新的信息:

      $m_0’=m_0+k_0 \ m_1’=m_1+k_1$

      并将信息发送给B。因为此时每一个信息都增加了 $k_i$,所以B无法直接还原信息 $m$;

    8. B此时知道自己选择的信息编号 $b$,于是选出 $m_b$,计算出 $k_b$,并且用 $m_b=m_b’-k_b$ 得到此时的解密信息。

    • 攻击
      • 构造 $v$ 得 $m_0,m_1$

        $v=\cfrac{\text{scale}^e \cdot x_0-x_1}{\text{scale}^e-1}$

        可使 $k_1=\text{scale} \cdot k_0$,因此 $\text{scale} \cdot m_0’-m_1’=m_0 \cdot \text{scale} -m_1$。

        首先,如果恰巧随机数 $m_0$ 和 $m_1$ 都小于 $\text{scale}$,那么直接可以从 $m_0 \cdot \text{scale} -m_1$ 将两者求出。

        其次,如果 $\text{scale}$ 取值不能取得太大,而导致两个 $m$ 总是比它大,那只能老老实实穷举可能的低字节,再向高字节搜索。

        参考:

        Pwnhub - BabyOT

        Hackergame 2020 - 不经意传输

  • 其他实现

    1. A发送 $g^s$ 给B,B知道 $g$ 和 $g^s$ 也无法破译 $s$,因为DLP问题不存在高效解法;

    2. B基于 $i$ 生成 $L_i=\begin{cases} g^k ,& i=0 \ g^{s-k} ,& i=1 \end{cases}$;

    3. B发送 $L_i$ 给A,A知道 $g$ 和 $g_k$ 也无法破译 $k$,因为DLP问题不存在高效解法。

      因此,A无法知道B发来的是 $g_k$ 还是 $g_{s-k}$,也就无法知道 $i$;

    4. A生成 $C_0,C_1$:

      $C_0=(g^{r_0},(L_i)^{r_0} \oplus v_0)\ C_1=(g^{r_1},(\frac{g^s}{L_i})^{r_1} \oplus v_1)$

    5. A发送 $C_0,C_1$ 给B,B知道 $g,g^{r_0},g^{r_1}$ 也无法破译 $r_0,r_1$,因为DLP问题不存在高效解法。

    6. B解密 $v_i$:

      (1) 对于 $i=0$ 的情形:

      B可以通过如下方式解密获得 $v_0$:

      $C_0[0]^k \oplus C_0[1]=(g^{r_0})^k \oplus (L_i)^{r_0} \oplus v_0=(g^{r_0})^k \oplus (g^k)^{r_0} \oplus v_0=v_0$

      B无法获得 $v_1$ 因为 $C_1[1]=(\frac{g^s}{L_i})^{r_1} \oplus v_1=g^{(s-k)r_1} \oplus v_1$,而 B不知道 $s,r_1$。

      (2) 对于 $i=1$ 的情形:

      B可以通过如下方式解密获得 $v_1$:

      $C_1[0]^k \oplus C_1[1]=(g^{r_1})^k \oplus (L_i)^{r_1} \oplus v_1=(g^{r_1})^k \oplus (g^k)^{r_1} \oplus v_1=v_1$

      B无法获得 $v_0$ 因为 $C_0[1]=(L_i)^{r_0} \oplus v_0=g^{(s-k)r_0} \oplus v_0$,而 B不知道 $s,r_0$。

    7. 因此,B只能解密 $v_i$ 而不能解密 $v_{1-i}$。