暗号勉強会

あまりコードが出てこない話

Mental PokerとGarbled Circuitについて解説!

この記事では古典的なマルチパーティ計算モデルであるMental PokerとGarbled Circuitを解説します。どちらも1980年代の手法でマルチパーティ計算の歴史を知る上では重要だと思います。

Mental Poker

メンタルポーカーとはポーカーのカードをサードパーティなしに公平に交換しようというプロトコルで、RSA暗号のRivestとShamirとAdlemanの提案した手法です。なお、当時はRSA暗号の研究が進んでいなかったので十分な方式だったのですが、今は欠陥が発見されており、危殆化してしまった方式でもあります。

メンタルポーカーは以下の性質を満たすような鍵とメッセージがあれば実現可能です。

  1. E_K(X)を鍵Kによって暗号化されたメッセージXと定義する。

  2. 任意の鍵KとメッセージXについてD _ K(E _ K(X))=Xが成立する。(一意復号の可能性)

  3. 任意の鍵JとKについてE _ J(E _ K(X))=E _ K(E _ J(X))が成立する。 (暗号関数の可換性)

  4. 任意のメッセージXとE _ K(X)から、すべてのXとKに対してKを導出することは計算量的に困難である。

  5. 任意のメッセージXとYから、E_J(X) = E_K(Y)となるような鍵JとKを見つけることは計算量的に困難である。

これを実現しているのは論文の筆者であるRivest,Shamir,Adleman,が提案したRSA暗号の復号、暗号アルゴリズムです。RSAが可換なのは以下より明らかでしょう。


Enc_K(X)=X^K mod\ n \\
Dec_L(C)=M^L mod\ n

実際、

Enc _{K}(Enc_{J}(X))= Enc_{J}(Enc_{K}(X))=X^{JK} mod\ n

は容易にわかる。それで、この可換性を利用することで、ポーカーのプロトコルは以下のように実現できる。

  1. ボブは各52枚のカードを受け取り、すべてのカードをおのおの暗号化する。

  2. ボブは暗号化されたデッキをシャッフルしてアリスに送る。

  3. アリスはデッキから5枚選びボブに送る。ボブはこの5枚を手札にする。

  4. アリスはデッキから自分のために5枚選び暗号化し、ボブに送る。

  5. ボブはその5枚を復号し、アリスに送る。アリスはこの5枚を手札にする。

4ができるのは暗号化関数の可換性より

Dec_B(E_A(E_B(X)))=Dec_B(E_B(E_A(X)))=E_A(X)

このプロトコルが面白いのは、ボブの手札を選ぶのはボブの鍵を持たずデッキを復号できないアリスで、アリスの手札を選ぶのはアリスの鍵を知らずデッキを復号できないボブということろだと思いました。

Garbled Circuit

ここからはGarbled Circuitについて説明します。Garbled Circuitは1982年にYaoが提案した2パーティ間のマルチパーティ計算プロトコルです。

2入力の場合

  1. アリスはGCTを作成する。これをシャッフルすることで、鍵との対応を分からないようにする。

  2. アリスは各ワイアx,y,xについて、k^{0} _ x,k^{1} _ x,k^{0} _ y,k^{1} _ y,k^{0} _ z,k^{1} _ zを生成する。

  3. アリスは入力ビットをa\in\{0,1\}として、k^{1} _ xをボブに送る。

  4. アリスはボブにk^{0}  _  y,k^{1} _ yのどちらかの鍵を送る。この時にOblivious Transferを用いる。ボブはb\in\{0,1\}を手に入れる。

  5. ボブは手に入れたk _ {y}^bとアリスから送られてきたk _ {x}^aからGCTを復号して、結果をアリスに共有する。

x y z GCT
0 0 0 E^{0}  _ {k _ {x}}(E^{0} _ {k _ y}(k^{0} _ z))
0 1 0 E^{1} _ {k _ {x}}(E^{0} _ {k _ y}(k^{0} _ z))
1 0 0 E^{0}  _ {k _ {x}}(E^{1} _ {k _ y}(k^{0} _ z))
1 1 1 E^{1} _ {k _ {x}}(E^{1} _ {k _ y}(k^{1} _ z))

注意

  • 5ではGCTを復号しているので結果が4行分返ってきますが、このうち復号できているのは一行だけです。この時、復号に失敗したランダムな値と成功したk^{g(a,b)} _ zと見分けがつかないのでZワイアに割り当てる値は、パディングのような冗長な値で復号の成功を確かめられるようにします。
  • GCTをシャッフルしているのは、結果と表の対応関係を隠すためです。シャッフルしないまま計算すると、入力にかかわらず復号に成功した行に対応する真偽値表が分かってしまうので出力から入力が漏洩します。

  • 鍵を送る時に、1 out-of 2 Oblivious Transferを利用して秘密を交換します。アリスはx_0x_1をボブに送信する。この時、ボブはx_sを受け取るためにs\in\{0,1\}を入力します。すると、ボブはx_sを受け取ることができます。この時アリスはボブがx_0x_1のどちらを受け取ったか分からず、ボブはx_s以外の情報を得ることができません。

  • この例ではzワイアにも鍵を割り当てていますが、実は鍵でなくゲートの計算結果である0か1でも問題ありません。鍵を割り当てるのは、zワイアが次のゲートの入力となっていた時に割り当てた鍵k^{i} _ zをもとに鍵を生成するためです。この構成法については後述します。

多入力回路や多段回路の場合

参考文献の他、ここにも詳しく書いてあります。

https://www.researchgate.net/figure/A-simple-example-of-Yaos-garbled-circuit_fig1_313017494www.researchgate.net

鍵はzワイアが次のゲートの入力となっていた時に割り当てた鍵k^{i} _ zをもとに鍵を生成するためと前述しましたが、具体的には鍵を次のGCTを連続的に復号するのに利用します。

まず、n入力関数の評価方法を示し、ゲートの出力が入力になっているような場合にどのような処理をするか確認します。

回路評価の一般化

1: アリスは2(n+m+|G|))個の鍵を生成する。アリスの入力ワイアの数をn、ボブの入力ワイアの数をm|G|fのゲートの総数かつ出力ワイアの数とする。鍵はそれぞれアリスの入力ワイア、ボブの入力ワイア、各ゲートの出力ワイアに対応する。


(k ^ {0} _ {x _ 1},k ^ {1} _ {x _ 1}),\dots,(k ^ {0} _ {x _ n},k ^ {1} _ {x _ n})\\
(k ^ {0} _ {y _ 1},k ^ {1} _ {y _ 1}),\dots,(k ^ {0} _ {y _ m},k ^ {1} _ {y _ m})\\
(k ^ {0} _ {z _ 1},k ^ {1} _ {z _ 1}),\dots,(k ^{0} _ {z _ {|G|}},k ^ {1} _ {z _ {|G|}})\\

2: アリスは関数fのGCTを作成して、シャッフルする。アリスはボブにGCTを送信する。

3: アリスは各入力をa_1,\dots,a _ n \in \{0,1\}としてk _ {a _ 1}^{x_1},\dots k _ {a _ n} ^ {x _ n}n個の鍵をボブに送る。 4: アリスとボブはボブにm回Oblivious Transferを行う。i=1,\dots,m の場合 , i番目の Oblivious Transferの入力は以下のようになる。なお、ここで生成する鍵はそれぞれ(k _ {y_i} ^ {0} , k _ {y_i} ^ {1})に対応する。


Alice’s\ input: (k _ {y_i} ^ {0} , k  _ {y_i} ^ {1})\\
Bob’s\ input: s \in \{0,1\}\\
Bob's\ output: k  _ {y_i} ^ {s}\\

5: ボブは回路のm+n個の入力ワイアのそれぞれに対応する鍵を持っているので、これらの鍵を使ってGCTを復号し、復号で得られる(k ^ {0} _ {z _ 1},k ^ {1} _ {z _ 1}),\dots,(k ^ {0} _ {z _ {|G|}},k ^ {1} _ {z _ {|G|}})を用いつつ関数を評価する。関数f(x _ 1,\dots,x _ n,y _ 1,\dots,y _ m)の評価結果をアリスに共有する。

具体例

以下のような3入力回路f(x_1,x_2,y_1)を考えます。x_1,x_2はアリス、y_1はボブの入力です。

f:id:ATen:20200610232126p:plain
Garbled Circuitの一例

アリスは以下の10個の鍵生成します。


(k ^ {0} _ {x _ 1},k ^ {1} _ {x _ 1}),(k ^ {0} _ {x _ 2},k ^ {1} _ {x _ 2})\\
(k ^ {0} _ {y _ 1},k ^ {1} _ {y _ 1})\\
(k ^ {0} _ {z _ 1},k ^ {1} _ {z _ 1}),(k ^{0} _ {z _ 2},k ^ {1} _ {z _ 2})\\

ANDゲート1に対応するGCT1は

x_1 y_1 z_1 GCT1
0 0 0 E ^ {0}  _ {k _ {x _ 1}}(E ^ {0} _ {k _ {y _ 1}}(k ^ {0} _ {z _ 1}))
0 1 0 E^{1} _ {k _ {x _ 1}}(E^{0} _ {k _ {y _ 1}}(k^{0} _ {z _ 1}))
1 0 0 E^{0}  _ {k _ {x _ 1}}(E^{1} _ {k _ {y _ 1}}(k^{0} _ {z _ 1}))
1 1 1 E^{1} _ {k _ {x _ 1}}(E^{1} _ {k _ {y _ 1}}(k^{1} _ {z _ 1}))

ANDゲート2に対応するGCT2は

x_2 z _1 z _ 2 GCT2
0 0 0 E^{0}  _ {k _ {x _ 2}}(E^{0} _ {k _ {z _ 1}}(k^{0} _ {z _ 2}))
0 1 0 E^{1} _ {k _ {x _ 2}}(E^{0} _ {k _ {z _ 1}}(k^{0} _ {z _ 2}))
1 0 0 E^{0}  _ {k _ {x _ 2}}(E^{1} _ {k _  {z _1}}(k^{0} _ {z _ 2}))
1 1 1 E^{1} _ {k _ {x _ 2}}(E^{1} _ {k _ {z _ 1}}(k^{1} _ {z _2}))
  • アリスはGCT1とGCT2の行をシャッフルしてボブに送ります。

  • 次に、アリスはx _ 1=1,x _ 2=1を入力したいのでk ^ {1} _ {x _ 1},k ^ {1} _ {x _ 2}をボブに送ります。

  • それに続いて、Oblivious Transferを1回行います。ボブがy=1を入力したいとしてs=1を選択したとすれば k ^ {1} _ {y _ 1}をボブは受け取ります。

この時点でボブはk ^ {1} _ {x _ 1},k ^ {1} _ {x _ 2},k ^ {1} _ {y _ 1}を持っています。これを使って、GCTをすべて復号します。

  • まず、GCT1をk ^ {1} _ {x _ 1},k ^ {1} _ {x _ 2},k ^ {1} _ {y _ 1}で復号すると、k ^ {1} _ {z _ 1}だけ復号が成功します。

  • 次にGCT2でk ^ {1} _ {x _ 2},k ^ {1} _ {z _ 1}を復号するとk ^ {1} _ {z _1}だけ復号が成功します。

  • 全体の評価結果はk ^ {1} _ {z _1}、つまり1をアリスに共有します。

ここで最後の出力ワイアに宛てた値はk ^ {1} _ {z _1}ですが、0か1にしても問題ありません。

まとめ

Mental PokerとGarbled Circuitについてまとめました。どちらのモデルもマルチパーティ計算において重要な役割を持った方式だと思いました。

何か間違いがあればコメントをください、お願いします!

参考文献

Protocols for Secure Computations,Andrew C. Yao,1982

A Gentle Introduction to Yao’s Garbled Circuits,Sophia Yakoubov

Oblivious Transfer and Yao's Garbled Circuits 1 Introduction

Mental Pocker ,A Shamir, RL Rivest, LM Adleman,1981