2-out-of-2修正Elgamal暗号
修正Elgamal暗号はElgamal暗号を加法に対して準同型性を持つように修正を加えたものです。修正Elgamal暗号について以下のサイトがとても参考になりました!
これに更に修正を加えることで、2-ouf-of-2のしきい値Elgamal暗号を構成することができます。
- 鍵生成 ここでとする。
は次のように鍵を生成する。
は次のように鍵を生成する。
- 暗号化
について暗号文はとする。
- 復号
が、を半分復号する。が、で復号を完了する。
これを利用することで、half-decryptという半分だけ復号された状態を作り出すことができる。これにより、二人がいないと復号できない状態になります。 鍵を複数に分割すれば、n-out-of-nに拡張することもできそうです。
参考文献の論文では集合に関連付けられた値を暗号化したまま集計するのに利用していました。統計値は現実的な値にしかならないので修正Elgamalの欠点である平文空間の小ささは問題にならなそう。
参考文献
ゲーム理論とマルチパーティ計算
はじめに
誰かが不正を働いたり、利潤追求のために動いても安全...それを保証した技術の例にブロックチェーンがある。 この記事では、それを一般化したRational Adversaryという研究分野について書く。まだ理解の浅い部分があるので気持ちだけわかってもらえれば嬉しい。
忙しい人ためのまとめ
利己的に動くパーティとそれに対して非合理的な動きをするパーティがいるMMPCというMPCモデルがある。
各プレイヤーのインセンティヴの指標として満足度やユーティリティというものを使う。
各プレイヤーはt-NCCという性質を持つ関数の下ではマルチパーティ計算から逸脱できない。
出てくる暗号と関係のない用語の簡単な解説
- maximal set
ある性質Pを満たすAとBがある。この時、ならである。つまり、集合Aは性質Pを満たすようなmaximal setである。 これがあると、小さい集合について考えなくてよいのである性質を満たすような集合の定義が簡略化される。
どのプレイヤーもその戦略を選ばざるを得ないような状態のこと。「囚人のジレンマ」で有名。
- 支配
どの戦略を選ぶよりも有効な戦略を支配戦略という。
MMPCモデル
特徴と記号の意味
どのパーティもhonestではないのが特徴。Rationalなパーティはユーティリティを最大化するように行動するパーティで、Adversarial なパーティはそれに対して非合理的な行動で敵対するパーティで最終的には全パーティがプロトコルに従わざるをえなくなる。
MPCをゲームと見なして、プロトコルに逆らう
最大tまでのパーティが連携して、に敵対的な行動をする
- C
Pが使用可能なチャンネルとよばれるチューリングマシンのこと。4つ組で表される。
- C(P)
Pが使用可能なチャンネルの集合。
MMPCモデルの構成
と表す。RationalとAdversarialの集合が全体のパーティであることを表す。
チャンネル
プロトコルの通信方法をモデル化したもの。
チャンネルでの一連の処理
に含まれる各がテープにを書き込み、すべてのが書き込むまで待つ。もしタイムアウトしたらをそうでなければをCにインプットする。
このインプットをもとに状態操作関数でのように適用して、チャンネルの状態を変化させる。
テープにの各に向けてを書き込む。
プロトコルの処理の定式化
上の一連の処理をランとする。
は各の受け取ったメッセージである。
はの受け取ったメッセージである。はまとめて1つの連合とされていることに注意。
各パーティが最後に受け取ったメッセージをという。
これが意味するのは、に含まれる各がをそれぞれ実行し、を介して、を受け取っているということだ。そして、Rを繰り返すうちに最後に入手したメッセージはと呼ばれる。
MMPCモデルでのインセンティヴ
ユーティリティ
ユーティリティはこのプロトコルのインセンティブにあたるものだ。 今回はが利益のために動くので、その利潤をプロトコルにおいて数値化する。各パーティは関数について知りたいという状況を考える。 各ランRに対する関数をプロトコルユーティリティ関数とする。
Rationalなパーティはユーティリティ関数と関連付けられる。そしてユーティリティを計算するために、満足度というものがある。
例えば、はにおいてどれだけ望むような計算が結果が返ってきたかを表す。
は全体の満足度。各満足度は以下のように閉区間[0,1]かにマッピングされる。は邪魔をするだけなので、特にユーティリティを持たない。
この個人満足度から全体の満足度を計算するような関数を定義する。ここで、全員の満足度から個人のユーティリティを評価するのは、後述のような性質をユーティリティが持つため、個人の満足度だけでは測れないポイントがあるからだ。
さて、各パーティはそのランRでが得られた全体の満足度を計算できるという関数の集合とする。定義は
このはという性質を持ち、Rの関数であったを満足度を介することで評価できる。 ユーティリティには以下の3つのような性質がある
は学習するとが上昇する。
はであるようなが学習するとが下降する。
はであるようながだとになる。
t-NCC関数
定義に向けた準備
関数の入力をビットから文字列に一般化することを考えたい。 の変数関数とし、 、そしてをプロトコルユーティリティ関数とする。各パーティの入力とは以下のように定義される。
ここで、 とし、かつ、をAによる入力に置き換えるという処理を使っている。すなわち、とはAによって置き換えられた部分だけ違う。これはが自分の入力を変えるようなシナリオを想定している。
新しい概念を導入する。入力から任意の値を得ようとする行為を戦略(strategy)という。
- はとについて、を満たすようなのmaximal setである。なお、ここ以降で登場する記法の意味は以下である。