(57)【特許請求の範囲】
【請求項１】
管理すべき機密画像から、複数のメンバーに配布する複数の分散画像を生成する分散画像生成装置であって、
頂点集合が前記複数のメンバーの集合に対応するグラフを外部より入力するグラフ入力手段と、
前記グラフ入力手段によって入力されたグラフに基づいて、ベーシスマトリクスを生成するマトリクス生成手段と、
外部より入力された前記機密画像と、前記マトリクス生成手段より取得したベーシスマトリクスとに基づいて、前記複数のメンバーに配布する複数の分散画像を生成する分散画像生成手段とを備え、
前記複数の分散画像は、それら分散画像が組み合わされたときに前記機密画像をなし、
前記複数のメンバーはn(n＞２)人のメンバーであって、
前記分散画像生成手段は、前記n人のメンバーに対応するところの、前記グラフを構成するn個の各頂点間の距離に従い、前記n人のメンバーに含まれる２人のメンバーのそれぞれに配布される前記分散画像を組み合わせることで生成される機密画像が、該２人に対応する頂点間の距離に応じて異なるように、前記n人のメンバー全員のそれぞれに配布される分散画像を前記機密画像のそれぞれの画素成分に応じて選択される前記ベーシスマトリクスに応じて生成することにより、前記n人のメンバーに配布される前記複数の分散画像を生成し、
前記マトリクス生成手段が生成するベーシスマトリクスS00, S01, S10, S11はバイナリ行列であり、かつ複数の行成分u_i(1≦i≦n)で構成され、
前記分散画像生成手段は、i番目(1≦i≦n)のメンバーに配布される前記分散画像を、前記ベーシスマトリクスS00, S01, S10, S11のu_i行成分を用いて生成し、
R(A) の(u_i, u_j)成分を、バイナリ行列 A の u_i 行目のベクトル(1≦i≦n)と u_j 行目のベクトル(1≦j≦n)との論理和を取ったベクトルの、ハミング距離と定義する場合に、
（条件１）前記ベーシスマトリクスS00, S01, S10, S11のu_i行に含まれる「１」成分の数は、1≦i≦nのそれぞれについて一致し、
（条件２）R(S00) は、対角成分以外はすべて同じ成分を有する行列であり、
（条件３）R(S01) - R(S00) は、前記グラフにおいてx番目のメンバーとy番目のメンバーとの距離が２であるときにu_x行u_y列の成分が「１」であり当該距離が２ではないときにu_x行u_y列の成分が「０」である行列の、定数倍であり(1≦x,y≦n)、
（条件４）R(S10) - R(S00) は、前記グラフにおいてx番目のメンバーとy番目のメンバーとの距離が１であるときにu_x行u_y列の成分が「１」であり当該距離が１ではないときにu_x行u_y列の成分が「０」である行列の、定数倍であり(1≦x,y≦n)、
（条件５）R(S11) - R(S00) は、対角成分以外はすべて１以上の値を持つ行列である、
という以上（条件１）〜（条件５）を満たすように、前記マトリクス生成手段は前記ベーシスマトリクスS00, S01, S10, S11を生成することを特徴とする分散画像生成装置。
【請求項２】
管理すべき機密画像から、複数のメンバーに配布する複数の分散画像を生成する分散画像生成装置の制御方法であって、
グラフ入力手段が、頂点集合が前記複数のメンバーの集合に対応するグラフを外部より入力するグラフ入力工程と、
マトリクス生成手段が、前記グラフ入力工程にて入力されたグラフに基づいて、ベーシスマトリクスを生成するマトリクス生成工程と、
分散画像生成手段が、外部より入力した前記機密画像と、前記マトリクス生成工程にて生成したベーシスマトリクスとに基づいて、前記複数のメンバーに配布する複数の分散画像を生成する分散画像生成工程とを有し、
前記複数の分散画像は、それら分散画像が組み合わされたときに前記機密画像をなし、
前記複数のメンバーはn(n＞２)人のメンバーであって、
前記分散画像生成工程では、前記n人のメンバーに対応するところの、前記グラフを構成するn個の各頂点間の距離に従い、前記n人のメンバーに含まれる２人のメンバーのそれぞれに配布される前記分散画像を組み合わせることで生成される機密画像が、該２人に対応する頂点間の距離に応じて異なるように、前記n人のメンバー全員のそれぞれに配布される分散画像を前記機密画像のそれぞれの画素成分に応じて選択される前記ベーシスマトリクスに応じて生成することにより、前記n人のメンバーに配布される前記複数の分散画像を生成し、
前記マトリクス生成工程で生成するベーシスマトリクスS00, S01, S10, S11はバイナリ行列であり、かつ複数の行成分u_i(1≦i≦n)で構成され、
前記分散画像生成工程では、i番目(1≦i≦n)のメンバーに配布される前記分散画像を、前記ベーシスマトリクスS00, S01, S10, S11のu_i行成分を用いて生成し、
R(A) の(u_i, u_j)成分を、バイナリ行列 A の u_i 行目のベクトル(1≦i≦n)と u_j 行目のベクトル(1≦j≦n)との論理和を取ったベクトルの、ハミング距離と定義する場合に、
（条件１）前記ベーシスマトリクスS00, S01, S10, S11のu_i行に含まれる「１」成分の数は、1≦i≦nのそれぞれについて一致し、
（条件２）R(S00) は、対角成分以外はすべて同じ成分を有する行列であり、
（条件３）R(S01) - R(S00) は、前記グラフにおいてx番目のメンバーとy番目のメンバーとの距離が２であるときにu_x行u_y列の成分が「１」であり当該距離が２ではないときにu_x行u_y列の成分が「０」である行列の、定数倍であり(1≦x,y≦n)、
（条件４）R(S10) - R(S00) は、前記グラフにおいてx番目のメンバーとy番目のメンバーとの距離が１であるときにu_x行u_y列の成分が「１」であり当該距離が１ではないときにu_x行u_y列の成分が「０」である行列の、定数倍であり(1≦x,y≦n)、
（条件５）R(S11) - R(S00) は、対角成分以外はすべて１以上の値を持つ行列である、
という上記（条件１）〜（条件５）を満たすように、前記マトリクス生成工程で前記ベーシスマトリクスS00, S01, S10, S11を生成することを特徴とする分散画像生成装置の制御方法。
【請求項３】
請求項１に記載の分散画像生成装置としてコンピュータを動作させるプログラムコードが格納されている
ことを特徴とするコンピュータ読み取り可能な記憶媒体。
【請求項４】
請求項２に記載の分散画像生成装置の制御方法をコンピュータによって実現可能なプログラムコードが格納されている
ことを特徴とするコンピュータ読み取り可能な記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、対象画像を機密情報として分散させる分散画像生成装置及び分散画像生成方法及びコンピュータ読み取り可能な記憶媒体に関する。
【０００２】
【従来の技術】
従来より、コンピュータ等の情報処理装置において機密情報を管理する場合には、情報管理の不備や管理者の意図的な流出などにより、機密情報が外部に漏洩する危険性が指摘されており、この問題は、複数の情報処理装置が通信ネットワークを介して接続される近年の情報処理環境において対処すべき大きな問題となっている。
【０００３】
そこで、機密情報の管理を特定の一個人に依存させるのでなく、管理すべき機密情報を、あるグループを構成する複数のメンバーに予め分散して配布しておき、その機密情報が必要な場合にのみ、分散配布した情報から元の機密情報を復元して利用する方式が提案されており、この方式は、秘密分散法 (Secret Sharing Scheme) と呼ばれている。
【０００４】
また、上記の秘密分散法においては、グループを構成する各メンバーに配布した全ての分散情報が揃わなくても、機密情報を元通りに復元するように構成することもできる。即ち、従来の秘密分散法は、配布した分散情報が幾つか流出したとしても、流出した分散情報によっては管理すべき機密情報が漏洩したことにはならず、また分散情報の幾つかが破壊されたとしても、残りの分散情報に基づいて本来の機密情報を復元できるという利点を持つ。
【０００５】
このような特徴を有する秘密分散法の一例である(k,n) しきい値秘密分散法は、機密情報Ｓをｎ個の分配情報Ｗ_i (1≦i≦n) に符号化する方式であり、この方式においては、任意の k(k≦n) 個の分配情報 から機密情報Ｓを復号することは可能であるが、k-1 個以下の分配情報からは機密情報Ｓに関する情報は全く得られないという性質を有する。尚、この方式は A.Shamir"How to Share a Secret",Commun.of ACM, Vol.22, No.11, pp.612 - 613, 1979 もしくは 岡本龍明、 山本博資、 "現代暗号"、 産業図書、 pp.209 - 219 で提案されている。
【０００６】
また、このような秘密分散法の新しいタイプの方式として、機密情報および分散情報として画像を用い、分散情報としての画像の復号の際には、数学的演算を行わない視覚復号型秘密分散法 (Visual Secrect Sharing Scheme) も提案されている。
【０００７】
このような視覚復号型秘密分散法の一例として、上記の(k,n) しきい値秘密分散法に基づく視覚復号型秘密分散法は、 M.Naor and A.Shamir, Visual Cryptography (in Advances in Cryptology - Eurocrypt'94, Lecture Notes in Computer Science 950, pp.1-12, Springer-Verlag) においてはじめて紹介された方式である。この方式では、管理すべき機密情報としての機密画像を、複数の分散画像に予め分散すると共に、それら分散画像を、半透明なスライドのように透過性を有し、物理的に重ねあわせが可能な媒体に印刷しておき、元の機密画像を復元する際には、それぞれの分散画像を重ね合わせれば、特別な暗号演算を行うことなく、当該機密画像を復元することができる。
【０００８】
ここで、上記の(k,n) しきい値秘密分散法に基づく視覚復号型秘密分散法の構成方法についてより具体的に説明する。この方法は、１枚の機密画像からｎ枚の分散画像を予め作成し、k 枚以上の分散画像を重ね合わせることにより、元の機密画像を復元できるが、（k-1） 枚以下の分散画像を重ねあわせても、当該機密画像に関する情報は取得できない仕組みを提供するものであり、機密画像ＳＩは白黒（バイナリ）画像とし、その画像を構成する各成分ＳＩ(x,y) は、画素が白の場合には 0、 黒の場合には 1 と表現するものとする。
【０００９】
この場合、機密画像ＳＩを構成する各画素は、ｎ 枚の分散画像においてはｍ個の部分画素で表現され（つまり部分画素は、機密画像のｍ倍に拡大される）、複数枚の分散画像を重ね合わせたときには、このｍ個の部分画素の白と黒の割合の差（即ち、コントラスト）によって白か黒かが視覚的に復元され、元の機密画像を得ることができる。
【００１０】
また、上記の視覚復号型秘密分散法において、分散画像の構成方法については以下の通りである。
【００１１】
まず、ベーシスマトリクスについて説明する。分散画像は、ベーシスマトリクスに基づいて構成される。機密画像から分散画像を構成するに際して使用するベーシスマトリクスには２種類あり、ベーシスマトリクスS0 は、機密画像の画素成分が 0 のときに利用し、ベーシスマトリクスS1 は、機密画像の画素成分が 1のときに利用する。これら各ベーシスマトリクスは、共にｎ ×ｍの行列であり、当該行列の各行は、頂点集合 {u_i | 1≦i≦n} により添字付けされる。
【００１２】
また、ある閾値 d （1≦d≦n）に対して、これらのベーシスマトリクスは、次の性質を持つように作成される。
【００１３】
（１）ベーシスマトリクスS0, S1 は、バイナリ行列である。
【００１４】
（２）1≦i≦n となる i に対して、ベーシスマトリクスS0 の u_i 行成分の重み（1 成分の個数）と、ベーシスマトリクスS1 の u_i 行成分の重みは一致する。
【００１５】
（３）ベーシスマトリクスS0 の任意の異なる k 個の行ベクトルを選択し、ＯＲ（論理和）演算を行ったベクトルのハミング距離（すなわちベクトル中の 1 の個数）は d 未満である。
【００１６】
（４）ベーシスマトリクスS1 の任意の異なる k 個の行ベクトルを選択し、ＯＲ（論理和）演算を行ったベクトルのハミング距離は d 以上である。
【００１７】
（５）すべての 1≦q＜k を満たす q に対し、ベーシスマトリクスS0 の任意の異なる q 個の行ベクトルを選択し、ＯＲ（論理和）演算を行ったベクトルのハミング距離と、ベーシスマトリクスS1 の任意の異なる q 個の行ベクトルを選択し、ＯＲ（論理和）演算を行ったベクトルのハミング距離とは一致する。
【００１８】
次に、分散画像を作成するために、外部より入力された機密画像ＳＩの各成分 SI(x,y) に対して次の処理を行う。
【００１９】
（１）ベーシスマトリクスとして、SI(x,y) が 0 の場合は SO、 1 の場合は S1 を選択する。
【００２０】
（２）ｍ次の置換群から 置換 Φ を任意に選ぶ。
【００２１】
（３）各分散画像 w_i (1≦i≦n) の分散前の(x,y) 成分は、ベーシスマトリクスの u_i 行成分（ｍ変数のベクトル）に置換Φ を施したものとする。
【００２２】
以上により、ｍ倍に拡大された分散画像 w_i (1≦i≦n) が生成され、その分散画像を k 枚以上重ね合わせることにより、元の機密画像ＳＩを復元できるが、（k-１）枚以下の分散画像を重ね合わせても、当該機密画像ＳＩに関する情報はまったく得られないような仕組みを提供することができる。
【００２３】
図１１は、上述した従来の(k,n) しきい値秘密分散法に基づく視覚復号型秘密分散法の一例として、(2,2) しきい値秘密分散法に基づく視覚復号型秘密分散法を実現できるベーシスマトリクスSO及びS1（ｍ＝4）を例示する図である。また、図１２は、図１１に例示したベーシスマトリクスを基に分散画像を構成した例が図１２であり、同図では、分散画像１２０１と分散画像１２０２とを重ね合わせることにより、機密画像１２０３が復元される。
【００２４】
【発明が解決しようとする課題】
上記従来の(k,n)しきい値秘密分散法に基づく視覚復号型秘密分散法においては、各分散画像に機密画像をなす情報が平等に分配される方式である。これに対して、実社会における様々な活動においては、管理すべき機密情報の復元の際に特定のメンバーの許可が必ず必要であったり、特定のメンバーによる構成では復元が許可されない等のさまざまなアクセス構造が考えられ、複数のメンバーに分散画像が平等に分配される方式では都合が良くない場合も多い。
【００２５】
そこで本発明は、機密性及び運用性に優れる分散画像生成装置及び分散画像生成方法及びコンピュータ読み取り可能な記憶媒体の提供を目的とする。
【００２６】
【課題を解決するための手段】
上記の目的を達成するため、本発明に係る分散画像生成装置は、以下の構成を特徴とする。
【００２７】
即ち、管理すべき機密画像から、複数のメンバーに配布する複数の分散画像を生成する分散画像生成装置であって、頂点集合が前記複数のメンバーの集合に対応するグラフ（無向グラフ、または重み付きグラフ）を外部より入力するグラフ入力手段と、前記グラフ入力手段によって入力されたグラフに基づいて、ベーシスマトリクスを生成するマトリクス生成手段と、外部より入力された前記機密画像と、前記マトリクス生成手段より取得したベーシスマトリクスとに基づいて、前記複数のメンバーに配布する複数の分散画像を生成する分散画像生成手段とを備え、前記複数の分散画像は、それら分散画像が組み合わされたときに前記機密画像をなすことを特徴とする。
【００２８】
また、例えば、前記複数のメンバーはａ(ａ＞２)人のメンバーであって、前記分散画像生成手段は、前記ａ人のメンバーに対応するところの、前記グラフを構成するａ個の頂点間のそれぞれの距離に基づいて（例えば、算出した各頂点間の距離の和 w 、或いは、各頂点間の距離のうち最小距離 yに基づいて）、前記機密画像の復元の可否が決定されるように、前記複数の分散画像を生成することを特徴とする。
【００２９】
また、例えば、前記複数のメンバーはａ(ａ＞２)人のメンバーであって、前記分散画像生成手段は、前記ａ人のメンバーに対応するところの、前記グラフを構成するａ個の各頂点間の距離に基づいて（例えば、算出した各頂点間の距離の和 w 、各頂点間の距離のうち最小距離 y、或いは各頂点間の距離のうち最大距離 ｚに基づいて）、前記ａ人のメンバーに配布される該機密画像が異なるように、前記複数の分散画像を生成することを特徴とする。
【００３０】
上記の同目的を達成するため、本発明に係る分散画像生成方法は、以下の構成を特徴とする。
【００３１】
即ち、管理すべき機密画像から、複数のメンバーに配布する複数の分散画像を生成する分散画像生成方法であって、頂点集合が前記複数のメンバーの集合に対応するグラフを外部より入力するグラフ入力工程と、前記グラフ入力工程にて入力されたグラフに基づいて、ベーシスマトリクスを生成するマトリクス生成工程と、外部より入力した前記機密画像と、前記マトリクス生成工程にて生成したベーシスマトリクスとに基づいて、前記複数のメンバーに配布する複数の分散画像を生成する分散画像生成工程とを有し、前記複数の分散画像は、それら分散画像が組み合わされたときに前記機密画像をなすことを特徴とする。
【００３２】
また、例えば、前記複数のメンバーはａ(ａ＞２)人のメンバーであって、前記分散画像生成工程では、前記ａ人のメンバーに対応するところの、前記グラフを構成するａ個の頂点間のそれぞれの距離に基づいて、前記機密画像の復元の可否が決定されるように、前記複数の分散画像を生成すると良い。
【００３３】
また、例えば、前記複数のメンバーはａ(ａ＞２)人のメンバーであって、前記分散画像生成工程では、前記ａ人のメンバーに対応するところの、前記グラフを構成するａ個の各頂点間の距離に基づいて、前記ａ人のメンバーに配布される該機密画像が異なるように、前記複数の分散画像を生成すると良い。
【００３４】
更に、上記の分散画像生成装置及び分散画像生成方法を、コンピュータによって実現するプログラムコードが格納されている、コンピュータ読み取り可能な記憶媒体を特徴とする。
【００３５】
【発明の実施の形態】
以下、本発明に係る分散画像生成装置の実施形態を、図面を参照して詳細に説明する。
【００３６】
［第１の実施形態］
はじめに、本実施形態における分散画像生成装置を実現可能な情報処理装置の装置構成について説明する。
【００３７】
図７は、第１の実施形態における分散画像生成装置としての情報処理装置のブロック構成図である。
【００３８】
同図において、代表的な情報処理装置であるホストコンピュータ 701 は、例えば一般的なパーソナルコンピュータであり、ユーザによる各種指示等は、マウス 712 やキーボード 713 からの入力により行われ、文字情報や画像情報はプリンタ 715 から印刷させることが可能である。
【００３９】
また、ホストコンピュータ 701 の内部では、バス 716 を介して後述する各ブロックが接続され、種々のデータの受け渡しが可能である。702 は、ユーザへの指示、文字情報や画像情報の表示に用いられるモニタである。
【００４０】
703 は、ハードディスク706等から読み出されたところの、後述する情報分散処理等のソフトウエアプログラムに従って、内部の各ブロックの動作を制御するＣＰＵである。704 は、印刷されることが認められていない特定の画像を記憶したり、あらかじめ必要な画像処理プログラム等を記憶しておくＲＯＭである。705 は、ＣＰＵ703にて処理を行うために一時的にプログラムや処理対象のテキストデータを格納しておくＲＡＭである。
【００４１】
706 は、文字情報や画像情報、或いは、実行時にＲＡＭ等に転送される情報分散処理等のソフトウエアプログラム等を保存するところの、大容量記憶装置の一例としてのハードディスク（ＨＤ）である。708 は、外部記憶媒体の一つであるＣＤ（ＣＤ−Ｒ）に記憶されたデータを読み込み或いは書き出すことのできるＣＤドライブである。709 は、ＣＤドライブ708 と同様にＦＤ（フロッピーディスク）からの読み込み、ＦＤへの書き出しができるＦＤドライブである。710は、ＣＤドライブ708 と同様にＤＶＤ（デジタルビデオディスク）からの読み込み、ＤＶＤへの書き出しができるＤＶＤドライブである。
【００４２】
尚、ＣＤ，ＦＤ，ＤＶＤ等の外部記憶媒体に、編集用のプログラム、或いはプリンタドライバが記憶されている場合には、これらプログラムをＨＤ 706 上にインストールし、必要に応じてＲＡＭ 705 に転送されるように構成しても良い。
【００４３】
711 は、マウス 712 或いはキーボード 713 からの入力指示を受け付けるために、これらと接続されるインターフェイス（Ｉ／Ｆ）である。718 は、通信モデムでありインターフェース（Ｉ／Ｆ）719 を介して、例えば公衆回線を通じて、外部のネットワークに接続される。707 は、ネットワーク接続装置でありインターフェース（Ｉ／Ｆ）714を介して外部のネットワークに接続される。
【００４４】
図３は、第１の実施形態における分散画像生成装置（図７）の機能構成を説明する図であり、同図に示す各ブロックは、当該分散画像生成装置としてのホストコンピュータ701にて実行されるソフトウエアプログラムの１機能単位（モジュール）を表わす。
【００４５】
図３において、当該分散画像生成装置への外部からの入力は、機密画像 301 と グラフ 302 とである。入力されたグラフ 302 は、グラフ格納モジュール 303 によって例えばＨＤ706に格納される。後述するステップＳ２０２に対応する変換モジュール 304 は、読み出したグラフ 302 に基づいてベーシスマトリクスを生成し、生成したベーシスマトリクスは、ベーシスマトリクス格納モジュール 305 によって例えばＨＤ706に格納される。
【００４６】
そして、分散画像生成モジュール 306 は、外部より入力された機密画像 301 と、ベーシスマトリクス格納モジュール 305 より読み出したベーシスマトリクスとに基づいて複数の分散画像 307 を生成し、生成された複数の分散画像は、例えばプリンタ７１５に出力される。
【００４７】
尚、グラフ 302 の当該分散画像生成装置への入力は、機密画像 301 の入力と同時に行う同期型、或いは、事前にグラフ入力とベーシスマトリクスの作成とを行っておく非同期型のいずれでもよい。
【００４８】
次に、上述した装置構成及び機能構成を有するホストコンピュータ７０１にて実行される情報分散処理について説明する。
【００４９】
図１は、第１の実施形態における画像分散処理を示すフローチャートであり、本実施形態における特徴的な視覚復号型秘密分散法の手順の概略を示す。
【００５０】
図１において、ステップＳ１０１では、例えばインタフェース７１９、７１４、或いはＦＤ７０９等を介して、分散化させたい機密画像の入力処理を行う。この処理は、上記のグラフ格納モジュール 303 の機能に相当する。
【００５１】
ステップＳ１０２では、予めＨＤ706等に格納されているベーシスマトリクス（後述するベーシスマトリクスSOまたはベーシスマトリクスS1）を読み出し、読み出したベーシスマトリクスに基づいて、ステップＳ１０１にて取得した機密画像の分散画像を生成する分散画像生成処理を行う。即ち、入力された機密画像ＳＩの各成分SI(x,y) に対して次の処理を行う。
【００５２】
（１）成分SI(x,y) が 0 の場合は ベーシスマトリクスSO, 1 の場合は ベーシスマトリクスS1 を選択する。
【００５３】
（２）ｍ次の置換群から 置換 Φ を任意に選ぶ。
【００５４】
（３）各分散画像 w_i (1≦i≦n) の 分散前の(x,y) 成分を、ベーシスマトリクスの u_i 行成分（ｍ変数のベクトル）に 置換Φ を施した値とする。
【００５５】
尚、本実施形態において使用するベーシスマトリクス作成手順については後述する。
【００５６】
そして、ステップＳ１０３では、作成された分散画像を、例えばプリンタ７１５より出力する分散画像出力処理を行う。
【００５７】
ステップＳ１０２及びステップＳ１０３の各ステップは、上記の分散画像生成モジュール 306 の機能に相当する。
【００５８】
＜ベーシスマトリクスの作成手順＞
次に、上記の変換モジュール 304 の機能に相当するベーシスマトリクスの作成手順について、図２を参照して説明する。
【００５９】
図２において、ステップＳ２０１では、グラフの入力を行う。ここで、グラフ G とは、頂点集合 V と、辺（ V × V の元）の集合 E とのペアである。本実施形態では、グラフG を G = (V,E) と記述することもある。
【００６０】
図４は、第１の実施形態において入力されるグラフを示す図であり、グラフ３０２の実態は、図５に示す隣接行列の形態で入力され、例えばＨＤ706に格納される。本実施形態において、当該隣接行列は、行・列ともに頂点集合 {u_i | 1≦i≦n} により添字付けされる行列であって、 (u_x,u_y) 成分は、 (u_x ,u_y)⊂ E (辺集合) のとき 1、 そうでないとき 0 と定義する。例えば、図４において、 u_1 と u_2 との間には辺があるため、 図５の (1,2) 成分は 1 であるが、u_1 と u_3との間には辺がないため 、(1,3) 成分は 0 である。
【００６１】
次に、ステップＳ２０２では、入力されたグラフＧから、特定の複数のメンバーに配布された分散画像の組み合わせにより、元の機密画像を復元できるようにベーシスマトリクスに変換する。グラフＧに基づくベーシスマトリクスへの変換方法については後述する。
【００６２】
そして、ステップＳ２０３では、ステップＳ２０２にて取得したベーシスマトリクスを、例えばＨＤ706等に格納する。
【００６３】
ここで、上記のステップＳ２０２にて行われるグラフＧに基づくベーシスマトリクスへの変換方法について、２人のメンバーに分散画像を配布する場合を例に説明する。より具体的には、ｍ＝5 として、距離が２となる２頂点に対応する分散画像を重ねあわせたときに、元の機密画像を復元できるようなアクセス構造を実現する場合を例に説明する。
【００６４】
図６は、第１の実施形態における２つのベーシスマトリクスを示す図である。
【００６５】
同図において、ベーシスマトリクスS0 は 機密画像の画素成分が 0 のときに利用するベーシスマトリクスであり、ベーシスマトリクスS1 は 機密画像の画素成分が 1 のときに利用するベーシスマトリクスである。これらのベーシスマトリクスは、共にｎ×ｍの行列（本実施形態では 4 × 5 行列）であり、各行は 頂点集合 {u_i | 1≦i≦n} により添字付けされている。これらのベーシスマトリクスは、次の性質を持つように作成される。
【００６６】
但し、バイナリ行列 A に対して、R(A)を次のように定義する。即ち、R(A) の (u_i,  u_j)成分は、バイナリ行列 A の u_i 行目のベクトルと u_j 行目のベクトルのＯＲ(論理和)を取ったベクトルのハミング距離（1成分の個数）と定義する。
【００６７】
（１）ベーシスマトリクスS0, S1 はバイナリ行列である。
【００６８】
（２）1≦i≦n となる i に対して ベーシスマトリクスS0 の u_i 行成分の重み（1 成分の個数）と、ベーシスマトリクスS1 の u_i 行成分の重みとは一致する。
【００６９】
（３）R(S0) は、対角成分以外はすべて同じ成分を持つ（但し 演算 * は通常の行列の積の演算を表わす。以下同様）。
【００７０】
（４）R(S1) - R(S0) は、グラフの距離２の隣接行列（距離２の頂点の成分を1とした行列）の定数倍である。
【００７１】
ここで、図６に示すベーシスマトリクスS0,S1 は、図４及び図５のグラフに対して以上の条件を満たす。
【００７２】
上述した本実施形態によれば、ｍ（ここでは ｍ＝５）倍に拡大された分散画像 w_i (1≦i≦n) が生成され、距離が２となる２頂点に対応する分散画像を重ね合わせたときに、元の機密画像を復元可能な分散画像を生成することができる。即ち、２人のメンバーに対応する２頂点間の距離により、機密画像の復元の可否が決定されるように分配することができ、機密性及び運用性に優れる分散画像生成装置が実現する。
【００７３】
尚、本実施形態では、上述した情報分散処理を一般的なコンピュータ上で実現したが、このシステム構成に限られるものではなく、専用のハードウエアを備える装置として構成しても良い。
【００７４】
［第２の実施形態］
上述した第１の実施形態においては、２人のメンバーに対応する２頂点間の距離により、「機密画像の復元の可否」が決定されるように分配する分散画像生成方法について説明した。第２の実施形態では、２人のメンバーに対応する２頂点間の距離により、「異なる機密画像を分配する」分散画像生成方法について、第１の実施形態と同様な構成については重複する説明を省略し、本実施形態における特徴的な点を中心に説明する。
【００７５】
＜ベーシスマトリクスの作成手順＞
図８は、第２の実施形態において入力されるグラフであり、図２のステップＳ２０１にて外部より入力される。また、図９は、図８に示すグラフの隣接行列であり、グラフ格納モジュール 303 によってＨＤ706に格納される。
【００７６】
次に、本実施形態におけるステップＳ２０２の具体例を示す。本実施形態では、ｎ=5, ｍ＝7 とし、入力される機密画像数は 2 であり、機密画像SI_1 及び機密画像SI_2 とする。ここで、機密画像SI_1 及び SI_2 は同じ画素数からなる。
【００７７】
以下、２人のメンバーに対応する２頂点間の距離が１のときにSI_1 が機密画像として復元され、距離が２のときにSI_2 が機密画像として復元される分散画像生成方法について説明する。
【００７８】
図１０は、第２の実施形態における４つのベーシスマトリクスを示す図である。
【００７９】
同図において、ベーシスマトリクスS00 は、機密画像 SI_1 の画素成分SI_1(x,y)が 0 かつ 機密画像 SI_2 の画素成分SI_2(x,y) が 0 のときに利用するベーシスマトリクスである。ベーシスマトリクスS01 は、SI_1(x,y) = 0 かつ SI_2(x,y) =1 のとき利用するベーシスマトリクスである。ベーシスマトリクスS10 は、SI_1(x,y) = 1 かつ SI_2(x,y) =0 のとき利用するベーシスマトリクスである。そして、ベーシスマトリクスS11 は、SI_1(x,y) = 1 かつ SI_2(x,y) =1 のときに利用するベーシスマトリクスである。
【００８０】
これらの４つのベーシスマトリクスは、共に 5 × 7 行列であり、各行は 頂点集合 {u_i | 1≦i≦5} により添字付けされ、これらのベーシスマトリクスは、次の性質を持つように作成される。但し、バイナリ行列Aに対するR(A)の定義は、上述した第１の実施形態における定義に準ずる。
（１）ベーシスマトリクスS00, S01, S10, S11 はバイナリ行列である。
【００８１】
（２）1≦i≦n となる i に対して 各Sab (a=0 または 1, b=0または1）の u_i 行成分の重み（1 成分の個数の重み）は一致する。
【００８２】
（３）R(S00) は、対角成分以外はすべて同じ成分を持つ。
【００８３】
（４）R(S01) - R(S00) は、グラフの距離２の隣接行列の定数倍である。
【００８４】
（５）R(S10) - R(S00) は、隣接行列の定数倍である。
【００８５】
（６）R(S11) - R(S00) は、対角成分以外はすべて１以上の値を持つ。
【００８６】
ここで、図１０に示すベーシスマトリクスS00, S01, S10, S11 は、図８及び図９のグラフに対して以上の条件を満たす。
【００８７】
また、分散画像生成処理を行うステップＳ１０２（図１）では、入力された機密画像 SI_1 及び SI_2 の各成分に対して次の処理を行う。
【００８８】
（１）成分SI_1(x,y) = 0 かつ SI_2(x,y) =0 の場合はベーシスマトリクスS00を選択する。成分SI_1(x,y) = 0 かつ SI_2(x,y) =1 の場合はベーシスマトリクスS01を選択する。成分SI_1(x,y) = 1 かつ SI_2(x,y) =0 の場合はベーシスマトリクスS10を選択する。そして、成分SI_1(x,y) = 1 かつ SI_2(x,y) =1 の場合はベーシスマトリクスS11を選択する。
【００８９】
（２）ｍ次の置換群から 置換 Φ を任意に選ぶ。
【００９０】
（３）各分散画像 w_i (1≦i≦n) の 分散前の(x,y) 成分を、ベーシスマトリクスの u_i 行成分（ｍ変数のベクトル）に 置換Φ を施した値とする。
【００９１】
上述した本実施形態によれば、ｍ（ここでは ｍ＝７）倍に拡大された分散画像 w_i (1≦i≦5) が生成され、２人のメンバーに対応する２頂点間の距離が１のときにはSI_1、距離が２のときにはSI_2 が機密画像として復元できる。即ち、２人のメンバーに対応する２頂点間の距離により、異なる機密画像を分配することができ、機密性及び運用性に優れる分散画像生成装置が実現する。
【００９２】
［第３の実施形態］
第１の実施形態及び第２の実施形態においては、２人のメンバーに対応する２点間の距離を考慮したアクセス構造を実現したが、３人以上のメンバーによる判断方法への拡張も可能であり、その場合、ａ(ａ＞２)人のメンバーに対応するａ個の頂点間のそれぞれの距離から距離の和を求める方式、最小距離を求める方式、最大距離を求める方式などが考えられる。
【００９３】
［第４の実施形態］
上述した第１乃至第３の実施形態においては、入力するグラフとして無向グラフのみを扱っていたが、重み付けグラフを用いる方法への拡張も可能であり、その場合、上記の各実施形態における距離を、辺の重みに置きかえることで実現することができる．
［他の実施形態］
また、本発明の目的は、前述した実施形態の機能を実現するソフトウェアのプログラムコードを記録した記憶媒体を、システム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ）が記憶媒体に格納されたプログラムコードを読み出し、読み出したプログラムコードを実行することによっても達成される。
【００９４】
この場合、記憶媒体から読出されたプログラムコード自体が前述した実施形態の機能を実現することになり、そのプログラムコードを記憶した記憶媒体は本発明を構成することになる。
【００９５】
プログラムコードを供給するための記憶媒体としては、例えば、フロッピーディスク，ハードディスク，光磁気ディスク，ＣＤ−ＲＯＭ，ＣＤ−Ｒ，ＣＤ−ＲＷ，ＤＶＤ−ＲＯＭ，ＤＶＤ−ＲＡＭ，ＤＶＤ−ＲＷ，ＤＶＤ＋ＲＷ，磁気テープ，不揮発性のメモリカード，ＲＯＭなどを用いることができる。
【００９６】
また、コンピュータが読み出したプログラムコードを実行することにより、前述した実施形態の機能が実現されるだけでなく、そのプログラムコードの指示に基づき、コンピュータ上で稼動しているＯＳ（オペレーティングシステム）などが実際の処理の一部または全部を行い、その処理によって前述した実施形態の機能が実現される場合も含まれる。
【００９７】
更に、記憶媒体から読み出されたプログラムコードが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書き込まれた後、そのプログラムコードの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行い、その処理によって前述した実施形態の機能が実現される場合も含まれる。
【００９８】
【発明の効果】
以上説明したように、本発明によれば、機密性及び運用性に優れる分散画像生成装置及び分散画像生成方法及びコンピュータ読み取り可能な記憶媒体の提供が実現する。
【図面の簡単な説明】
【図１】第１の実施形態における画像分散処理を示すフローチャートである。
【図２】第１の実施形態におけるベーシスマトリクスの作成手順を示すフローチャートである。
【図３】第１の実施形態における分散画像生成装置（図７）の機能構成を説明する図である。
【図４】第１の実施形態において入力されるグラフを示す図である。
【図５】第１の実施形態における入力グラフの隣接行列を例示する図である。
【図６】第１の実施形態における２つのベーシスマトリクスを示す図である。
【図７】第１の実施形態における分散画像生成装置としての情報処理装置のブロック構成図である。
【図８】第２の実施形態において入力されるグラフである。
【図９】第２の実施形態における入力グラフの隣接行列を例示する図である。
【図１０】第２の実施形態における４つのベーシスマトリクスを示す図である。
【図１１】従来技術における (2,2) しきい値秘密分散法に基づく視覚復号型秘密分散法を実現するベーシスマトリクスを例示する図である。
【図１２】従来技術における分散画像と、それら分散画像を重ね合わせることによって復元された機密画像とを例示する図である。
【符号の説明】
301：機密画像，
302：グラフ，
303：グラフ格納モジュール，
304：グラフからベーシスマトリクスへの変換処理モジュール，
305：ベーシスマトリクス格納モジュール，
306：分散画像生成モジュール，
307：分散画像，
701：ホストコンピュータ，
702：モニタ，
703：ＣＰＵ，
704：ＲＯＭ，
705：ＲＡＭ，
706：ハードディスク（ＨＤ），
707：ネットワーク接続装置，
708：ＣＤドライブ，
709：ＦＤドライブ，
710：ＤＶＤドライブ，
711：マウス或いはキーボードとのインターフェイス（Ｉ／Ｆ），
712：マウス，
713：キーボード，
714：ネットワーク接続装置とのインターフェース（Ｉ／Ｆ），
715：プリンタ，
716：バス，
717：プリンタとのインターフェース（Ｉ／Ｆ），
718：モデム，
719：モデムとのインターフェース（Ｉ／Ｆ），
【図１】
0004771504.tif 000002
【図２】
0004771504.tif 000003
【図３】
0004771504.tif 000004
【図４】
0004771504.tif 000005
【図５】
0004771504.tif 000006
【図６】
0004771504.tif 000007
【図７】
0004771504.tif 000008
【図８】
0004771504.tif 000009
【図９】
0004771504.tif 000010
【図１０】
0004771504.tif 000011
【図１１】
0004771504.tif 000012
【図１２】
0004771504.tif 000013