HTML5 Webook

24/72

（k,n）閾値分散法[12]を説明する。（k,n）閾値秘密分散法では、最初に、秘密データS（整数）のデータオーナーがSからn個のシェアと呼ばれる値を生成する。次に、データオーナーは、シェアサーバ（1～n）に各シェアを秘密裏に渡す。データオーナーは、この後、秘密データを消去する。秘密データの復元には、k台シェアサーバが協力してk個のシェアを収集し、所定の計算をすることにより、秘密データSを復元できる。このときkを閾値と定義する。数式での記述は、以下のようになる。分散：定数項を秘密データSとするランダムなk-1次多項式（1）を生成する。ここで、はランダムな整数であり、が秘密データSである。シェア保有者の識別子をiとしたとき、シェア保有者にはシェアとしてを配布する。復元時、k台のシェアサーバがを持ち寄ることにより、を求める。秘密データSの復元は、下記の式に従って行う。復元に協力するk人のシェアサーバの識別子をとする。このとき、各シェアサーバの保有するシェアについて、（2）が成り立つ。ここで、が与えられれば、未知変数をのk個とするk変数1次方程式がk個与えられる。したがって、この連立方程式より、すべての未知変数を求めることが可能であり、秘密データSを復元できる。実際に秘密情報を復元する際には、ラグランジュ補間が利用される。図１には、閾値分散法（3,4）の例を示している。2次方程式中の3つの変数を確定するために、3組以上のがあれば、秘密データSを復元できる。2.2　パスワード秘密分散プロトコルシェアの状態から秘密データの情報が漏洩することはないという特徴のほかに、シェアはシェア同士で足し算、掛け算が可能であるという特徴を有している。例えばデータ と の和のシェアは となる。同様に のシェアは となる。ここで留意点としては、シェアの足し算の際には閾値が変化しないことに対し、　　　　　　　　の多項式の次元は となり、データの復元には 個のシェアが必要となる。我々が実装したパスワード分散はこの性質を大いに利用し、情報理論的安全な認証を1つのパスワードで可能なスキームとなっている。スキームは3段階に大別される。最初に秘密データとパスワードのシェアを伝送するレジストレーションフェーズ、データ復元時の秘匿性を担保するためのシェアの計算を行うサーバ間通信・計算フェーズ、最後にデータ復元フェーズとなる。以下に閾値（3,4）の例を挙げて詳細を記述する。（１）レジストレーションフェーズ（registration phase）（１－１）計算機での演算に適したメルセンヌ素数 を用い、秘密データを ビット単位のl個のブロック||| に分割する。さらにパスワードPを用いてメッセージ認証コード（MAC）を と計算し、データに として連接する。以下の方法で作成する。（１－２）其々のデータブロックに対して1～4のシェアサーバに伝送するシェア1 , 2 , 3 , 4 （ ）を作成する。その際多項式の次元は2である。さらにパスワードPに対しても1次元の多項式を用いてシェア1 , 2 , 3 , 4 を作成する。（１－３）シェアをシェアサーバにQKDリンクからの鍵を用いたOTP暗号化し伝送する。以下、サーバ間の通信は全てQKD＋OTPでの暗号化を用いる。（１－４）各シェアサーバはシェアを格納する。（２）サーバ間通信・計算フェーズ（pre-computation phase）（２－１）其々のサーバ（j-th）で乱数Rjを生成し、その乱数のシェア　　　　　 　　　　　　を１次の多項式で生成する。さらにデータ“0”のシェア 1,2,3,4 図１　シャミアの閾値分散法（3,4）の例f(x)=a2x2+a1x+a00a0シェア秘密情報yx(i1, f(i1))(i2, f(i2))(i3, f(i3))(i4, f(i4))“シェア”をシェアサーバに配布3　量子光ネットワーク技術20　　　情報通信研究機構研究報告 Vol. 63 No. 1 （2017）