暗号勉強会

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

秘密分散方式のモデル化とマルチパーティ計算手法について解説

マルチパーティ計算 秘密分散

この論文は暗号の中でも秘密分散法に焦点を当てたサーベイ論文。秘密分散法方式ををモデル化し、マルチパーティ計算を行う手法について述べる。 その後、モデル化した秘密分散法によってその秘密分散方式のシェアの長さの下界を求める。この論文に書いてあることを関連性に注目しながらざっとまとめた。

用語

シェア

秘密分散方式においては、秘密kをs={s_1,s_2,\dots,s_n}のように分割して、パーティp={p_1,p_2,\dots,p_n}に共有するが、このs={s_1,s_2,\dots,s_n}をシェアとここでは呼ぶ。

アクセス構造

アクセス構造とは秘密を復元可能なパーティの集合の集合のこと。秘密を復元可能な集合とは、その集合に属するパーティのシェアを全て集めると秘密を復元できるような集合のこと。

monotone

Aをアクセス構造とする。Aは復元できるユーザの集合Bの集合族である。この時、B\subseteq CであるときB\in AならC\in Aのとき、Aをmonotone（単調族）という。以後はmonotoneなアクセス構造を単調アクセス構造と呼ぶ。秘密分散はmonotoneでなければならない。monotoneであるとは、例えばパーティ1,2が集まると秘密が復元可能とする。すると、パーティ1,2,3も当然復元可能である。これがmonotoneである。

情報比

秘密とその秘密に対するシェアの長さの比を情報比（information ratio）という。なお、情報比は1（つまり秘密とシェアの長さが同じ）が最適であり、1より大きくならない（つまりシェアは秘密以上の長さになる）ことが知られている。

秘密分散法について

(k,n)閾値法

ポピュラーな方式で多くのサイトや書籍で解説されているので以下のようなサイトを参考にしてほしい。

https://www.slideshare.net/AkitoTabira/ss-56244856

自分で実装したこともあった。

qiita.com

なお、この秘密分散方式はシェア長が秘密と同じ長さになる、つまり最適である。このように秘密が一定の閾値に達しなければ何も情報が漏洩しない方式を完全秘密分散方式という。 だが、シェアの情報量が多いと伝達効率が悪いので、伝達効率が良くなるように考えられたランプ型というものがある。これは、シェアが短くなる代わり閾値よりも小さい値で少しずつ秘密情報が漏洩することを許容する方式である。この方式ではt-out-of-n（n個のうちt個が集まったら秘密が復元できる）つまり\mathcal{A}_t= \{ A \subseteq {p_1\dots p_n }:|A| \leq t \} という限られたアクセス構造しか実現できない。

無向グラフによる構成方法A_{ustcon}[15]

閾値秘密分散方式とは異なる秘密分散方式の実現方法である。 アクセス構造をグラフ頂点の集合V={v_1,\dots,v_m}によって表現する手法。無向グラフを利用したV_1をv_1から到達できる頂点の集合、(v_i,v_j)をi<jとしパーティを表すとする。この時、辺の集合（パーティの集合）がv_mに到達できる経路を持つなら、辺の集合はアクセス構造である。

秘密分散の構成法

  1. kを0か1の二値をとる秘密情報とする。ディーラーはr_1=kかつr_ m=0とし、r_2から r _ {m-1}までは一様乱数を使う。辺(v_i,v_j)に対応するシェアはv_i \oplus v_jである。

  2. シェアから以下の方法で秘密を再構成できる。この方法は集めたシェア（辺）にv_mに到達できる経路がない、すなわちアクセス構造に含まれない時、秘密を復元できない。

f:id:ATen:20200506004033p:plain

伊藤、西関、斎藤の手法

任意の単調アクセス構造に対して、秘密分散方式を構築する方法を示した。\mathcal{A}_t= \{ A \subseteq {p_1\dots p_n }:|A| \leq t \}以外のアクセス構造でも実現可能である。

秘密分散方式の構成法

Aを単調アクセス構造とし、秘密を復元可能な集合をB\in Aとする。ディーラーは[tex:B={p{i_1},\dots,p{i_l}}]ごとにkをシェアとして分割する。

  1. l-1個の一様な乱数ビットr_1,\dots,r_{l-1}を選択する。
  2. r_l=k\oplus r_1\oplus \dots r_{l-1}を計算する。
  3. r_jをp_{i_j}に与える。

この時、[tex:p{i_1}]はr_1、[tex:p{i_2}]はr_2,\dots,p_{i_j}はr_jを持つ。 この方式はあるパーティp_kがp_k\in B_iかつp_k\in B_jであるとき、B_iのシェアとB_jのシェアを保持することになり効率が悪い。必要最低限Bにだけ共有する方法があるが、そのBの数が多いとやはり効率が悪くなる。

BenalohとLeichterの手法

西関らの手法を更に一般化した効率的な手法。アクセス構造の表現力がより高くなる。最低限のパーティにシェアを配ることを考える。ただし、この手法を使ってもシェアの長さがパーティ数に従う指数関数になる。

秘密分散方式の構成法

以下のアルゴリズムを再帰的に用いて構成する。 A_1、A_2を単調アクセス構造とする。この二つにはminimum authorized setに属さないパーティがある可能性があるのでB\in A_1かB\in A_2のどちらかだけであればB\in A_1\cap A_2、B\in A_1かつB\in A_2であればB\in A_1 \cup A_2としてそれを排除する。

  1. B\in A_1\cup A_2の時、秘密分散スキーム\Sigma_iを用いて、独立に秘密kを分散する。これは二つのアクセス構造に冗長なパーティが無かったことを意味する。

  2. B\in A_1\cap A_2の時、秘密分散スキーム\Sigma_iを用いて、一様乱数k_1に選び、k_2 = (k-k_1) mod mを計算し、\Sigma_iを使ってA_iにk_iを分散する。この時、A_1\cap A_2はk=(k_1+k_2)mod mを計算でき、秘密を復元できる。これはA_1\cap A_2以外はkを復元できず、k_1かk_2のどちらかしか復元できないことを意味する。

Monotone-span-program

線形秘密分散方式の情報比の下限値はmonotone-span-programのシェアのサイズの下限値に帰着できるという。このことを使って下限値を証明すれば、線形秘密分散方式の下限値を証明できる。 monotone-span-programによって構成されたスキームの情報比はmax_{1\leq j \leq n} a_jとなる。

定義

三つ組\mathcal{M}=(\mathbb{F},M,\rho)で表す。\mathbb{F}は有限体、\mathcal{M}は\mathbb{F}上のa\times b行列、\rhoは列番号とパーティ番号を対応させる関数である。 例えば\rho(1)=p_2となったら、1行目をパーティp_2と対応させ、\rho(2)=\rho(3)=p_5となったら、2,3行目をパーティp_5と対応させる。この時、パーティp_jと対応する行をa_jと書く。 M_AをＭに対して\rhoを適用した部分行列とする。\rhoは全単射とは限らないのでM_Aの行数がaとは限らない（行数が減るかもしれない）。

  • 行列がspanであるとは(日本語で言うと「張る」)

e_1 = (1,0,\dots,0) = vMとなるようないくつかのベクトルvが存在するようなMのことをspanな行列という。また、その行列は完全階数となっている必要がある。M_Bがe_1に対してspanであることと、Mが集合Bをacceptすることと、集合Bはminimum authorized setであることは同値である。なおBがアクセス構造Aに含まれているときだけ受け入れられるなら、アクセス構造AはMを受け入れる。

Multi-linear Monotone-span-program

今までは秘密は一つの体で定義された一要素のものに限られていた。この手法では二つ以上の体の要素からなる秘密でも秘密分散方式を実現できるmonotone-span-programを構成する。 この構成では、通常の線形秘密分散方式と比べ情報比が効率化される。具体的にはcを秘密の次元数とすると、max_{1\leq j \leq n} a_j/cとなる。

定義 多重線形モノトーンスパンプログラムはM=(F,M,\rho,V)の4つ組で表される。ここでFは有限体であり,Mは体上のa行b行列であり,\rho:{1,\dots,a}\rightarrow{p_1,\dots,p_n} はＭの各行をパーティと対応付ける。V={e_1,\dots ,e_c}はF ^ bに含まれるベクトルの集合であり,A\subseteq{p_1,\dots, p_n},1≤c<bを満たす。

  • M_Aの行は \{e_1,\dots,e_c\}の各ベクトルに対してspanである。この場合、MがAを受け入れると言う。
  • M_Aの各行は\{e_1,\dots, e_c\}に対してspanであるような線形空間の非ゼロのベクトルに対してspanである。

マルチパーティ計算

このマルチパーティ計算では、honest-but-curiousを仮定する。つまり最初は全てのパーティはプロトコルに従うが、プロトコルの最後にパーティの何人かが結託して得られたメッセージから情報を得ようとるする、という敵対者に対して情報理論的安全性を実現するようなマルチパーティ計算を構成する。

マルチパーティ計算の実現法

Q_1 と Q_2 をそれぞれシェア s _ {1,1}\dots s _ {1,n} とs _ {2,1},\dots, s _ {2,n}を生成する最大 tの次数の多項式とする。i\in{1, 2}と1\leq j\leq nとする。ここで、\alpha_1,\dots,\alpha_n \in F_q はn個の非ゼロの異なり、かつ全てのパーティから既知の値である。例えば、q>nであるようなnが素数なら、\alpha_j=jを得る。

  • Q_i(0) = k_i
  • Q_i(\alpha_j) = s _ {i,j}
  • Q(x) = Q_1(x) + Q_2(x)

とすると、

  1. Q(0)=Q_1(0)+Q_2(0)=k_1+k_2（Q(x) = Q_1(x) + Q_2(x)とQ_i(0) = k_iを使った。)

  2. Q(\alpha_j) = s _ {1,j} + s _ {2,j}（Q(x) = Q_1(x) + Q_2(x)とQ_i(\alpha_j) = s_{i,j}を使った。）

となるのでこれはシェアの和になっている。これを使えば各パーティp_jに秘密x_1,x_2のシェアs _ {1,j},s _ {2,j}をそれぞれ計算し、s_j = s _ {1,j} + s _ {2,j}を計算することで、足し算ができる。

加算の実現方法

  1. 各パーティp_jはx_1,x_2から計算されたs _ {1,j}とs _ {2,j}を受け取る。

  2. 各パーティp_jはs_j = s _ {1,j} + s _ {2,j}を計算する。

s_jを集めて秘密を復元すると、それはx_1+x_2になっている。このように加算においては通信が発生しない

乗算の実現方法

  1. 各パーティp_jはx_1,x_2から計算されたs _ {1,j}とs _ {2,j}を受け取る。

  2. 各パーティp_jはs_j = s _ {1,j}\cdot s _ {2,j}を計算する。その結果s_jからシェアを計算して、それをq _ {j,1}\dots q _ {j,n}としてq _ {j,l}(1\leq l\leq n)に送る。

  3. \beta_1,\dots \beta_lは、Shamirの(2t + 1)-out-of-nスキームにおける秘密の再構成のための定数である。各パーティp_lはu_l =\Sigma^{n}_{j=1}(\beta_j q _ {j,l})を計算する。

  4. u_l=\beta_1 q _ {1,l}+\beta_2 q _ {2,l}+\dots+\beta_n q _ {n,l}

  5. s_j=q _ {j,1}+\dots +q _ {j,n}

q _ {j,1}+\dots+q _ {j,n}はx_1\cdot x_2の演算結果で、これだけでは復元が出来ない。ステップ2で各パーティp_lはq _ {1,l},q _ {2,l}\dots q _ {n,l}を手に入れ、(q _ {l,l}は最初から持っている。一番目のインデックスはここではシェアqを送ってきたパーティ$p_jのjになる）、それからu_lを計算できる。

つまり最終的には、各パーティp_lはu_lというx_1\cdot x_2から計算されたシェアを保持していることになる。

マルチパーティ計算による任意回路の計算方法

回路への入力時に各パーティに秘密をシェアする。一つのゲートが進むごとに全ての各パーティが計算を行うので、一つのゲートを全パーティが共有していると考える。例えば、次に出てくるG_iの処理は各パーティp_jで行う処理である。なお、各シェアはq _ {i,j}ならp_jが持っているx_iの秘密のシェアと読める。

各パーティは秘密x_i一つにつき一つのシェアを保持する。つまりx_iについてはq _ {i,j}だけを持つ。x_jとx_kだったらq _ {j,i}とq _ {k,i}を持つ。

初期化ステップ

まず各パーティp_iはx_iからシェアを計算する。x_iのシェアを[tex:q{i,1},q{i,2},\dots,q_{i,n}]とし、p_iはp_jにq _ {i,j}に送る。 つまり各パーティp_jが最初に持っているのは、x_1,x_2\dots x_iのシェアの一部であるq _ {1,j},q _ {2,j}\dots q _ {i,j}\dots q _ {n,j}である。これらはn個の入力ゲートに入力されたものである。

計算ステップ

ゲートG_iの入力辺がG_jとG_kの二つだとする。なおここj,k<iである。つまりjとkからiへの経路が存在し、iはjとkより後ろにある。各パーティが入力されたシェアq _ {j,1},\dots, q _ {j,n} はG _ jの出力でq _ {k,1},\dots,q _ {k,n}はG _ kの出力である。

  • G_iが加算ゲートの場合、各パーティp_mはその場でq _ {i,m}= q _ {j,m} +q _ {k,m}を計算し、これをG_iの出力とする。

  • G_iが乗算ゲートの場合、各パーティは入力の積を取るために、上記に述べた乗算方法を利用する。

秘密の復元

各パーティ p_m は自分のシェア q _ {l,m}を p _ 1 に送る．パーティ p_1 はシェア q _ {l,1},\dots, q _ {l,t+1} から秘密sを復元し、すべてのパーティにsを送信する。各パーティはこのsを出力する。 どのt個のパーティも(t+1)-out-of-n秘密共有スキームの最大t個のシェアしか見られないので、そのパーティのt個の集合はシェアの入力の集合と和から秘密の情報を一切得られない。

まとめ

マルチパーティ計算と秘密分散に関する論文についてまとめた。秘密分散にも多くの実現方法があることが確認できたのでよし！