暗号理論とゲーム理論 ー オークションを題材として

2010年度 オープンキャンパス模擬授業
暗号理論とゲーム理論
ー オークションを題材として
情報セキュリティ大学院大学
有田正剛
はじめに
• 暗号理論の世界観
– 対象はプロトコル
対象はプロトコル。
– 各パーティーは、１００％正直か１００％悪意か、のいずれか。
– 悪意あるパーティの振る舞いを統制する。他者統制。
• ゲーム理論の世界観
– 対象はゲーム。
対象はゲ ム
– 各プレイヤーは、ただ自分の利得に合理的に振る舞う。（た
だし、自分の利得は他者の振る舞いに依存。）
– 合理的なプレイヤーたちの振る舞いを誘導する。自己誘導。
• モチベーション
– 「社会的なメカニズム」をITによって効率的に実現するた
めには ２つの世界観の協調が必要
めには、２つの世界観の協調が必要。
– オークションの場合。
オ クション
オークション
• 財を人々に割り当てるための社会的なメカニズム
– 各入札者は、財の個人的な評価額をもつ。
– 勝者となった場合、利得 = 評価額 ‐ 支払額。
オ クションに望まれる性質
オークションに望まれる性質
• その価値を最も高く評価する人に財が渡ること。
その価値を最も高く評価する人に財が渡る と。
• 各自の評価額のプライバシーが守られること。
• 不正行為の影響にロバストであること。
第 価格秘密オ クション
第一価格秘密オークション
• 各入札者は、他者の入札額を知らされずに入札する。
各入札者は 他者の入札額を知らされずに入札する
• 最も高い入札額をつけた入札者が、その入札額で落札する。
仲介者のアルゴリズム
入力： 入札額 t1, t2, …, tN
ti = Max {t
Max {t1, t
, t2, …, t
, …, tN}
return (“Win”, ti) to Player i
return “Loose” to Player j with j ≠ i
第二価格秘密オ クション
第二価格秘密オークション
• 各入札者は、他者の入札額を知らされずに入札する。
各入札者は 他者の入札額を知らされずに入札する
• 最も高い入札額をつけた入札者が、二番目に高い入札額で
落札する。
仲介者のアルゴリズム
入力：入札額 t1, t2, …, tN
ti = Max {t
Max {t1, t
, t2, …, t
, …, tN}
ti 2 = SecondMax {t1, t2, …, tN}
return (“Win”, ti2) to Player i
return “Loose”
return Loose to Player j with j ≠ i
to Player j with j ≠ i
第二価格秘密入札は誘因両立
• 第二価格秘密入札では、各入札者にとって、自分の評価額
をそのまま入札するのが、支配戦略。（正直が最善）
• 各入札者にとって
– 自分が勝者となった場合、支払額は自分の入札額ではなく、
二番目に高い入札額なので 自分の入札額を下げようとする
二番目に高い入札額なので、自分の入札額を下げようとする
誘因はない。
– 赤字を出しても意味がないので、評価額よりも入札額を高く
する誘因はない。
入力： t1, t2, …, tN
ti = Max {t1, t2, …, tN}
ti2 = SecondMax {t1, t2, …, tN}
return (“Win” ti2) to Player i
return (“Win”, t
) to Player i
return “Loose” to Player j with j ≠ i
第 価格秘密入札の均衡戦略
第一価格秘密入札の均衡戦略
• 支配戦略は一般には存在しない。
支配戦略は 般には存在しない。
• 評価額が
評価額が一様分布であるとき、自分の評価額の
様分布であるとき、自分の評価額の (N
(N‐1)/N
1)/N 倍を入
倍を入
札するのが均衡戦略。（Ｎはプレイヤー数）
入力： t1, t2, …, tN
i = Max {t1, t2, …, tN}
return (“Win”, ti) to Player i
return “Loose” to Player j with j ≠ i
return “Loose”
to Player j with j ≠ i
仲介者は信頼できるか？
• オンラインオークションでは一層心配
– 仲介者にはすべての入札者の評価額がわかる。プライ
バシーの問題。
– 仲介者が入札者と結託していたら？
– 仲介者が売り手と結託していたら？ とくに第二価格秘
密入札の場合。
• 仲介者をセキ
仲介者をセキュアプロトコルで実現したらどうか。
アプロト ルで実現したらどうか
– お互いに他者の入札額を知らずに、オークションの自分
の結果だけ（自分が勝者か否か 勝者の場合の支払額）を
の結果だけ（自分が勝者か否か、勝者の場合の支払額）を
計算できる。
– 財の利得だけでなく、情報の利得も設定する。
回路としての仲介者
• まず、仲介者の アルゴリズム を AND‐gate と XOR‐gate からな
る 多項式サイズの回路にコンパイル。
(u,v) = f(x, y): /* x : player 1の入札値, y : player 2の入札値 */
x1 x2 ... xn
y1 y2 ... yn
| | | | | |
‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐
gates
‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐
| |
| | | | | |
|
| |
|
‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐
gates
‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐
| | | | | |
u1 u2 ... un
v1 v2 ... vn
仲介者のセキュアプロトコル
P1 : x=(x
: x=(x1,…,xxn) P
)
P2 : y=(y
: y=(y1,…,yyn) )
各xiをaiとriに分割：
各yiをbiとsiに分割：
y1=b1+s1, ...., yn=bn+sn
x1 = a1+r1, ..., xn=an+rn
r1,....,rrn
s1,....,ssn
入力シェアの分配
a1 a2 an s1 s2 sn
r1 r2 rn
b1 b2 bn
| | |
| | | | | | | | | | | |
| | |
| | |
| | |
‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐
‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐
gates gates
‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐
‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐
| | | | | | | | | | | |
‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐
‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐
gates gates
‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐
‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐
| | |
| | | | | | | | | | | |
| | |
| | |
| | |
u1 u2 un v1 v2 vn
w1 w2wn
z1 z2 zn
出力シェアの分配
v1, ...., vvn
Output u1+w1,...,un+wn
※
さらに 「回路に従 て
さらに、「回路に従って
正直に計算している」こと
を示すゼロ知識証明を
組み込む必要がある。
w1,....,w
wn
Output z1+v1,....,zn+vn
素朴な試みではＮＧ
• オークションの仲介者を先のようにストレートにセキュアプロ
ク
仲介者を先
う
キ
トコルで実現しても、
• 出力シェアの分配を受けて、自分が敗者であることが判明し
出力シ アの分配を受けて、自分が敗者である とが判明し
たら、それ以上プロトコルを実行し続ける誘因がない。
P1
出力シェアの分配
x
P2
x
P3
‐ 安全だけど、最後まで実行する理由がない！
‐ 暗号技術の落とし穴。
暗号技術の落とし穴
MNTプロトコル
P.B.Miltersen, J.B. Nielsen, Nikos Triandopoulos CRYPT ‘09
• 各参
各参加者にとって、自分が勝者か敗者か、最後までいかな
者
、自分 勝者 敗者 、最後
な
いと判明しないよう工夫。
– 出力シェアの分配を、複数のエポックをかけて、実行する。（繰り返しゲーム）
– 勝者には、e番目のエポックでは確率2‐eで「勝ち」の出力シェアを、残りの確率
で「不明」の出力シェアを分配する。 最後まで「不明」なら負け。
– 自分のシェアを一度でも提供しなかったパーティには、二度とシェアを与えな
自分 シ アを 度 も提供 な
ティ
、 度 シ アを与 な
い。（トリガー戦略）
エポック１
ポ
エポックＥ
エポック２
P1
P1
P1
・・・
P2
P3
P2
P3
P2
P3
MNTプロトコルによって、
• 第一価格秘密入札はプロトコルで実現可能！
（ただし、財の利得が情報の利得より十分大きいと仮定。）
• ところが、第二価格秘密入札では、「勝ち逃げ」が誘因をもっ
ところが 第二価格秘密入札では 「勝ち逃げ」が誘因をもっ
てしまう。 （プロトコルなので勝ち逃げは全く容易）
– 勝者には第2位の入札額がわかる。その情報の利得が大きけ
れば、それで満足。
• ラウンド数の問題。
– １つのプロトコルの中で、ゲ
１つのプロトコルの中で ゲームを繰り返す必要があるか？
ムを繰り返す必要があるか？
おわりに
• さまざまな、望ましい「社会的なメカニズム」をITによって効率
的に実現するためには、２つの世界観の協調が必要。
• 暗号理論（規範的な世界観）とゲ
暗号理論（規範的な世界観）とゲーム理論（自律的な世界観）
ム理論（自律的な世界観）
• 「重層的な」 情報セキュリティ
情報セキ リティ