(57)【要約】  第1のランダム行列を生成するステップと、第1のランダム行列から第1の射影行列を生成するステップと、第1の射影行列および第1の秘密行列から第1の剰余行列を決定するステップとを含む秘密を分散するための装置および方法。第1の秘密行列は、剰余行列および複数の分散されたベクトル共有を使用して決定され得る。【特許請求の範囲】
【請求項１】
秘密を共有する方法であって、
少なくとも1つの第1のランダム行列を生成するステップと、
前記少なくとも1つの第1のランダム行列から少なくとも1つの第1の射影行列を生成するステップと、
前記少なくとも1つの第1の射影行列と少なくとも1つの第1の秘密行列とから少なくとも1つの第1の剰余行列を決定するステップとを含む方法。 
【請求項２】
さらに、
1つまたは複数のベクトル共有Vを生成するステップと、
前記少なくとも1つの第1の剰余行列を1人または複数の人に配布するステップと、
前記1つまたは複数のベクトル共有Vを1人または複数の参加者Pに配布するステップとを含み、
前記少なくとも1つの第1の秘密行列は、前記少なくとも1つの第1の剰余行列と前記ベクトル共有VのうちのK個以上とから決定され得る請求項1に記載の方法。
【請求項３】
条件付アクセスシステムであって、
少なくとも1つの暗号化された信号を送信する送信機と、
前記少なくとも1つの暗号化された信号を受信し、K個のベクトル共有を含む受信機とを備え、
前記受信機は、K個のベクトル共有を使用して、前記少なくとも1つの暗号化された信号を復号することができる条件付アクセスシステム。 
【請求項４】
コンピュータシステムであって、少なくとも1つのサーバーコンピュータと、ネットワークを通じて前記少なくとも1つのサーバーに結合されている少なくとも1つのユーザーコンピュータとを備え、前記少なくとも1つのサーバーコンピュータは、少なくとも1つのプログラムが格納されており、前記プログラムは、
少なくとも1つの第1のランダム行列を生成するステップと、
前記少なくとも1つの第1のランダム行列から少なくとも1つの第1の射影行列を生成するステップと、
前記少なくとも1つの第1の射影行列と少なくとも1つの第1の秘密行列とから少なくとも1つの第1の剰余行列を決定するステップとを実行するコンピュータシステム。 
【請求項５】
マシンによる処理のためのコンピュータプログラムを具現化しているコンピュータ可読媒体であって、前記コンピュータプログラムは、
少なくとも1つの第1のランダム行列を生成する第1のコードセグメントと、
前記少なくとも1つの第1のランダム行列から少なくとも1つの第1の射影行列を生成する第2のコードセグメントと、
前記少なくとも1つの第1の射影行列と少なくとも1つの第1の秘密行列とから少なくとも1つの第1の剰余行列を決定する第3のコードセグメントとを含むコンピュータ可読媒体。 
【請求項６】
キャリア波内に具現化された(または埋め込まれた)コンピュータデータ信号であって、
少なくとも1つの第1のランダム行列を生成する第1のコードセグメントと、
前記少なくとも1つの第1のランダム行列から少なくとも1つの第1の射影行列を生成する第2のコードセグメントと、
前記少なくとも1つの第1の射影行列と少なくとも1つの第1の秘密行列とから少なくとも1つの第1の剰余行列を決定する第3のコードセグメントとを含むコンピュータデータ信号。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号化のためのシステムおよび方法に関するものであり、特に、安全なマスメディアストレージ(secure mass medium storage)の秘密分散法を実装するためのシステムおよび方法に関するものである。
【背景技術】
【０００２】
今日の世界では、情報およびオーディオビジュアルコンテンツは、多数のコンテンツプロバイダによりさまざまな媒体を介して伝送される。媒体は、標準的な無線放送システム、有線放送システム、衛星放送システム、およびインターネットを含む。さらに、極秘の金融情報は、安全で、信頼性の高い格納および伝送を必要とする。
【０００３】
暗号化システムは、極秘の、または選りすぐりの観客のみを対象とする、情報およびコンテンツを保護することを可能にする。例えば、衛星ラジオ放送のプロバイダは、認定された受信機のみが伝送されたコンテンツを再生できるように、伝送を暗号化することができる。
【０００４】
「秘密分散」として知られている技法を利用する既存の暗号化システムの1つは、「しきい値暗号法」と呼ばれる。(k,n)しきい値秘密分散法は、秘密分散システムの一種である。Adi Shamirにより開発された「秘密分散」技法は、共有秘密値から「n」個の共有を構成するために(k-1)次多項式関数を使用する(k,n)しきい値秘密分散技法を述べたものである。この技法は、2つの情報エントロピー要件、つまり、i)任意の「k」個以上の共有を使用して、秘密を再構成することができるという要件、およびii)任意のk-1個以下の共有では、秘密に関する情報を明らかにすることができないという要件を満たす(E. D. KarninJ. W. Greene、およびM. E. Hellman, "On secret sharing systems," IEEE Trans. Inform. Theory, vol. IT-29, no. 1, pp.35-41, Jan. 1983、A. Shamir, "How to share a secret," Communications of the ACM, Vo. 22, No. 11, pp. 612-613, November 1979を参照)。しきい値暗号法では、秘密分散技法を使用して暗号鍵を「n」個の共有に分割し、そのうち任意の「k」個の共有を使用して鍵を再構成することができる。
【０００５】
Van Dijkら、およびJacksonらは、「秘密分散」概念を線形コーディングを使用することにより、複数の秘密の共有に拡張することを提案した(M. Van Dijk, "A linear construction of perfect secret sharing schemes", in Advances in Cryptology - (EUROCRYPT '94): Workshop on the Theory and Application of Cryptographic Techniques Advances in Cryptology、A. De Santis, Ed., IACR. Perugia, Italy: Springer-Verlag, May 1994, pp. 23-35、W. A. JacksonおよびK. M. Martin, "Geometric secret sharing schemes and their duals", Designs, Codes and Cryptography, vol.4, no.1, pp.83-95, Jan.1994を参照)。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかし、複数の秘密を共有するための既存の方法およびシステムには、情報オーバーヘッドに関する厳しい要件が課せられている。
【０００７】
そのため、現在、低い情報オーバーヘッドを有しながらも、高レベルのセキュリティを保持する複数の鍵を共有するためのシステムおよび方法が必要とされている。
【課題を解決するための手段】
【０００８】
本発明の例示的な一実施形態は、少なくとも1つの第1のランダム行列を生成するステップと、少なくとも1つの第1のランダム行列から少なくとも1つの第1の射影行列を生成するステップと、少なくとも1つの第1の射影行列および少なくとも1つの第1の秘密行列から少なくとも1つの第1の剰余行列を決定するステップとを含む。
【０００９】
本発明の他の例示的な実施形態は、少なくとも1つの暗号化された信号を送信するための送信機と少なくとも1つの暗号化された信号を受信するための受信機を含み、K個のベクトル共有を含む、条件付きアクセスシステムを備え、受信機は、このK個のベクトル共有を使用して、少なくとも1つの暗号化された信号を復号することができる。
【００１０】
本発明の他の例示的な実施形態は、少なくとも1つのサーバーコンピュータおよびネットワークを通じて少なくとも1つのサーバーに結合されている少なくとも1つのユーザーコンピュータを含むコンピュータシステムを備え、少なくとも1つのサーバーコンピュータは、その中に格納される少なくとも1つのプログラムを備え、前記プログラムは少なくとも第1のランダム行列を生成するステップと、少なくとも1つの第1のランダム行列から少なくとも1つの第1の射影行列を生成するステップと、少なくとも1つの第1の射影行列および少なくとも1つの第1の秘密行列から少なくとも1つの第1の剰余行列を決定するステップとを実行する。
【００１１】
本発明の例示的な他の実施形態は、マシンにより処理を行うためのコンピュータプログラムを具現化したコンピュータ可読媒体を含み、コンピュータプログラムは少なくとも1つの第1のランダム行列を生成するための第1のコードセグメントと、少なくとも1つの第1のランダム行列から少なくとも1つの第1の射影行列を生成するための第2のコードセグメントと、少なくとも1つの第1の射影行列および少なくとも1つの第1の秘密行列から少なくとも1つの第1の剰余行列を決定するための第3のコードセグメントとを含む。
【００１２】
本発明の例示的な他の実施形態は、少なくとも1つの第1のランダム行列を生成するための第1のコードセグメントと、少なくとも1つの第1のランダム行列から少なくとも1つの第1の射影行列を生成するための第2のコードセグメントと、少なくとも1つの第1の射影行列および少なくとも1つの第1の秘密行列から少なくとも1つの第1の剰余行列を決定するための第3のコードセグメントとを含むキャリアにおいて具現化されたコンピュータデータ信号を含む。
【発明を実施するための最良の形態】
【００１３】
本発明は、例示的な一実施形態では、行列射影技法を使用する複数の秘密を共有するためのシステムおよび方法を含む。本発明は、秘密値を保護する情報エントロピー特性の条件を満たすが、秘密共有を格納し、送信する際にかかる情報オーバーヘッドを低減するという付加的な利点を有する。
【００１４】
本発明のシステムおよび方法は、さらに、情報コンテンツに対するオーバーヘッド要件が低いためイメージ秘密分散アプリケーションに拡張することも可能である。イメージ秘密分散システムおよび方法は、さらに、1)秘密イメージのサイズと比較してイメージ共有に対するサイズが小さい、2)秘密イメージのほぼ可逆の再構成を行える、3)すべてのイメージの種類に対しイメージ秘密分散が可能である(例えば、白黒イメージ、濃淡イメージ、カラーイメージ)という利点を有する。
【００１５】
上記のように、Shamirは、(k,n)しきい値秘密分散技法のアイデアを発展させた。(A. Shamir, "How to share a secret", Communications of the ACM, vol.22, no.11, pp.612-613, Nov.1979、およびG. Blakley, "Safeguarding cryptographic keys", presented at the Proceedings of the AFIPS 1979 National Computer Conference, vol.48, Arlington, VA, June 1997, pp.313-317を参照。)「秘密分散」の背景にある概念は、秘密(例えば、暗号化/復号鍵)を「n」個の異なる参加者に分配して、任意の「k」人の参加者が秘密を再構成することができ、またk-1以下の参加者はその秘密に関していっさい明らかにできないようにするものである。これらの要件は、情報エントロピーに関する「完全な」秘密分散の基礎でもある(E. D. Karnin, J. W. Greene、およびM. E. Hellman, "On secret sharing systems", IEEE Trans. Inform. Theory, vol.IT-29, no.1, pp.35-41, Jan.1983を参照)。
【００１６】
「秘密分散」概念は、さらに、Itoらによって一般化秘密分散技法として拡張された(M. Ito, A. Saito、およびT. Nishizeki, "Secret sharing scheme realizing general access structure", in Proc. IEEE Global Telecommunications Conference (Globecom'87), Tokyo, Japan, Jan.1987, pp.99-102を参照)。秘密Kは、「n」人の参加者の集合
【数１】
2008541169.tif 000002
に分散され、
【数２】
2008541169.tif 000003
の有資格部分集合のみが(複数の)秘密を構成することができる。Γとして表されている、これらの有資格部分集合は、秘密分散法の「アクセス構造」と呼ばれる。完全秘密分散法では、Γに入っていない参加者の部分集合は、(複数の)秘密に関する情報を取得することができない。Γのそれぞれの部分集合内の参加者の数は、必ずしも同じではない。例えば、4人の参加者からなる集合
【数３】
2008541169.tif 000004
において、一般化秘密分散法は、アクセス構造Γ={{P1, P2}, {P2, P3, P4}}を持つことができる。ここで、第1の部分集合には2人の参加者が入っており、第2の部分集合には3人の参加者が入ることができる。(3,4)しきい値秘密分散法では、アクセス構造Γ={{P1, P2, P3,}, { P1, P3, P4}, {P2, P3, P4}, {P1, P2, P4},}を持つことができる。それぞれの有資格部分において、参加者の数は3である。(k,n)しきい値秘密分散法は、特別な一般化秘密分散技法である。
【００１７】
完全秘密分散法は、以下のように情報エントロピーを使用して定義される。
【００１８】
1)任意の有資格部分集合Yは、以下の式で(複数の)機密Kを再構成することができる。
【００１９】
∀γ∈Γ  H(K|Y)=0、および
2)任意の無資格部分集合Yは、以下のように、(複数の)機密Kに関する情報を持たない。
【００２０】
∀γ∈Γ  H(K|Y)=H(K)
Benalohらは、単調回路設計に基づく一般化完全秘密分散技法を提案した(G. Blakley, "Safeguarding cryptographic keys", presented at the Proceedings of the AFIPS 1979 National Computer Conference, vol.48, Arlington, VA, June 1997, pp.313-317を参照)。Brickellは、さらに、秘密分散法を拡張した(E. F. Brickell, "Some ideal secret sharing schemes", in Advances in Cryptology - (EUROCRYPT '89): Workshop on the Theory and Application of Cryptographic Techniques Advances in Cryptology, J.-J. Quisquater and J. Vandewalle, Eds., IACR. Houthalen, Belgiumを参照)。Brickellは、複数秘密分散法を構成するのに必要だが、十分ではない条件を示し、さらに、コンパートメント秘密分散法(compartment secret sharing)を導入した。コンパートメント秘密分散では、複数のグループを異なるしきい値と連携させて秘密を取得することができる。Jacksonらは、幾何学的アプローチを使用して複数秘密分散法を記述した([JAC94]を参照)。Van Dijkは、ベクトル空間構成において複数秘密分散と線形符号との間のつながりを確立した(M. Van Dijk, "A linear construction of perfect secret sharing schemes", in Advances in Cryptology - (EUROCRYPT '94): Workshop on the Theory and Application of Cryptographic Techniques Advances in Cryptology, A. De Santis, Ed., IACR. Perugia, Italy: Springer-Verlag, 
May 1994, pp.23-35を参照)。これらの級数秘密分散技法は、線形秘密分散法(LSSS)として分類されることが多い。
【００２１】
秘密分散法の効率を測定するアプローチは少なくとも2つある(H. M. SunおよびS. P. Shieh, "Constructing perfect secret sharing schemes for general and uniform access structures", Journal of Information Science and Engineering, vol.15, pp.679-689, Oct.1999を参照)。これら2つのアプローチは、i)情報率、およびii)ディーラーのランダム係数である(C. Blundo、A. De Santis、A. G. Gaggia、およびU. Vaccaro, "New bounds on the information rate of secret sharing schemes", IEEE Trans. Inform. Theory, vol.41, no.2, pp.549-554, Mar. 1995、F. BrickellおよびD. M. Davenport, "On the classification of ideal secret sharing schemes", in Advances in Cryptology - (CRYPT '89), G. Brassard, Ed., IACR. Springer-Verlag, 1989, pp.278-285、C. Blundo、A. G. Gaggia、およびD. R. Stinson, "On the dealer's randomness required in secret sharing schemes", in Advances in Cryptology - (EUROCRYPT '94): Workshop on the Theory and Application of Cryptographic Techniques Advances in Cryptology, A. De Santis, Ed., IACR. Perugia, Italy: Springer-Verlag, May 1994, pp.35-46、A. De SantisおよびB. Masucci, "Multiple ramp schemes", IEEE Trans. Inform. Theory, vol.45, no.5, pp.1720-1728, July 1999を参照)。
【００２２】
情報率ρは、(複数の)秘密の長さ(ビット単位)と複数の参加者の複数の共有の最大長との間の率である。
【数４】
2008541169.tif 000005
【００２３】
ただし、Kは、秘密分散法の可能なすべての秘密の集合であり、S(Pi)は、i番目の参加者
【数５】
2008541169.tif 000006
に対する可能なすべての共有の集合である。
【００２４】
参加者に与えられる共有のサイズは、秘密分散法の設計における重要な尺度である。共有が大きすぎる場合、秘密を計算するために使用される必要メモリ量は効率的な量にならない。したがって、理想的な秘密分散は、情報率ρ(Σ,Γ,K)=1である完全秘密分散として定義される(E. F. BrickellおよびD. M. Davenport, "On the classification of ideal secret sharing schemes", in Advances in Cryptology - (CRYPT '89), G. Brassard, Ed., IACR. Springer-Verlag, 1989, pp.278-285を参照)。
【００２５】
第2の尺度は、ディーラーのランダム係数μである。これは、この方式をセットアップするためにディーラー側で必要とする(複数の)秘密の1ビット当たりのランダムの量を表し([BLU94]を参照)、以下の式で表すことができる。
【数６】
2008541169.tif 000007
【００２６】
ただし、ΠKは、秘密Kに関する確率分布である。ディーラーは、与えられたアクセス構造Γに対する秘密分散法Σを設定するためにランダムの可能な最小量に関心を持つことが多い。完全秘密分散法の欠点は、秘密共有のサイズを秘密のサイズよりも小さくすることができないためオーバーヘッドとなっていることである。無資格グループに（複数の）秘密の部分情報の入手を許可する他の方法があるが、その（複数の）秘密を解読するのには十分ではない。これらの方式では、機密共有のサイズを秘密のサイズよりも小さくすることが可能である。公開された情報が無資格グループのサイズに比例する場合、ランプ型秘密分散法とみなされる(A. De Santis and B. Masucci, "Multiple ramp schemes," IEEE Tram. Inform. Theory, vol. 45, no.5, pp.1720-1728, My 1999、H. Yamamoto, "On secret sharing systems using (k, 1, n) threshold scheme," Electronics and Communications in Japan, Part I, vol.69, no.9, pp.46-54, 1986を参照)。本発明は、強い機密保護対策を維持しながら共有のサイズを縮小する強いランプ型秘密分散法として分類される
複数秘密分散技法は、NaorおよびShamirによるイメージ秘密分散で使用されてきた(M. NaorおよびA. Shamir, "Visual cryptography", presented at the Proceedings of the Conference on Advances in Cryptology - Eurocrypt '94, A. De Santis, Ed., Berlin, Germany, 1994, pp.1-12を参照)。技法的な詳細は、上述の複数秘密分散と極めて異なっているが、イメージ秘密分散法では、任意のk個のイメージ共有をスタックして、元のイメージを示すという単純なアイデアを提案している。これは、視覚暗号法または視覚秘密分散とも呼ばれるが、それは、この方法が多量の暗号を計算を伴わず、むしろ2進値または演算だけを伴うからである。
【００２７】
このイメージ秘密分散法は、白黒イメージに対する(2,2)しきい値イメージ秘密分散技法として導入された。Atenieseらは、(k,n)しきい値イメージ秘密分散技法を開発した(G. Ateniese、C. Blundo、A. De Santis、およびD. R. Stinson, "Visual cryptography for general access structures", Information and Computation, vol.129, no.2, pp.86-106, 1996を参照)。しかし、(k,n)しきい値イメージ秘密分散技法にはいくつかの障害がある。さまざまな研究者たちが、これらの難題の解決に大変な骨を折っており、これはi)カラーイメージ拡張、およびii)最適なイメージコントラスト率を含む(R. LukacおよびK. N. Plataniotis, "Colour image secret sharing", Electronics Letters, vol.40, no.9, pp.529-531, Apr.2004、M. NaorおよびA. Shair. (1996, June) Visual cryptography II: Improving the contrast via the cover base。[オンライン]入手可能: http://philby.ucsd.edu/cryptolib/1996/96-07.html。最終アクセス日: March 2005, C. N. Yang, "A note on efficient color visual encryption", Journal of Information Science and Engineering, vol.18, pp.367-372, 2002、C. Blundo、A. De Santis、およびD. R. Stinson, "On the contrast in visual cryptography schemes", Journal of Cryptology, vol.12, pp.261-289, 1999、C. KuhlmannおよびH. U. Simon, "Construction of visual secret sharin
g schemes with almost optimal contrast", presented at the Proceedings of the eleventh annual ACM-SIAM symposium on discrete algorithms, D. Shmoys, Ed., San Francisco, California, United States, Jan.2000, pp.263-272、M. NaorおよびA. Shair. (1996, June) Visual cryptography II: Improving the contrast via the cover base. [オンライン]入手可能: http://philby.ucsd.edU/cryptolib/l 996/96-07.html。最終アクセス日: March 2005)。
【００２８】
本発明の例示的な一実施形態では、(k,n)法による秘密分散の行列射影技法、およびデータ秘密分散とイメージ秘密分散におけるその応用を取り扱う。共有「n」は、ベクトルとして分散され(指定されたビット長を持つ値とは反対に)、これらの共有から選択された任意の「k」個のベクトルは、同じ射影行列を持つ。秘密は、行列で表されているため、秘密共有のサイズを潜在的に縮小し得る。行列射影秘密分散技法がイメージ共有に適用された場合、イメージ共有のサイズは、元のイメージのサイズよりもかなり小さくなる。さらに、これらの共有を送信するのに必要な送信帯域幅も、上述のイメージ秘密分散法に比べてかなり小さい。
【００２９】
次に、行列射影をどのように定義するかについて簡単に説明する。さらに、行列射影は、相似変換の下で不変であり、いくつかの独自の特性を有する。
【００３０】
行列射影
第1に、行列射影は、単純な例を通して定義されなければならない。例えば、行列Aを階数k(k<m)のm×x行列とし、Aの射影行列を
【数７】
2008541169.tif 000008
として表すものとする。射影行列
【数８】
2008541169.tif 000009
は
【数９】
2008541169.tif 000010
として定義されるが、ただし、(・)'は、転置行列である。さらに、
【数１０】
2008541169.tif 000011
と書くこともできる。
【００３１】
例えば、3×2行列Aを
【数１１】
2008541169.tif 000012
と考えると、
【数１２】
2008541169.tif 000013
を3×3行列として計算するのに定義
【数１３】
2008541169.tif 000014
を使用することができる。上記の行列射影
【数１４】
2008541169.tif 000015
は、相似変換の下で不変である。
【００３２】
BがAの相似変換行列であり、Xをk×k正則行列としてB=AXとなっている場合、
【数１５】
2008541169.tif 000016
を証明することができる。
【００３３】
証明:
【数１６】
2008541169.tif 000017
Xはk×k正則行列であるため、XX-1および(X')-1X'は恒等行列である。式
【数１７】
2008541169.tif 000018
は、
【数１８】
2008541169.tif 000019
としてさらに簡約することができる。
【００３４】
行列Xの一実施例として、
【数１９】
2008541169.tif 000020
となるような2×2行列をとる。
【００３５】
行列Bを
【数２０】
2008541169.tif 000021
として計算することができる。
【００３６】
式
【数２１】
2008541169.tif 000022
を検証することができる。
【００３７】
次元kを持つ任意のk個の一次独立ベクトルxiがある場合、ベクトルviの集合を、1≦i≦kとして、
vi=Axiと計算することができる。これらのk個のベクトルviで、行列Bを
B=[v1 v2 ... vk]
と構成することができる。
【００３８】
式
【数２２】
2008541169.tif 000023
を証明することができる。
【００３９】
したがって、階数kのm×k次元行列A(k≦m)、および1≦i≦kとしてk個の一次独立ベクトルxiを選択することができる[定理2.1]。vi=AXiであるk個のベクトルviを使用して、行列Bを
B=[v1 v2 ... vk]
と構成することができる。射影行列は、
【数２３】
2008541169.tif 000024
を満たす。
【００４０】
証明:B=[v1 v2 ... vk]およびvi=Axiであるため、
B=[v1 v2 ... vk]
=[Ax1 Ax2 ... Axk]
=A[x1 x2 ... xk]
X=[x1 x2 ... xk]とし、Xはk個の一次独立のベクトルxisを持つので、Xは最大階数のk×k行列である。B=AXと書くことができる。補題2.1の結果から、
【数２４】
2008541169.tif 000025
が得られる。
【００４１】
射影行列
【数２５】
2008541169.tif 000026
は、行列Aから他の行列Bへの相似変換の下で不変である。射影行列
【数２６】
2008541169.tif 000027
が有する重要な特性もいくつかある。これらは以下のとおりである。
【００４２】
1)
【数２７】
2008541169.tif 000028
は対称的である、
2)
【数２８】
2008541169.tif 000029
3)
【数２９】
2008541169.tif 000030
は、べき等行列である、つまり、
【数３０】
2008541169.tif 000031
である、
4)
【数３１】
2008541169.tif 000032
ただし、
【数３２】
2008541169.tif 000033
は、
【数３３】
2008541169.tif 000034
となる行列
【数３４】
2008541169.tif 000035
に対するトレースである。
【００４３】
上記の特性(1)〜(3)は、行列操作により容易に示すことができる。特性(4)は、べき等行列に対する重要な特性であり、得られた射影行列が正しいかどうかを検証するのに役立ち、また単純である。
【００４４】
べき等行列Dは、固有値として0と1しかとらない[補題2.2]。
【００４５】
証明:べき等行列Dについて、その固有値は、λであり、
Dx=λx => D2x=Dλx
となる。
【００４６】
Dは、D2=Dとなるべき等行列であるため、Dx=λDxであることを証明することができ、あるいは、λx=λλxと簡約することができる。つまり、(λ2-λ)x=0となる。この条件は、非ゼロのxについて成立しなければならず、これは、
λ2-λ=0、またはλ=0、1
を意味する。
【００４７】
べき等行列Dについて、tr(D)=rank(D)である[補題2.3]。
【００４８】
証明:べき等行列Hは、
D=TΛT-1となるような対角相似行列Λを持つが、ただし、Tは固有ベクトル行列であり、Λは、固有値行列である。DおよびΛは、相似行列であるため、
rank(D)=rank(Λ)、
および
tr(D)=tr(Λ)
であることがわかる。
【００４９】
補題2でも述べたように、べき等行列Dは、固有値として0または1を持つ。Λは、その対角要素に0と1の固有値を持たなければならない。
【００５０】
tr(Λ)=rank(Λ)
したがって、
tr(D)=rank(D)
となる。
【００５１】
階数k(k≦m)のm×k次元行列Aを
【数３５】
2008541169.tif 000036
とするが、ただし、
【数３６】
2008541169.tif 000037
とする。
【００５２】
証明:rank(A)=kであるため、rank(A'A)=kおよびrank((A'A )-1)=kとなる。
【００５３】
M=(A'A)-1ならば、rank(A×M)を
rank(A)+rank(M)-min(m,k)≦rank(A×M)-min(rank(A),rank(M))
と求めることができる。
【００５４】
つまり、
k+k-k≦rank(A×M)≦min(k;k)、またはrank(A×M)=k
と簡約されるのほあ明らかである。
【００５５】
ここで、
【数３７】
2008541169.tif 000038
と表すことができるので、
rank(A×M)+rank(A')-min(m;k)≦rank(A×M×A')≦min(rank(A×M),rank(A')
k+k-k≦rank(A×M×A')≦min(k,k)、または
【数３８】
2008541169.tif 000039
となる。
【数３９】
2008541169.tif 000040
であることが示される。
【数４０】
2008541169.tif 000041
は、べき等行列であり、
【数４１】
2008541169.tif 000042
であるため、
【数４２】
2008541169.tif 000043
であることが証明された。
【００５６】
次に行列射影を使用する秘密分散について説明する。このアイデアは、相似変換の下で行列射影不変特性を使用するというものである。まず最初に、Shamirの多項式秘密分散技法について説明する。
【００５７】
行列射影秘密分散
上述のように、Shamirは、k≦nについて(k-1)次多項式関数を用いる(k,n)しきい値秘密分散技法を実証した(A. Shamir, "How to share a secret", Communications of the ACM, vol.22, no.11, pp.612-613, Nov.1979を参照)。秘密値d0∈Zを共有するために、1≦i≦k-1についていくつかのランダム係数di∈Zを用いてk-1次多項式関数f(x)を
f(x)=d0+d1x+ ... +dk-1xk-1 mod p
と書くことができるが、
ただし、p∈Zは、素数である。「n」個の共有を「n」個の異なる参加者に分配するために、分散中心は、「n」個の異なる値に対しyi=f(xi)、xi∈Zとする値(xi,yi)の「n」個の対を計算することができる。変数d0は、ラグランジュ法を使用してk個の共有により
【数４３】
2008541169.tif 000044
と決定することができる。
【００５８】
例えば、秘密値d0=5を考え、p=19に対し(2,4)秘密分散を構成したいとする。多項式関数f(x)は、
f(x)=5+3x mod 19
と書くことができるが、ただし、d1は3に選択されている。
【００５９】
x1=3、x2=5、x3=7、x4=10に対しいくつかの値をランダムに選んだ場合、これら4つの共有を(3,14)、(5,1)、(7,7)、(10,16)として計算することができる。k-1個以下の共有について、秘密値d0に関して知られていない。k個以上の共有について、上述のようにラグランジュ法を使用してd0の値を決定することができる。秘密のサイズは、共有のサイズと同じである。
【００６０】
モジュロ算術演算は、暗号法にとって重要であり、秘密分散技法にも等しく重要である。秘密分散において行列射影を使用するために、まず、ある種の行列モジュロ算術演算を導かなければならない。
【００６１】
モジュロ算術演算では、整数rは逆数r-1をとることができ、r×r-1(mod p)≡1となる。pが素数であれば、フェルマーの定理から、r-1(mod p)≡rp-2(mod p)が成り立つ。例えば、
4-1(mod 19)=419-2(mod 19)=5(mod 19)
である。
【００６２】
またpが素数でない場合に、ユークリッドのアルゴリズムを使用して、r-1(mod p)を計算することもできるが、rおよびpは、互いに素である、つまりgcd(r,p)=1でなければならない([SEB89]を参照)。
【００６３】
行列射影公式(上述)に行列逆演算があるのでモジュロ演算で逆行列を計算する方法は興味深い。Hill換字暗号でも、モジュロ行列逆演算を使用して、復号鍵行列を計算した(D. R. Stinson, Cryptography: Theory and Practice, 2nd edition. Chapman & Hall/CRC, 2002, ch.1.2.4, pp.34-36を参照)。幸いなことに、行列演算に対するモジュロ算術演算は、行列理論における数学的演算と同じように拡張することもできる。
【００６４】
正方行列Mは、det(M)≠0の場合に逆行列M-1を持つ。モジュロ計算では、正方行列は、さらに、mod(det(M),p)≠0の場合に、モジュロ逆行列M-1 (mod p)を持つこともできる。本発明に関する説明の残り部分は、以下の2つの条件に制限される。
【００６５】
1)pは素数であり、
2)mod(det(M),p)≠0である。
【００６６】
M-1(mod p)は、M-1(mod p)=[(det(M))-1(mod p)×adj(M)](mod p)と計算することができる。
【００６７】
ただし、adj(M)は、Mの随伴行列である。
【００６８】
p=19とし、
【数４４】
2008541169.tif 000045
となる2×2行列Mを考える。
【００６９】
det(M)=-29、またはdet(M) (mod 19)=9と計算することができる。9-1(mod 19)=17であり、adj(M)は
【数４５】
2008541169.tif 000046
となることがわかる。
【００７０】
したがって、
【数４６】
2008541169.tif 000047
となる。
【００７１】
上の定理2.1に示されているように、1≦i≦kについてこれらk個のベクトルxiは、射影行列が相似変換の下で不変であるように一次独立であることが要求される。本発明による(k,n)行列秘密分散技法では、この要件は、モジュロ演算逆行列が存在するかどうかを決定するうえで非常に重要である。Miglerらは、固定階数の有限体に多くの一次独立のランダム行列またはベクトルがあることを示した(T. Migler、K. E. Morrison、およびM. Ogle. "Weight and rank of matrices over finite fields", September 29 2003、[オンライン]入手可能: http://www.calpoly.edu/〜kmorriso/Research/weight.pdf。最終アクセス日: March 2006)。特に、階数kのランダムm×k行列の個数(行列Aの利用可能性)は、(pm-1)(pm-p)...(pm-pk-1)であり、 次元k×1のk一次独立ランダムベクトルの個数は、(pk-1)(pk-p) ... (pk-pk-1)(ベクトルxiの利用可能性、または許容される参加者の可能な数)である。これは、逆行列を持つ多くのモジュロ行列を構成できることを示唆している。
【００７２】
行列
【数４７】
2008541169.tif 000048
の中の秘密を解くために(k-1)個のいずれの共有をも使用することはできないため、この要件を満たすように他の条件を制限しなければならない。(k-1)個のベクトルviを知っていると考えると、さらに、
【数４８】
2008541169.tif 000049
および
【数４９】
2008541169.tif 000050
が成り立ち、行列
【数５０】
2008541169.tif 000051
は対称行列である。(k-1)mの連立方程式をたてて、行列
【数５１】
2008541169.tif 000052
内のm(m+1)/2-1個の値を解くことができることは明らかである。それを防ぐために、(k-1)m<m(m+1)/2-1であることを保証する必要がある。したがって、本発明の秘密分散法の他の要件は、m>2(k-1)-1である。
【００７３】
次に、本発明の例示的な一実施形態による行列射影を使用する秘密分散について、説明する。(複数の)秘密は、次元m×1で正方行列
【数５２】
2008541169.tif 000053
に格納される。本発明の例示的な一実施形態による秘密分散法を、i)共有の構成およびii)秘密の再構成に関して説明する。
【００７４】
行列
【数５３】
2008541169.tif 000054
を秘密分散するために、まず、素数「p」を選択しなければならない。この素数の値が、システムの秘密性を直接的に決定する。特に、素数は、モジュロ(mod)計算(後述)で使用されるため、素数が大きいほど、秘密行列
【数５４】
2008541169.tif 000055
を確定することが困難である。ここでの(k,n)行列射影分散法は、以下のステップで説明される。
【００７５】
1)階数kのm×k行列Aを構成する(m>2(k-1)-1)
2)
【数５５】
2008541169.tif 000056
を計算する
3)aiに対するn個の異なる値をランダムに選択し、n個のベクトルxiを
【数５６】
2008541169.tif 000057
として構成する
4)i番目の参加者の共有viを1≦i≦nについてvi=Axi (mod p)として計算する。
【００７６】
5)剰余行列
【数５７】
2008541169.tif 000058
を決定し、公開する
6)行列A、
【数５８】
2008541169.tif 000059
およびn個のベクトルxiを破壊する
7)これらn個の共有viを
【数５９】
2008541169.tif 000060
のn人の異なる参加者に分配する
k-1個以下の共有について、射影行列
【数６０】
2008541169.tif 000061
は、完全な次元性を欠いているため計算することができない。したがって、秘密行列
【数６１】
2008541169.tif 000062
を求めることはできない。k個以上のベクトル共有viがある場合、秘密行列
【数６２】
2008541169.tif 000063
を以下のように決定することができる。
【００７７】
これらのベクトル共有をv1、v2、...、vkとすると、秘密行列
【数６３】
2008541169.tif 000064
は、以下のように決定することができる。
【００７８】
1)行列BをB=[v1 v2 ... vk]と構成するが、ただし、viの次数は重要でない。
【００７９】
2)
【数６４】
2008541169.tif 000065
を計算し、
【数６５】
2008541169.tif 000066
を検証する
3)
【数６６】
2008541169.tif 000067
であることがわかっているので、秘密行列
【数６７】
2008541169.tif 000068
が
【数６８】
2008541169.tif 000069
であることが容易にわかる。
【００８０】
例えば、単純な(2,4)行列秘密分散法を考えて、この技法を明らかにする。p=19とし、秘密(3×3)行列
【数６９】
2008541169.tif 000070
を
【数７０】
2008541169.tif 000071
とする。
【００８１】
秘密共有を構成するために、
【数７１】
2008541169.tif 000072
であるランダム(3×2)行列Aを選ぶ。
【００８２】
式
【数７２】
2008541169.tif 000073
を
【数７３】
2008541169.tif 000074
として計算し、4つの値を選んで、a1=17、a2=7、a3=9、およびa4=10とする。次いで、4ベクトルのベクトルxiを
【数７４】
2008541169.tif 000075
として構成することができる。
【００８３】
次に、i=1、2、3、および4に対するベクトル共有vi=A×xi(mod 19)を
【数７５】
2008541169.tif 000076
として計算し、
【数７６】
2008541169.tif 000077
を
【数７７】
2008541169.tif 000078
として計算する。
【００８４】
剰余行列
【数７８】
2008541169.tif 000079
が公開情報にされる。A、xi、
【数７９】
2008541169.tif 000080
、および
【数８０】
2008541169.tif 000081
を破壊することができ、次いで、4つのベクトル共有viを4人の異なる参加者に分配する。個々の参加者は、剰余行列
【数８１】
2008541169.tif 000082
およびその所有する共有を知っても、秘密行列
【数８２】
2008541169.tif 000083
を明らかにすることはできない。
【００８５】
秘密行列
【数８３】
2008541169.tif 000084
を計算するために、剰余行列
【数８４】
2008541169.tif 000085
とともに、2つの共有が必要である。例えば、これら2つの共有をv1およびv4とすると、行列Bを
【数８５】
2008541169.tif 000086
として構成することができる。
【００８６】
射影行列
【数８６】
2008541169.tif 000087
は、
【数８７】
2008541169.tif 000088
および
【数８８】
2008541169.tif 000089
として計算することができる。結果は、kと全く同じ値である。秘密行列
【数８９】
2008541169.tif 000090
は、
【数９０】
2008541169.tif 000091
および
【数９１】
2008541169.tif 000092
を用いて、
【数９２】
2008541169.tif 000093
として再構成することができる。
【００８７】
この結果は、元の秘密行列
【数９３】
2008541169.tif 000094
と同じである。そこで、行列射影を使用する安全な秘密分散技法を開発した。秘密のサイズは、それぞれの共有のサイズよりも大きい。オーバーヘッドコストに関して、Shamirの方法と本発明の(2,4)方式の実施例を使用する本発明の方法について計算することもできる。Shamirの方法では、秘密値1つに4つの共有値がある。オーバーヘッドコストは、
【数９４】
2008541169.tif 000095
となる。
【００８８】
Shamirの方式の参加者の可能な数は、p-1、またはこの場合、19をモジュロとして18人の参加者である。
【００８９】
本発明の行列射影秘密分散技法では、9つの秘密値にわたって、3つの要素がそれぞれの共有(ベクトル)に含まれる4つのベクトル共有viがある(3×3秘密行列
【数９５】
2008541169.tif 000096
において)。さらに9つの秘密値の剰余行列
【数９６】
2008541169.tif 000097
を加えた場合、オーバーヘッドコストは、
【数９７】
2008541169.tif 000098
となる。
【００９０】
明らかに、本発明の秘密分散技法はオーバーヘッドコストをかなり削減する。それに加えて、本発明の技法の参加者の可能な数は、(pk-1)(pk-p)...(pk-pk-1)または19を法としてk=2の場合に参加者123,120人である。本発明により、さらに多くの数の参加者に、さらに多くの秘密を共有させることができる。
【００９１】
次に、上述の例示的な秘密分散技法をイメージ秘密分散などのいくつかの重要な用途に拡張する。イメージ秘密分散は、NaorおよびShamirによって説明されており、視覚的秘密分散と呼ばれた(M. NaorおよびA. Shamir, "Visual cryptography", presented at the Proceedings of the Conference on Advances in Cryptology - Eurocrypt '94, A. De Santis, Ed., Berlin, Germany, 1994, pp.1-12, M. NaorおよびA. Shair. (1996, June) Visual cryptography II: Improving the contrast via the cover base。[オンライン]入手可能: http://philby.ucsd.edu/cryptolib/1996/96-07.html。最終アクセス日: March 2005)。イメージ秘密分散は、不正アクセスから秘密イメージを保護するために使用されることが多いが、信頼性を高めて信頼できない伝送(信頼できない衛星伝送などの)の破損ピクセルによるイメージ損傷を防止することも行う。
【００９２】
行列射影イメージ秘密分散
(k,n)イメージ秘密分散法では、イメージは、i)任意のk個以上のイメージ共有がイメージの再構成に使用することができ、ii)任意のk-1個以下のイメージ共有では秘密イメージに関する情報が明らかにならないように「n」個の共有に分割される。NaorおよびShamirの技法は、白黒イメージに関して提案されたものである。第1の方式は、(2,2)であり、以下のとおりである。
【００９３】
1)白色ピクセルは、共有毎に2つのピクセルとして表される-1つは黒色、もう1つは白色で、これら2つの共有を重ね合わせることで、1つの白色ピクセルと1つの黒色ピクセルを以下のように表示する。
【表１】
2008541169.tif 000099
【００９４】
2)黒色ピクセルは、共有毎に2つのピクセルとして表される-1つは黒色、もう1つは白色で、これら2つの共有を重ね合わせることで、2つの黒色ピクセルを以下のように表示する。
【表２】
2008541169.tif 000100
【００９５】
しかし、再構成されたイメージは、解像度においてそのコントラストを失い、ときには歪む。それに加えて、共有のサイズは、元のイメージの2倍大きくなる。全体として、イメージ共有のための記憶領域は、秘密イメージのサイズよりも4倍大きい。Atenieseは、この技法を(k,n)イメージ秘密分散として拡張した(G. Ateniese、C. Blundo、A. De Santis、およびD. R. Stinson, "Visual cryptography for general access structures", Information and Computation, vol.129, no.2, pp.86-106, 1996を参照)。さまざまな研究者たちが濃淡イメージとカラーイメージの技法を拡張するうえで課題がまだ残っているが、再構成されたイメージに対するコントラストが喪失することで、元のイメージを完全に再構成することが妨げられる(R. LukacおよびK. N. Plataniotis, "Colour image secret sharing", Electronics Letters, vol.40, no.9, pp.529-531, Apr. 2004、M. NaorおよびA. Shair. (1996, June) Visual cryptography II: Improving the contrast via the cover base。[オンライン]入手可能: http://philby.ucsd.edu/cryptolib/1996/96-07.html。最終アクセス日: March 2005、C. N. Yang, "A note on efficient color visual encryption", Journal of Information Science and Engineering, vol.18, pp.367-372, 2002を参照)。
【００９６】
本発明の発明者は、上述の行列射影秘密分散技法を使用してカラーイメージを「n」個の共有に分割することを伴うアプローチを説明している。このアイデアは、m×m個のピクセルのイメージを秘密行列
【数９８】
2008541169.tif 000101
とみなすことである。本発明では、m×k行列Aおよびその射影行列
【数９９】
2008541169.tif 000102
を構成することができる。それぞれの共有は、次元をm×1とする、または1≦i≦nとしてm個のピクセルを有するベクトルvi=Axi (mod p)であり、xiは、ファンデルモンデ行列から構成されたk×1個のベクトルである。それに加えて、剰余行列
【数１００】
2008541169.tif 000103
も計算される。
【００９７】
イメージが必要になった場合、任意のｋ個のベクトルviを、m×k行列Bに組み合わせて、B=[v1 v2 ... vk]にする。秘密イメージは、秘密行列
【数１０１】
2008541169.tif 000104
として構成され、これは、
【数１０２】
2008541169.tif 000105
として計算することができる。このアプローチでは、再構成されたイメージ中のコントラストはほぼ損失なしであり、それぞれのイメージ共有は、元の秘密イメージよりもm倍小さい。
【００９８】
行列射影秘密分散を使用するイメージ秘密分散には少なくとも2つの課題がある。
【００９９】
1)カラーイメージは、3層からなる、つまり、2D赤色ピクセル、2D緑色ピクセル、および2D青色ピクセルを含むRGBである。
【０１００】
2)ピクセル強度レベルは、典型的には、0〜255であり、これらは素数のモジュロpとして使用することはできない。
【０１０１】
第1の課題は、それぞれの共有がさらに3つの層(赤色、緑色、および青色の強度)を赤色の共有における秘密分散赤色ピクセル、緑色共有における秘密分散緑色ピクセル、および青色共有における秘密分散青色ピクセルとして持つ場合に対処しやすい。
【０１０２】
ピクセル強度を取り扱うために、Ωを可能な最大ピクセル強度レベル(例えば、255)として表し、次いで、「p」をΩに近い最大の素数として選択する。例えば、8ビット分解能イメージでは、Ω=255およびp=233となる。しかし、2つの剰余行列が生成され、1つはp=233よりも大きいピクセル値を含む剰余行列、もう1つは行列射影を使用する秘密分散の計算結果から計算された
【数１０３】
2008541169.tif 000106
である剰余行列である。
【０１０３】
これら2つの剰余m×m行列を組み合わせて単一のm×m行列にすることができる。まず最初に、元のイメージ行列を、1≦i, j≦mおよび0≦gij≦Ωとして
【数１０４】
2008541169.tif 000107
で表し、秘密行列を、0≦dij≦pとして
【数１０５】
2008541169.tif 000108
で表すと、差行列
【数１０６】
2008541169.tif 000109
は、
【数１０７】
2008541169.tif 000110
となる。
【０１０４】
これにより、秘密行列は、モジュロ行列射影操作に使用できることが保証される。
【０１０５】
行列
【数１０８】
2008541169.tif 000111
を秘密分散するために、1≦i,j≦mとする他の剰余行列
【数１０９】
2008541169.tif 000112
を用意する。ここでは、2つの剰余行列
【数１１０】
2008541169.tif 000113
および
【数１１１】
2008541169.tif 000114
を格納したくなく、そこで、これら2つの行列を1つの行列
【数１１２】
2008541169.tif 000115
に、EFを偶数床関数、OFを奇数床関数として
【数１１３】
2008541169.tif 000116
のようにまとめることができる。
【０１０６】
イメージが再構成されるときに、k個のベクトルviを使用して、射影行列
【数１１４】
2008541169.tif 000117
を計算することができる。最も重要なことは、2つの剰余行列を
【数１１５】
2008541169.tif 000118
から逆に2つの剰余行列
【数１１６】
2008541169.tif 000119
と
【数１１７】
2008541169.tif 000120
とに組み立てる必要があるという点である。剰余行列
【数１１８】
2008541169.tif 000121
は、
【数１１９】
2008541169.tif 000122
として構成することができ、他の剰余行列
【数１２０】
2008541169.tif 000123
は、
【数１２１】
2008541169.tif 000124
として構成することができる。
【０１０７】
元のイメージ
【数１２２】
2008541169.tif 000125
は、
【数１２３】
2008541169.tif 000126
として再構成することができる。
【０１０８】
明らかに、この方法によれば、それぞれの秘密共有が、元のイメージを明らかにし得ないことは保証されるだろう。大きなイメージの場合、m×mウィンドウを使用し、イメージ全体をより小さなイメージに分割し、イメージ秘密分散を行えるようにする。さらに、イメージは、行列のさらに小さなブロックに分割できるため、本発明では、いくつかのイメージブロックにおいてリアルタイム処理および伝送のエラーの可能性を許容する。
【０１０９】
本発明では、図1に示されているように「空軍」イメージを秘密分散する、単純なデモンストレーション用のソフトウェアを作成した。
【０１１０】
図1において、288×322ピクセルのカラー「空軍」イメージは、n=5個の共有に分割されるが、ただし、しきい値はk=3で、剰余イメージがある(つまり、(k,n)=(3,5)秘密分散)。m=4を選択した場合、それぞれの共有は、72×84ピクセルである。この場合、「m」は、反復毎に処理されるピクセルの個数に等しい。したがって、「m」の値が増大すると、オーバーヘッドは減少する(つまり、それぞれの個別の共有が小さくなる)が、1分当たりの計算量は増大する。
【０１１１】
これらの共有は、図1の右下に示されている。この実施例では、共有1、2、および4を使用して、剰余イメージによりイメージを再構成しており、実際、3つの共有の組合せを使用して、元のイメージを再構成することが可能である。右上のイメージは、再構成されたイメージであり、これは、歪みまたはコントラスト差のない元の秘密イメージと全く同じである。また、5つの共有のうち1つおよび真ん中に示されている剰余イメージは、元のイメージに関する情報を明らかにしないことに留意されたい。
【０１１２】
図2において、不正な共有(共有2)は、共有1および4で秘密イメージを構成することができない。その結果、この秘密イメージは、k-1個以下のイメージ共有が使用される場合に保護される。
【０１１３】
この技法は、衛星通信ネットワーク(衛星用送信機から衛星用受信機へ)またはクライアント-複数サーバーベースのアーキテクチャ(例えば、共有が複数のサーバー上に格納されるが、クライアント側は、どのサーバーであるかを知らず、移動エージェントを使用して共有を取り出す)で実装されている場合、秘密共有の伝送セキュリティを劇的に変える可能性がある。以下の利点は容易にわかる。
【０１１４】
1)イメージ伝送のセキュリティ
盗聴者は、イメージを再構成するために少なくともk個のチャネルに押し入らなければならず、これは、1つのチャネルでイメージを送信するよりも確かに安全である。それぞれのチャネルを別々に暗号化することによりセキュリティを高めることが可能である。
【０１１５】
2)イメージ再構成の信頼性
通信チャネル上のデータ伝送は、多数のエラーを含み得る。提案されている技法は、この伝送エラーを低減するエラーを起こしやすいアプローチとなっている。元のイメージから構成することができる組合せが多数ある。例えば、上記の「空軍」イメージでは、複数の組合せ(1,2,3)、(1,2,4)、(1,2,5)、(2,3,4)、(2,3,5)、および(3,4,5)、または4つの共有の任意の組合せを一度に使用してイメージを再構成することができる。
【０１１６】
3)帯域幅利用の効率
イメージ共有は元のイメージよりもかなり小さいため、これらの「n」個の秘密共有を送信するために使用される帯域幅は、オーバーヘッドを大きくしない。上記の実施例では、元のイメージは、92,736個のピクセルを有し、共有のそれぞれは、6,048個のピクセルを有する。公開イメージ(または剰余行列)は、元のイメージと同じサイズである92,736個のピクセルを有する。プロセス全体の全伝送は、元のイメージサイズの(92,736+6,048*5)/92,736=1.3261倍である。伝送速度は、1+n/m^2=1+5/16=1.3125におおよそ等しい。NaorおよびShamirの方法を使用する必要がある場合(また、白黒イメージにのみ使用できる場合)、(2,2)しきい値に対する伝送速度は、4であるが、それは、2つのイメージ共有があり、それぞれのイメージ共有は、元の秘密イメージの倍のサイズであるからである。それに加えて、この構成により、イメージは歪む。
【０１１７】
4)他の用途
提案されている行列射影秘密分散法は、データファイル、電子メール、ビデオなどの安全な伝送にも使用することが可能である。さらに、クライアント-複数サーバーアーキテクチャ(上記)は、この技法を使用して、情報共有を宛先に、無線環境であっても、確実に、安全に配信することができる。
【０１１８】
要するに、本発明は、(k,n)カラーイメージ機密分散において使用することができる、行列射影を使用する(k,n)秘密分散法を含む。任意のｋ個のベクトル共有は、通常同じ射影行列を共有することができる同じ射影行列内にある。射影行列は、対称行列であるため、秘密行列は、射影行列と剰余行列(公開情報である)との総和である。しかし、(公開)剰余行列は、射影行列が知られていない場合に秘密行列を明らかにしない。
【０１１９】
本発明の行列射影秘密分散(k,n)法が、情報を保護するために衛星伝送で使用される場合、衛星送信機は、暗号化された情報信号(例えば、秘密行列
【数１２４】
2008541169.tif 000127
)を「n」個の別々のチャネル上で衛星用受信機に送ることができ、剰余行列
【数１２５】
2008541169.tif 000128
を公開することができる。例示的な一実施形態では、衛星用受信機は、「n」個のベクトル共有(vi)のうちの任意の「k」個を含み、このようなベクトル共有および公開される剰余行列を使用して、秘密行列
【数１２６】
2008541169.tif 000129
を導き出す。それとは別に、衛星用受信機は、k-1個のベクトル共有を含むことができ、k番目のベクトル共有に暗号化された情報を入れて、受信機に存在するベクトル共有と剰余行列の組合せにより、受信機側に秘密行列
【数１２７】
2008541169.tif 000130
を生成させるようにできる。
【０１２０】
本発明の行列射影秘密分散技法は、さらに、銀行またはクレジット会社が貴重な情報を安全で信頼性の高い方法により格納するために使用することもできる。この情報は、したがって、あまりコンパクトでない形態で効率よく格納できる。
【０１２１】
本発明の行列射影秘密分散技法は、さらに、オーディオ、ビデオ、およびオーディオビジュアル秘密分散にも拡大適用することができる。音楽およびビデオ産業では、これを用いて、所有権を保護し、不法配給の流通元を追跡することができる。また、オンラインの不法ファイル共有システムを防止するために使用することもできる。例えば、音楽ファイル共有システムにおいて、それぞれの参加者Pに、ベクトル共有(vi)の一意的集合を提供し、それぞれのユーザーの射影行列
【数１２８】
2008541169.tif 000131
が一意となるようにすることができる。この方法を用いると、ユーザーがそのユーザーに割り当てられていない射影行列を使用して音楽ファイルまたは他のコンテンツを復号しようとしても、そのコンテンツは効果的に復号されない。
【０１２２】
本発明は、例示的な実施形態に関して説明されているが、それらの実施形態に限定されない。むしろ、当業者が本発明の範囲およびその等価物の範囲から逸脱することなく実施できる本発明の他の変更形態および実施形態を含むように付属の請求項を広く解釈すべきである。
【図面の簡単な説明】
【０１２３】
【図１】本発明の例示的な一実施形態によるイメージ秘密分散法を示すコンピュータ画面である。
【図２】破損(または無許可)イメージ共有を持つ図1のイメージ秘密分散法を示すコンピュータ画面である。
【図１】
2008541169.tif 000132
【図２】
2008541169.tif 000133
【国際調査報告】
2008541169.tif 000134