秘密情報分散法： 宝の地図の断片を集めて宝物をゲット（２／３）
３． (k, n)-しきい値法 ～ n個のシェア情報をk個集めるスタンプラリー ～
中学生のときに y=ax+b と表される直線のグラフを描いたことがありますね。 x の値ごとに y の値が決まり、直線上の点 ( x, y ) が決まります。この直線を用いて、(2, 3)-しきい値法を説明しましょう。
銀行の支店長は、直線の係数 a, b を秘密に決めて、 b を金庫の暗証番号の値としました。 b が秘密情報に当たるのですね。そして、直線上の点 ( x1, y1 ), ( x2, y2 ), ( x3, y3 ) を計算して、三人の金銭出納係に1点ずつ渡し、「金庫の暗証番号は直線の定数項 b ですよ。」と教えます。直線上の3点がシェア情報となるのですね。ご存知の通り、1点だけでは直線は定まらず、定数項 b の値は求まりません。任意の2点の座標がわかると直線は定まり、定数項 b の値が求まります（図1）。これで、先に紹介した「三人中任意の二人が合意した場合のみ、金庫が開けられるようにしたい」という問題が解決できますね。
銀行の支店長は、直線の係数 a, b を秘密に決めて、 b を金庫の暗証番号の値としました。 b が秘密情報に当たるのですね。そして、直線上の点 ( x1, y1 ), ( x2, y2 ), ( x3, y3 ) を計算して、三人の金銭出納係に1点ずつ渡し、「金庫の暗証番号は直線の定数項 b ですよ。」と教えます。直線上の3点がシェア情報となるのですね。ご存知の通り、1点だけでは直線は定まらず、定数項 b の値は求まりません。任意の2点の座標がわかると直線は定まり、定数項 b の値が求まります（図1）。これで、先に紹介した「三人中任意の二人が合意した場合のみ、金庫が開けられるようにしたい」という問題が解決できますね。
図１． (2,3)-しきい値法
シェア情報が1個の場合、直線は定まらない。
シェア情報が2個の場合、直線が定まる。
三人に情報を分散するだけでは不安だという場合には、もっと多くの人が集まらないと金庫の暗証番号がわからないようにすればいいですよね。k 人集まらないと金庫の暗証番号がわからないようにするには、直線 (1次式)ではなく、(k-1)次曲線を考えればいいのです。
(k-1)次曲線 y=ak-1xk-1+ak-2xk-2+・・・+a1x+b
(k-1)次曲線 y=ak-1xk-1+ak-2xk-2+・・・+a1x+b
の係数を秘密に決め、定数項 を秘密情報とし、この(k-1)次曲線上の n 個の点をシェア情報として n 人の管理者に与える。そうすれば、n 人中 k 人以上の管理者が集まれば秘密情報を復元できますが、(k-1)人以下なら秘密情報は復元できません。これが、(k, n)-しきい値法の仕組みです。
直線の場合は計算が簡単ですが、(k-1)次曲線になると計算が複雑になり大変ですね。シェア情報から秘密情報への復元を簡単にするには、どうすればよいでしょう？
直線の場合は計算が簡単ですが、(k-1)次曲線になると計算が複雑になり大変ですね。シェア情報から秘密情報への復元を簡単にするには、どうすればよいでしょう？
４．秘密情報が画像の場合はどうなるの？～宝の地図を簡単に復元する方法～
ある海賊が、自分が埋めた財宝の隠し場所を示す宝の地図を作成しました。そのままでは、地図を見た人には、すぐに隠し場所がわかってしまいます。そこで、この地図を複数に分け、分けられた地図を一定以上集めなければ隠し場所がわからないようにしたい。
このような問題も、秘密情報分散法で解決できます。今回の秘密情報は、宝の地図、つまり画像です。
今までの方法では、秘密情報から各管理者が保管するシェア情報をつくる場合にも、集めたシェア情報から元の秘密情報を復元する場合にも、多くの計算が必要になり、計算機を使わなければなりません。しかし、海賊は、宝の地図を復元するために計算機を持ち歩きたくありません。「秘密情報を複数のシェア情報に分ける」場合には計算機などを使って複雑な計算をしてもよいが、「複数のシェア情報から元の秘密情報を復元する」場合には、できるだけ簡単に復元したい。このような場合の解決策が、秘密情報を画像として扱う 5.の 視覚復号型秘密分散法です。
このような問題も、秘密情報分散法で解決できます。今回の秘密情報は、宝の地図、つまり画像です。
今までの方法では、秘密情報から各管理者が保管するシェア情報をつくる場合にも、集めたシェア情報から元の秘密情報を復元する場合にも、多くの計算が必要になり、計算機を使わなければなりません。しかし、海賊は、宝の地図を復元するために計算機を持ち歩きたくありません。「秘密情報を複数のシェア情報に分ける」場合には計算機などを使って複雑な計算をしてもよいが、「複数のシェア情報から元の秘密情報を復元する」場合には、できるだけ簡単に復元したい。このような場合の解決策が、秘密情報を画像として扱う 5.の 視覚復号型秘密分散法です。
