合理的な秘密分散における 不可能性とその回避方法 安永 憲司 九州先端科学技術研究所 コンピュータセキュリティシンポジウム 2012 ＠ 松江

暗号理論とゲーム理論 ともにプレイヤー間の相互作用に関する研究 暗号理論 プレイヤーは正直者 or 悪者 正直者をどのように守るか？ プレイヤーは合理的 合理的なプレイヤーはどう振る舞うか？

暗号理論とゲーム理論（既存研究） 暗号理論をゲーム理論に利用 信頼できる仲介者を暗号技術で実現 [DHR06, ADGH06, LMPS04, ILM05, ILM08] ゲーム理論を暗号理論へ適用 合理的なプレイヤーが暗号プロトコルを実行 秘密分散 [HT04, ADGH06, LT06, GK06, KN08a, KN08b, MS09, OPRV09, AL09, FKN10, PS11] リーダー選出，ランダムサンプリング [Gra10] ビザンチン合意 [GKTZ12] 公開鍵暗号 [Y12] ゲーム理論と暗号理論の概念間の関係 暗号理論向けのゲーム理論の概念 [HP10, GLV10, PS11] ゲーム理論の概念による安全性特徴付け[ACH11, GK12]

暗号理論とゲーム理論（既存研究） 本研究 暗号理論をゲーム理論に利用 信頼できる仲介者を暗号技術で実現 [DHR06, ADGH06, LMPS04, ILM05, ILM08] ゲーム理論を暗号理論へ適用 合理的なプレイヤーが暗号プロトコルを実行 秘密分散 [HT04, ADGH06, LT06, GK06, KN08a, KN08b, MS09, OPRV09, AL09, FKN10, PS11] リーダー選出，ランダムサンプリング [Gra10] ビザンチン合意 [GKTZ12] 公開鍵暗号 [Y12] ゲーム理論と暗号理論の概念間の関係 暗号理論向けのゲーム理論の概念 [HP10, GLV10, PS11] ゲーム理論の概念による安全性特徴付け[ACH11, GK12] 本研究

秘密分散 分散フェーズ 復元フェーズ (m, n) しきい値型秘密分散 m 個のシェアから秘密を復元でき m 個未満からは秘密について情報がもれない

合理的な秘密分散 単純な設定では、各プレイヤーは正直者と仮定

合理的な秘密分散 単純な設定では、各プレイヤーは正直者と仮定 Halpern, Teague (STOC ’04) プレイヤーが自分の利益のため行動すると？

合理的な秘密分散 単純な設定では、各プレイヤーは正直者と仮定 Halpern, Teague (STOC ’04) プレイヤーが自分の利益のため行動すると？  Shamir の秘密分散は正しく実行されない

合理的な秘密分散 単純な設定では、各プレイヤーは正直者と仮定 Halpern, Teague (STOC ’04) プレイヤーが自分の利益のため行動すると？  Shamir の秘密分散は正しく実行されない 自分の利益のために行動するプレイヤー  合理的なプレイヤー

合理的な秘密分散 単純な設定では、各プレイヤーは正直者と仮定 Halpern, Teague (STOC ’04) プレイヤーが自分の利益のため行動すると？  Shamir の秘密分散は正しく実行されない 自分の利益のために行動するプレイヤー  合理的なプレイヤー 合理的なプレイヤーが正しく実行可能  合理的な秘密分散

Halpern, Teague (STOC ’04) To discuss the behavior of players, we need to introduce some notions of game theory.

Halpern, Teague (STOC ’04) プレイヤーの利得関数 秘密を復元したい より少ない人数で復元したい To discuss the behavior of players, we need to introduce some notions of game theory.

Halpern, Teague (STOC ’04) プレイヤーの利得関数 秘密を復元したい より少ない人数で復元したい (n, n) 秘密分散の復元フェーズを考える To discuss the behavior of players, we need to introduce some notions of game theory.

Halpern, Teague (STOC ’04) プレイヤーの利得関数 秘密を復元したい より少ない人数で復元したい (n, n) 秘密分散の復元フェーズを考える プレイヤーは正直にシェアを出すだろうか？ To discuss the behavior of players, we need to introduce some notions of game theory.

Halpern, Teague (STOC ’04) プレイヤーの利得関数 秘密を復元したい より少ない人数で復元したい (n, n) 秘密分散の復元フェーズを考える プレイヤーは正直にシェアを出すだろうか？ 他プレイヤーがシェアを出すと仮定したとき To discuss the behavior of players, we need to introduce some notions of game theory.

Halpern, Teague (STOC ’04) プレイヤーの利得関数 秘密を復元したい より少ない人数で復元したい (n, n) 秘密分散の復元フェーズを考える プレイヤーは正直にシェアを出すだろうか？ 他プレイヤーがシェアを出すと仮定したとき 自分がシェアを出せば、 n 人全員が秘密を復元 To discuss the behavior of players, we need to introduce some notions of game theory.

Halpern, Teague (STOC ’04) プレイヤーの利得関数 秘密を復元したい より少ない人数で復元したい (n, n) 秘密分散の復元フェーズを考える プレイヤーは正直にシェアを出すだろうか？ 他プレイヤーがシェアを出すと仮定したとき 自分がシェアを出せば、 n 人全員が秘密を復元 自分がシェアを出さなければ、自分 1 人が復元 To discuss the behavior of players, we need to introduce some notions of game theory.

Halpern, Teague (STOC ’04) プレイヤーの利得関数 秘密を復元したい より少ない人数で復元したい (n, n) 秘密分散の復元フェーズを考える プレイヤーは正直にシェアを出すだろうか？ 他プレイヤーがシェアを出すと仮定したとき 自分がシェアを出せば、 n 人全員が秘密を復元 自分がシェアを出さなければ、自分 1 人が復元  シェアを出さない方が利得が高い 　　（シェアを出すことは Nash 均衡でない） To discuss the behavior of players, we need to introduce some notions of game theory.

Nash 均衡と結託耐性 Nash 均衡 どのプレイヤーも、 他のプレイヤーがプロトコルに従うとき、 プロトコルから逸脱しても利得は増えない どのプレイヤーも、 他のプレイヤーがプロトコルに従うとき、 プロトコルから逸脱しても利得は増えない 逸脱したときに利得が減る  狭義 Nash 均衡 結託耐性 r の Nash 均衡 r 人が結託して逸脱しても Nash 均衡

不可能性に関する既知結果 Asharov, Lindell (Crypto ’09) 解概念として Nash 均衡を考える場合 復元ラウンド数が利得の値に依存することを証明 結託耐性 n/2 を達成する 定数ラウンド復元プロトコルは存在しない n = 2 の場合に帰着して証明

本研究 KOTY プロトコルの問題点の指摘 回避方法の提案 不可能性の回避につながる [KOTY12] A. Kawachi, Y. Okamoto, K. Tanaka, K. Yasunaga. Rational secret sharing for non-simultaneous channels. IEICE Technical Report, 2012

KOTY プロトコル ブロードキャスト通信路を仮定 １人ずつ順番にブロードキャスト 定数ラウンド復元 高い確率で 2 ラウンド 結託耐性 n/2 – 1 の狭義 Nash 均衡 定数ラウンド復元では最適な結託耐性

KOTY プロトコル （分散フェーズ） (n/2 + 1, n) SS S1 (n/2, n) SS S2 ・・・ ・・・ 確率 α (n/2 + 1, n) SS S1 Step 1. 通常の SS S1 識別不能 Step 2. 通常の SS S2 確率 1 – α Step 3. RSS S3 (n/2, n) SS S2 秘密 b 1 (S1 で本物) 0 (S1 で偽物) 秘密 b = ・・・ ・・・ (n, n) RSS S3 ・・・ ・・・ ・・・ ・・・ ・・・ ・・・ ・・・ ・・・ 1 2 ・・・ n/2 ・・・ n

KOTY プロトコル （復元フェーズ） Step 1. (n/2 + 1, n) S1 のシェア を順に出す 全員正しいシェア  次のラウンド それ以外  終了 Step 2. (n/2, n) S2 のシェア　　 を順に出す 全員正しいシェア ∧ b = 0  次のラウンド それ以外  終了 Step 3. (n, n) S3 のシェア　　 を使って秘密 s を復元 結託耐性 n/2 – 1 の狭義 Nash である直観的理由 Step 1 で逸脱  偽物の可能性が残る Step 2 で逸脱  Step 3 に進めない

KOTY プロトコルの性質 定理 S3 が結託耐性 n/2 – 1 の狭義 Nash であるとき、 KOTY も結託耐性 n/2 – 1 の狭義 Nash 復元ラウンド数 = 2(1 - α) + T3 ・α T3 は S3 の復元ラウンド数 α を十分小さくとれば復元ラウンド数 ≈ 2

KOTY プロトコルの問題点

KOTY プロトコルの問題点 より望ましく見える戦略が存在

KOTY プロトコルの問題点 より望ましく見える戦略が存在 Step 1 で、n/2 個のシェアが出た後、 自分のシェアとあわせて秘密を復元して終了

KOTY プロトコルの問題点 より望ましく見える戦略が存在 Step 1 で、n/2 個のシェアが出た後、 自分のシェアとあわせて秘密を復元して終了 最初の n/2 人のプレイヤーは秘密を復元できない 残りの n/2 人は確率 1 – α で本物の秘密を復元 少ない人数で復元  利得が高くなる可能性

KOTY プロトコルの問題点 より望ましく見える戦略が存在 Step 1 で、n/2 個のシェアが出た後、 自分のシェアとあわせて秘密を復元して終了 最初の n/2 人のプレイヤーは秘密を復元できない 残りの n/2 人は確率 1 – α で本物の秘密を復元 少ない人数で復元  利得が高くなる可能性 結託耐性 n/2 – 1 の狭義 Nash に矛盾？

KOTY プロトコルの問題点 より望ましく見える戦略が存在 Step 1 で、n/2 個のシェアが出た後、 自分のシェアとあわせて秘密を復元して終了 最初の n/2 人のプレイヤーは秘密を復元できない 残りの n/2 人は確率 1 – α で本物の秘密を復元 少ない人数で復元  利得が高くなる可能性 結託耐性 n/2 – 1 の狭義 Nash に矛盾？  矛盾しない 上記の議論では n/2 人が逸脱する必要

何が問題なのか？

何が問題なのか？ 結託耐性が n/2 – 1 しかないこと 結託耐性が n – 1 なら問題は生じない

何が問題なのか？ 結託耐性が n/2 – 1 しかないこと 結託耐性が n – 1 なら問題は生じない しかし、不可能性の結果 [AL 11] から、 定数ラウンドプロトコルの結託耐性 ≤ n/2 – 1

何が問題なのか？ 結託耐性が n/2 – 1 しかないこと 結託耐性が n – 1 なら問題は生じない しかし、不可能性の結果 [AL 11] から、 定数ラウンドプロトコルの結託耐性 ≤ n/2 – 1  不可能性を回避する必要

不可能性の回避方法

不可能性の回避方法 利得関数に仮定を追加 「偽物の秘密を復元することを嫌がる」

不可能性の回避方法 利得関数に仮定を追加 「偽物の秘密を復元することを嫌がる」 先ほどの問題は回避可能 偽物の可能性があれば、逸脱しない

不可能性の回避方法 利得関数に仮定を追加 「偽物の秘密を復元することを嫌がる」 先ほどの問題は回避可能 偽物の可能性があれば、逸脱しない 利得関数に仮定を追加 「偽物の秘密を復元することを嫌がる」 先ほどの問題は回避可能 偽物の可能性があれば、逸脱しない 定理 上記仮定のもと、修正版 KOTY プロトコルは 結託耐性 n – 1 の狭義 Nash を達成 S1 と S2 をともに (n, n) 秘密分散に変更

まとめ KOTY プロトコルの問題点 より望ましい戦略が存在  結託耐性が小さいことが問題 不可能性の回避 利得関数に仮定を追加 「偽物の秘密を復元することを嫌がる」  結託耐性 n – 1 を達成可能に

既存プロトコル 文献 通信路 その他の 仮定 MPC ラウンド数 解概念 結託 耐性 [HT04] 同時同報 秘密通信路 ✔ O(1/β) IEWDS [ADGH06] 2 whp n/2 − 1 [GK06] n − 1 [KN08a] M/M Enc. [KN08b] 狭義 Nash 1 [OPRV09] 同報 正直者 2 THPE [AL09] [GK06] 等 [FKN10] P2P VRF [KOTY12] 既存の RSS n/2 – 1 IEWDS = 弱支配戦略の連続的削除 狭義 Nash = 狭義 Nash 均衡 THPE = 摂動完全均衡 β : 利得に依存する十分小さな値

Nash 均衡と結託耐性 戦略の組 σ = (σ1, …, σn) が Nash 均衡 どのプレイヤーも、他プレイヤーが σ に従う とき、戦略 σ から逸脱しても利得は増えない 戦略の組 σ = (σ1, …, σn) が 狭義 Nash 均衡 どのプレイヤーも、他のプレイヤーが σ に従う とき、戦略 σ から逸脱すると利得が下がる 戦略の組 σ が結託耐性 r の Nash 均衡 r 人が結託して逸脱しても、Nash 均衡

KOTY プロトコル （分散フェーズ） (n/2 + 1, n) 秘密分散 S1 を使って秘密 s を分散 ただし、確率 α で s は偽物

KOTY プロトコル （復元フェーズ） (n/2 + 1, n) S1 のシェアを順に出す (n, n) S3 のシェアを使って秘密 s を復元

KOTY プロトコルの性質 定理 S3 が結託耐性 n/2 – 1 の狭義 Nash であるとき、 KOTY も結託耐性 n/2 – 1 の狭義 Nash 復元ラウンド数は < 2(1- α) + T3 ・α 証明の概要 サイズ n/2 – 1 の結託を考える Round 1 で逸脱  n/2 + 1 個の正しいシェアが 出されるので、全員復元して終了 確率 α で偽物の可能性 Round 2 で逸脱  s’ ≠ 1 なら偽物を復元して終 了 s’ = 1 のとき、どんな行動も逸脱とみなさない Round 3 で逸脱  S3 の性質より利得は下がる

戦略と Nash 均衡 プレイヤー i の戦略 σi どの状況でどの行動を取るかを記述したもの 戦略の組 σ = (σ1, …, σn) が Nash 均衡 ∀ i, ∀ σi’, Ui(σi’, σ− i) ≤ Ui(σ), Ui(σ) : 戦略 σ に従ったときの期待利得 Here we define strategy and Nash equilibrium. A strategy sigma i of player i specifies an action of player i to be taken in every possible situation. Therefore, if the strategies of all players are determined, we can discuss the outcome of the game. A set of all players strategies is called a strategy profile. And a strategy profile is called a Nash equilibrium if the following condition holds. Let U_i(sigma) denote the expected payoff of player i when the players follow sigma. The left-side of the inequality means the expected payoff of player i when player i follow sigma prime and the other players follow sigma. The strategy profile is Nash equilibrium if for any player i, the expected payoff of player i does not increase by changing the strategy from sigma to sigma prime. Next we discuss why Shamir’s scheme does not work. どのプレイヤーも、他のプレイヤーが σ に従う限り、 戦略 σ から逸脱しても、利得は増えない

Shamir の (m, n) 秘密分散の問題点 In the reconstruction phase, players are asked to reveal their shares. This strategy is a problem. If we assume that the shares are authenticated, namely we consider authenticated secret sharing, then players have essentially two choices as a strategy. Reveal the secret and not reveal the secret.

Shamir の (m, n) 秘密分散の問題点 復元フェーズで、 全員がシェアを出すという戦略はよくない 復元フェーズで、 全員がシェアを出すという戦略はよくない In the reconstruction phase, players are asked to reveal their shares. This strategy is a problem. If we assume that the shares are authenticated, namely we consider authenticated secret sharing, then players have essentially two choices as a strategy. Reveal the secret and not reveal the secret.

Shamir の (m, n) 秘密分散の問題点 復元フェーズで、 全員がシェアを出すという戦略はよくない 復元フェーズで、 全員がシェアを出すという戦略はよくない 認証つき秘密分散を仮定すると プレイヤーの選択肢は実質的に２つ シェアを「出す」 シェアを「出さない」 In the reconstruction phase, players are asked to reveal their shares. This strategy is a problem. If we assume that the shares are authenticated, namely we consider authenticated secret sharing, then players have essentially two choices as a strategy. Reveal the secret and not reveal the secret.

Shamir の (m, n) 秘密分散の問題点 m = n のとき m < n のとき

Shamir の (m, n) 秘密分散の問題点 m = n のとき 「出す」  n 人で復元 「出さない」  1 人で復元 「出さない」  1 人で復元 m < n のとき

Shamir の (m, n) 秘密分散の問題点 Nash 均衡ではない m = n のとき 「出す」  n 人で復元 「出さない」  1 人で復元 m < n のとき Nash 均衡ではない

Shamir の (m, n) 秘密分散の問題点 Nash 均衡ではない m = n のとき 「出す」  n 人で復元 「出さない」  1 人で復元 m < n のとき シェアを出しても出さなくても n 人で復元 「出さない」が「出す」より悪い状況はなく、 また、ある状況では真に良い Nash 均衡ではない

Shamir の (m, n) 秘密分散の問題点 Nash 均衡ではない 弱支配される Nash 均衡 m = n のとき 「出さない」  1 人で復元 m < n のとき シェアを出しても出さなくても n 人で復元 「出さない」が「出す」より悪い状況はなく、 また、ある状況では真に良い Nash 均衡ではない 弱支配される Nash 均衡

狭義 Nash 均衡と結託耐性 戦略の組 σ = (σ1, …, σn) が 狭義 Nash 均衡 ∀ i, ∀σi’ ≠ σi, ∃δ > 0, Ui(σi’, σ- i) ≤ Ui(σ) − δ, 戦略の組 σ が結託耐性 r の Nash 均衡 ∀ 結託 C ⊆ {1, 2, …, n} s.t. |C| ≤ r, ∀ σC’, UC(σC’, σ- C) ≤ UC(σC, σ- C) 結託耐性 1 の Nash 均衡 =（通常の）Nash 均衡 結託耐性 r の 狭義 Nash 均衡 も同様に定義 σ 以外の戦略を取ると、利得が真に下がる r 人が結託しても、 σ は Nash 均衡