(57)【特許請求の範囲】
【請求項１】
秘密情報と、閾値kと、分散情報総数nとが入力されると、秘密情報に関してn個の分散秘密情報を生成してn個の記憶装置に出力する分散秘密情報生成部と、
前記分散秘密情報生成部で生成されたn個の分散秘密情報と、前記分散情報総数nと、想定不正者数tとが入力されると、分散秘密情報の非改竄性を検証するための第一検証情報を生成し、n個のうち任意のt+1個から該第一検証情報を復元可能に分散符号化したn個の分散情報を生成して前記n個の記憶装置に出力する第一検証情報生成部と、
前記分散秘密情報生成部で生成されたn個の分散秘密情報と、前記第一検証情報生成部で生成された第一検証情報と、前記分散情報総数nと、前記想定不正者数tとが入力されると、前記第一検証情報と予め定められた関係にある第二検証情報を生成し、n個のうち任意のt+1個から該第二検証情報を復元可能に分散符号化したn個の分散情報を生成して前記n個の記憶装置に出力する第二検証情報生成部と、
を有することを特徴とする分散情報生成装置。
【請求項２】
請求項１に記載の分散情報生成装置において、
前記n個の分散秘密情報をv1,v2,...,vnとし、前記第一検証情報をe0とし、該第一検証情報の分散情報をA｛1,i｝ (i=1,2,...,n)とし、前記第二検証情報をe1とし、該第二検証情報の分散情報をA｛2,i｝ (i=1,2,...,n)とすると、
前記第一検証情報生成部は、前記n個の分散秘密情報v1,v2,...,vnと、定数c0と、f0(c0)=e0となるランダムなt次多項式f0と、一体一関数φとに基づいて、前記第一検証情報e0の分散情報A｛1,i｝=f0(φ(i,vi))を生成し、
前記第二検証情報生成部は、前記n個の分散秘密情報v1,v2,...,vnと、定数c1と、f1(c1)=e1となるランダムなt次多項式f1と、一体一関数φとに基づいて、前記第二検証情報e1の分散情報A｛2,i｝=f1(φ(i,vi))を生成することを特徴とする分散情報生成装置。
【請求項３】
閾値kと、k個以上n個以下の記憶装置のそれぞれに格納された分散秘密情報とが入力されると、k個以上の分散秘密情報から秘密情報を復元可能な秘密情報復元部と、
t+1個の記憶装置のそれぞれに格納された、分散秘密情報および該分散秘密情報の非改竄性を検証するための第一検証情報の分散情報と、想定不正者数tとが入力されると、t+1個の該分散情報から該第一検証情報を復元する第一検証情報復元部と、
前記t+1個の記憶装置に格納された、分散秘密情報および該分散秘密情報の非改竄性を検証するための第二検証情報の分散情報と、想定不正者数tとが入力されると、t+1個の該分散情報から該第二検証情報を復元する第二検証情報復元部と、
前記k個以上の記憶装置のうち、全ての組み合わせのt+1個の記憶装置に格納された情報を部分集合として、該部分集合毎に、t+1個の前記分散秘密情報および前記第一検証情報の分散情報を前記第一検証情報復元部に出力し、t+1個の前記分散秘密情報および前記第二検証情報の分散情報を前記第二検証情報復元部に出力し、全ての部分集合について、前記第一検証情報復元部で復元された第一検証情報と前記第二検証情報復元部で復元された第二検証情報が予め定められた関係を満たすか否かを判定し、これら２つの検証情報が予め定められた関係を満たす場合、前記秘密情報復元部に前記秘密情報を復元させ、前記２つの検証情報が予め定められた関係を満たさない部分集合がある場合、該２つの検証情報が予め定められた関係を満たす部分集合の記憶装置をn個の記憶装置から除去した後の記憶装置を、改竄された分散秘密情報が格納された記憶装置としてリストにして出力する整合性判定部と、
を有することを特徴とする復元装置。
【請求項４】
請求項３に記載の復元装置において、
前記第一検証情報をe0とし、前記第二検証情報をe1とし、
部分集合毎に、前記分散秘密情報をv｛i＿j｝ (i=1,2,...,n、j=1,2,...,t+1)とし、前記第一検証情報の分散情報をA｛1,i＿j｝とし、前記第二検証情報の分散情報をA｛2,i＿j｝とすると、
前記第一検証情報復元部は、t+1個のv｛i＿j｝およびA｛1,i＿j｝と、一体一関数φと、定数c0とから、A｛1,i＿j｝ = f0(φ(i＿j,v｛i＿j｝))を満たすt次多項式f0に対してe0=f0(c0)を求めることによって、前記第一検証情報e0を復元し、
前記第二検証情報復元部は、t+1個のv｛i＿j｝およびA｛2,i＿j｝と、一体一関数φと、定数c1とから、A｛2,i＿j｝ = f1(φ(i＿j,v｛i＿j｝))を満たすt次多項式f1に対してe1=f1(c1)を求めることによって、前記第二検証情報e1を復元することを特徴とする復元装置。
【請求項５】
請求項１に記載された分散情報生成装置と、
請求項３に記載された復元装置と、
を有することを特徴とする秘密情報分散システム。
【請求項６】
請求項２に記載の分散情報生成装置と、
請求項４に記載の復元装置と、
を有することを特徴とする秘密情報分散システム。
【請求項７】
請求項６に記載の秘密情報分散システムにおいて、
c0=0 かつ c1=0であることを特徴とする秘密情報分散システム。
【請求項８】
分散情報生成装置および復元装置を有する秘密情報分散システムによる情報処理方法であって、
前記分散情報生成装置は、秘密情報と、閾値kと、分散情報総数nとが入力されると、秘密情報に関してn個の分散秘密情報を生成してn個の記憶装置に出力し、
前記分散情報生成装置は、想定不正者数tが入力されると、前記n個の分散秘密情報、前記分散情報総数n、および該想定不正者数tに基づいて、分散秘密情報の非改竄性を検証するための第一検証情報を生成し、
前記分散情報生成装置は、n個のうち任意のt+1個から前記第一検証情報を復元可能に分散符号化したn個の分散情報を生成して前記n個の記憶装置に出力し、
前記分散情報生成装置は、前記分散秘密情報、前記第一検証情報、前記分散情報総数n、および前記想定不正者数tに基づいて、前記第一検証情報と予め定められた関係にある第二検証情報を生成し、
前記分散情報生成装置は、n個のうち任意のt+1個から前記第二検証情報を復元可能に分散符号化したn個の分散情報を生成して前記n個の記憶装置に出力し、その後、
前記復元装置は、k個以上、n個以下の記憶装置のうち、全ての組み合わせのt+1個の記憶装置に格納された情報を部分集合として、該部分集合毎に、t+1個の分散秘密情報および前記第一検証情報の分散情報と、前記想定不正者数tとに基づいて、該第一検証情報を復元し、
前記復元装置は、前記部分集合毎に、t+1個の分散秘密情報および前記第二検証情報の分散情報と、前記想定不正者数tとに基づいて、該第二検証情報を復元し、
前記復元装置は、全ての部分集合について、復元された第一検証情報と復元された第二検証情報が予め定められた関係を満たすか否かを判定し、これら２つの検証情報が予め定められた関係を満たす場合、k個以上の分散秘密情報から秘密情報を復元し、前記２つの検証情報が予め定められた関係を満たさない部分集合がある場合、該２つの検証情報が予め定められた関係を満たす部分集合の記憶装置をn個の記憶装置から除去した後の記憶装置を、改竄された分散秘密情報が格納された記憶装置としてリストにして出力することを特徴とする情報処理方法。
【請求項９】
コンピュータを、
秘密情報と、閾値kと、分散情報総数nとが入力されると、秘密情報に関してn個の分散秘密情報を生成してn個の記憶装置に出力する、分散情報生成装置の分散秘密情報生成部として機能させ、
想定不正者数tが入力されると、前記n個の分散秘密情報、前記分散情報総数n、および該想定不正者数tに基づいて、分散秘密情報の非改竄性を検証するための第一検証情報を生成し、n個のうち任意のt+1個から前記第一検証情報を復元可能に分散符号化したn個の分散情報を生成して前記n個の記憶装置に出力する、分散情報生成装置の第一検証情報生成部として機能させ、
前記分散秘密情報、前記第一検証情報、前記分散情報総数n、および前記想定不正者数tに基づいて、前記第一検証情報と予め定められた関係にある第二検証情報を生成し、n個のうち任意のt+1個から前記第二検証情報を復元可能に分散符号化したn個の分散情報を生成して前記n個の記憶装置に出力する、分散情報生成装置の第二検証情報生成部として機能させるためのプログラム。
【請求項１０】
コンピュータを、
閾値k個以上、n個以下の記憶装置のうち、全ての組み合わせのt+1個の記憶装置に格納された情報を部分集合として、該部分集合毎に、t+1個の分散秘密情報および該分散秘密情報の非改竄性を検証するための第一検証情報の分散情報と、想定不正者数tとに基づいて、該第一検証情報を復元する、復元装置の第一検証情報復元部として機能させ、
前記部分集合毎に、t+1個の分散秘密情報および該分散秘密情報の非改竄性を検証するための第二検証情報の分散情報と、想定不正者数tとに基づいて、該第二検証情報を復元する、復元装置の第二検証情報復元部として機能させ、
全ての部分集合について、復元された第一検証情報と復元された第二検証情報が予め定められた関係を満たすか否かを判定し、これら２つの検証情報が予め定められた関係を満たさない部分集合がある場合、該２つの検証情報が予め定められた関係を満たす部分集合の記憶装置をn個の記憶装置から除去した後の記憶装置を、改竄された分散秘密情報が格納された記憶装置としてリストにして出力する、復元装置の検証情報整合性判定部として機能させ、
前記２つの検証情報が予め定められた関係を満たす場合、k個以上の分散秘密情報から秘密情報を復元する、復元装置の秘密情報復元部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘密情報を分散して安全に保管するための分散情報生成装置と、保管された秘密情報を復元する復元装置と、秘密分散システムと、情報処理方法と、コンピュータに実行させるためのプログラムとに関する。
【背景技術】
【０００２】
秘密情報を複数の分散秘密情報に分散し、予め定められた分散秘密情報が集まった場合にのみ秘密情報が復元される暗号技術として秘密分散法が知られている。
【０００３】
秘密分散法の中で最も有名な技術は、(k,n)閾値秘密分散法と呼ばれる技術である。この技術は、秘密分散法の中で (1) 秘密情報をn個の分散秘密情報に分散し、(2) その中の任意のk個が集まった場合には秘密情報が復元でき、(3) k個未満の分散情報からは秘密に関するいかなる情報も得られないという特徴を持ったものである（非特許文献１参照）。
【０００４】
非特許文献１に示されている(k,n)閾値秘密分散法は、分散秘密情報を管理する者の不正や、分散秘密情報を管理する装置の故障を考慮していない方式になっていた。そのため、k個の分散秘密情報を集めて秘密の復元を行う際、一つでも元の情報とは異なる分散秘密情報が出されると、秘密を正しく復元することができず、また、復元された秘密が元の秘密情報とは異なっているという事実も検知することができなかった。
【０００５】
この問題を解決するため、非特許文献２、非特許文献３および特許文献１のそれぞれには、k-1個の改竄された分散秘密情報が秘密復元時に集められた場合でも、復元された秘密が元の秘密情報とは異なっているという事実を検知できる方式が開示されている。しかし、これらの技術では、分散秘密情報が改竄されていることを秘密復元時に検知できたが、どの分散秘密情報が改竄されたものであるかを特定することはできなかった。
【０００６】
改竄された分散秘密情報が含まれていることが秘密復元時に明らかになる場合に、どの分散秘密情報が改竄されているかを特定する技術としては、非特許文献４〜７が知られている。非特許文献５および非特許文献７では、改竄された分散秘密情報の個数tがk≧3t+1の場合に、改竄されたt個の分散秘密情報全てを高い確率で特定することが可能な方式が示されている。非特許文献４および非特許文献６では、改竄された分散秘密情報の個数tがk≧2t+1の場合に、改竄されたt個の分散秘密情報全てを高い確率で特定することが可能な方式が示されている。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】国際公開  ＷＯ ２００８／００１６２８
【非特許文献】
【０００８】
【非特許文献１】Adi Shamir, "How to share a secret", Comm. ACM, 22(11), 612-613(1979)
【非特許文献２】Martin Tompa, Heather Woll, "How to Share a Secret with Cheaters", Journal of Cryptology, vol.1, pages 133-138, 1988
【非特許文献３】Wakaha Ogata, Kaoru Kurosawa, Douglas R Stinson, "Optimum Secret Sharing Scheme Secure Against Cheating", SIAM Journal on Discrete Mathematics, vol.20, no1, pages 79-95, 2006
【非特許文献４】T. Rabin and M. Ben-Or, "Verifiable Secret Sharing and Multiparty Protocols with Honest Majority", Proc. STOC'89, pp. 73--85, 1989
【非特許文献５】K. Kurosawa, S. Obana and W. Ogata, "t-Cheater Identifiable (k,n) Secret Sharing Schemes," Proc. Crypto'95, Lecture Notes in Computer Science, vol. 963, Springer Verlag, pp. 410--423, 1995
【非特許文献６】W. Ogata and K. Kurosawa, "Provably Secure Metering Scheme", Proc. Asiacrypt'00, Lecture Notes in Computer Science, vol. 1976, Springer Verlag, pp. 388--398, 2000
【非特許文献７】尾花, "ｔ人までの不正者を特定できる準最適な秘密分散法",2007年暗号と情報セキュリティシンポジウム, 3D1-1, 2007
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかし、非特許文献４および非特許文献６で示されているk≧2t+1の場合に対する各方式における分散秘密情報のサイズは、秘密情報のビット長をLとした場合、それぞれ(3n-2)Lビット、(2k+1)Lビットとなり、分散秘密情報のサイズが非常に大きくなるという問題があった。
【００１０】
本発明は上述したような技術が有する問題点を解決するためになされたものであり、分散情報のデータサイズをより小さくすることを可能にした分散情報生成装置、復元装置、秘密分散システム、情報処理およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
上記目的を達成するための本発明の分散情報生成装置は、
秘密情報と、閾値kと、分散情報総数nとが入力されると、秘密情報に関してn個の分散秘密情報を生成してn個の記憶装置に出力する分散秘密情報生成部と、
前記分散秘密情報生成部で生成されたn個の分散秘密情報と、前記分散情報総数nと、想定不正者数tとが入力されると、分散秘密情報の非改竄性を検証するための第一検証情報を生成し、n個のうち任意のt+1個から該第一検証情報を復元可能に分散符号化したn個の分散情報を生成して前記n個の記憶装置に出力する第一検証情報生成部と、
前記分散秘密情報生成部で生成されたn個の分散秘密情報と、前記第一検証情報生成部で生成された第一検証情報と、前記分散情報総数nと、前記想定不正者数tとが入力されると、前記第一検証情報と予め定められた関係にある第二検証情報を生成し、n個のうち任意のt+1個から該第二検証情報を復元可能に分散符号化したn個の分散情報を生成して前記n個の記憶装置に出力する第二検証情報生成部と、
を有する構成である。
【００１２】
また、本発明の復元装置は、
閾値kと、k個以上n個以下の記憶装置のそれぞれに格納された分散秘密情報とが入力されると、k個以上の分散秘密情報から秘密情報を復元可能な秘密情報復元部と、
t+1個の記憶装置のそれぞれに格納された、分散秘密情報および該分散秘密情報の非改竄性を検証するための第一検証情報の分散情報と、想定不正者数tとが入力されると、t+1個の該分散情報から該第一検証情報を復元する第一検証情報復元部と、
前記t+1個の記憶装置に格納された、分散秘密情報および該分散秘密情報の非改竄性を検証するための第二検証情報の分散情報と、想定不正者数tとが入力されると、t+1個の該分散情報から該第二検証情報を復元する第二検証情報復元部と、
前記k個以上の記憶装置のうち、全ての組み合わせのt+1個の記憶装置に格納された情報を部分集合として、該部分集合毎に、t+1個の前記分散秘密情報および前記第一検証情報の分散情報を前記第一検証情報復元部に出力し、t+1個の前記分散秘密情報および前記第二検証情報の分散情報を前記第二検証情報復元部に出力し、全ての部分集合について、前記第一検証情報復元部で復元された第一検証情報と前記第二検証情報復元部で復元された第二検証情報が予め定められた関係を満たすか否かを判定し、これら２つの検証情報が予め定められた関係を満たす場合、前記秘密情報復元部に前記秘密情報を復元させ、前記２つの検証情報が予め定められた関係を満たさない部分集合がある場合、該２つの検証情報が予め定められた関係を満たす部分集合の記憶装置をn個の記憶装置から除去した後の記憶装置を、改竄された分散秘密情報が格納された記憶装置としてリストにして出力する整合性判定部と、
を有する構成である。
【００１３】
また、本発明の情報処理方法は、分散情報生成装置および復元装置を有する秘密情報分散システムによる情報処理方法であって、
前記分散情報生成装置は、秘密情報と、閾値kと、分散情報総数nとが入力されると、秘密情報に関してn個の分散秘密情報を生成してn個の記憶装置に出力し、
前記分散情報生成装置は、想定不正者数tが入力されると、前記n個の分散秘密情報、前記分散情報総数n、および該想定不正者数tに基づいて、分散秘密情報の非改竄性を検証するための第一検証情報を生成し、
前記分散情報生成装置は、n個のうち任意のt+1個から前記第一検証情報を復元可能に分散符号化したn個の分散情報を生成して前記n個の記憶装置に出力し、
前記分散情報生成装置は、前記分散秘密情報、前記第一検証情報、前記分散情報総数n、および前記想定不正者数tに基づいて、前記第一検証情報と予め定められた関係にある第二検証情報を生成し、
前記分散情報生成装置は、n個のうち任意のt+1個から前記第二検証情報を復元可能に分散符号化したn個の分散情報を生成して前記n個の記憶装置に出力し、その後、
前記復元装置は、k個以上、n個以下の記憶装置のうち、全ての組み合わせのt+1個の記憶装置に格納された情報を部分集合として、該部分集合毎に、t+1個の分散秘密情報および前記第一検証情報の分散情報と、前記想定不正者数tとに基づいて、該第一検証情報を復元し、
前記復元装置は、前記部分集合毎に、t+1個の分散秘密情報および前記第二検証情報の分散情報と、前記想定不正者数tとに基づいて、該第二検証情報を復元し、
前記復元装置は、全ての部分集合について、復元された第一検証情報と復元された第二検証情報が予め定められた関係を満たすか否かを判定し、これら２つの検証情報が予め定められた関係を満たす場合、k個以上の分散秘密情報から秘密情報を復元し、前記２つの検証情報が予め定められた関係を満たさない部分集合がある場合、該２つの検証情報が予め定められた関係を満たす部分集合の記憶装置をn個の記憶装置から除去した後の記憶装置を、改竄された分散秘密情報が格納された記憶装置としてリストにして出力するものである。
【００１４】
また、本発明のプログラムは、コンピュータを、
秘密情報と、閾値kと、分散情報総数nとが入力されると、秘密情報に関してn個の分散秘密情報を生成してn個の記憶装置に出力する、分散情報生成装置の分散秘密情報生成部として機能させ、
想定不正者数tが入力されると、前記n個の分散秘密情報、前記分散情報総数n、および該想定不正者数tに基づいて、分散秘密情報の非改竄性を検証するための第一検証情報を生成し、n個のうち任意のt+1個から前記第一検証情報を復元可能に分散符号化したn個の分散情報を生成して前記n個の記憶装置に出力する、分散情報生成装置の第一検証情報生成部として機能させ、
前記分散秘密情報、前記第一検証情報、前記分散情報総数n、および前記想定不正者数tに基づいて、前記第一検証情報と予め定められた関係にある第二検証情報を生成し、n個のうち任意のt+1個から前記第二検証情報を復元可能に分散符号化したn個の分散情報を生成して前記n個の記憶装置に出力する、分散情報生成装置の第二検証情報生成部として機能させるものである。
【００１５】
さらに、本発明のプログラムは、コンピュータを、
閾値k個以上、n個以下の記憶装置のうち、全ての組み合わせのt+1個の記憶装置に格納された情報を部分集合として、該部分集合毎に、t+1個の分散秘密情報および該分散秘密情報の非改竄性を検証するための第一検証情報の分散情報と、想定不正者数tとに基づいて、該第一検証情報を復元する、復元装置の第一検証情報復元部として機能させ、
前記部分集合毎に、t+1個の分散秘密情報および該分散秘密情報の非改竄性を検証するための第二検証情報の分散情報と、想定不正者数tとに基づいて、該第二検証情報を復元する、復元装置の第二検証情報復元部として機能させ、
全ての部分集合について、復元された第一検証情報と復元された第二検証情報が予め定められた関係を満たすか否かを判定し、これら２つの検証情報が予め定められた関係を満たさない部分集合がある場合、該２つの検証情報が予め定められた関係を満たす部分集合の記憶装置をn個の記憶装置から除去した後の記憶装置を、改竄された分散秘密情報が格納された記憶装置としてリストにして出力する、復元装置の検証情報整合性判定部として機能させ、
前記２つの検証情報が予め定められた関係を満たす場合、k個以上の分散秘密情報から秘密情報を復元する、復元装置の秘密情報復元部として機能させるものである。
【発明の効果】
【００１６】
本発明によれば、秘密情報に関する分散情報のデータサイズを小さくすることができる。
【図面の簡単な説明】
【００１７】
【図１】本実施形態の分散情報生成装置の一構成例を示すブロック図である。
【図２】本実施形態の復元装置の一構成例を示すブロック図である。
【図３】本実施形態の分散情報生成装置および復元装置をコンピュータで実現する場合の一例を示すブロック図である。
【図４】本実施形態の分散情報生成装置の動作を示すフローチャートである。
【図５】本実施形態の復元装置の動作を示すフローチャートである。
【発明を実施するための形態】
【００１８】
本実施形態の秘密情報分散システムは、秘密情報を保管する場合、閾値および分散情報総数にしたがって秘密情報を分散符号化した分散秘密情報を生成し、生成した分散情報秘密情報を分散情報総数の個数存在する記憶装置に分散して格納し、さらに、分散符号化された分散秘密情報と、想定不正者数とにしたがって、第一検証情報と第二検証情報とを生成し、それらを分散符号化した情報を、対応する記憶装置に格納する。
【００１９】
また、本実施形態の秘密情報分散システムは、秘密情報を復元する場合、閾値に対応する数の記憶装置から分散符号化された分散秘密情報および対応する第一検証情報と第二検証情報を読み出し、改竄された分散秘密情報を特定する。改竄された分散秘密情報が検出されなければ、秘密情報を復元する。
【００２０】
本実施形態の秘密情報分散システムを、図１および図２を参照して説明する。
【００２１】
図１は分散情報生成装置の一構成例を示すブロック図であり、図２は復元装置の一構成例を示すブロック図である。
【００２２】
本実施形態の秘密情報分散システムは、分散情報生成装置100および復元装置200を有する。分散情報生成装置100および復元装置200のそれぞれは、複数(n個)の記憶装置300-1〜300-nと接続される。記憶装置300-1〜300-nは、分散符号化された分散秘密情報が格納される分散秘密情報格納部301-1〜301-nと、第一検証情報が分散符号化された分散情報が格納される第一検証情報格納部302-1〜302-nと、第二検証情報が分散符号化されたが分散情報が格納される第二検証情報格納部303-1〜303-nとを備えている。第一検証情報および第二検証情報は、分散秘密情報の非改竄性を検証するための情報である。
【００２３】
はじめに、分散情報生成装置100の構成について図１を用いて説明する。
【００２４】
図１に示すように、分散情報生成装置100は、分散秘密情報生成部101と、第一検証情報生成部102と、第二検証情報生成部103とを有する。
【００２５】
分散情報生成装置100は、秘密情報集合の元である秘密情報s、閾値k、分散情報総数n、想定不正者数tが入力されると、記憶装置300-1〜300-nの各分散秘密情報格納部301-1〜301-nに分散秘密情報生成部101の出力を格納し、記憶装置300-1〜300-nの各第一検証情報格納部302-1〜302-nに第一検証情報生成部102の出力を格納し、記憶装置300-1〜300-nの各第二検証情報格納部303-1〜303-nに第二検証情報生成部103の出力を格納する。
【００２６】
分散秘密情報生成部101は、秘密情報s、閾値k、分散情報総数nが入力されると、n個の分散情報 vi (i=1,2,...,n) を、対応する記憶装置300-iの分散秘密情報格納部301-iに格納する。
【００２７】
第一検証情報生成部102は、分散秘密情報生成部101の出力である、n個の分散秘密情報v1,...,vnと、想定不正者数tと、分散情報総数nとが入力されると、n個の分散情報vi (i=1,2,...,n) に対応する第一検証情報の分散情報 A｛1,i｝を記憶装置300-iの第一検証情報格納部302-iに格納する。
【００２８】
第二検証情報生成部103は、分散秘密情報生成部101の出力である、n個の分散秘密情報v1,...,vnと、想定不正者数tと、第一検証情報生成部102の出力である第一検証情報と、分散情報総数nとが入力されると、n個の分散情報vi (i=1,2,...,n) に対応する第二検証情報の分散情報 A｛2,i｝を記憶装置300-iの第二検証情報格納部303-iに格納する。
【００２９】
次に、復元装置200の構成について図２を用いて説明する。
【００３０】
図２に示すように、復元装置200は、秘密情報復元部201と、第一検証情報復元部202と、第二検証情報復元部203と、検証情報整合性判定部204とを有する。
【００３１】
復元装置200には、閾値kおよび想定不正者数tが入力される。復元装置200は、記憶装置300-1〜300-nのうち、k個以上の記憶装置300-i＿1〜300-i＿mが備える分散秘密情報格納部301-i＿1〜301-i＿mから分散秘密情報v｛i＿1｝〜v｛i＿m｝を読み出し、記憶装置300-i＿1〜300-i＿kが備える第一検証情報格納部302-i＿1〜302-i＿mから第一検証情報の分散情報A｛1,i＿1｝〜A｛1,i＿m｝を読み出し、記憶装置300-i＿1〜300-i＿kが備える第二検証情報格納部303-i＿1〜303-i＿mから第二検証情報の分散情報A｛2,i＿1｝〜A｛2,i＿m｝を読み出す。そして、復元装置200は、それら読み出した情報から不正者を検出した場合には、不正者を検出したことを示す記号および不正者の識別子を要素とする集合を出力し、不正者が検出されなかった場合には、復元された秘密情報と、不正者が存在しなかったことを示す空集合とを出力する。
【００３２】
第一検証情報復元部202は、想定不正者数tと、検証情報整合性判定部204から出力される、t+1個の記憶装置に格納された情報とが入力されると、入力された情報に基づいて第一検証情報を出力する。
【００３３】
第二検証情報復元部203は、想定不正者数tと、検証情報整合性判定部204から出力される、t+1個の記憶装置に格納された情報とが入力されると、入力された情報に基づいて第二検証情報を出力する。
【００３４】
検証情報整合性判定部204は、復元装置200に入力された、m個の記憶装置300-i＿1〜300-i＿mに格納された情報と、想定不正者数tとが入力されると、入力された、m個の情報の全てのt+1個の部分集合に対して、それぞれ第一検証情報復元部202と第二検証情報復元部203とに、t+1個の記憶装置300に格納された情報を入力することにより、第一検証情報復元部202から復元された第一検証情報を受け取り、第二検証情報復元部203から復元された第二検証情報を受け取る。そして、検証情報整合性判定部204は、これら二つの検証情報が予め定められた関係を満たすかどうかをチェックし、関係を満たす場合は、対応するt+1個の記憶装置には、改竄された分散秘密情報が含まれていないと判定する処理を繰り返し、全てのt+1個の部分集合に対して判定を行った後に、分散秘密情報の改竄が行われた記憶装置のリストを出力する。
【００３５】
秘密情報復元部201は、復元装置200に入力された、m個の記憶装置300に格納された情報と、検証情報整合性判定部204の出力Lと、閾値kとが入力されると、Lが空集合であった場合にのみ秘密情報の復元処理を行い、復元された秘密情報を出力する。Lが空集合でない場合には、秘密情報復元部201は、不正が検出されたことを示す記号を出力する。
【００３６】
図１および図２は機能ブロック図であり、図１に示した分散情報生成装置100および図２に示した復元装置200は、例えば、論理回路等から構成されるLSI (Large Scale Integration)やDSP (Digital Signal Processor)等の半導体集積回路によって実現される。
【００３７】
また、分散情報生成装置100および復元装置200のそれぞれは、図３に示すように、プログラムにしたがって所定の処理を実行する処理装置10と、処理装置10に対してコマンドや情報等を入力するための入力装置20と、処理装置10の処理結果をモニタするための出力装置30とを備えたコンピュータによって実現されてもよい。
【００３８】
図３に示す処理装置10は、CPU(Central Processing Unit)11と、CPU11の処理に必要な情報を一時的に記憶する主記憶装置12と、CPU11に分散情報生成装置100または復元装置200としての処理を実行させるためのプログラムが記録された記録媒体13と、秘密情報やアクセス構造データが格納されるデータ蓄積装置14と、主記憶装置12、記録媒体13およびデータ蓄積装置14とのデータ転送を制御するメモリ制御インタフェース部15と、入力装置20および出力装置30とのインタフェース装置であるＩ／Ｏインタフェース部16とを有し、それらがバス18を介して接続された構成である。
【００３９】
なお、データ蓄積装置14は、処理装置10内に必ずしも設けられている必要はなく、処理装置10とは別に独立して設けられていてもよい。また、データ蓄積装置14は、分散秘密情報格納部301、第一検証情報格納部302および第二検証情報格納部303を備えた記憶装置300であってもよい。
【００４０】
処理装置10は、記録媒体13に記録されたプログラムにしたがって、分散情報生成装置100または復元装置200としての機能を実現する。記録媒体13は、磁気ディスク、半導体メモリ、光ディスクあるいはその他の記録媒体であってもよい。
【００４１】
次に、本実施形態の秘密情報分散システムの動作について、図４および図５を参照して説明する。
【００４２】
図４は分散情報生成装置の動作を示すフローチャートであり、図５は復元装置の動作を示すフローチャートである。
【００４３】
図４に示すように、分散情報生成装置100に、秘密情報s、閾値k、分散情報総数n、および想定不正者数tが入力される(ステップA1)。
【００４４】
秘密情報分散装置100は、分散秘密情報生成部101に秘密情報s、閾値k、分散情報総数nが入力されると、秘密情報sを任意のk個の分散情報で復元できるように分散符号化し、記憶装置300の分散秘密情報格納部301に格納する(ステップA2)。
【００４５】
次に、秘密情報分散装置100は、第一検証情報生成部102に想定不正者数t、分散情報総数n、分散秘密情報生成部101の出力v1,...,vnを入力すると、第一検証情報e0を生成し(ステップA3)、e0を任意のt+1個の分散情報で復元できるように分散符号化し、記憶装置300の第一検証情報格納部302に格納する(ステップA4)。
【００４６】
次に、秘密情報分散装置100は、第二検証情報生成部103に想定不正者数t、分散情報総数n、分散秘密情報生成部101の出力v1,...,vn、および第一検証情報e0を入力すると、e0と予め定められた関係にあるe1を第二検証情報として生成し(ステップA5)、e1を任意のt+1個の分散情報で復元できるように分散符号化し、記憶装置300の第二検証情報格納部303に格納する(ステップA6)。
【００４７】
図５に示すように、復元装置200に、閾値kおよび想定不正者数tが入力されると、復元装置200は、m≧kなるm個の記憶装置300に格納されたデータを読み出す(ステップB1)。
【００４８】
復元装置200は、検証情報整合性判定部204にm個の記憶装置から読み出した情報V｛i＿1｝,...,V｛i＿m｝と、想定不正者数tとを入力し、｛V｛i＿1｝,...,V｛i＿m｝｝の要素数t+1個の全ての部分集合に対して、以下のステップB3〜B6を繰り返す(ステップB2)。
【００４９】
復元装置200が、第一検証情報復元部202にt+1個の情報と、想定不正者数tとを入力して、第一検証情報e0を復元する(ステップB3)。
【００５０】
次に、復元装置200が、第二検証情報復元部203にt+1個の情報と、想定不正者数tとを入力して、第二検証情報e1を復元する(ステップB4)。
【００５１】
復元装置200は、ステップB3で復元された第一検証情報とステップB4で復元された第二検証情報を検証情報整合性判定部204に入力し、これら二つの検証情報が予め定められた関係を満たすかどうかを判定する(ステップB5)。判定の結果、二つの検証情報が予め定められた関係を満たす場合、復元装置200は、そのt+1個の情報には分散秘密情報が改竄されていないと判定し、分散秘密情報の改竄された記憶装置候補から該当するt+1個の記憶装置を除去し(ステップB6)、その後、ステップB2に戻る。
【００５２】
ステップB5の判定の結果、二つの検証情報が予め定められた関係を満たさない場合、復元装置200は、分散秘密情報の改竄された記憶装置候補のリストは変更せずにステップB2に戻る。ただし、分散秘密情報の改竄された記憶装置候補のリストの初期値は、情報を読み出した全記憶装置のリストとする。
【００５３】
ステップB2〜B6の処理が全てのt+1個の部分集合に対して行われた後、復元装置200は、検証情報整合性判定部204の出力である、分散秘密情報が改竄されたと判定した記憶装置リストLが空集合であるか否かをチェックする(ステップB7)。ステップB7の結果、Lが空集合、つまりステップB1で読み出した分散秘密情報は全て改竄されていないと判定した場合、復元装置200は、秘密情報復元部201に秘密情報を復元させて出力する(ステップB8)。ステップB7の結果、Lが空集合でない場合、復元装置200は、分散秘密情報が改竄されたと判定した記憶装置を示すリストを出力する(ステップB9)。
【００５４】
本実施形態では、第一検証情報および第二検証情報を任意のt+1個の分散情報から復元できるということと、分散秘密情報が一つでも改竄された場合、改竄された分散秘密情報を含むt+1個の分散秘密情報から復元される二つの検証情報が非常に低い確率でしか予め定められた関係を満たさないという性質を用いることで、分散秘密情報とその改竄を検出するための分散情報とを含む情報のデータサイズを小さくすることができる。
【００５５】
以下に、本実施形態の実施例を説明する。各実施例において、秘密情報のデータ集合にGF(p)を用いる。また、GF(p)は素数または素数の冪乗pに対する有限体であり、有限体上の加算を「＋」で表し、減算を「−」で表し、乗算を「＊」で表し、除算を「／」で表し、冪乗算を「^」で表す。
【００５６】
(第１実施例)
第１実施例における、分散秘密情報生成部101は、非特許文献１に記載された(k,n)閾値法を用いて秘密情報およびチェック用データを分散符号化し、秘密情報復元部201は、その(k,n)閾値法に対応する復元方法を用いて秘密情報を復元するものとする。
【００５７】
次に、第１実施例の分散情報生成装置100および復元装置200について説明する。
【００５８】
第１実施例の分散情報生成装置100には、秘密情報s、閾値k、分散情報総数nおよび想定不正者数tが入力される。本実施例では、k≧2t+1が成立しているものとする。
【００５９】
分散情報生成装置100は、秘密情報s、閾値k、分散情報総数n、および想定不正者数tが入力されると、分散秘密情報生成部101に、GF(p)上の定数項がsであるk-1次多項式をランダムに生成させる。このk-1次多項式をfs(x)と記す。
【００６０】
分散秘密情報生成部101は、fs(1), fs(2),...,fs(n) を計算し、その計算結果と入力のペア Vi=(i,vi) (i=1,2,...,n、vi=fs(i))をそれぞれ記憶装置300-iの分散秘密情報格納部301-iに格納する。
【００６１】
第１実施例における第一検証情報生成部102は、以下のように構成される。
【００６２】
第一検証情報生成部102に、分散情報総数n、想定不正者数tが入力されると、第一検証情報生成部102は、分散秘密情報生成部101の出力 Vi=(i,vi) を読み出し、q≧n＊pとなるqに対し、GF(q)上で xi = φ(i,vi) (i=1,2,...,n) を計算する。ここで、φはGF(p)→GF(q)となる任意の一体一関数とする。そして、第一検証情報生成部102は、第一検証情報e0をGF(q)からランダムに生成し、f0(0) = e0となる、GF(q)上のt次多項式f0(x)をランダムに生成し、これをA｛1,i｝=f0(xi)とする。さらに、第一検証情報生成部102は、生成したA｛1,i｝を記憶装置300-iの第一検証情報格納部302-iに格納するとともに、第一検証情報e0を第二検証情報生成部103に出力する。
【００６３】
第１実施例における第二検証情報生成部103は、以下のように構成される。
【００６４】
第二検証情報生成部103に、分散情報総数n、想定不正者数t、第一検証情報e0が入力されると、第二検証情報生成部103は、分散秘密情報生成部101の出力 Vi=(i,vi) を読み出し、第一検証情報生成部102と同様に、GF(q)上で xi = φ(i,vi) (i=1,2,...,n) を計算する。ここで、φは第一検証情報生成部102の場合と同じ一体一関数とする。そして、第二検証情報生成部103は、第一検証情報e0から第二検証情報e1をe1=e0により生成し、f1(0) = e1となる、GF(q)上のt次多項式f1(x)をランダムに生成し、これをA｛2,i｝=f1(xi)とする。さらに、第二検証情報生成部103は、生成したA｛2,i｝を記憶装置300-iの第二検証情報格納部303-iに格納する。
【００６５】
一方、第１実施例の復元装置200には、閾値k、および想定不正者数tが入力される。
【００６６】
復元装置200は、記憶装置300-i＿1, 300-i＿2,...,300-i＿mの各分散秘密情報格納部301からデータ V｛i＿j｝=(i＿j,v｛i＿j｝) (j=1,2,...,m)を読み出し、第一検証情報格納部302からデータA｛1,i＿j｝ (j=1,2,...,m)を読み出し、第二検証情報格納部303からデータA｛2,i＿j｝ (j=1,2,...,m)を読み出す。
【００６７】
次に、検証情報整合性判定部204が、｛i＿1,i＿2,...,i＿m｝について、全ての組み合わせの要素数t+1となる部分集合｛l＿1,l＿2,...,l＿｛t+1｝｝について、以下の(1)〜(4)を繰り返す。
【００６８】
(1) (l＿j,V＿｛l＿j｝,A｛1,l＿j｝,A｛2,l＿j｝) (j=1,2,...,t+1)を第一検証情報復元部202と第二検証情報復元部203とに入力する。
【００６９】
(2) t+1個のデータ (l＿j,V＿｛l＿j｝,A｛1,l＿j｝,A｛2,l＿j｝) (j=1,2,...,t+1)が入力されると、第一検証情報復元部202は、(V＿｛l＿j｝,A｛1,l＿j｝)からe0=f0(0)を復元して出力する。f0(0)を求める方法としては、(t+1)元１次の連立方程式を解く方法や、ラグランジュ補間を用いる方法などが存在する。
【００７０】
(3) 同様に、t+1個のデータ(l＿j,V＿｛l＿j｝,A｛1,l＿j｝,A｛2,l＿j｝) (j=1,2,...,t+1)が入力されると、第二検証情報復元部203は、(V＿｛l＿j｝,A｛2,l＿j｝)からe1=f1(0)を復元して出力する。f1(0)を求める方法としては、f0(0)を求める方法と同様に、(t+1)元１次の連立方程式を解く方法や、ラグランジュ補間を用いる方法などが存在する。
【００７１】
(4) 検証情報整合性判定部204は、e0=e1が成立するか否かをチェックし、e0=e1が成立する場合は、初期値 L=｛i＿1,...,i＿m｝ となる不正者リストから｛l＿1,...,l＿｛t+2｝｝の要素を全て除去する。e0=e1が成立しない場合、検証情報整合性判定部204は、Lに対する処理を行わない。
【００７２】
上記(1)〜(4)の処理を全ての要素数t+1の部分集合について行った後、検証情報整合性判定部204は、リストLを不正者リストとして出力する。
【００７３】
不正者リストLが空集合である場合、秘密情報復元部201は、(i＿j,v｛i＿j｝)から、s=fs(0)を復元し、sを秘密情報として出力する。fs(0)を求める方法としては、k元１次の連立方程式を解く方法や、ラグランジュ補間を用いる方法等が存在する。
【００７４】
復元装置200は、検証情報整合性判定部204の出力Lと秘密情報復元部201の出力のペアを装置の出力とする。
【００７５】
第１実施例の秘密情報分散システムでは、秘密情報のサイズはpであり、分散秘密情報と第一検証情報および第二検証情報の分散情報とを含む分散情報のサイズはp＊q^2であり、そのビット長は、秘密情報のビット長の３倍程度となる。これは、非特許文献４および非特許文献６で示されている方式のそれぞれの分散情報のビット長が、秘密情報の(3n-2)倍、(2k+1)倍となることと比較して、非常に小さくなっていることが確かめられる。
【００７６】
(第２実施例)
第２実施例の秘密情報分散システムは、２つの検証情報の復元法が第１実施例の一般化となっているシステムである。
【００７７】
第２実施例における、分散秘密情報生成部101は、非特許文献１に記載された(k,n)閾値法を用いて秘密情報およびチェック用データを分散符号化し、秘密情報復元部201は、その(k,n)閾値法に対応する復元方法を用いて秘密情報を復元するものとする。
【００７８】
次に、第２実施例の分散情報生成装置100および復元装置200について説明する。
【００７９】
第２実施例の分散情報生成装置100には、秘密情報s、閾値k、分散情報総数nおよび想定不正者数tが入力される。本実施例では、k≧2t+1が成立しているものとする。
【００８０】
分散情報生成装置100は、秘密情報s、閾値k、分散情報総数nおよび想定不正者数tが入力されると、分散秘密情報生成部101に、GF(p)上の定数項がsであるk-1次多項式をランダムに生成させる。このk-1次多項式をfs(x)と記す。
【００８１】
分散秘密情報生成部101は、fs(1), fs(2),...,fs(n)を計算し、その計算結果と入力のペア Vi=(i,vi) (i=1,2,...,n, vi=fs(i))をそれぞれ記憶装置300-iの分散秘密情報格納部301-iに格納する。
【００８２】
第２実施例における第一検証情報生成部102は、以下のように構成される。
【００８３】
第一検証情報生成部102に、分散情報総数nおよび想定不正者数tが入力されると、第一検証情報生成部102は、分散秘密情報生成部101の出力 Vi=(i,vi) を読み出し、q≧n＊pとなるqに対し、GF(q)上でxi = φ(i,vi) (i=1,2,...,n) を計算する。ここで、φは、GF(p)→GF(q)となる任意の一体一関数とする。そして、第一検証情報生成部102は、第一検証情報e0をGF(q)からランダムに生成し、予め定められた定数c0に対し、f0(c0) = e0 となる、GF(q)上のt次多項式f0(x)をランダムに生成し、これをA｛1,i｝=f0(xi)とする。さらに、第一検証情報生成部102は、生成したA｛1,i｝を記憶装置300-iの第一検証情報格納部302-iに格納するとともに、第一検証情報e0を第二検証情報生成部103に出力する。
【００８４】
第２実施例における第二検証情報生成部103は、以下のように構成される。
【００８５】
第二検証情報生成部103に、分散情報総数n、想定不正者数tおよび第一検証情報e0が入力されると、第二検証情報生成部103は、分散秘密情報生成部101の出力 Vi=(i,vi) を読み出し、第一検証情報生成部102と同様に、GF(q)上でxi = φ(i,vi) (i=1,2,...,n)を計算する。ここで、φは、第一検証情報生成部102の場合と同じ一体一関数とする。そして、第二検証情報生成部103は、第一検証情報e0から第二検証情報e1をe1=e0により生成し、予め定められた定数c1に対しf1(c1) = e1となる、GF(q)上のt次多項式f1(x)をランダムに生成し、これをA｛2,i｝=f1(xi)とする。さらに、第二検証情報生成部103は、A｛2,i｝を記憶装置300-iの第二検証情報格納部303-iに格納する。
【００８６】
一方、第２実施例の復元装置200には、閾値kおよび想定不正者数tが入力される。
【００８７】
復元装置200は、記憶装置300-i＿1, 300-i＿2,...,300-i＿mの各分散秘密情報格納部301からデータ V｛i＿j｝=(i＿j,v｛i＿j｝) (j=1,2,...,m)を読み出し、第一検証情報格納部302からデータA｛1,i＿j｝ (j=1,2,...,m)を読み出し、第二検証情報格納部303からデータA｛2,i＿j｝ (j=1,2,...,m)を読み出す。
【００８８】
次に、検証情報整合性判定部204が、｛i＿1,i＿2,...,i＿m｝について、全ての組み合わせの要素数t+1となる部分集合｛l＿1,l＿2,...,l＿｛t+1｝｝について、以下の(1)〜(4)を繰り返す。
【００８９】
(1) (l＿j,V＿｛l＿j｝,A｛1,l＿j｝,A｛2,l＿j｝) (j=1,2,...,t+1)を第一検証情報復元部202と第二検証情報復元部203とに入力する。
【００９０】
(2) t+1個のデータ (l＿j,V＿｛l＿j｝,A｛1,l＿j｝,A｛2,l＿j｝) (j=1,2,...,t+1)が入力されると、第一検証情報復元部202は、(V＿｛l＿j｝,A｛1,l＿j｝)からe0=f0(c0)を復元して出力する。f0(c0)を求める方法としては、(t+1)元１次の連立方程式を解く方法や、ラグランジュ補間を用いる方法などが存在する。
【００９１】
(3) 同様に、t+1個のデータ (l＿j,V＿｛l＿j｝,A｛1,l＿j｝,A｛2,l＿j｝) (j=1,2,...,t+1)が入力されると、第二検証情報復元部203は、(V＿｛l＿j｝,A｛2,l＿j｝)からe1=f1(c1)を復元して出力する。f1(c1)を求める方法としては、f0(c0)を求める方法と同様に、(t+1)元１次の連立方程式を解く方法や、ラグランジュ補間を用いる方法などが存在する。
【００９２】
(4) 検証情報整合性判定部204は、e0=e1が成立するか否かをチェックし、e0=e1が成立する場合は、初期値 L=｛i＿1,...,i＿m｝ となる不正者リストから｛l＿1,...,l＿｛t+2｝｝の要素を全て除去する。e0=e1が成立しない場合、検証情報整合性判定部204は、Lに対する処理を行わない。
【００９３】
上記(1)〜(4)の処理を全ての要素数t+1の部分集合について行った後、検証情報整合性判定部204はリストLを不正者リストとして出力する。
【００９４】
不正者リストLが空集合である場合、秘密情報復元部201は、(i＿j,v｛i＿j｝) から、s=fs(0)を復元し、sを秘密情報として出力する。fs(0)を求める方法としては、k元１次の連立方程式を解く方法や、ラグランジュ補間を用いる方法等が存在する。
【００９５】
復元装置200は、検証情報整合性判定部204の出力Lと秘密情報復元部201の出力のペアを装置の出力とする。
【００９６】
第２実施例の秘密情報分散システムにおいても、第１実施例の秘密分散システムと同様に、分散秘密情報および検証情報を含む分散情報のビット長は秘密情報のビット長の３倍程度となる。これは、非特許文献４および非特許文献６で示されている、いずれの方式と比較しても、分散情報のサイズが有意に小さくなっていることが確かめられる。
【００９７】
(第３実施例)
第３実施例の秘密情報分散システムは、第１実施例および第２実施例とは異なり、２つの検証情報e0,e1の値が一致しておらず、e0＊e1 = 1という関係を有することを特徴とするシステムである。
【００９８】
第３実施例における、分散秘密情報生成部101は、非特許文献１に記載された(k,n)閾値法を用いて秘密情報およびチェック用データを分散符号化し、秘密情報復元部201は、その(k,n)閾値法に対応する復元方法を用いて秘密情報を復元するものとする。
【００９９】
次に、第３実施例の分散情報生成装置100および復元装置200について説明する。
【０１００】
第３実施例の分散情報生成装置100には、秘密情報s、閾値k、分散情報総数nおよび想定不正者数tが入力される。本実施例では、k≧2t+1が成立しているものとする。
【０１０１】
分散情報生成装置100は、秘密情報s、閾値k、分散情報総数nおよび想定不正者数tが入力されると、分散秘密情報生成部101に、GF(p)上の定数項がsであるk-1次多項式をランダムに生成させる。このk-1次多項式をfs(x)と記す。
【０１０２】
分散秘密情報生成部101は、fs(1), fs(2),...,fs(n) を計算し、その計算結果と入力のペア Vi=(i,vi) (i=1,2,...,n, vi=fs(i))をそれぞれ記憶装置300-iの分散秘密情報格納部301-iに格納する。
【０１０３】
第３実施例における第一検証情報生成部102は、以下のように構成される。
【０１０４】
第一検証情報生成部102に、分散情報総数nおよび想定不正者数tが入力されると、第一検証情報生成部102は、分散秘密情報生成部101の出力 Vi=(i,vi) を読み出し、q≧n＊pとなるqに対し、GF(q)上でxi = φ(i,vi) (i=1,2,...,n) を計算する。ここで、φは、GF(p)→GF(q)となる任意の一体一関数とする。そして、第一検証情報生成部102は、第一検証情報e0(ただし e0≠0)をGF(q)からランダムに生成し、f0(0) = e0となる、GF(q) 上のt次多項式f0(x)をランダムに生成し、これをA｛1,i｝=f0(xi)とする。さらに、第一検証情報生成部102は、生成したA｛1,i｝を記憶装置300-iの第一検証情報格納部302-iに格納するとともに、第一検証情報e0を第二検証情報生成部103に出力する。
【０１０５】
第３実施例における第二検証情報生成部103は、以下のように構成される。
【０１０６】
第二検証情報生成部103に、分散情報総数n、想定不正者数tおよび第一検証情報e0が入力されると、第二検証情報生成部103は、分散秘密情報生成部101の出力 Vi=(i,vi) を読み出し、第一検証情報生成部102と同様に、GF(q)上でxi = φ(i,vi) (i=1,2,...,n) を計算する。ここで、φは、第一検証情報生成部102の場合と同じ一体一関数とする。そして、第二検証情報生成部103は、第一検証情報e0から第二検証情報e1をe1=1/e0 により生成し、f1(0) = e1となる、GF(q)上のt次多項式f1(x)をランダムに生成し、これをA｛2,i｝=f1(xi)とする。さらに、第二検証情報生成部103は、生成したA｛2,i｝を記憶装置300-iの第二検証情報格納部303-iに格納する。
【０１０７】
一方、第３実施例の復元装置200には、閾値kおよび想定不正者数tが入力される。
【０１０８】
復元装置200は、記憶装置300-i＿1, 300-i＿2,...,300-i＿mの各分散秘密情報格納部301からデータ V｛i＿j｝=(i＿j,v｛i＿j｝) (j=1,2,...,m)を読み出し、第一検証情報格納部302からデータA｛1,i＿j｝ (j=1,2,...,m)を読み出し、第二検証情報格納部303からデータA｛2,i＿j｝ (j=1,2,...,m)を読み出す。
【０１０９】
次に、検証情報整合性判定部204が、｛i＿1,i＿2,...,i＿m｝について、全ての組み合わせの要素数t+1となる部分集合｛l＿1,l＿2,...,l＿｛t+1｝｝について、以下の(1)〜(4)を繰り返す。
【０１１０】
(1) (l＿j,V＿｛l＿j｝,A｛1,l＿j｝,A｛2,l＿j｝) (j=1,2,...,t+1)を第一検証情報復元部202と第二検証情報復元部203とに入力する。
【０１１１】
(2) t+1個のデータ (l＿j,V＿｛l＿j｝,A｛1,l＿j｝,A｛2,l＿j｝) (j=1,2,...,t+1)が入力されると、第一検証情報復元部202は、(V＿｛l＿j｝,A｛1,l＿j｝)からe0=f0(0)を復元して出力する。f0(0)を求める方法としては、(t+1)元１次の連立方程式を解く方法や、ラグランジュ補間を用いる方法などが存在する。
【０１１２】
(3) 同様に、t+1個のデータ (l＿j,V＿｛l＿j｝,A｛1,l＿j｝,A｛2,l＿j｝) (j=1,2,...,t+1)が入力されると、第二検証情報復元部203は、(V＿｛l＿j｝,A｛2,l＿j｝)からe1=f1(0)を復元して出力する。f1(0)を求める方法としては、f0(0)を求める方法と同様に、(t+1)元１次の連立方程式を解く方法や、ラグランジュ補間を用いる方法などが存在する。
【０１１３】
(4) 検証情報整合性判定部204は、e0＊e1=1が成立するか否かをチェックし、e0＊e1=1が成立する場合は、初期値 L=｛i＿1,...,i＿m｝ となる不正者リストから｛l＿1,...,l＿｛t+2｝｝ の要素を全て除去する。e0＊e1=1が成立しない場合、検証情報整合性判定部204は、Lに対する処理を行わない。
【０１１４】
上記 (1)〜(4) の処理を全ての要素数t+1の部分集合について行った後、検証情報整合性判定部204はリストLを不正者リストとして出力する。
【０１１５】
不正者リストLが空集合である場合、秘密情報復元部201は、(i＿j,v｛i＿j｝)から、s=fs(0)を復元し、sを秘密情報として出力する。fs(0)を求める方法としては、k元１次の連立方程式を解く方法や、ラグランジュ補間を用いる方法等が存在する。
【０１１６】
復元装置200は、検証情報整合性判定部204の出力Lと秘密情報復元部201の出力のペアを装置の出力とする。
【０１１７】
第３実施例の秘密情報分散システムにおいても、第１実施例および第２実施例の秘密分散システムと同様に、分散秘密情報および検証情報を含む分散情報のビット長は秘密情報のビット長の３倍程度となる。これは、非特許文献４および非特許文献６で示されている、いずれの方式と比較しても、分散情報のサイズが有意に小さくなっていることが確かめられる。
【符号の説明】
【０１１８】
１００    分散情報生成装置
１０１    分散秘密情報生成部
１０２    第一検証情報生成部
１０３    第二検証情報生成部
２００    復元装置
２０１    秘密情報復元部
２０２    第一検証情報復元部
２０３    第二検証情報復元部
２０４    検証情報整合性判定部
３００−１〜３００−ｎ    記憶装置
３０１−１〜３０１−ｎ    分散秘密情報格納部
３０２−１〜３０２−ｎ    第一検証情報格納部
３０３−１〜３０３−ｎ    第二検証情報格納部
【図１】
0005640624.tif 000002
【図２】
0005640624.tif 000003
【図３】
0005640624.tif 000004
【図４】
0005640624.tif 000005
【図５】
0005640624.tif 000006