Ballare-Micali OT

oblivious_transfer elgamal暗号

1-out-of-n Oblivious Transferを構成するプロトコル。すなわち、n個のメッセージを送信し、受信者はそのうち1つだけを受信するが、送信者には、受信者がどれを受信したかわからない

準備

G:素数位数pを持つ巡回群

g: Gのgenerator

H: G \to {0,1}^nである、何かしらのハッシュ、SHA1とかでいい

c: Gのある元

プロトコル

Alice から Bob にメッセージを送る

  • Alice は 平文 m_0, m_1 \in {0,1}^n を持ち、 Bob は b \in {0,1} と k \in Z_p を持つ。 m_0 または m_1 のどちらかがBobに受信される

  • Bob は
    PK_b = g^k, PK_{b-1} = c / g^k を計算した後、 PK_0, PK_1 をAliceに送る。Aliceは PK_0PK_1 = c となっていることを確かめておく

  • Aliceは次の C_0, C_1 を計算してBobに送る。これは実は ElGamal暗号 っぽいことになっているらしいのだが、よくわからない

    • C_0 = (g^{r_0}, H(PK_0^{r_0}) \oplus m_0)

    • C_1 = (g^{r_1}, H(PK_1^{r_1}) \oplus m_1)

  • Bobは C_b を復号する。 C_b = (V_1, V_2) とおいて、 m_b = H(V_1^k)\oplus V_2 である

理論

H(V_1^k) = H(g^{rk}) = H(PK_b^r)となるので m_bが復号できることはわかる。また復号の選択権はBobにあるので、Aliceには知りようがないこともわかる

C_{b-1}は復号できないのだろうか。 PK_{b-1} = c / g^kなので、 g^rから (c / g^k)^rが計算できるならOKだが、 rを計算するのが基本的に離散対数問題なので解けない