JP2008541169A

JP2008541169A - 低オーバーヘッド情報コンテンツにおける秘密分散技法

Info

Publication number: JP2008541169A
Application number: JP2008511174A
Authority: JP
Inventors: バイ，リー
Original assignee: Temple University of Commonwealth System of Higher Education
Current assignee: Temple University of Commonwealth System of Higher Education
Priority date: 2005-05-13
Filing date: 2006-05-03
Publication date: 2008-11-20
Also published as: WO2006124289A3; EP1884059A2; US8059816B2; WO2006124289A2; US20100008505A1

Abstract

第1のランダム行列を生成するステップと、第1のランダム行列から第1の射影行列を生成するステップと、第1の射影行列および第1の秘密行列から第1の剰余行列を決定するステップとを含む秘密を分散するための装置および方法。第1の秘密行列は、剰余行列および複数の分散されたベクトル共有を使用して決定され得る。

Description

本発明は、暗号化のためのシステムおよび方法に関するものであり、特に、安全なマスメディアストレージ(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」人の参加者の集合

に分散され、

の有資格部分集合のみが(複数の)秘密を構成することができる。Γとして表されている、これらの有資格部分集合は、秘密分散法の「アクセス構造」と呼ばれる。完全秘密分散法では、Γに入っていない参加者の部分集合は、(複数の)秘密に関する情報を取得することができない。Γのそれぞれの部分集合内の参加者の数は、必ずしも同じではない。例えば、4人の参加者からなる集合

において、一般化秘密分散法は、アクセス構造Γ={{P₁, P₂}, {P₂, P₃, P₄}}を持つことができる。ここで、第1の部分集合には2人の参加者が入っており、第2の部分集合には3人の参加者が入ることができる。(3,4)しきい値秘密分散法では、アクセス構造Γ={{P₁, P₂, P₃,}, { P₁, P₃, P₄}, {P₂, P₃, P₄}, {P₁, 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を参照)。

情報率ρは、(複数の)秘密の長さ(ビット単位)と複数の参加者の複数の共有の最大長との間の率である。

ただし、Kは、秘密分散法の可能なすべての秘密の集合であり、S(P_i)は、i番目の参加者

に対する可能なすべての共有の集合である。

参加者に与えられる共有のサイズは、秘密分散法の設計における重要な尺度である。共有が大きすぎる場合、秘密を計算するために使用される必要メモリ量は効率的な量にならない。したがって、理想的な秘密分散は、情報率ρ(Σ,Γ,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]を参照)、以下の式で表すことができる。

ただし、Π_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の射影行列を

として表すものとする。射影行列

は

として定義されるが、ただし、(・)'は、転置行列である。さらに、

と書くこともできる。

例えば、3×2行列Aを

と考えると、

を3×3行列として計算するのに定義

を使用することができる。上記の行列射影

は、相似変換の下で不変である。

BがAの相似変換行列であり、Xをk×k正則行列としてB=AXとなっている場合、

を証明することができる。

証明:

Xはk×k正則行列であるため、XX^-1および(X')^-1X'は恒等行列である。式

は、

としてさらに簡約することができる。

行列Xの一実施例として、

となるような2×2行列をとる。

行列Bを

として計算することができる。

式

を検証することができる。

次元kを持つ任意のk個の一次独立ベクトルx_iがある場合、ベクトルviの集合を、1≦i≦kとして、
v_i=Ax_iと計算することができる。これらのk個のベクトルv_iで、行列Bを
B=[v₁ v₂ ... v_k]
と構成することができる。

式

を証明することができる。

したがって、階数kのm×k次元行列A(k≦m)、および1≦i≦kとしてk個の一次独立ベクトルx_iを選択することができる[定理2.1]。v_i=AX_iであるk個のベクトルv_iを使用して、行列Bを
B=[v₁ v₂ ... v_k]
と構成することができる。射影行列は、

を満たす。

証明:B=[v₁ v₂ ... v_k]およびv_i=Ax_iであるため、
B=[v₁ v₂ ... v_k]
=[Ax₁ Ax₂ ... Ax_k]
=A[x₁ x₂ ... x_k]
X=[x₁ x₂ ... x_k]とし、Xはk個の一次独立のベクトルx_isを持つので、Xは最大階数のk×k行列である。B=AXと書くことができる。補題2.1の結果から、

が得られる。

射影行列

は、行列Aから他の行列Bへの相似変換の下で不変である。射影行列

が有する重要な特性もいくつかある。これらは以下のとおりである。

1)

は対称的である、
2)

3)

は、べき等行列である、つまり、

である、
4)

ただし、

は、

となる行列

に対するトレースである。

上記の特性(1)〜(3)は、行列操作により容易に示すことができる。特性(4)は、べき等行列に対する重要な特性であり、得られた射影行列が正しいかどうかを検証するのに役立ち、また単純である。

べき等行列Dは、固有値として0と1しかとらない[補題2.2]。

証明:べき等行列Dについて、その固有値は、λであり、
Dx=λx => D²x=Dλx
となる。

Dは、D²=Dとなるべき等行列であるため、Dx=λDxであることを証明することができ、あるいは、λx=λλxと簡約することができる。つまり、(λ²-λ)x=0となる。この条件は、非ゼロのxについて成立しなければならず、これは、
λ²-λ=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を

とするが、ただし、

とする。

証明: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
と簡約されるのほあ明らかである。

ここで、

と表すことができるので、
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)、または

となる。

であることが示される。

は、べき等行列であり、

であるため、

であることが証明された。

次に行列射影を使用する秘密分散について説明する。このアイデアは、相似変換の下で行列射影不変特性を使用するというものである。まず最初に、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を参照)。秘密値d₀∈Zを共有するために、1≦i≦k-1についていくつかのランダム係数d_i∈Zを用いてk-1次多項式関数f(x)を
f(x)=d₀+d₁x+ ... +d_k-1x^k-1 mod p
と書くことができるが、
ただし、p∈Zは、素数である。「n」個の共有を「n」個の異なる参加者に分配するために、分散中心は、「n」個の異なる値に対しy_i=f(x_i)、x_i∈Zとする値(x_i,y_i)の「n」個の対を計算することができる。変数d₀は、ラグランジュ法を使用してk個の共有により

と決定することができる。

例えば、秘密値d₀=5を考え、p=19に対し(2,4)秘密分散を構成したいとする。多項式関数f(x)は、
f(x)=5+3x mod 19
と書くことができるが、ただし、d₁は3に選択されている。

x₁=3、x₂=5、x₃=7、x₄=10に対しいくつかの値をランダムに選んだ場合、これら4つの共有を(3,14)、(5,1)、(7,7)、(10,16)として計算することができる。k-1個以下の共有について、秘密値d₀に関して知られていない。k個以上の共有について、上述のようにラグランジュ法を使用してd₀の値を決定することができる。秘密のサイズは、共有のサイズと同じである。

モジュロ算術演算は、暗号法にとって重要であり、秘密分散技法にも等しく重要である。秘密分散において行列射影を使用するために、まず、ある種の行列モジュロ算術演算を導かなければならない。

モジュロ算術演算では、整数rは逆数r^-1をとることができ、r×r^-1(mod p)≡1となる。pが素数であれば、フェルマーの定理から、r^-1(mod p)≡r^p-2(mod p)が成り立つ。例えば、
4^-1(mod 19)=4^19-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とし、

となる2×2行列Mを考える。

det(M)=-29、またはdet(M) (mod 19)=9と計算することができる。9^-1(mod 19)=17であり、adj(M)は

となることがわかる。

したがって、

となる。

上の定理2.1に示されているように、1≦i≦kについてこれらk個のベクトルx_iは、射影行列が相似変換の下で不変であるように一次独立であることが要求される。本発明による(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の利用可能性)は、(p^m-1)(p^m-p)...(p^m-p^k-1)であり、次元k×1のk一次独立ランダムベクトルの個数は、(p^k-1)(p^k-p) ... (p^k-p^k-1)(ベクトルx_iの利用可能性、または許容される参加者の可能な数)である。これは、逆行列を持つ多くのモジュロ行列を構成できることを示唆している。

行列

の中の秘密を解くために(k-1)個のいずれの共有をも使用することはできないため、この要件を満たすように他の条件を制限しなければならない。(k-1)個のベクトルviを知っていると考えると、さらに、

および

が成り立ち、行列

は対称行列である。(k-1)mの連立方程式をたてて、行列

内のm(m+1)/2-1個の値を解くことができることは明らかである。それを防ぐために、(k-1)m<m(m+1)/2-1であることを保証する必要がある。したがって、本発明の秘密分散法の他の要件は、m>2(k-1)-1である。

次に、本発明の例示的な一実施形態による行列射影を使用する秘密分散について、説明する。(複数の)秘密は、次元m×1で正方行列

に格納される。本発明の例示的な一実施形態による秘密分散法を、i)共有の構成およびii)秘密の再構成に関して説明する。

行列

を秘密分散するために、まず、素数「p」を選択しなければならない。この素数の値が、システムの秘密性を直接的に決定する。特に、素数は、モジュロ(mod)計算(後述)で使用されるため、素数が大きいほど、秘密行列

を確定することが困難である。ここでの(k,n)行列射影分散法は、以下のステップで説明される。

1)階数kのm×k行列Aを構成する(m>2(k-1)-1)
2)

を計算する
3)a_iに対するn個の異なる値をランダムに選択し、n個のベクトルx_iを

として構成する
4)i番目の参加者の共有v_iを1≦i≦nについてv_i=Ax_i (mod p)として計算する。

5)剰余行列

を決定し、公開する
6)行列A、

およびn個のベクトルx_iを破壊する
7)これらn個の共有viを

のn人の異なる参加者に分配する
k-1個以下の共有について、射影行列

は、完全な次元性を欠いているため計算することができない。したがって、秘密行列

を求めることはできない。k個以上のベクトル共有v_iがある場合、秘密行列

を以下のように決定することができる。

これらのベクトル共有をv₁、v₂、...、v_kとすると、秘密行列

は、以下のように決定することができる。

1)行列BをB=[v₁ v₂ ... v_k]と構成するが、ただし、v_iの次数は重要でない。

2)

を計算し、

を検証する
3)

であることがわかっているので、秘密行列

が

であることが容易にわかる。

例えば、単純な(2,4)行列秘密分散法を考えて、この技法を明らかにする。p=19とし、秘密(3×3)行列

を

とする。

秘密共有を構成するために、

であるランダム(3×2)行列Aを選ぶ。

式

を

として計算し、4つの値を選んで、a₁=17、a₂=7、a₃=9、およびa₄=10とする。次いで、4ベクトルのベクトルx_iを

として構成することができる。

次に、i=1、2、3、および4に対するベクトル共有v_i=A×x_i(mod 19)を

として計算し、

を

として計算する。

剰余行列

が公開情報にされる。A、x_i、

、および

を破壊することができ、次いで、4つのベクトル共有v_iを4人の異なる参加者に分配する。個々の参加者は、剰余行列

およびその所有する共有を知っても、秘密行列

を明らかにすることはできない。

秘密行列

を計算するために、剰余行列

とともに、2つの共有が必要である。例えば、これら2つの共有をv₁およびv₄とすると、行列Bを

として構成することができる。

射影行列

は、

および

として計算することができる。結果は、kと全く同じ値である。秘密行列

は、

および

を用いて、

として再構成することができる。

この結果は、元の秘密行列

と同じである。そこで、行列射影を使用する安全な秘密分散技法を開発した。秘密のサイズは、それぞれの共有のサイズよりも大きい。オーバーヘッドコストに関して、Shamirの方法と本発明の(2,4)方式の実施例を使用する本発明の方法について計算することもできる。Shamirの方法では、秘密値1つに4つの共有値がある。オーバーヘッドコストは、

となる。

Shamirの方式の参加者の可能な数は、p-1、またはこの場合、19をモジュロとして18人の参加者である。

本発明の行列射影秘密分散技法では、9つの秘密値にわたって、3つの要素がそれぞれの共有(ベクトル)に含まれる4つのベクトル共有viがある(3×3秘密行列

において)。さらに9つの秘密値の剰余行列

を加えた場合、オーバーヘッドコストは、

となる。

明らかに、本発明の秘密分散技法はオーバーヘッドコストをかなり削減する。それに加えて、本発明の技法の参加者の可能な数は、(p^k-1)(p^k-p)...(p^k-p^k-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つの黒色ピクセルを以下のように表示する。

2)黒色ピクセルは、共有毎に2つのピクセルとして表される-1つは黒色、もう1つは白色で、これら2つの共有を重ね合わせることで、2つの黒色ピクセルを以下のように表示する。

しかし、再構成されたイメージは、解像度においてそのコントラストを失い、ときには歪む。それに加えて、共有のサイズは、元のイメージの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個のピクセルのイメージを秘密行列

とみなすことである。本発明では、m×k行列Aおよびその射影行列

を構成することができる。それぞれの共有は、次元をm×1とする、または1≦i≦nとしてm個のピクセルを有するベクトルv_i=Ax_i (mod p)であり、x_iは、ファンデルモンデ行列から構成されたk×1個のベクトルである。それに加えて、剰余行列

も計算される。

イメージが必要になった場合、任意のｋ個のベクトルv_iを、m×k行列Bに組み合わせて、B=[v₁ v₂ ... v_k]にする。秘密イメージは、秘密行列

として構成され、これは、

として計算することができる。このアプローチでは、再構成されたイメージ中のコントラストはほぼ損失なしであり、それぞれのイメージ共有は、元の秘密イメージよりも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つは行列射影を使用する秘密分散の計算結果から計算された

である剰余行列である。

これら2つの剰余m×m行列を組み合わせて単一のm×m行列にすることができる。まず最初に、元のイメージ行列を、1≦i, j≦mおよび0≦g_ij≦Ωとして

で表し、秘密行列を、0≦d_ij≦pとして

で表すと、差行列

は、

となる。

これにより、秘密行列は、モジュロ行列射影操作に使用できることが保証される。

行列

を秘密分散するために、1≦i,j≦mとする他の剰余行列

を用意する。ここでは、2つの剰余行列

および

を格納したくなく、そこで、これら2つの行列を1つの行列

に、EFを偶数床関数、OFを奇数床関数として

のようにまとめることができる。

イメージが再構成されるときに、k個のベクトルv_iを使用して、射影行列

を計算することができる。最も重要なことは、2つの剰余行列を

から逆に2つの剰余行列

と

とに組み立てる必要があるという点である。剰余行列

は、

として構成することができ、他の剰余行列

は、

として構成することができる。

元のイメージ

は、

として再構成することができる。

明らかに、この方法によれば、それぞれの秘密共有が、元のイメージを明らかにし得ないことは保証されるだろう。大きなイメージの場合、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)法が、情報を保護するために衛星伝送で使用される場合、衛星送信機は、暗号化された情報信号(例えば、秘密行列

)を「n」個の別々のチャネル上で衛星用受信機に送ることができ、剰余行列

を公開することができる。例示的な一実施形態では、衛星用受信機は、「n」個のベクトル共有(v_i)のうちの任意の「k」個を含み、このようなベクトル共有および公開される剰余行列を使用して、秘密行列

を導き出す。それとは別に、衛星用受信機は、k-1個のベクトル共有を含むことができ、k番目のベクトル共有に暗号化された情報を入れて、受信機に存在するベクトル共有と剰余行列の組合せにより、受信機側に秘密行列

を生成させるようにできる。

本発明の行列射影秘密分散技法は、さらに、銀行またはクレジット会社が貴重な情報を安全で信頼性の高い方法により格納するために使用することもできる。この情報は、したがって、あまりコンパクトでない形態で効率よく格納できる。

本発明の行列射影秘密分散技法は、さらに、オーディオ、ビデオ、およびオーディオビジュアル秘密分散にも拡大適用することができる。音楽およびビデオ産業では、これを用いて、所有権を保護し、不法配給の流通元を追跡することができる。また、オンラインの不法ファイル共有システムを防止するために使用することもできる。例えば、音楽ファイル共有システムにおいて、それぞれの参加者Pに、ベクトル共有(vi)の一意的集合を提供し、それぞれのユーザーの射影行列

が一意となるようにすることができる。この方法を用いると、ユーザーがそのユーザーに割り当てられていない射影行列を使用して音楽ファイルまたは他のコンテンツを復号しようとしても、そのコンテンツは効果的に復号されない。

本発明は、例示的な実施形態に関して説明されているが、それらの実施形態に限定されない。むしろ、当業者が本発明の範囲およびその等価物の範囲から逸脱することなく実施できる本発明の他の変更形態および実施形態を含むように付属の請求項を広く解釈すべきである。

本発明の例示的な一実施形態によるイメージ秘密分散法を示すコンピュータ画面である。破損(または無許可)イメージ共有を持つ図1のイメージ秘密分散法を示すコンピュータ画面である。

Claims

秘密を共有する方法であって、
少なくとも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のコードセグメントとを含むコンピュータデータ信号。