(57)【要約】  要素データ生成装置は、複数のデータよりなるベクトルをそれぞれ暗号化して、暗号文からなるベクトルを生成して要素データとして出力する。データベース生成システムは、第１の複数の分散装置を有し、全ての要素データの列を前記データベースとして出力する。データベース提示システムは、第２の複数の分散装置を有し、参照する項目が指定された参照項目に基づいて、データベースより参照するデータの列を複数個生成し、データの列を全ての第２の分散装置により各要素の順番入れ替えを行い、データ列の要素の順番の入れ替えが全てのデータ列に対して同じとなるようにする。
2010053036.tif 000002
【特許請求の範囲】
【請求項１】
要素データを生成する要素データ生成装置と、
前記要素データを複数集めてデータベースを生成するデータベース生成システムと、
前記データベースから参照するデータを出力するデータベース提示システムとを備え、
前記要素データ生成装置は、複数のデータよりなるベクトルをそれぞれ暗号化して、暗号文からなるベクトルを生成して前記要素データとして出力し、
前記データベース生成システムは、第１の複数の分散装置を有し、全ての要素データの列を前記データベースとして出力し、
前記データベース提示システムは、第２の複数の分散装置を有し、参照する項目が指定された参照項目に基づいて、前記データベースより参照するデータの列を複数個生成し、前記データの列を全ての前記第２の分散装置により各要素の順番入れ替えを行い、データ列の要素の順番の入れ替えが全てのデータ列に対して同じであるデータ参照システム。
【請求項２】
前記要素データ生成装置は、前記暗号文からなるベクトルに対する署名を生成し、前記暗号文からなるベクトルと、前記署名と、を要素データとして出力し、
前記署名は、署名者の識別子の暗号文と、署名者に認められた属性の一部の集合とを含む、請求項１記載のデータ参照システム。
【請求項３】
前記データベース生成システムは、各前記要素データに含まれる署名を検証する検証手段を有し、
複数の前記要素データに対して各要素データの暗号文の一部を全ての前記第１の分散装置によりそれぞれ決定的な関数で変換したデータの暗号文に変換して、全ての要素データの列を前記データベースとして出力する、請求項２記載のデータ参照システム。
【請求項４】
前記データベース提示システムは、前記各要素データの暗号文の一部に対して、全ての前記分散装置により列を構成する全ての要素をそれぞれ変換するべき乗化するべき乗化手段を有し、
前記べき乗化手段によりべき乗化されたデータ列、あるいは他の前記データ列における参照データを全ての前記第２の分散装置により要素の順番入れ替えを行う、請求項３記載のデータ参照システム。
【請求項５】
前記各要素データの暗号文の一部は、識別子に関連するデータの列である、請求項４記載のデータ参照システム。
【請求項６】
複数のデータベース提示装置を備えるデータベース提示分散システムであって、
前記データベース提示装置は、他のデータベース提示装置と通信する通信手段を有し、
データベースと、参照項目と、暗号の分散秘密鍵と、順番の入れ替え方と、前記他のデータベース提示装置の公開鍵とが入力され、
参照項目に基づいて、前記データベースより参照する暗号文の列を複数個生成し、一部の暗号文の列に対して、前記他のデータベース提示装置と通信することで、全ての暗号文を復号結果が同じ数でべき乗したものとなる暗号文に変換するべき乗化手段を有し、
べき乗化手段によりべき乗化処理された暗号文の列、及び他の前記暗号文における参照データの列を前記他のデータベース提示装置と通信することで、自身、及び前記他のデータベース提示装置でミックスネットを構成し、全ての暗号文の列の順番を全て同じ順番で入れ替えて出力することを特徴とするデータベース提示分散システム。
【請求項７】
要素データ生成装置により、複数のデータよりなるベクトルをそれぞれ暗号化して、
暗号文からなるベクトルを生成して要素データとして出力し、
複数の第１の分散装置を有するデータベース生成システムにより、全ての要素データの列をデータベースとして出力し、
複数の第２の分散装置を有するデータベース提示システムは、参照する項目が指定された参照項目に基づいて、前記データベースより参照するデータの列を複数個生成し、
前記データの列を全ての前記第２の分散装置により各要素の順番入れ替えを行い、
データ列の要素の順番の入れ替えが全てのデータ列に対して同じであることを特徴とするデータ参照方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ参照システムに関し、更に詳しくは、データベースの各データが個人に属するなどデータに特に秘密にしたいラベルが付されているデータベースを参照するデータ参照システムに関する。本発明は、更に、データベース提示分散システム、及びデータ参照方法に関する。
【背景技術】
【０００２】
データベースには、データベース内の各データが個人に属するため、特に秘密にしたいラベルがデータに付されているデータベースがある。例えば非特許文献１には、電子健康情報の仮名化の技術が記載されている。また、例えば非特許文献２、及び非特許文献３には、匿名化のための暗号技術でシャッフルと呼ばれる技術が記載されている。【０００３】
非特許文献１に記載の技術について、図１０を参照して説明する。仮名化を行う匿名化システム１００の権限者は、鍵１０１を保持し、匿名化システム１００には、共通鍵暗号方式の暗号化関数１０２が準備されている。【０００４】
臨床システム１０３から名称１０４が匿名化システム１００に渡されると、匿名化システム１００の権限者は、名称１０４を暗号化関数１０２に入力する。暗号化関数１０２は、その仮名化用の鍵として、匿名化システム１００の権限者が保持する鍵１０１を利用する。暗号化関数１０２の出力が仮名１０５であり、研究システム１０６に渡される。【０００５】
非特許文献２に記載の技術について、図１１を参照して詳細に説明する。この技術では、ミックス装置２００に複数のElGamal暗号文２０１が入力される。入力される暗号文の数をＱとする。Ｑ個の暗号文は列をなしており、順番が付けられている。【０００６】
ミックス装置２００は、Ｑ個の暗号文のランダムな順番の入れ替えを行い、さらに各暗号文は、再暗号化されて、新たなElGamal暗号文２０２として出力される。再暗号化とは、ElGamal暗号文を、復号結果が変らないようにしつつも、暗号化で用いる乱数を替えることで、暗号文としては異なるものに変換することを意味する。【０００７】
入力されたＱ個の暗号文からなるElGamal暗号文２０１の列と、出力したＱ個の暗号文からなるElGamal暗号文２０２の列は、相互に対応関係にある。つまり、前者の列の各要素の順番を入れ替え再暗号化したものが後者の列となる。この対応関係は、ElGamal暗号を復号できる装置、あるいは順番の入れ替えと再暗号化を行ったミックス装置２００のみが知る。【０００８】
ミックス装置２００は、入力されたｎ個の暗号文と、出力したｎ個の暗号文の間に一対一の対応関係があることを、ゼロ知識証明２０３を用い、この対応関係を隠して証明する。非特許文献２の技術を用いると、ゼロ知識証明を用いて証明したことにより、（１）入出力の対応関係を隠すことと、（２）正当な入出力の対応関係が存在することを署名すること、が可能となる。【０００９】
上記で説明したミックス装置２００を複数個用意すると、ミックスネットと呼ばれるシステムが構成できることが知られている。このミックスネットについて、図１２を参照して詳細に説明する。ｑを素数とし、Ｇを離散対数問題が難しいとされる巡回群で、その位数が素数ｑであるものとする。ｇをＧの生成子とする。ElGamal暗号文を検証可能なミックスネット２０５を構成するミックス装置はＨ個あり、1,...,Ｈの各ｉに関して、ｉ番目のミックス装置は、y[i]=gx[i]なる暗号方式の分散秘密鍵x[i]∈Z/qZを所持しているとする。ここで、y[i]は公開されており、yは、以下の式で表される。
2010053036.tif 000003
【００１０】
ここで、公開鍵(g,y)により、m∈GのElGamal暗号文を生成するとは、ランダムにr∈Z/qZを選び、(a,b)=(gr、myr)を生成することである。  【００１１】
ElGamal暗号文Ｑ個の列２０４が、１番目のミックス装置に与えられると、i=1からHまで順番に、ｉ番目の装置は、それぞれ、ｉ−１番目のミックス装置にもらった暗号文の列の順番をランダムに入れ替え、それぞれを独立に再暗号化してｉ＋１番目のミックス装置に渡す。【００１２】
さらに、ｉ番目のミックス装置は、ｉ＋１番目に渡した暗号文の列がｉ−１番目のミックス装置から受け取った暗号文の列の順番を入れ替えて、それぞれを再暗号化しただけであることのゼロ知識証明を行う。【００１３】
ここで、各ElGamal暗号文は、公開鍵(g、y)により暗号化されたものである。再暗号化とは、例えばElGamal暗号文(a,b)が与えられたら、ランダムなs∈Z/qZを用いて、(ags,bys)と変換することである。なお、１番目のミックス装置は、ミックスネットに入力されたElGamal暗号文Ｑ個の列を用いる。Ｈ番目のミックス装置は、自身が生成した暗号文列を、ミックスネットの次の処理へと渡す。【００１４】
最後にミックスネットは、Ｈ番目のミックス装置より渡された暗号文の列を、Ｈ個ミックス装置が協力して平文２０６に復号する。このときの復号化は、各暗号文をＨ個のミックス装置が協力して復号する。例えばElGamal暗号文(a,b)が与えられると、各ｉ番目のミックス装置はa'[i]=ax[i]を生成する。(a,b)の復号結果は、b/Πa'[i]である。各ミックス装置は、a'[i]=ax[i]、y[i]=gx[i]を満すx[i]が存在することをゼロ知識証明する。        【００１５】
上記のように各ミックス装置が行った二つのゼロ知識証明、すなわち、順番の入れ替えと再暗号化のゼロ知識証明と、復号のゼロ知識証明と、を集めると、ミックスネットが全体として、入力された暗号文の順番を入れ替え、これらを復号したものを出力したことのゼロ知識証明２０７となる。【００１６】
非特許文献３に記載の技術について、図１３を参照して詳細に説明する。この技術は、「ハイブリッド暗号文の検証可能ミックスネット」を実現するものである。非特許文献３の技術でも、非特許文献２の技術と同様に、複数のミックス装置が存在する。ここで、ミックス装置の個数をＨとし、それぞれのミックス装置に１からＨまでの番号を順番に割り振り、番号ｉが振られたミックス装置を、ｉ番目のミックス装置と呼ぶ。【００１７】
非特許文献３におけるハイブリッド暗号文３０１は、非特許文献２の技術で使われる暗号文とは異なり、ElGamal暗号文ではなく、任意の長さの平文を暗号化できるようになっている。また、１番目のミックス装置に渡される暗号文は、Ｑ回に亘って部分復号されると完全に復号され、平文となる様に暗号文が生成されている。【００１８】
すなわち、ｑを素数、Ｇを離散対数問題が難しいとされる巡回群で、その位数が素数ｑであるものとする。ｇをＧの生成子とする。ミックスネットを構成するミックス装置はＨ個で、１,...,Ｈの各ｉに関して、ｉ番目のミックス装置は、y[i]=gx[i]なる暗号方式の分散秘密鍵x[i]∈Z/qZを所持している。y[i]は、公開されている。【００１９】
ここで、暗号文の作り方について説明する。文字列ｍのハイブリッド暗号文は、次のようにして生成する。ElGamal暗号文のシステムパラメタ─ｇとElGamal暗号方式の公開鍵(y[i]∈G)i=1,...,Hが与えられたとする。senc、sdecを共通鍵暗号方式の暗号化関数と復号関数とし、Ｋを鍵の空間とする。χ∈Kに関するｍ暗号化を、senc(χ,m)、その復号をsdec(χ,senc(χ,n))=mとする。ψをＫからＧへの一対一への関数で、逆も計算可能であるとする。【００２０】
まず、各i=1,...,Hに関してランダムに選んだχ[i]∈K、r[i]∈Z/qZを準備する。次に、m[H]=mとしてi=Hから1まで下降順にm[i-1]=(gr[i],ψ(χ[i])y[i]r[i],senc(χ[i],m[i]))を生成し、m[0]を暗号文とする。  【００２１】
続いて、ハイブリッド暗号のミックスネット処理について詳細に説明する。ハイブリッド暗号文の検証可能ミックスネット３００は、次のように、Ｈ個のミックス装置が協力して処理するシステムである。ハイブリッド暗号文Ｑ個の列３０１が、１番目のミックス装置に与えられると、i=1からHまで順番に、ｉ番目のミックス装置は、それぞれ、ｉ−１番目のミックス装置にもらった暗号文の列の順番をランダムに入れ替え、それぞれを部分的に復号してＱ個の暗号文の組を作り、ｉ＋１番目のミックス装置に渡す。【００２２】
さらに、ｉ番目のミックス装置は、ｉ＋１番目に渡した暗号文の列はｉ−１番目のミックス装置から受け取った暗号文の列の順番を入れ替えて、それぞれを部分復号しただけであることのゼロ知識証明を行う。ここで、１番目のミックス装置は、非特許文献２に記載の技術と同様に、直接Ｑ個の暗号文が入力される。Ｈ番目のミックス装置は、復号された平文の列３０２を出力する。ゼロ知識証明全体がハイブリッドミックスネットの正当性証明３０３となる。【００２３】
ここで、ハイブリッド暗号文は、公開鍵(g,(y[i])i=1,...,H)により暗号化されたものである。部分復号とは、例えば、ｉ番目のミックス装置がm[i-1]=(a[i],b[i],c[i])=(gr[i],ψ(χ[i])y[i]r[i],senc(χ[i],m[i]))が与えられたら、ψ[i]=b[i]/a[i]x[i]、m[i]=sdec(ψ[i],c[i])と、を生成することである。
【先行技術文献】
【非特許文献】
【００２４】
【非特許文献１】Alain Lemay、Jean-Marc Lina1、Pseudonymization of Radiology Data for Research Purposes、Journal of Digital Imaging、Volume 20、Number 3、(2007)、p.284-295
【非特許文献２】Jun Furukawa、Efficient and Verifiable Shuffling and Shuffle-Decryption、IEICE Transactions 88-A(1)、(2005)、p.172-188
【非特許文献３】Jun Furukawa、Kazue Sako、An Efficient Publicly Verifiable Mix-Net for Long Inputs、IEICE Transactions 90-A(1)、(2007)、p.113-127
【発明の開示】
【発明が解決しようとする課題】
【００２５】
非特許文献１に記載の技術は、個人の電子健康情報に付随する名前を共通鍵暗号の暗号化関数等で変換することによって仮名化する。しかし、鍵が一ヵ所で一時に使われるため、暗号化関数に入力する鍵が分かると、仮名から本名が分かってしまう。鍵が一ヵ所で使われると、その使われる場所をその時に操作する権限のあるものは、この鍵を簡単に入手することができる。鍵が一人の権限者に完全に知られたものとなると、この権限者が鍵を故意、あるいは事故で漏洩することを完全に防ぐことは難しい。【００２６】
一方、鍵が一ヵ所で一時に使われないとはどのような場合であるかというと、鍵が分散されて使われる場合である。すなわち、これは、鍵データが分散して所持されており、これら分散された鍵データを集積しないと鍵を復元できず、鍵を用いた処理も各分散された鍵データを個別に用いて計算し、その結果を別途集めると、単一の鍵を用いた処理と同じ結果が得られる場合である。この様な分散した処理は、共通鍵暗号の暗号化関数では難しい問題がある。【００２７】
また、鍵が漏洩しないとしても、本名とそれを変換してできた仮名を同時に知るものが存在すると、仮名に関して本名との対応を知ることができる。すなわち、仮名化処理において、単一の本名が入力され、単一の仮名が出力されるという処理があると、これは対応関係が漏洩する可能性が高い処理であるといえる。【００２８】
非特許文献1におけるもう一つの問題点は、各個人電子健康情報が仮名化された集団電子健康情報の正当性が確認できないことである。実際の個人の電子健康情報と対応しない集団電子健康情報を偽造したら、特定の医薬品の有効性などを偽わることができる。これを防ぐためには、個人の電子健康情報と対応した集団電子健康情報が生成されていることが確認できなければならない。しかしながら、非特許文献1における技術では、個人の電子健康情報を隠したままこれを行うことは難しい。【００２９】
非特許文献1における技術は、電子健康情報に関するものであるが、同種の技術は、健康情報以外のデータベースにも適用され得る。例えば、犯罪情報のデータベース、成績のデータベース、クレジットカードのブラックリストのデータベース等、各データが個人と結び付けられたものは多い。さらには、各データが結び付けられ、対象が個人でない場合として、企業名に関するデータ、製品に関するデータ等幅広い応用対象が考えられる。しかし、これらデータベースは、何れにしても上記問題を抱えることになる。【００３０】
非特許文献２における技術は、入力された暗号文の列と出力された暗号文の列の各要素の対応関係を分からなくする技術である。この技術を用いたミックスネットや非特許文献３の技術によれば、全てのミックス装置の管理者が共謀しない限り、入力と最終的な出力の対応関係は誰にも分からない。【００３１】
しかしながら、この方法を電子健康情報のデータベース等に応用した場合、入力される個人の電子健康情報の正当性を保証することは難しい。例えば、ある電子健康情報を入力とするとき、これが誰の電子健康情報かを明らかにする必要がある。【００３２】
なぜなら、偽りの人物の電子健康情報を集めても、正しい集団電子健康情報が生成されないからである。この電子健康情報自体は、暗号化することにより、集団電子健康情報の一部となるまで、情報を隠すことは可能である。しかし、この情報が正しく作られたことを証明するには医療機関等の保証が必要である。もし、医療機関がこのデータに署名を打つと、個人がどの医療機関で治療を受けたかが分かってしまうといった問題が発生する。【００３３】
そこで本発明は、上記問題点に鑑みてなされたもので、各データの生成主が、データが正当であることを証明可能であり、データベースがこの正当であることを証明されたデータから生成されていることが証明可能であり、かつ、効率的に参照可能なデータ参照システムを提供することを目的とする。本発明は、更に、このようなデータベースを参照するデータ参照方法、及び、そのデータベースを分散して提示可能なデータベース提示分散システムを提供することを目的とする。
【課題を解決するための手段】
【００３４】
本発明は、要素データを生成する要素データ生成装置と、要素データを複数集めてデータベースを生成するデータベース生成システムと、データベースから参照するデータを出力するデータベース提示システムと、を備え、要素データ生成装置は、複数のデータよりなるベクトルをそれぞれ暗号化して、暗号文からなるベクトルを生成して要素データとして出力し、データベース生成システムは、第１の複数の分散装置を有し、全ての要素データの列を前記データベースとして出力し、データベース提示システムは、第２の複数の分散装置を有し、参照する項目が指定された参照項目に基づいて、データベースより参照するデータの列を複数個生成し、データの列を全ての第２の分散装置により各要素の順番入れ替えを行い、データ列の要素の順番の入れ替えが全てのデータ列に対して同じであるデータ参照システムを提供する。【００３５】
また、本発明は、複数のデータベース提示装置を備えるデータベース提示分散システムであって、データベース提示装置は、他のデータベース提示装置と通信する通信手段を有し、データベースと、参照項目と、暗号の分散秘密鍵と、順番の入れ替え方と、他のデータベース提示装置の公開鍵とが入力され、参照項目に基づいて、データベースより参照する暗号文の列を複数個生成し、一部の暗号文の列に対して、他のデータベース提示装置と通信することで、全ての暗号文を復号結果が同じ数でべき乗したものとなる暗号文に変換するべき乗化手段を有し、べき乗化手段によりべき乗化処理された暗号文の列、及び他の暗号文の列における参照データを他のデータベース提示装置と通信することで、自身、及び他のデータベース提示装置でミックスネットを構成し、全ての暗号文の列の順番を全て同じ順番で入れ替えて出力するデータベース提示分散システムを提供する。【００３６】
更に、本発明は、要素データ生成装置により、複数のデータよりなるベクトルをそれぞれ暗号化して、暗号文からなるベクトルを生成して要素データとして出力し、複数の第１の分散装置を有するデータベース生成システムにより、全ての要素データの列をデータベースとして出力し、複数の第２の分散装置を有するデータベース提示システムは、参照する項目が指定された参照項目に基づいて、データベースより参照するデータの列を複数個生成し、データの列を全ての第２の分散装置により各要素の順番入れ替えを行い、データ列の要素の順番の入れ替えが全てのデータ列に対して同じであるデータ参照方法を提供する。
【発明の効果】
【００３７】
本発明のデータベース参照システムは、データを集めてデータベースを構成し、データベースを解析するためデータの一部を参照するシステムであり、この参照過程においてデータに付けられた識別子を分散して仮名化し、かつこの仮名化されたデータと元のデータの対応を分からなくする。このため、各データの生成主が、データが正当であることを証明可能であり、データベースが、正当であることを証明されたデータから生成されていることが証明可能であり、かつ適切に参照可能となる。また、本発明のデータ参照方法、及び、データベース提示分散システムは、上記データベース参照システムで提供されるデータベースを適切に取り扱うことが出来る。【００３８】
本発明の上記、及び、他の目的、特徴及び利益は、図面を参照する以下の説明により明らかになる。
【図面の簡単な説明】
【００３９】
【図１】本発明の実施形態に係る属性選択開示型署名装置の説明図である。
【図２】本発明の実施形態に係る分散仮名化システムの説明図である。
【図３】本発明の実施形態に係るデータ参照システムの構成図である。
【図４】本発明の実施形態に係る要素データ生成装置の説明図である。
【図５】要素データ生成装置のフローチャートである。
【図６】本発明の実施形態に係るデータベース生成システムの説明図である。
【図７】データベース生成システムのフローチャートである。
【図８】本発明の実施形態に係るデータベース提示システムの説明図である。
【図９】データベース提示システムのフローチャートである。
【図１０】非特許文献１に記載のシステムのブロック図である。
【図１１】非特許文献２に記載のシステムのブロック図である。
【図１２】非特許文献２に記載のシステムのブロック図である。
【図１３】非特許文献３に記載のシステムのブロック図である。
【発明を実施するための形態】
【００４０】
本発明の最小構成のデータ参照システムは、要素データを生成する要素データ生成装置と、要素データを複数集めてデータベースを生成するデータベース生成システムと、データベースから参照するデータを出力するデータベース提示システムと、を備えるデータベース参照システムであって、要素データ生成装置は、複数のデータよりなるベクトルをそれぞれ暗号化して、暗号文からなるベクトルを生成して要素データとして出力し、データベース生成システムは、第１の複数の分散装置を有し、全ての要素データの列を前記データベースとして出力し、データベース提示システムは、第２の複数の分散装置を有し、参照する項目が指定された参照項目に基づいて、データベースより参照するデータの列を複数個生成し、データの列を全ての第２の分散装置により各要素の順番入れ替えを行い、データ列の要素の順番の入れ替えが全てのデータ列に対して同じである。
【００４１】
また、本発明の最小構成のデータベース提示分散システムは、複数のデータベース提示装置を備えるデータベース提示分散システムであって、データベース提示装置は、他のデータベース提示装置と通信する通信手段を有し、データベースと、参照項目と、暗号の分散秘密鍵と、順番の入れ替え方と、他のデータベース提示装置の公開鍵とが入力され、参照項目に基づいて、データベースより参照する暗号文の列を複数個生成し、一部の暗号文の列に対して、他のデータベース提示装置と通信することで、全ての暗号文を復号結果が同じ数でべき乗したものとなる暗号文に変換するべき乗化手段を有し、べき乗化手段によりべき乗化処理された暗号文の列、及び他の暗号文の列における参照データを他のデータベース提示装置と通信することで、自身、及び他のデータベース提示装置でミックスネットを構成し、全ての暗号文の列の順番を全て同じ順番で入れ替えて出力する。
【００４２】
更に、本発明の最小構成のデータ参照方法は、要素データ生成装置により、複数のデータよりなるベクトルをそれぞれ暗号化して、暗号文からなるベクトルを生成して要素データとして出力し、複数の第１の分散装置を有するデータベース生成システムにより、全ての要素データの列をデータベースとして出力し、複数の第２の分散装置を有するデータベース提示システムは、参照する項目が指定された参照項目に基づいて、データベースより参照するデータの列を複数個生成し、データの列を全ての第２の分散装置により各要素の順番入れ替えを行い、データ列の要素の順番の入れ替えが全てのデータ列に対して同じである。
【００４３】
上記構成のデータベース参照システムは、データを集めてデータベースを構成し、データベースを解析するためデータの一部を参照するシステムであり、この参照過程においてデータに付けられた識別子を分散して仮名化し、かつこの仮名化されたデータと元のデータの対応を分からなくする。このため、各データの生成主が、データが正当であることを証明可能であり、データベースが、正当であることを証明されたデータから生成されていることが証明可能であり、かつ効率的に参照可能となる。また、本発明のデータ参照方法、及び、データベース提示分散システムは、上記データベース参照システムで提供されるデータベースを適切に取り扱うことが出来る。
【００４４】
以下、図面を参照し、本発明の実施形態について説明する。まず、ハイブリッド暗号の形を少し変え、正しく復号したことのゼロ知識証明をする方法について詳細に説明する。
【００４５】
電子署名を利用するときには一般的に、署名者は、文書にある秘密鍵を用いて署名を生成し、添付する。この秘密鍵に対応する公開鍵には、認証局による公開鍵証明書が発行されている。
【００４６】
公開鍵証明書は、署名者の公開鍵と署名者の属性等に対する認証局の署名がうたれている。文書に対する署名者の署名を検証する検証処理は、（１）署名を公開鍵で検証する、（２）公開鍵証明書の内容を見て、署名者を確認する。（３）公開鍵証明書に打たれている認証局の署名を検証する、処理を含む。
【００４７】
上記署名の検証処理において、署名を検証するときには公開鍵証明書を検証者に見せる必要が有り、公開鍵証明書に記述されている署名者の属性が全て検証者に分かってしまう。署名により文書の正当性を示すときには、署名者の全ての属性を明らかにする必要は無い場合も多く、この様な公開鍵証明書の全面的な開示は、個人情報の漏洩となってしまう場合もある。
【００４８】
そこで、本実施形態における署名方法では、署名者は署名を生成するときに、公開鍵証明書の開示する属性を選んで署名することができ、該署名からは、署名者が署名生成時に開示された属性を持つ公開鍵証明書に対応する秘密鍵で署名したという事実以外は分からない。この様な署名を属性選択開示型署名と呼ぶこととする。
【００４９】
以下では、より具体的に本実施形態における「署名システム」について図１を参照して説明する。まず、属性選択開示型署名方式における、認証局公開鍵４０１、認証局の秘密鍵、追跡情報、追跡用秘密鍵、追跡用公開鍵４０２について説明する。
【００５０】
ｑは素数とする。Ｇ１、Ｇ２、Ｇを位数ｑの群で、Ｇ１×Ｇ１からＧ２への双線形写像ｅが存在する。ｇ1、ｇ2、ｇをＧ１、Ｇ２、Ｇの生成元とする。Ｇは、離散対数問題が難しいものとする。
【００５１】
Hashqを、任意の文字列を体(Z/qZ)へと写像するハッシュ関数とし、自然数Ｎを公開鍵証明書４１２の項目数とする。  
【００５２】
h,h[1],...,h[N],fを無作為に選ばれたＧ１の元とする。(h[1],...,h[n])の各h[i]は、ｉ番目の属性に関連づけられている。
【００５３】
γを無作為に選ばれた体Z/qZの元とし、Y=g2γとする。また、ｓを無作為に選ばれた体Z/qZ上の点とし、T=gsとする。
【００５４】
認証局秘密鍵を、γとする。認証局公開鍵４０１を、ｑと、Ｇ１、Ｇ２、Ｇ、ｅ、ハッシュ関数Hashqの記述と、g1、g2、g、N、h[0]、h[1],...,h[N]、f、Yとする。また、追跡用秘密鍵を、sとする。追跡用公開鍵４０２を、Ｔとする。  
【００５５】
認証局の発行する公開鍵証明書４１２と、これに対応する署名者秘密鍵４０３、及び属性値４０４について説明する。次の関係を満たす、A∈G1、b、a、a[1],...,a[n]、z∈Z/qZを、公開鍵被発行者と協力して生成する。
2010053036.tif 000004
【００５６】
公開鍵証明書４１２を(A,a,b)とし、追跡情報をＢ、属性値４０４を(a[1],...,a[n])、署名者秘密鍵４０３を(z)とする。
【００５７】
メッセージ４０６であるmに対するもので、開示属性集合４０５であるO⊂[1,...,N]に属する属性値のみを公開した署名４１１は、属性選択開示型署名装置４００によって下記のように生成される。
【００５８】
ランダムにt∈Z/qZを選び、enc(z)=(gt、gzTt)を生成する。(a[i])i ∈ Oと、enc(z)、及び、以下の式を満たすt、(a[i])i∈[1,...,N]＼o、A、z、b、bの知識の非対話的ゼロ知識証明prf、開示属性集合４１０であるO、開示属性値４０９である(a[i])i∈O 、を署名とする。
2010053036.tif 000005
【００５９】
但し、非対話的零知識証明においてハッシュ値を計算するときに、引数にmをいれる。ここでenc(z)を識別子暗号部４０７と、非対話的ゼロ知識証明prfを証明部４０８と呼び、署名の検証は、prfの正当性の確認を持って行われる。
【００６０】
次に、名称の暗号文を仮名の暗号文に変換する「暗号文中の識別子の分散仮名化システム」について図２を参照して詳細に説明する。ｑを素数、Ｇを離散対数問題が難しいとされる巡回群で、その位数が素数ｑであるものとし、ｇ、ｈをＧの生成子とする。
【００６１】
暗号文中の識別子の分散仮名化のシステム５００は、複数の分散仮名化装置により構成される。ここでは、分散仮名化装置は、Ｈ個あり、1,...,Hの各ｉに関して、ｉ番目の分散仮名化装置は、y[i]=gx[i]なる暗号方式の分散秘密鍵x[i]∈Z/qZを所持している。なお、y[i]は公開されており、yは、以下の式で表される。    
2010053036.tif 000006
【００６２】
senc、sdecを共通鍵暗号方式の暗号化関数と復号関数で、Ｋを鍵の空間とする。χ∈Kに関するm暗号化を、senc(χ,m)、その復号をsdec(χ,senc(χ,n))=mとする。ψをＫからＧへの一対一の関数で、逆も計算可能であるとし、識別子の空間をZ/qZとする。
【００６３】
分散仮名化装置は、初期設定を最初に行う。各i=1,...,Hに関して、ｉ番目の分散仮名化装置は、仮名化の分散秘密σ[i]，τ[i]∈Z/qZをランダムに生成し、w[i]=gσ[i]fτ[i]を生成する。分散仮名化のシステム５００は、    
2010053036.tif 000007
として、wを仮名乱数のコミットメント５０２として公開する。
【００６４】
次に、識別子u∈Z/qZの暗号文５０３の生成方法について説明する。各i=1,...,Hに関してランダムに選んだχ[i]∈K、r[i]∈ Z/qZを準備し、ランダムにr∈Z/qZを選ぶ。各i=1,...,Hに関してランダムに、以下の式を満たすようにランダムに選んだu[i]、v[i]∈Z/qZを準備する。
2010053036.tif 000008
【００６５】
i=1からＨに関して、c[i]=(gu[i]hv[i],gr[i],ψ(χ[i])y[i]r[i],senc(χ[i],u[i],v[i]))を生成し、c=(guhv)を生成する。(c,c[1],c[2],...,c[H])が識別子uの暗号文である。続いて、暗号文中の識別子の分散仮名化方法を説明する。
【００６６】
各ｉ番目の分散仮名化装置には、仮名化の分散秘密鍵σ[i]、τ[i]と、暗号方式の分散秘密鍵x[i]で構成される鍵５０１のデータが入力される。分散仮名化システム５００には、識別子暗号文５０３(c,c[1],c[2],...,c[H])が入力される。ここで、c[i]=(c[i1],c[i2],c[i3],c[i4])とする。
【００６７】
全ての分散仮名化装置は、以下の確認を行う。
2010053036.tif 000009
【００６８】
ｉ番目の分散仮名化装置は、以下を生成する。
2010053036.tif 000010
ｉ番目の分散仮名化装置は、c[i1]=gu'[i]hv'[i]を確認する。全ての分散仮名化装置は、互いに通信することでマルチパーティ計算を行う。また、各iで、ランダムにτ'[i]∈Z/qZを選び、z[i]=(z[i1],z[i2])=(gτ'[i],gρ[i]yτ'[i])を生成する。各ｉ番目の分散装置は、以下を満たすρ[i]を得る。    
2010053036.tif 000011
2010053036.tif 000012
全ての分散仮名化装置がそれぞれ自身の計算の正当性をゼロ知識証明することで、zがg1/(u+σ)のElGamal暗号文である事が証明される。なお、本分散仮名化システムにおいては、g1/(u+σ)を乱数σによるuの仮名と呼ぶ。得られた仮名の暗号文５０４であるz、及び証明文５０５を出力する。
【００６９】
ここでは、識別子の暗号文を対応する仮名の暗号文に変換する方法を述べたが、識別子そのものから対応する仮名の暗号文を生成することもできる。これは、識別子そのものがあれば、これを誰でも暗号化できることから明らかである。
【００７０】
ところで、医療機関の署名から医療機関が特定される問題は、上記記載の「署名システム」の技術を用いれば解決できる。例えば、ある種の認可を受けた医療機関であるという属性のみを公開して署名を生成すれば良い。しかし、これだけでは生成された集団電子健康情報に医療機関の情報が残らず、医療機関情報を用いた解析ができなくなる問題が残る。その他の問題としては、集団電子健康情報が血縁情報を用いて解析できると有益であるが、これを行う手段が備えられていない。
【００７１】
また、「暗号文中の識別子の分散仮名化システム」の技術を用いれば、単一の本名が入力され、単一の仮名が出力されるという処理があると対応関係が漏洩するという問題が残ってしまう。そこで、以下では、参照仮定においてデータに付けられた識別子を分散して仮名化し、かつ、仮名化されたデータと元のデータの対応を分からなくして、各データの生成主が正当であることを証明可能で、データベースがこの正当であることを証明されたデータから生成されていることが証明可能で、かつ、効率的に参照可能なシステムについて詳細に説明をする。
【００７２】
図３は、本発明の実施形態におけるデータ参照システムの構成図である。データ参照システム６００は、要素データ生成装置７００と、データベース生成システム８００と、データベース提示システム９００と、から構成される。
【００７３】
要素データ生成装置７００は、個別のデータを生成し、データベース生成システム８００は、要素データ生成装置７００により生成された個別データを多数集めて、データベースを生成する。データベース提示システム９００は、該データベースから必要なデータを集めて、データの集合を提示する。
【００７４】
図４は、本発明の実施形態における要素データ生成装置の構成図である。要素データ生成装置７００は、識別子暗号化部７０７と、ElGamal暗号化部７０８と、ハイブリッド暗号化部７０９と、属性選択開示型署名部７１０と、を有して構成される。これら各部は、１又は複数のコンピュータプログラムによって構成される。
【００７５】
また、要素データ生成装置７００には、システム定数７０１と、識別子７０２（ｕ）、関連識別子ベクトル７０３（V=(v[1],...,v[NV])）、短いデータのベクトル７０４(d[1],...,d[Nd])、長いデータのベクトル７０５(m[1],...,m[Nm])と、属性選択開示署名の為のデータ７０６である公開鍵証明書(A,a,b)、属性値a[1],...,a[Na]、開示項目リストO⊂[1,...,Na]、署名者秘密鍵zが入力される。
【００７６】
システム定数７０１には、以下のデータが含まれる：
・素数ｑと群Ｇの記述（Ｇは離散対数問題が難しいとされる巡回群で、その位数が素数ｑであるもの）； 
・ElGamal暗号方式の定数ｇ（ｇはＧの生成子）；
・識別子空間でIDS=Z/qZ；
・分散装置個数Ｈ；
・分散ElGamal暗号方式の公開鍵y[1],...,y[H]∈G；
2010053036.tif 000013
・関連識別子の数Ｎｖ；
・関数φ（IDS→G、一対一の関数で、逆も計算可能である）；
・共通鍵暗号方式の鍵空間Ｋ、平文空間Ｍ、暗号文空間Ｃ、暗号化関数senc（K×M→C）、復号関数sdec（K×C→M）；
・関数ψ（K→G、一対一の関数で、逆も計算可能である）；
・データの数Ｎd、Ｎm（Ｎdは短いデータの数で、各短い情報はＧの要素。Ｎmは長いデータの数で、各長いデータは任意の文字列。d[1],...,d[Nd]は短いデータのベクトル、m[1],...,m[Nm]は長いデータのベクトル）；
・属性選択開示型署名における認証局の公開鍵(q,G1,G2,G,e,ハッシュ関数Hashqの記述,g1,g2,g,N,h[0],h[1],...,h[N],f,Y)と、追跡用公開鍵Ｔ；及び
・暗号文中の識別子の分散仮名化における仮名乱数のコミットメントｗ。
なお、重複する記号Ｇ、ｑ、ｇ等は同一のものを表す。
【００７７】
次に、図５に示すフローチャートを参照して、要素データ生成装置７００の処理について、詳細に説明する。
【００７８】
システム定数７０１と、識別子７０２と、関連識別子ベクトル７０３と、短いデータのベクトル７０４と、長いデータのベクトル７０５と、属性選択開示署名の為のデータ７０６とのデータが入力されると（ステップＳ１１）、識別子暗号化部７０７は、関連識別子ベクトルv[1],...,v[Nv]の各成分の暗号文である識別子暗号文ベクトル７１１を、上記の実施形態における「暗号文中の識別子の分散仮名化システム」の方法を用いて生成する（ステップＳ１２）。このとき、各識別子暗号文ベクトル７１１を、それぞれev[1],...,ev[Nv]とする。
【００７９】
次に、ElGamal暗号化部７０８は、短いデータのベクトルd[1],...,d[Nv]を、(g,y)をElGamal暗号方式の公開鍵として、それぞれのElGamal暗号文よりなる短い暗号文のベクトル７１２を生成する（ステップＳ１３）。このとき、各短い暗号文のベクトル７１２をed[1],...,ed[Nd]とする。
【００８０】
次に、ハイブリッド暗号化部７０９は、長いデータのベクトルm[1],...,m[Nm]を、(g,(y[i])i=1,...,H)を公開鍵として、それぞれのハイブリッド暗号文よりなるハイブリッド暗号文のベクトル７１３を非特許文献３に記載の方法を用いて生成する（ステップＳ１４）。このとき、各ハイブリッド暗号文のベクトル７１３をem[1],...,em[Nm]とする。
【００８１】
属性選択開示型署名部７１０は、(u,ev[1],...,ev[Nv],ed[1],...,ed[Nd],em[1],...,em[Nm])に対する属性選択開示型署名７１４であるsig=(enc(z),prf,O,(a[i])∈O)を上記の実施形態の「署名システム」における方法を用いて生成する（ステップＳ１５）。ここで、enc(z)は識別子暗号部、prfは証明部であり、公開する属性値をOとする。
【００８２】
上記ステップにて生成された下記データ：(u,ev[1],...,ev[Nv],ed[1],...,ed[Nd],em[1],...,em[Nm],(enc(z),prf,O,(a[i])i∈O))
を要素データ７１５として出力する（ステップＳ１６）。  
【００８３】
次に、本発明の実施形態におけるデータベース生成システムについて、図６を参照して詳細に説明する。データベース生成システム８００は、Ｈ個の分散装置８０６から構成される分散仮名化システム８０７と、属性選択開示型署名検証装置８０２とで構成され、各ｉ番目の分散装置には、それぞれシステム定数と、仮名化の分散秘密σ[i]、τ[i]と暗号方式の分散秘密鍵x[i]からなるデータ８０１と、属性値の集合O'⊂[1,...,N]と、複数の要素データ７１５の列８０３と、が入力される。
【００８４】
次に、図７に示すフローチャートを参照して、データベース生成システム８００の処理について、詳細に説明する。
【００８５】
上記の各データが入力されると（ステップＳ２１）、属性選択開示型署名検証装置８０２は、各要素データに対して属性選択開示型署名を検証し（ステップＳ２２）、さらにO'⊂Oと、開示すべき属性が開示されていることを検証する（ステップＳ２３）。
【００８６】
開示すべき属性が開示されていれば、分散仮名化システム８０７は、識別子ｕ、及び識別子暗号文ベクトルev[1],...,ev[Nv]を、それぞれ、上記の実施形態における「暗号文中の識別子の分散仮名化システム」の方法を用いて、それぞれの仮名の暗号文を生成する（ステップＳ２４）。このとき、それぞれの仮名の暗号文を、epu,epv[1],...,epv[Nv]とする。ここで、それぞれのｉ番目の分散装置は、ｉ番目の分散仮名化装置として動作する。
【００８７】
全ての分散装置を通して得られた仮名化要素データ(epu,epv[1],...,epv[Nv],ed[1],...,ed[Nd],em[1],...,em[Nm],(enc(z),prf,O,(a[i])i∈O))の列をデータベース８０４として出力する（ステップＳ２５）。呼び出された分散仮名化システムの証明は、データベース生成の正当性の証明８０５となる。  
【００８８】
次に、本発明の実施形態におけるデータベース提示システムについて、図８を参照して詳細に説明する。データベース生成システム９００は、Ｈ個の分散装置９０６から構成される。各分散装置は、１または複数のプログラムによって構成される。
【００８９】
各ｉ番目の分散装置には、それぞれシステム定数と暗号方式の分散秘密鍵x[i]とからなるデータ９０１と、参照データ項目セット９０２と、データベース８０４が入力される。参照データ項目セット９０２は、識別子、関連識別子、短いデータ項目、長いデータ項目、署名者のデータの中から参照したい項目を指定するデータである。なお、参照するデータは複数であっても良い。
【００９０】
次に、図９に示すフローチャートを参照して、データベース生成システム８００の処理について、詳細に説明する。データベース８０４、及び参照項目セット９０２が入力されると（ステップＳ３１）、参照データ項目セット９０２に含まれる全ての項目に対応するデータを、データベース８０４の全ての要素データから選択して、取り出したものの列を作成する（ステップＳ３２）。
【００９１】
取り出した各列に関して、識別子、関連識別子の仮名の暗号文からなる列９０５であるか否かを判断し（ステップＳ３３）、仮名の暗号文でなければステップＳ３７以降の処理を実行する。一方、仮名の暗号文であれば、べき乗化処理システム９０８にて以下に示すべき乗化処理を行う。
【００９２】
各ｉ番目の分散装置９０６は、乱数９０９を用いてμ[i]、ν[i]∈Z/qZを生成して、ε[i]=gμ[i]hν[i]を生成し（ステップＳ３４）、全ての要素、例えばElGamal暗号文(a,b)に対して(aμ[i],bμ[i])を生成する（ステップＳ３５）。また、べき乗化処理を正直に行ったことのゼロ知識証明を行う（ステップＳ３６）。このとき、全ての分散装置９０６の結果を合わせると、全て仮名の暗号文(a,b)に関して、元の仮名をμ乗したべき乗された仮名暗号文の列９１０である(aμ,bμ)を得ることができる。    
2010053036.tif 000014
【００９３】
次に、ステップＳ３２で取り出された列がハイブリッド暗号文の列９１２であるか否かを判断し（ステップＳ３７）、ハイブリッド暗号文の列９１２であれば、非特許文献３に記載されるようなハイブリッド暗号文の検証可能なミックスネット９１３により、ミックス処理を行う（ステップＳ３８）。一方、仮名の暗号文の列９０５や短い暗号文の列９１１であれば、非特許文献２に記載されるようなElGamal暗号文の検証可能なミックスネット９０７により、ミックス処理を行う（ステップＳ３９）。なお、識別子に関する仮名の暗号文の列９０５は、ステップＳ３４からステップＳ３６の処理により、仮名をμ乗したものの暗号文の列に変換されている。ここで、各分散装置９０６は、ミックス装置として働く。
【００９４】
また、それぞれのミックス装置は、各列に関して、異なった列も全て同じ順番の入れ替え方９１４を用いて動作したことをゼロ知識証明する（ステップＳ４０）。最後に、全てのミックスネットの処理結果を参照データと証明文９１６として出力する（ステップＳ４１）。
【００９５】
出力されるデータの列は、ミックスネットを通しているので、どの要素データと対応するか分からないが、全て同じ順番の入れ替えが行われているので、異なる列の要素であっても、同じ要素データに属していたかは判別できる。また、識別子は、同じ仮名化処理と同じ数によるべき乗処理を受けているので、ある識別子が他の要素データの関連識別子に入っていれば、これらが同一であることが分かる。なお、この識別子の同一性の判定は、血縁関係等を調べる時に有効である。
【００９６】
以上説明したように、本発明の実施形態によるデータベースの正当性の保証された仮名化データ参照システムによれば、固有の識別子以外は、全て暗号化されており、かつ、これを復号するための鍵は分散されて所持されるので、これらの鍵保持者が結託しない限り、識別子の情報は漏洩しない。ここで、要素データには、作成者の署名がついていることによりその正当性も保証される。そして、この署名は、署名者の選択された属性しか開示しないため、正当な署名者であると言うことしか分からず、個別の署名者の識別子を隠すことができる。これにより、署名者からデータ固有の識別と署名者の関係をも隠すことができる。
【００９７】
さらに、本発明の実施形態によるデータベースの一部の参照方法では、全てのデータの順番がランダムに入れ替えられて出力されるので、識別子との対応が分からない効果がある。また、識別子自体は仮名化されて出てくるので、識別子との対応は分からないまま、関連識別子を持つデータとの繋がりを調べることが可能である。また、全ての列は、同じ順番の入れ替えがなされて出力されるので、参照データ項目セットに二つ以上の項目が含まれれば、それらの項目の相関関係も容易に調べることができる効果がある。そして、これらの処理は全てゼロ知識証明されているので、偽りのデータを提示することはできない。
【００９８】
以上、説明したように、本発明は以下の態様を採用できる。要素データ生成装置は、暗号文からなるベクトルに対する署名を生成し、暗号文からなるベクトルと、署名と、を要素データとして出力し、署名は、署名者の識別子の暗号文と、署名者に認められた属性の一部の集合を含むことができる。
【００９９】
データベース生成システムは、各要素データに含まれる署名を検証する検証手段を有し、複数の要素データに対して各要素データの暗号文の一部を全ての第１の分散装置によりそれぞれ決定的な関数で変換したデータの暗号文に変換して、全ての要素データの列をデータベースとして出力することができる。
【０１００】
データベース提示システムは、各要素データの暗号文の一部に対して、全ての分散装置により列を構成する全ての要素をそれぞれ変換するべき乗化するべき乗化手段を有し、べき乗化手段によりべき乗化されたデータ列、あるいは他のデータ列における参照データを全ての第２の分散装置により要素の順番入れ替えを行うことができる。各要素データの暗号文の一部は、識別子に関連するデータの列であることができる。
【０１０１】
本発明を特別に示し且つ例示的な実施形態を参照して説明したが、本発明は、その実施形態及びその変形に限定されるものではない。当業者に明らかなように、本発明は、添付の請求の範囲に規定される本発明の精神及び範囲を逸脱することなく、種々の変更が可能である。
【０１０２】
本出願は、２００８年１１月５日出願に係る日本特許出願２００８−２８４７７７号を基礎とし且つその優先権を主張するものであり、引用によってその開示の内容の全てを本出願の明細書中に加入する。
【図１】
2010053036.tif 000015
【図２】
2010053036.tif 000016
【図３】
2010053036.tif 000017
【図４】
2010053036.tif 000018
【図５】
2010053036.tif 000019
【図６】
2010053036.tif 000020
【図７】
2010053036.tif 000021
【図８】
2010053036.tif 000022
【図９】
2010053036.tif 000023
【図１０】
2010053036.tif 000024
【図１１】
2010053036.tif 000025
【図１２】
2010053036.tif 000026
【図１３】
2010053036.tif 000027
【手続補正書】
【提出日】平成22年9月3日(2010.9.3)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】０００８
【補正方法】変更
【補正の内容】
【０００８】
の分散装置を有し、参照する項目が指定された参照項目に基づいて、データベースより参照するデータの列を複数個生成し、データの列を全ての第２の分散装置により各要素の順番入れ替えを行い、データ列の要素の順番の入れ替えが全てのデータ列に対して同じであるデータ参照システムを提供する。
［００３５］
また、本発明は、複数のデータベース提示装置を備えるデータベース提示分散システムであって、データベース提示装置は、他のデータベース提示装置と通信する通信手段を有し、データベースと、参照項目と、暗号の分散秘密鍵と、順番の入れ替え方と、他のデータベース提示装置の公開鍵とが入力され、参照項目に基づいて、データベースより参照する暗号文の列を複数個生成し、一部の暗号文の列に対して、他のデータベース提示装置と通信することで、全ての暗号文を復号結果が同じ数でべき乗したものとなる暗号文に変換するべき乗化手段を有し、べき乗化手段によりべき乗化処理された暗号文の列、及び他の暗号文の列における参照データを他のデータベース提示装置と通信することで、自身、及び他のデータベース提示装置でミックスネットを構成し、全ての暗号文の列の順番を全て同じ順番で入れ替えて出力するデータベース提示分散システムを提供する。
［００３６］
更に、本発明は、要素データ生成装置により、複数のデータよりなるベクトルをそれぞれ暗号化して、暗号文からなるベクトルを生成して要素データとして出力し、複数の第１の分散装置を有するデータベース生成システムにより、全ての要素データの列をデータベースとして出力し、複数の第２の分散装置を有するデータベース提示システムは、参照する項目が指定された参照項目に基づいて、データベースより参照するデータの列を複数個生成し、データの列を全ての第２の分散装置により各要素の順番入れ替えを行い、データ列の要素の順番の入れ替えが全てのデータ列に対して同じであるデータ参照方法を提供する。
発明の効果
［００３７］
本発明のデータベース参照システムは、データを集めて仮名化を施してデータベースを構成し、このデータベースの一部を参照するシステムであり、
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００９
【補正方法】変更
【補正の内容】
【０００９】
この参照過程においては、データに付けられた仮名化された識別子を分散して再度仮名化し、かつこの仮名化されたデータと元のデータの対応を分からなくする。このため、各データの生成主が、データが正当であることを証明可能であり、データベースが、正当であることを証明されたデータから生成されていることが証明可能であり、かつ適切に参照可能となる。また、本発明のデータ参照方法、及び、データベース提示分散システムは、上記データベース参照システムで提供されるデータベースを適切に取り扱うことが出来る。
［００３８］
本発明の上記、及び、他の目的、特徴及び利益は、図面を参照する以下の説明により明らかになる。
図面の簡単な説明
［００３９］
［図１］本発明の実施形態に係る属性選択開示型署名装置の説明図である。
［図２］本発明の実施形態に係る分散仮名化システムの説明図である。
［図３］本発明の実施形態に係るデータ参照システムの構成図である。
［図４］本発明の実施形態に係る要素データ生成装置の説明図である。
［図５］要素データ生成装置のフローチャートである。
［図６］本発明の実施形態に係るデータベース生成システムの説明図である。
［図７］データベース生成システムのフローチャートである。
［図８］本発明の実施形態に係るデータベース提示システムの説明図である。
［図９］データベース提示システムのフローチャートである。
［図１０］非特許文献１に記載のシステムのブロック図である。
［図１１］非特許文献２に記載のシステムのブロック図である。
［図１２］非特許文献２に記載のシステムのブロック図である。
［図１３］非特許文献３に記載のシステムのブロック図である。
発明を実施するための形態
［００４０］
本発明の最小構成のデータ参照システムは、要素データを生成する要素データ生成装置と、要素データを複数集めてデータベースを生成するデータベース生成システムと、データベースから参照するデータを出力するデータベース提示システムと、を備えるデータベース参照システムであって、要素デ
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００１１
【補正方法】変更
【補正の内容】
【００１１】
列に対して同じである。
［００４３］
上記構成のデータベース参照システムは、データを集めて仮名化を施してデータベースを構成し、このデータベースの一部を参照するシステムであり、この参照過程においては、データに付けられた仮名化された識別子を分散して再度仮名化し、かつこの仮名化されたデータと元のデータの対応を分からなくする。このため、各データの生成主が、データが正当であることを証明可能であり、データベースが、正当であることを証明されたデータから生成されていることが証明可能であり、かつ効率的に参照可能となる。また、本発明のデータ参照方法、及び、データベース提示分散システムは、上記データベース参照システムで提供されるデータベースを適切に取り扱うことが出来る。
［００４４］
以下、図面を参照し、本発明の実施形態について説明する。まず、ハイブリッド暗号の形を少し変え、正しく復号したことのゼロ知識証明をする方法について詳細に説明する。
［００４５］
電子署名を利用するときには一般的に、署名者は、文書にある秘密鍵を用いて署名を生成し、添付する。この秘密鍵に対応する公開鍵には、認証局による公開鍵証明書が発行されている。
［００４６］
公開鍵証明書は、署名者の公開鍵と署名者の属性等に対する認証局の署名がうたれている。文書に対する署名者の署名を検証する検証処理は、（１）署名を公開鍵で検証する、（２）公開鍵証明書の内容を見て、署名者を確認する。（３）公開鍵証明書に打たれている認証局の署名を検証する、処理を含む。
［００４７］
上記署名の検証処理において、署名を検証するときには公開鍵証明書を検証者に見せる必要が有り、公開鍵証明書に記述されている署名者の属性が全て検証者に分かってしまう。署名により文書の正当性を示すときには、署名者の全ての属性を明らかにする必要は無い場合も多く、この様な公開鍵証明書の全面的な開示は、個人情報の漏洩となってしまう場合もある。
［００４８］
そこで、本実施形態における署名方法では、署名者は署名を生成するときに、公開鍵証明書の開示する属性を選んで署名することができ、該署名から
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００１２
【補正方法】変更
【補正の内容】
【００１２】
は、署名者が署名生成時に開示された属性を持つ公開鍵証明書に対応する秘密鍵で署名したという事実以外は分からない。この様な署名を属性選択開示型署名と呼ぶこととする。
［００４９］
以下では、より具体的に本実施形態における「署名システム」について図１を参照して説明する。まず、属性選択開示型署名方式における、認証局公開鍵４０１、認証局の秘密鍵、追跡情報、追跡用秘密鍵、追跡用公開鍵４０２について説明する。
［００５０］
ｑは素数とする。Ｇ１、Ｇ２、Ｇを位数ｑの群で、Ｇ１×Ｇ２からＧ２への双線形写像ｅが存在する。ｇ１、ｇ２、ｇをＧ１、Ｇ２、Ｇの生成元とする。Ｇは、離散対数問題が難しいものとする。
［００５１］
Ｈａｓｈｑを、任意の文字列を体（Ｚ／ｑＺ）へと写像するハッシュ関数とし、自然数Ｎを公開鍵証明書４１２の項目数とする。
［００５２］
ｈ［０］，ｈ［１］，．．．，ｈ［Ｎ］，ｆを無作為に選ばれたＧ１の元とする。（ｈ［１］，．．．，ｈ［ｎ］）の各ｈ［ｉ］は、ｉ番目の属性に関連づけられている。
［００５３］
γを無作為に選ばれた体Ｚ／ｑＺの元とし、Ｙ＝ｇ２γとする。また、ｓを無作為に選ばれた体Ｚ／ｑＺ上の点とし、Ｔ＝ｇｓとする。
［００５４］
認証局秘密鍵を、γとする。認証局公開鍵４０１を、ｑと、Ｇ１、Ｇ２、Ｇ、ｅ、ハッシュ関数Ｈａｓｈｑの記述と、ｇ１、ｇ２、ｇ、Ｎ、ｈ［０］、ｈ［１］，．．．，ｈ［Ｎ］、ｆ、Ｙとする。また、追跡用秘密鍵を、ｓとする。追跡用公開鍵４０２を、Ｔとする。
［００５５］
認証局の発行する公開鍵証明書４１２と、これに対応する署名者秘密鍵４０３、及び属性値４０４について説明する。次の関係を満たす、Ａ∈Ｇ１、ｂ、ａ、ａ［１］，．．．，ａ［ｎ］、ｚ∈Ｚ／ｑＺを、公開鍵被発行者と協力して生成する。
［数２］
2010053036.tif 000028
［００５６］
公開鍵証明書４１２を（Ａ，ａ，ｂ）とし、追跡情報をＢ，属性値４０４を（ａ［１］，．．．，ａ［ｎ］）、署名者秘密鍵４０３を（ｚ）とする。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００１３
【補正方法】変更
【補正の内容】
【００１３】
［００５７］
メッセージ４０６であるｍに対するもので、開示属性集合４０５である０⊂［１，．．．，Ｎ］に属する属性値のみを公開した署名４１１は、属性選択開示型署名装置４００によって下記のように生成される。
［００５８］
ランダムにｔ∈Ｚ／ｑＺを選び、ｅｎｃ（ｚ）＝（ｇｔ、ｇｚＴｔ）を生成する。ｅｎｃ（ｚ）、及び、以下の式を満たす（ｔ、（ａ［ｉ］）ｉ∈［１，．．．，Ｎ］＼ｏ、Ａ、ｚ、ａ、ｂ）の知識の非対話的ゼロ知識証明ｐｒｆ、開示属性集合４１０である０、開示属性値４０９である（ａ［ｉ］）ｉ∈０、を署名とする。
［数３］
2010053036.tif 000029
［００５９］
但し、非対話的ゼロ知識証明においてハッシュ値を計算するときに、引数にｍをいれる。ここでｅｎｃ（ｚ）を識別子暗号部４０７と、非対話的ゼロ知識証明ｐｒｆを証明部４０８と呼び、署名の検証は、ｐｒｆの正当性の確認を持って行われる。
［００６０］
次に、名称の暗号文を仮名の暗号文に変換する「暗号文中の識別子の分散仮名化システム」について図２を参照して詳細に説明する。ｑを素数、Ｇを離散対数問題が難しいとされる巡回群で、その位数が素数ｑであるものとし、ｇ、ｈをＧの生成子とする。
［００６１］
暗号文中の識別子の分散仮名化のシステム５００は、複数の分散仮名化装置により構成される。ここでは、分散仮名化装置は、Ｈ個あり、１，．．．，Ｈの各ｉに関して、ｉ番目の分散仮名化装置は、ｙ［ｉ］＝ｇｘ［ｉ］なる暗号方式の分散秘密鍵ｘ［ｉ］∈Ｚ／ｑＺを所持している。なお、ｙ［ｉ］は公開されており、ｙは、以下の式で表される。
［数４］
2010053036.tif 000030
［００６２］
ｓｅｎｃ、ｓｄｅｃを共通鍵暗号方式の暗号化関数と復号関数で、Ｋを鍵の空間とする。χ∈Ｋに関するｍ暗号化を、ｓｅｎｃ（χ，ｍ）、その復号をｓｄｅｃ（χ，ｓｅｎｃ（χ，ｎ
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００１４
【補正方法】変更
【補正の内容】
【００１４】
））＝ｍとする。ψをＫからＧへの一対一の関数で、逆も計算可能であるとし、識別子の空間をＺ／ｑＺとする。
［００６３］
分散仮名化装置は、初期設定を最初に行う。各ｉ＝１，．．．，Ｈに関して、ｉ番目の分散仮名化装置は、仮名化の分散秘密鍵σ［ｉ］，τ［ｉ］∈Ｚ／ｑＺをランダムに生成し、ｗ［ｉ］＝ｇσ［ｉ］ｆτ［ｉ］を生成する。分散仮名化のシステム５００は、
［数５］
2010053036.tif 000031
として、各分散仮名化装置がｗ［ｉ］を公開することで、それぞれｗを生成し、ｗを仮名乱数のコミットメント５０２として公開する。
［００６４］
次に、識別子ｕ∈Ｚ／ｑＺの暗号文５０３の生成方法について説明する。暗号化のためのある装置（例えば図４に示す識別子暗号化部７０７など）は、各ｉ＝１，．．．，Ｈに関してランダムに選んだχ［ｉ］∈Ｋ、ｒ［ｉ］∈Ｚ／ｑＺを準備し、ランダムにｒ∈Ｚ／ｑＺを選ぶ。各ｉ＝１，．．．，Ｈに関してランダムに、以下の式を満たすようにランダムに選んだｕ［ｉ］、ｖ［ｉ］∈Ｚ／ｑＺを準備する。
［数６］
2010053036.tif 000032
［００６５］
ｉ＝１からＨに関して、ｃ［ｉ］＝（ｇｕ［ｉ］ｈｖ［ｉ］，ｇｒ［ｉ］，ψ（χ［ｉ］）ｙ［ｉ］ｒ［ｉ］，ｓｅｎｃ（χ［ｉ］，ｕ［ｉ］，ｖ［ｉ］））を生成し、ｃ＝（ｇｕｈｖ）を生成する。（ｃ，ｃ［１］，ｃ［２］，．．．，ｃ［Ｈ］）が識別子ｕの暗号文である。続いて、暗号文中の識別子の分散仮名化方法を説明する。
［００６６］
各ｉ番目の分散仮名化装置には、仮名化の分散秘密鍵σ［ｉ］、τ［ｉ］と、暗号方式の分散秘密鍵ｘ［ｉ］で構成される鍵５０１のデータが入力される。分散仮名化システム５００には、識別子暗号文５０３（ｃ，ｃ［１］，ｃ［２］，．．．，ｃ［Ｈ］）が入力される。ここで、ｃ［ｉ］＝（ｃ［ｉ１］，ｃ［ｉ２］，ｃ［ｉ３］，ｃ［ｉ４］）とする。
［００６７］
全ての分散仮名化装置は、以下の確認を行う。
［数７］
2010053036.tif 000033
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００１５
【補正方法】変更
【補正の内容】
【００１５】
［００６８］
ｉ番目の分散仮名化装置は、以下を生成する。
［数８］
2010053036.tif 000034
ｉ番目の分散仮名化装置は、ｃ［ｉ１］＝ｇｕ’［ｉ］ｈｖ’［ｉ］を確認する。全その分散仮名化装置は、互いに通信してマルチパーティ計算を行うことで、各ｉ番目の分散仮名化装置が
［数９］
2010053036.tif 000035
なるρ［ｉ］を得るように振る舞う。また、各ｉはランダムにτ’［ｉ］∈Ｚ／ｑＺを選び、ｚ［ｉ］＝（ｚ［ｉ１］，ｚ［ｉ２］）＝（ｇτ’［ｉ］，ｇρ［ｉ］ｙτ’［ｉ］）を生成する。ここで、
［数１０］
2010053036.tif 000036
とする。それぞれのｉ番目の分散仮名化装置は自身がρ［ｉ］を求めるために参加したマルチパーティ計算において、自身の担当した計算の正当性をゼロ知識証明することで、ｚがｇ１／（ｕ＋σ）のＥｌＧａｍａｌ暗号文である事が証明される。なお、本分散仮名化システムにおいては、ｇ１／（ｕ＋σ）を乱数σによるｕの仮名と呼ぶ。得られた仮名の暗号文５０４であるｚ、及び証明文５０５を出力する。
［００６９］
［００７０］
ところで、医療機関の署名から医療機関が特定される問題は、上記記載の「署名システム」の技術を用いれば解決できる。例えば、ある種の認可を受けた医療機関であるという属性のみを公開して署名を生成すれば良い。しかし、これだけでは生成された集団電子健康情報に医療機関の情報が残らず、医療機関情報を用いた解析ができなくなる問題が残る。その他の問題として
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００１６
【補正方法】変更
【補正の内容】
【００１６】
は、集団電子健康情報が血縁情報を用いて解析できると有益であるが、これを行う手段が備えられていない。
［００７１］
また、「暗号文中の識別子の分散仮名化システム」の技術を用いれば、仮名化自体が分散化されていない問題は解決される。しかし、単一の本名が入力され、単一の仮名が出力されるという処理があると対応関係が漏洩するという問題は残される。なぜなら、入力が一つで出力が一つであれば両者が対応することは明らかだからである。そこで、以下では、参照過程において、複数のデータに付けられた仮名化されたそれぞれの識別子を同時に分散して再度仮名化し、かつ、この仮名化する前と後のそれぞれにおける集合の要素は仮名と実名との対応を分からないようにする。もちろん実名の集合の各要素は、仮名の集合の要素のいずれかに対応するが、具体的にどの要素に対応するかが分からなくなる。さらに、各仮名化の処理が正当になされたことをゼロ知識証明する。
［００７２］
図３は、本発明の実施形態におけるデータ参照システムの構成図である。データ参照システム６００は、要素データ生成装置７００と、データベース生成システム８００と、データベース提示システム９００と、から構成される。
［００７３］
要素データ生成装置７００は、個別のデータを生成し、データベース生成システム８００は、要素データ生成装置７００により生成された個別データを多数集めて、データベースを生成する。データベース提示システム９００は、該データベースから必要なデータを集めて、データの集合を提示する。
［００７４］
図４は、本発明の実施形態における要素データ生成装置の構成図である。要素データ生成装置７００は、識別子暗号化部７０７と、ＥｌＧａｍａｌ暗号化部７０８と、ハイブリッド暗号化部７０９と、属性選択開示型署名部７１０と、を有して構成される。これら各部は、１又は複数のコンピュータプログラムによって構成される。
［００７５］
また、要素データ生成装置７００には、システム定数７０１と、識別子７０２（ｕ）、関連識別子ベクトル７０３（Ｖ＝（ｖ［１］，．．．，ｖ［Ｎｖ］））、短いデータの
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００１７
【補正方法】変更
【補正の内容】
【００１７】
ベクトル７０４（ｄ［１］，．．．，ｄ［Ｎｄ］）、長いデータのベクトル７０５（ｍ［１］，．．．，ｍ［Ｎｍ］）と、属性選択開示署名の為のデータ７０６である公開鍵証明書（Ａ，ａ，ｂ）、属性値ａ［１］，．．．，ａ［Ｎａ］、開示項目リスト０⊂［１，．．．，Ｎａ］、署名者秘密鍵ｚが入力される。ここで、関連識別子ベクトルの要素は、識別子が選ばれる空間と同じ空間から選ばれる。
［００７６］
システム定数７０１には、以下のデータが含まれる：
・素数ｑと群Ｇの記述（Ｇは離散対数問題が難しいとされる巡回群で、その位数が素数ｑであるもの）；
・ＥｌＧａｍａｌ暗号方式の定数ｇ（ｇはＧの生成子）；
・識別子空間でＩＤＳ＝Ｚ／ｑＺ；
・分散装置個数Ｈ；
・分散ＥｌＧａｍａｌ暗号方式の公開鍵ｙ［１］，．．．，ｙ［Ｈ］∈Ｇ；
［数１１］
2010053036.tif 000037
・関連識別子の数Ｎｖ：
・関数φ（ＩＤＳ→Ｇ、一対一の関数で、逆も計算可能である）；
・共通鍵暗号方式の鍵空間Ｋ、平文空間Ｍ、暗号文空間Ｃ、暗号化関数ｓｅｎｃ（Ｋ×Ｍ→Ｃ）、復号関数ｓｄｅｃ（Ｋ×Ｃ→Ｍ）；
・関数ψ（Ｋ→Ｇ、一対一の関数で、逆も計算可能である）；
・データの数Ｎｄ、Ｎｍ（Ｎｄは短いデータの数で、各短い情報はＧの要素。Ｎｍは長いデータの数で、各長いデータは任意の文字列。ｄ［１］，．．．，ｄ［Ｎｄ］は短いデータのベクトル、ｍ［１］，．．．，ｍ［Ｎｍ］は長いデータのベクトル）；
・属性選択開示型署名における認証局の公開鍵（ｑ，Ｇ１，Ｇ２，Ｇ，ｅ，ハッシュ関数Ｈａｓｈｑの記述，ｇ１，ｇ２，ｇ，Ｎ，ｈ［０］，ｈ［１］，．．．，ｈ［Ｎ］，ｆ．Ｙ）と、追跡用公開鍵Ｔ；及び
・暗号文中の識別子の分散仮名化における仮名乱数のコミットメントｗ。
なお、重複する記号Ｇ、ｑ、ｇ等は同一のものを表す。
［００７７］
次に、図５に示すフローチャートを参照して、要素データ生成装置７００の処理について、詳細に説明する。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】００１８
【補正方法】変更
【補正の内容】
【００１８】
［００７８］
システム定数７０１と、識別子７０２と、関連識別子ベクトル７０３と、短いデータのベクトル７０４と、長いデータのベクトル７０５と、属性選択開示署名の為のデータ７０６とのデータが入力されると（ステップＳ１１）、識別子暗号化部７０７は、関連識別子ベクトルｒｖ［１］，．．．，ｒｖ［Ｎｖ］の各成分の暗号文である識別子暗号文ベクトル７１１を、上記の実施形態における識別子の暗号文の生成方法を用いて生成する（ステップＳ１２）。このとき、各識別子暗号文ベクトル７１１を、それぞれｅｖ［１］，．．．，ｅｖ［Ｎｖ］とする。
［００７９］
次に、ＥｌＧａｍａｌ暗号化部７０８は、短いデータのベクトルｄ［１］，．．．，ｄ［Ｎｄ］を、（ｇ，ｙ）をＥｌＧａｍａｌ暗号方式の公開鍵として、それぞれのＥｌＧａｍａｌ暗号文よりなる短い暗号文のベクトル７１２を生成する（ステップＳ１３）。このとき、各短い暗号文のベクトル７１２をｅｄ［１］，．．．，ｅｄ［Ｎｄ］とする。
［００８０］
次に、ハイブリッド暗号化部７０９は、長いデータのベクトルｍ［１］，．．．，ｍ［Ｎｍ］を、（ｇ，（ｙ［ｉ］）ｉ＝１，．．．，Ｈ）を公開鍵として、それぞれのハイブリッド暗号文よりなるハイブリッド暗号文のベクトル７１３を非特許文献３に記載の方法を用いて生成する（ステップＳ１４）。このとき、各ハイブリッド暗号文のベクトル７１３をｅｍ［１］，．．．，ｅｍ［Ｎｍ］とする。
［００８１］
属性選択開示型署名部７１０は、（ｕ，ｅｖ［１］，．．．，ｅｖ［Ｎｖ］，ｅｄ［１］，．．．，ｅｄ［Ｎｄ］，ｅｍ［１］，．．．，ｅｍ［Ｎｍ］）に対する属性選択開示型署名７１４であるｓｉｇ＝（ｅｎｃ（ｚ），ｐｒｆ，０，（ａ［ｉ］）ｉ∈０）を上記の実施形態の「署名システム」における方法を用いて生成する（ステップＳ１５）。ここで、ｅｎｃ（ｚ）は識別子暗号部、ｐｒｆは証明部であり、公開する属性値を０とする。
［００８２］
上記ステップにて生成された下記データ：（ｕ，ｅｖ［１］，．．．，ｅｖ［Ｎｖ］，ｅｄ［１］，．．．，ｅｄ［Ｎｄ］，ｅｍ［１］，．．．，ｅｍ［Ｎｍ］，（ｅｎｃ（ｚ），ｐｒｆ，０，（ａ［ｉ］）ｉ∈０））を要素データ７１５として出力する（ステップＳ１６）。
［００８３］
次に、本発明の実施形態におけるデータベース生成システムについて、図６を参照して詳細に説明する。データベース生成システム８００は、Ｈ個の分散装置８０６から構成される分散仮名化システム８０７と、属性選択開示型署名検証装置８０２とで構成され、各ｉ番目の分散装置には、それぞれシ
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】００１９
【補正方法】変更
【補正の内容】
【００１９】
ステム定数と、仮名化の分散秘密鍵σ［ｉ］、τ［ｉ］と暗号方式の分散秘密鍵ｘ［ｉ］からなるデータ８０１と、属性値の集合０’⊂［１，．．．，Ｎ］と、複数の要素データ７１５の列８０３と、が入力される。
［００８４］
次に、図７に示すフローチャートを参照して、データベース生成システム８００の処理について、詳細に説明する。
［００８５］
上記の各データが入力されると（ステップＳ２１）、属性選択開示型署名検証装置８０２は、各要素データに対して属性選択開示型署名を検証し（ステップＳ２２）、さらに０’⊂０と、開示すべき属性が開示されていることを検証する（ステップＳ２３）。
［００８６］
開示すべき属性が開示されていれば、分散仮名化システム８０７は、識別子ｕ、及び識別子暗号文ベクトルｅｖ［１］，．．．，ｅｖ［Ｎｖ］を、それぞれ、上記の実施形態における「暗号文中の識別子の分散仮名化システム」の方法を用いて、それぞれの仮名の暗号文を生成する（ステップＳ２４）。このとき、それぞれの仮名の暗号文を、ｅｐｕ，ｅｐｖ［１］，．．．，ｅｐｖ［Ｎｖ］とする。ここで、それぞれのｉ番目の分散装置は、ｉ番目の分散仮名化装置として動作する。
［００８７］
全ての分散装置を通して得られた仮名化要素データ（ｅｐｕ，ｅｐｖ［１］，．．．，ｅｐｖ［Ｎｖ］，ｅｄ［１］，．．．，ｅｄ［Ｎｄ］，ｅｍ［１］，．．．，ｅｍ［Ｎｍ］，（ｅｎｃ（ｚ），ｐｒｆ，０，（ａ［ｉ］）ｉ∈０）の列をデータベース８０４として出力する（ステップＳ２５）。呼び出された分散仮名化システムの証明は、データベース生成の正当性の証明８０５となる。
［００８８］
次に、本発明の実施形態におけるデータベース提示システムについて、図８を参照して詳細に説明する。データベース提供システム９００は、Ｈ個の分散装置９０６から構成される。各分散装置は、１または複数のプログラムによって構成される。
［００８９］
各ｉ番目の分散装置には、それぞれシステム定数と暗号方式の分散秘密鍵ｘ［ｉ］とからなるデータ９０１と、参照データ項目セット９０２と、データベース８０４が入力される。参照データ項目セット９０２は、識別子、関連識別子、短いデータ項目、長いデータ項目、属性選択開示型署名の識別子暗号部の中から参照したい項目を指定するデータである。なお、参照するデータは
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】００２０
【補正方法】変更
【補正の内容】
【００２０】
複数であっても良い。
［００９０］
次に、図９に示すフローチャートを参照して、データベース提供システム９００の処理について、詳細に説明する。データベース８０４、及び参照項目セット９０２が入力されると（ステップＳ３１）、参照データ項目セット９０２に含まれる全ての項目に対応するデータを、データベース８０４の全ての要素データから選択して、取り出したものの列を作成する（ステップＳ３２）。
［００９１］
取り出した各列に関して、識別子、関連識別子の仮名の暗号文からなる列９０５であるか否かを判断し（ステップＳ３３）、仮名の暗号文でなければステップＳ３７以降の処理を実行する。一方、仮名の暗号文であれば、べき乗化処理システム９０８にて以下に示すべき乗化処理を行う。
［００９２］
各ｉ番目の分散装置９０６は、乱数９０９を用いてμ［ｉ］、ν［ｉ］∈Ｚ／ｑＺを生成して、取り出した列の全ての要素、例えばＥｌＧａｍａｌ暗号文（ａ，ｂ）に対して（ａμ［ｉ］，ｂμ［ｉ］）を生成する（ステップＳ３４）。また、べき乗化処理を正直に行ったことのゼロ知識証明を行う（ステップＳ３５）。このとき、全ての分散装置９０６の結果を合わせると、全て仮名の暗号文（ａ，ｂ）に関して、元の仮名をμ乗したべき乗された仮名暗号文の列９１０である（ａμ，ｂμ）を得ることができる。
［数１２］
2010053036.tif 000038
［００９３］
次に、ステップＳ３２で取り出された列がハイブリッド暗号文の列９１２であるか否かを判断し（ステップＳ３６）、ハイブリッド暗号文の列９１２であれば、非特許文献３に記載されるようなハイブリッド暗号文の検証可能なミックスネット９１３により、ミックス処理を行う（ステップＳ３７）。一方、仮名の暗号文の列９０５や短い暗号文の列９１１であれば、非特許文献２に記載されるようなＥｌＧａｍａｌ暗号文の検証可能なミックスネット９０７に
【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】００２１
【補正方法】変更
【補正の内容】
【００２１】
より、ミックス処理を行う（ステップＳ３８）。なお、識別子に関する仮名の暗号文の列９０５は、ステップＳ３３からステップＳ３５の処理により、仮名をμ乗したものの暗号文の列に変換されている。ここで、各分散装置９０６は、ミックス装置として働く。
［００９４］
また、それぞれのミックス装置は、各列に関して、異なった列も全て同じ順番の入れ替え方９１４を用いて動作したことをゼロ知識証明する（ステップＳ３９）。最後に、全てのミックスネットの処理結果を参照データと証明文９１６として出力する（ステップＳ４０）。
［００９５］
出力されるデータの列は、ミックスネットを通しているので、どの要素データと対応するか分からないが、全て同じ順番の入れ替えが行われているので、異なる列の要素であっても、同じ要素データに属していたかは判別できる。また、識別子は、同じ仮名化処理と同じ数によるべき乗処理を受けているので、ある識別子が他の要素データの関連識別子に入っていれば、これらが同一であることが分かる。なお、この識別子の同一性の判定は、血縁関係等を調べる時に有効である。
［００９６］
以上説明したように、本発明の実施形態によるデータベースの正当性の保証された仮名化データ参照システムによれば、識別子は、全て暗号化されており、かつ、これを復号するための鍵は分散されて所持されるので、これらの鍵保持者が結託しない限り、識別子の情報は漏洩しない。ここで、要素データには、作成者の署名がついていることによりその正当性も保証される。そして、この署名は、署名者の選択された属性しか開示しないため、正当な署名者であると言うことしか分からず、個別の署名者の識別子を隠すことができる。
［００９７］
さらに、本発明の実施形態によるデータベースの一部の参照方法では、全てのデータの順番がランダムに入れ替えられて出力されるので、出力されたデータと入力されたデータの識別子との対応関係が分からない効果がある。また、識別子自体は仮名化されて出てくるので、識別子との対応は分からないまま、関連識別子を持つデータとの繋がりを調べることが可能である。また、全ての列は、同じ順番の入れ替えがなさ
【手続補正１４】
【補正対象書類名】図面
【補正対象項目名】図９
【補正方法】変更
【補正の内容】
【図９】
2010053036.tif 000039
【国際調査報告】
2010053036.tif 000040
2010053036.tif 000041
2010053036.tif 000042
2010053036.tif 000043