Mental PokerとGarbled Circuitについて解説!
この記事では古典的なマルチパーティ計算モデルであるMental PokerとGarbled Circuitを解説します。どちらも1980年代の手法でマルチパーティ計算の歴史を知る上では重要だと思います。
Mental Poker
メンタルポーカーとはポーカーのカードをサードパーティなしに公平に交換しようというプロトコルで、RSA暗号のRivestとShamirとAdlemanの提案した手法です。なお、当時はRSA暗号の研究が進んでいなかったので十分な方式だったのですが、今は欠陥が発見されており、危殆化してしまった方式でもあります。
メンタルポーカーは以下の性質を満たすような鍵とメッセージがあれば実現可能です。
を鍵Kによって暗号化されたメッセージXと定義する。
任意の鍵KとメッセージXについてが成立する。(一意復号の可能性)
任意の鍵JとKについて=が成立する。 (暗号関数の可換性)
任意のメッセージXとから、すべてのXとKに対してKを導出することは計算量的に困難である。
任意のメッセージXとYから、となるような鍵JとKを見つけることは計算量的に困難である。
これを実現しているのは論文の筆者であるRivest,Shamir,Adleman,が提案したRSA暗号の復号、暗号アルゴリズムです。RSAが可換なのは以下より明らかでしょう。
実際、
は容易にわかる。それで、この可換性を利用することで、ポーカーのプロトコルは以下のように実現できる。
ボブは各52枚のカードを受け取り、すべてのカードをおのおの暗号化する。
ボブは暗号化されたデッキをシャッフルしてアリスに送る。
アリスはデッキから5枚選びボブに送る。ボブはこの5枚を手札にする。
アリスはデッキから自分のために5枚選び暗号化し、ボブに送る。
ボブはその5枚を復号し、アリスに送る。アリスはこの5枚を手札にする。
4ができるのは暗号化関数の可換性より
このプロトコルが面白いのは、ボブの手札を選ぶのはボブの鍵を持たずデッキを復号できないアリスで、アリスの手札を選ぶのはアリスの鍵を知らずデッキを復号できないボブということろだと思いました。
Garbled Circuit
ここからはGarbled Circuitについて説明します。Garbled Circuitは1982年にYaoが提案した2パーティ間のマルチパーティ計算プロトコルです。
2入力の場合
アリスはGCTを作成する。これをシャッフルすることで、鍵との対応を分からないようにする。
アリスは各ワイアx,y,xについて、を生成する。
アリスは入力ビットをとして、をボブに送る。
アリスはボブにのどちらかの鍵を送る。この時にOblivious Transferを用いる。ボブはを手に入れる。
ボブは手に入れたとアリスから送られてきたからGCTを復号して、結果をアリスに共有する。
x | y | z | GCT |
---|---|---|---|
0 | 0 | 0 | |
0 | 1 | 0 | |
1 | 0 | 0 | |
1 | 1 | 1 |
注意
- 5ではGCTを復号しているので結果が4行分返ってきますが、このうち復号できているのは一行だけです。この時、復号に失敗したランダムな値と成功したと見分けがつかないのでZワイアに割り当てる値は、パディングのような冗長な値で復号の成功を確かめられるようにします。
GCTをシャッフルしているのは、結果と表の対応関係を隠すためです。シャッフルしないまま計算すると、入力にかかわらず復号に成功した行に対応する真偽値表が分かってしまうので出力から入力が漏洩します。
鍵を送る時に、1 out-of 2 Oblivious Transferを利用して秘密を交換します。アリスはとをボブに送信する。この時、ボブはを受け取るためにを入力します。すると、ボブはを受け取ることができます。この時アリスはボブがとのどちらを受け取ったか分からず、ボブは以外の情報を得ることができません。
この例ではzワイアにも鍵を割り当てていますが、実は鍵でなくゲートの計算結果である0か1でも問題ありません。鍵を割り当てるのは、zワイアが次のゲートの入力となっていた時に割り当てた鍵をもとに鍵を生成するためです。この構成法については後述します。
多入力回路や多段回路の場合
参考文献の他、ここにも詳しく書いてあります。
https://www.researchgate.net/figure/A-simple-example-of-Yaos-garbled-circuit_fig1_313017494www.researchgate.net
鍵はzワイアが次のゲートの入力となっていた時に割り当てた鍵をもとに鍵を生成するためと前述しましたが、具体的には鍵を次のGCTを連続的に復号するのに利用します。
まず、n入力関数の評価方法を示し、ゲートの出力が入力になっているような場合にどのような処理をするか確認します。
回路評価の一般化
1: アリスは個の鍵を生成する。アリスの入力ワイアの数を、ボブの入力ワイアの数を、はのゲートの総数かつ出力ワイアの数とする。鍵はそれぞれアリスの入力ワイア、ボブの入力ワイア、各ゲートの出力ワイアに対応する。
2: アリスは関数のGCTを作成して、シャッフルする。アリスはボブにGCTを送信する。
3: アリスは各入力をとしての個の鍵をボブに送る。 4: アリスとボブはボブに回Oblivious Transferを行う。 の場合 , 番目の Oblivious Transferの入力は以下のようになる。なお、ここで生成する鍵はそれぞれに対応する。
5: ボブは回路の個の入力ワイアのそれぞれに対応する鍵を持っているので、これらの鍵を使ってGCTを復号し、復号で得られるを用いつつ関数を評価する。関数の評価結果をアリスに共有する。
具体例
以下のような3入力回路を考えます。はアリス、はボブの入力です。
アリスは以下の10個の鍵生成します。
ANDゲート1に対応するGCT1は
GCT1 | |||
---|---|---|---|
0 | 0 | 0 | |
0 | 1 | 0 | |
1 | 0 | 0 | |
1 | 1 | 1 |
ANDゲート2に対応するGCT2は
GCT2 | |||
---|---|---|---|
0 | 0 | 0 | |
0 | 1 | 0 | |
1 | 0 | 0 | |
1 | 1 | 1 |
アリスはGCT1とGCT2の行をシャッフルしてボブに送ります。
次に、アリスはを入力したいのでをボブに送ります。
それに続いて、Oblivious Transferを1回行います。ボブがを入力したいとしてを選択したとすれば をボブは受け取ります。
この時点でボブはを持っています。これを使って、GCTをすべて復号します。
まず、GCT1をで復号すると、だけ復号が成功します。
次にGCT2でを復号するとだけ復号が成功します。
全体の評価結果は、つまり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