(57)【特許請求の範囲】
【請求項１】
暗号化装置と暗号文比較装置とを含む暗号文比較システムであって、
前記暗号化装置は、
主鍵と文書とに基づいて、導出鍵を生成する導出鍵生成手段と、
前記主鍵と前記文書と前記導出鍵とに基づいて、補助導出鍵を生成する補助導出鍵生成手段と、
前記文書の識別子と前記導出鍵と前記補助導出鍵とに基づいて、前記識別子を暗号化した識別子別暗号文を生成する識別子別暗号文生成手段と、
前記識別子と前記導出鍵とに基づいて、前記主鍵と前記文書と前記導出鍵とから生成された相対値を暗号化した相対値暗号文を生成する相対値暗号文生成手段と、
を備え、
前記暗号文比較装置は、
前記導出鍵生成手段が第１文書から生成した第１導出鍵と、前記第１文書の第１識別子と、前記識別子別暗号文生成手段が前記第１識別子を暗号化した第１識別子別暗号と前記相対値暗号文生成手段が第１相対値を暗号化した第１相対値暗号文とを有する第１暗号文と、第２文書の第２識別子と、前記識別子別暗号文生成手段が前記第２識別子を暗号化した第２識別子別暗号と前記相対値暗号文生成手段が第２相対値を暗号化した第２相対値暗号文とを有する第２暗号文と、を用いて、前記第１暗号文の元である前記第１文書と前記第２暗号文の元である前記第２文書との大小関係を暗号文のままで判定する暗号文比較手段と、
を備える暗号文比較システム。
【請求項２】
請求項１に記載の暗号文比較システムに含まれる暗号化装置であって、
前記導出鍵生成手段と、前記補助導出鍵生成手段と、前記識別子別暗号文生成手段と、前記相対値暗号文生成手段と、を備え、
前記識別子別暗号文と前記相対値暗号文とを含む文字列である前記文書に対する暗号文と、前記識別子と、前記導出鍵と、を出力する暗号化装置。
【請求項３】
前記導出鍵生成手段は、ｉ＝n-1から0の降順に従い、前記主鍵と前記文書の要素ｂ[i]と前記導出鍵の既に生成された要素ｄ[i+1]とを用いて、第１ハッシュ関数のHash：｛0,1｝*→｛0,1｝kに従ったHash(K,(d[i+1],b[i]))により前記導出鍵の要素ｄ[i]を生成し、
前記補助導出鍵生成手段は、ｊ＝0からn-1の昇順に従い、前記主鍵と前記文書の要素ｂ[j]のビット反転（１−ｂ[j]）と前記導出鍵の要素ｄ[j+1]とを用いて、前記第１ハッシュ関数に従ったHash(Ｋ,ｄ[j+1],1-ｂ[j])により補助導出鍵の要素ｇ[j]を生成する請求項２に記載の暗号化装置。
【請求項４】
前記識別子別暗号文生成手段は、ｐ＝n-1,…,0の降順に従い、安全変数Ｌ[p]∈自然数の場合に｛0,1｝L[p]から識別子別暗号文の要素ｃ[p]の候補をランダムに選び、識別子ＩＤと前記導出鍵の要素ｄ[p]とを用いて、第２ハッシュ関数のHash2：｛0,1｝*→｛0,1｝において、０＝Hash2(ID,d[p],c[p]) mod 2が成り立ち、かつ、前記識別子ＩＤと前記補助導出鍵の要素ｇ[p]とを用いて、前記第２ハッシュ関数において、１＝Hash2(ID,g[p],c[p]) mod 2が成り立つ場合に、前記識別子別暗号文の要素ｃ[p]として採用する請求項２または３に記載の暗号化装置。
【請求項５】
請求項１に記載の暗号文比較システムに含まれる暗号化装置が実行する制御方法であって、
前記導出鍵生成手段が、主鍵と文書とに基づいて、導出鍵を生成する導出鍵生成ステップと、
前記補助導出鍵生成手段が、前記主鍵と前記文書と前記導出鍵とに基づいて、補助導出鍵を生成する補助導出鍵生成ステップと、
前記識別子別暗号文生成手段が、前記文書の識別子と前記導出鍵と前記補助導出鍵とに基づいて、前記識別子を暗号化した識別子別暗号文を生成する識別子別暗号文生成ステップと、
前記相対値暗号文生成手段が、前記識別子と前記導出鍵とに基づいて、前記主鍵と前記文書と前記導出鍵とから生成された相対値を暗号化した相対値暗号文を生成する相対値暗号文生成ステップと、
を含み、
前記識別子別暗号文と前記相対値暗号文とを含む文字列である前記文書に対する暗号文と、前記識別子と、前記導出鍵と、を出力するステップをさらに含む暗号化装置の制御方法。
【請求項６】
請求項１に記載の暗号文比較システムに含まれる暗号化装置の制御プログラムであって、
主鍵と文書とに基づいて、導出鍵を生成する導出鍵生成ステップと、
前記主鍵と前記文書と前記導出鍵とに基づいて、補助導出鍵を生成する補助導出鍵生成ステップと、
前記文書の識別子と前記導出鍵と前記補助導出鍵とに基づいて、前記識別子を暗号化した識別子別暗号文を生成する識別子別暗号文生成ステップと、
前記識別子と前記導出鍵とに基づいて、前記主鍵と前記文書と前記導出鍵とから生成された相対値を暗号化した相対値暗号文を生成する相対値暗号文生成ステップと、
前記識別子別暗号文と前記相対値暗号文とを含む文字列である前記文書に対する暗号文と、前記識別子と、前記導出鍵と、を出力するステップと、
をコンピュータに実行させる暗号文生成装置の制御プログラム。
【請求項７】
請求項１に記載の暗号文比較システムに含まれる暗号文比較装置であって、
前記第１暗号文と前記第１識別子と前記第１導出鍵とを取得する第１暗号文取得手段と、
前記第２暗号文と前記第２識別子とを取得する第２暗号文取得手段と、
前記暗号文比較手段と、
を備える暗号文比較装置。
【請求項８】
請求項１に記載の暗号文比較システムに含まれる暗号文比較装置が実行する制御方法であって、
第１暗号文取得手段が、前記第１暗号文と前記第１識別子と前記第１導出鍵とを取得する第１暗号文取得ステップと、
第２暗号文取得手段が、前記第２暗号文と前記第２識別子とを取得する第２暗号文取得ステップと、
前記暗号文比較手段が、前記第１暗号文、前記第１識別子、前記第１導出鍵、前記第２暗号文および前記第２識別子を用いて、前記第１暗号文の元である第１文書と前記第２暗号文の元である第２文書との大小関係を暗号文のままで判定する暗号文比較ステップと、
を含む暗号文比較装置の制御方法。
【請求項９】
請求項１に記載の暗号文比較システムに含まれる暗号文比較装置の制御プログラムであって、
前記第１暗号文と前記第１識別子と前記第１導出鍵とを取得する第１暗号文取得ステップと、
前記第２暗号文と前記第２識別子とを取得する第２暗号文取得ステップと、
前記第１暗号文、前記第１識別子、前記第１導出鍵、前記第２暗号文および前記第２識別子を用いて、前記第１暗号文の元である第１文書と前記第２暗号文の元である第２文書との大小関係を暗号文のままで判定する暗号文比較ステップと、
をコンピュータに実行させる暗号文比較装置の制御プログラム。
【請求項１０】
請求項１に記載の暗号文比較システムが実行する暗号文比較方法であって、
前記導出鍵生成手段が、主鍵と文書とに基づいて、導出鍵を生成する導出鍵生成ステップと、
前記補助導出鍵生成手段が、前記主鍵と前記文書と前記導出鍵とに基づいて、補助導出鍵を生成する補助導出鍵生成ステップと、
前記識別子別暗号文生成手段が、前記文書の識別子と前記導出鍵と前記補助導出鍵とに基づいて、前記識別子を暗号化した識別子別暗号文を生成する識別子別暗号文生成ステップと、
前記相対値暗号文生成手段が、前記識別子と前記導出鍵とに基づいて、前記主鍵と前記文書と前記導出鍵とから生成された相対値を暗号化した相対値暗号文を生成する相対値暗号文生成ステップと、
前記暗号文比較手段が、前記導出鍵生成ステップにおいて第１文書から生成した第１導出鍵と、前記第１文書の第１識別子と、前記識別子別暗号文生成ステップにおいて前記第１識別子を暗号化した第１識別子別暗号と前記相対値暗号文生成ステップにおいて第１相対値を暗号化した第１相対値暗号文とを有する第１暗号文と、第２文書の第２識別子と、前記識別子別暗号文生成ステップにおいて前記第２識別子を暗号化した第２識別子別暗号と前記相対値暗号文生成ステップにおいて第２相対値を暗号化した第２相対値暗号文とを有する第２暗号文と、を用いて、前記第１暗号文の元である前記第１文書と前記第２暗号文の元である前記第２文書との大小関係を暗号文のままで判定する暗号文比較ステップと、
を含む暗号文比較方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号文比較システム、暗号文比較方法、暗号化装置と暗号文比較装置およびそれらの制御プログラムに関する。
【背景技術】
【０００２】  上記技術分野において、非特許文献１には、次のような、暗号化された数値の大小比較をする技術が開示されている。平文としてのある数値Ｍと、鍵Ｋとが与えられたとき、その暗号文Ｃはある暗号化関数Ｅncを用いてＣ=Ｅnc(Ｋ，Ｍ)として生成される。この時、任意のＭ＞Ｍ’なる２つの数ＭとＭ’とに関して、Ｅnc(Ｋ，Ｍ)＞Ｅnc(Ｋ，Ｍ’)が成り立つ。すなわち、Ｃ＝Ｅnc(Ｋ，Ｍ)とＣ’＝Ｅnc(Ｋ，Ｍ’)とが与えられると、暗号文ＣやＣ’を復号せずとも数値Ｍと数値Ｍ’との大小関係を知ることができる。【０００３】  また、非特許文献２には、次のような、暗号化された数値の大小比較をする技術が開示されている。非特許文献２は、共通鍵暗号の一種であり、Ｍ＝(ｂ[1]，…，ｂ[n]) のように複数のブロックに分割して表現される平文である文書Ｍを暗号化して、Ｃ＝(ｃ[1]，…，ｃ[n])のように複数のブロックからなる暗号文を生成する。そして、もし２つの平文が最初のｋ個まで同一であるならば、それらの暗号文も最初のｋ個まで等しいものとなる。このように、部分的な一致を暗号文のまま判別できる方式となっている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Alexandra Boldyreva, Nathan Chenette, Younho Lee, Adam O'Neill: “Order-Preserving Symmetric Encryption. EUROCRYPT” 2009: 224-241
【非特許文献２】Georgios Amanatidis, Alexandra Boldyreva, Adam O'Neill: “Provably-Secure Schemes for Basic Query Support in Outsourced Databases”. DBSec 2007: 14-30
【発明の概要】
【発明が解決しようとする課題】
【０００５】  しかしながら、上記文献に記載の技術では、暗号化された数値の大小比較をすることができても、情報の漏洩する機会を期待するほど減らすことができなかった。非特許文献１の技術においては、暗号文の列が与えられると、鍵に関する知識を全く持たずとも直ちにその対応する平文の大小関係が全て分かってしまう問題がある。また、非特許文献１の方式が暗号化の前後でデータの順序を保存させることの要請から、暗号文から平文のおよその大きさが分かってしまう問題がある。【０００６】  さらに、データベースの運用において、様々な属性を持つタップルの集合である表の中から、ある属性がある数より大きいあるいは小さい数であるタップルを全て送り返すことを、利用者がデータベースに要求することがある。ここで、データベースが非特許文献１の方法で暗号化されていれば、データベースは暗号化に使われた鍵を知らずとも数値の大小を判定できるため、利用者の要求に応えることができる。しかし、データベースは、利用者の要求があったときのみ数値の大小が判定できれば十分であるのに、要求がなくともこれが可能である。この不必要な能力は、データベースから情報の漏洩する機会を増加させることになる。【０００７】  一方、非特許文献２においては、暗号文の最初のｋ個の一致を知ることができても、大小を直接判別することはできなかった。そのため、最初のｋ個の一致する、候補となる暗号文を全て送らねばならなかった。また、２つの暗号文の最初のｋ個が一致することは暗号化のための鍵を保持せずとも直接行うことができるので、これをデータベースに用いた場合、データベースから情報の漏洩する機会を増加させることになる。【０００８】  本発明の目的は、上述の課題を解決するため、暗号化された数値の大小比較をすることができると共に、隠匿性を維持して情報の漏洩する機会を大幅に減らすことができる技術を提供することにある。
【課題を解決するための手段】
【０００９】
上記目的を達成するため、本発明に係る暗号文比較システムは、
暗号化装置と暗号文比較装置とを含む暗号文比較システムであって、
前記暗号化装置は、
主鍵と文書とに基づいて、導出鍵を生成する導出鍵生成手段と、
前記主鍵と前記文書と前記導出鍵とに基づいて、補助導出鍵を生成する補助導出鍵生成手段と、
前記文書の識別子と前記導出鍵と前記補助導出鍵とに基づいて、前記識別子を暗号化した識別子別暗号文を生成する識別子別暗号文生成手段と、
前記識別子と前記導出鍵とに基づいて、前記主鍵と前記文書と前記導出鍵とから生成された相対値を暗号化した相対値暗号文を生成する相対値暗号文生成手段と、
を備え、
前記暗号文比較装置は、
前記導出鍵生成手段が第１文書から生成した第１導出鍵と、前記第１文書の第１識別子と、前記識別子別暗号文生成手段が前記第１識別子を暗号化した第１識別子別暗号と前記相対値暗号文生成手段が第１相対値を暗号化した第１相対値暗号文とを有する第１暗号文と、第２文書の第２識別子と、前記識別子別暗号文生成手段が前記第２識別子を暗号化した第２識別子別暗号と前記相対値暗号文生成手段が第２相対値を暗号化した第２相対値暗号文とを有する第２暗号文と、を用いて、前記第１暗号文の元である前記第１文書と前記第２暗号文の元である前記第２文書との大小関係を暗号文のままで判定する暗号文比較手段と、
を備える。
【００１０】
上記目的を達成するため、本発明に係る暗号化装置は、
上記暗号文比較システムに含まれる暗号化装置であって、
前記導出鍵生成手段と、前記補助導出鍵生成手段と、前記識別子別暗号文生成手段と、前記相対値暗号文生成手段と、を備え、
前記識別子別暗号文と前記相対値暗号文とを含む文字列である前記文書に対する暗号文と、前記識別子と、前記導出鍵と、を出力する。
【００１１】
上記目的を達成するため、本発明に係る暗号化装置の制御方法は、
上記暗号文比較システムに含まれる暗号化装置が実行する制御方法であって、
前記導出鍵生成手段が、主鍵と文書とに基づいて、導出鍵を生成する導出鍵生成ステップと、
前記補助導出鍵生成手段が、前記主鍵と前記文書と前記導出鍵とに基づいて、補助導出鍵を生成する補助導出鍵生成ステップと、
前記識別子別暗号文生成手段が、前記文書の識別子と前記導出鍵と前記補助導出鍵とに基づいて、前記識別子を暗号化した識別子別暗号文を生成する識別子別暗号文生成ステップと、
前記相対値暗号文生成手段が、前記識別子と前記導出鍵とに基づいて、前記主鍵と前記文書と前記導出鍵とから生成された相対値を暗号化した相対値暗号文を生成する相対値暗号文生成ステップと、
を含み、
前記識別子別暗号文と前記相対値暗号文とを含む文字列である前記文書に対する暗号文と、前記識別子と、前記導出鍵と、を出力するステップをさらに含む。
【００１２】
上記目的を達成するため、本発明に係る暗号化装置の制御プログラムは、
上記暗号文比較システムに含まれる暗号化装置の制御プログラムであって、
主鍵と文書とに基づいて、導出鍵を生成する導出鍵生成ステップと、
前記主鍵と前記文書と前記導出鍵とに基づいて、補助導出鍵を生成する補助導出鍵生成ステップと、
前記文書の識別子と前記導出鍵と前記補助導出鍵とに基づいて、前記識別子を暗号化した識別子別暗号文を生成する識別子別暗号文生成ステップと、
前記識別子と前記導出鍵とに基づいて、前記主鍵と前記文書と前記導出鍵とから生成された相対値を暗号化した相対値暗号文を生成する相対値暗号文生成ステップと、
前記識別子別暗号文と前記相対値暗号文とを含む文字列である前記文書に対する暗号文と、前記識別子と、前記導出鍵と、を出力するステップと、
をコンピュータに実行させる。
【００１３】
上記目的を達成するため、本発明に係る暗号文比較装置は、
上記暗号文比較システムに含まれる暗号文比較装置であって、
前記第１暗号文と前記第１識別子と前記第１導出鍵とを取得する第１暗号文取得手段と、
前記第２暗号文と前記第２識別子とを取得する第２暗号文取得手段と、
前記暗号文比較手段と、
を備える。
【００１４】
上記目的を達成するため、本発明に係る暗号文比較装置の制御方法は、
上記暗号文比較システムに含まれる暗号文比較装置が実行する制御方法であって、
第１暗号文取得手段が、前記第１暗号文と前記第１識別子と前記第１導出鍵とを取得する第１暗号文取得ステップと、
第２暗号文取得手段が、前記第２暗号文と前記第２識別子とを取得する第２暗号文取得ステップと、
前記暗号文比較手段が、前記第１暗号文、前記第１識別子、前記第１導出鍵、前記第２暗号文および前記第２識別子を用いて、前記第１暗号文の元である第１文書と前記第２暗号文の元である第２文書との大小関係を暗号文のままで判定する暗号文比較ステップと、
を含む。
【００１５】
上記目的を達成するため、本発明に係る暗号文比較装置の制御プログラムは、
上記暗号文比較システムに含まれる暗号文比較装置の制御プログラムであって、
前記第１暗号文と前記第１識別子と前記第１導出鍵とを取得する第１暗号文取得ステップと、
前記第２暗号文と前記第２識別子とを取得する第２暗号文取得ステップと、
前記第１暗号文、前記第１識別子、前記第１導出鍵、前記第２暗号文および前記第２識別子を用いて、前記第１暗号文の元である第１文書と前記第２暗号文の元である第２文書との大小関係を暗号文のままで判定する暗号文比較ステップと、
をコンピュータに実行させる。
【００１６】
上記目的を達成するため、本発明に係る暗号文比較方法は、
上記暗号文比較システムが実行する暗号文比較方法であって、
前記導出鍵生成手段が、主鍵と文書とに基づいて、導出鍵を生成する導出鍵生成ステップと、
前記補助導出鍵生成手段が、前記主鍵と前記文書と前記導出鍵とに基づいて、補助導出鍵を生成する補助導出鍵生成ステップと、
前記識別子別暗号文生成手段が、前記文書の識別子と前記導出鍵と前記補助導出鍵とに基づいて、前記識別子を暗号化した識別子別暗号文を生成する識別子別暗号文生成ステップと、
前記相対値暗号文生成手段が、前記識別子と前記導出鍵とに基づいて、前記主鍵と前記文書と前記導出鍵とから生成された相対値を暗号化した相対値暗号文を生成する相対値暗号文生成ステップと、
前記暗号文比較手段が、前記導出鍵生成ステップにおいて第１文書から生成した第１導出鍵と、前記第１文書の第１識別子と、前記識別子別暗号文生成ステップにおいて前記第１識別子を暗号化した第１識別子別暗号と前記相対値暗号文生成ステップにおいて第１相対値を暗号化した第１相対値暗号文とを有する第１暗号文と、第２文書の第２識別子と、前記識別子別暗号文生成ステップにおいて前記第２識別子を暗号化した第２識別子別暗号と前記相対値暗号文生成ステップにおいて第２相対値を暗号化した第２相対値暗号文とを有する第２暗号文と、を用いて、前記第１暗号文の元である前記第１文書と前記第２暗号文の元である前記第２文書との大小関係を暗号文のままで判定する暗号文比較ステップと、
を含む暗号文比較方法。
【発明の効果】
【００１７】  本発明によれば、暗号化された数値の大小比較をすることができると共に、隠匿性を維持して情報の漏洩する機会を大幅に減らすことができる。
【図面の簡単な説明】
【００１８】
【図１】本発明の第１実施形態に係る暗号文生成装置の構成を示すブロック図である。
【図２Ａ】本発明の第２実施形態に係る暗号文生成装置を含む暗号文比較システムの構成を示すブロック図である。
【図２Ｂ】本発明の第２実施形態に係る暗号文生成装置を含む暗号文比較システムを適用したサービスを示す図である。
【図３】本発明の第２実施形態に係る暗号文生成装置の導出鍵生成部の構成を示すブロック図である。
【図４】本発明の第２実施形態に係る暗号文生成装置の補助導出鍵生成部の構成を示すブロック図である。
【図５Ａ】本発明の第２実施形態に係る暗号文生成装置の暗号文生成部の構成を示すブロック図である。
【図５Ｂ】本発明の第２実施形態に係る識別子別暗号文生成部の構成を示すブロック図である。
【図６】本発明の第２実施形態に係る暗号文比較装置の暗号文比較部の構成を示すブロック図である。
【図７】本発明の第２実施形態に係る暗号文生成装置のハードウェア構成を示すブロック図である。
【図８】本発明の第２実施形態に係る暗号文生成テーブルの構成を示す図である。
【図９】本発明の第２実施形態に係る暗号文生成装置の処理手順を示すフローチャートである。
【図１０Ａ】本発明の第２実施形態に係る導出鍵生成処理の手順を示すフローチャートである。
【図１０Ｂ】本発明の第２実施形態に係る補助導出鍵生成処理の手順を示すフローチャートである。
【図１０Ｃ】本発明の第２実施形態に係る識別子別暗号文生成処理の手順を示すフローチャートである。
【図１０Ｄ】本発明の第２実施形態に係る相対値暗号文生成処理の手順を示すフローチャートである。
【図１１】本発明の第２実施形態に係る暗号文比較装置のハードウェア構成を示すブロック図である。
【図１２】本発明の第２実施形態に係る暗号文比較テーブルの構成を示す図である。
【図１３】本発明の第２実施形態に係る暗号文比較装置の処理手順を示すフローチャートである。
【図１４】本発明の前提技術となる暗号化装置の構成を示すブロック図である。
【図１５】本発明の前提技術となる暗号化装置の処理手順を示すフローチャートである。
【発明を実施するための形態】
【００１９】  以下に、図面を参照して、本発明の実施の形態について例示的に詳しく説明する。ただし、以下の実施の形態に記載されている構成要素は単なる例示であり、本発明の技術範囲をそれらのみに限定する趣旨のものではない。
【００２０】  ［第１実施形態］  本発明の第１実施形態としての暗号文生成装置１００について、図１を用いて説明する。暗号文生成装置１００は、暗号文のままで大小比較するための暗号文を生成する装置である。
【００２１】  図１に示すように、暗号文生成装置１００は、導出鍵生成部１１０と、補助導出鍵生成部１２０と、識別子別暗号文生成部１３０と、相対値暗号文生成１４０と、を含む。導出鍵生成部１１０は、主鍵１０１と文書１０２とに基づいて、導出鍵１０４を生成する。補助導出鍵生成部１２０は、主鍵１０１と文書１０２と導出鍵１０４とに基づいて、補助導出鍵１０５を生成する。識別子別暗号文生成部１３０は、文書１０２の識別子１０３と導出鍵１０４と補助導出鍵１０５とに基づいて、識別子１０３を暗号化した識別子別暗号文１０６を生成する。相対値暗号文生成１４０は、識別子１０３と導出鍵１０４とに基づいて、主鍵１０１と文書１０２と導出鍵１０４とから生成された相対値１０７を暗号化した相対値暗号文１０８を生成する。そして、暗号文生成装置１００は、識別子別暗号文１０６と相対値暗号文１０８とを含む文字列を文書１０２に対する暗号文１０９とす。
【００２２】  本実施形態によれば、導出鍵と補助導出鍵とを生成して暗号文生成に使用することにより、暗号化された数値の大小比較をすることができると共に、数値データの隠匿性を維持して情報の漏洩する機会を大幅に減らすことができる。
【００２３】  ［第２実施形態］  次に、本発明の第２実施形態に係る暗号文生成装置と、暗号文生成装置と暗号文比較装置とを含む暗号文比較システムについて説明する。本実施形態の暗号文比較システムにおいては、導出鍵生成部が、主鍵と文書とに基づいて、導出鍵を生成する。また、補助導出鍵生成部が、主鍵と文書と導出鍵とに基づいて、補助導出鍵を生成する。また、識別子別暗号文生成部が、文書の識別子と導出鍵と補助導出鍵とに基づいて、識別子を暗号化した識別子別暗号文を生成する。相対値暗号文生成部が、識別子と導出鍵とに基づいて、主鍵と文書と導出鍵とから生成された相対値を暗号化した相対値暗号文を生成する。そして、暗号文比較部が、第１文書から生成した第１導出鍵と、第１文書の第１識別子と、第１識別子を暗号化した第１識別子別暗号と第１相対値を暗号化した第１相対値暗号文とを有する第１暗号文と、第２文書の第２識別子と、第２識別子を暗号化した第２識別子別暗号と第２相対値を暗号化した第２相対値暗号文とを有する第２暗号文と、を用いて、第１暗号文の元である第１文書と第２暗号文の元である第２文書との大小関係を暗号文のままで判定する。
【００２４】  なお、導出鍵生成部と、補助導出鍵生成部と、識別子別暗号文生成部と、相対値暗号文生成部とを暗号文生成装置が備え、暗号文比較部を暗号文比較装置が備える。しかし、暗号文生成装置と暗号文比較装置とは別の装置でなく、１つに併合された装置であってもよい。
【００２５】  《前提技術》  本実施形態の技術を説明する前に、その前提技術である非特許文献２の技術の概要を説明する。
【００２６】  図１４は、前提技術となる暗号化装置１４１０の構成を示すブロック図である。また、図１５は、前提技術となる暗号化装置１４１０の処理手順を示すフローチャートである。
【００２７】  鍵Ｋ１４０１と、平文としてのある文書Ｍ１４０２がＭ＝(ｂ[1]，…，ｂ[n])で与えられたとき、暗号文Ｃ”１４０５を次のように生成する。なお、Ｃ[0]＝０とする。ｔ＝１，…，ｎに関してｂ[t]１４０３を選びだし(Ｓ１５０１)、鍵１４０１と暗号文のt-1番目のブロックｃ[t-1]１４０５も併せて利用して、ハッシュ関数等で実現される導出部１４１１を再帰的に用いて、暗号文のt番目のブロック要素ｃ[t]１４０４を、ｃ[t]＝Hash(K,(c[t-1],b[t]))により計算する（Ｓ１５０２）。暗号文Ｃ”１４０６をＣ”(ｃ[1]，…，ｃ[n])とする。暗号文Ｃ”の最初のｋ個のブロック要素=(ｃ[1]，…，ｃ[k])を、暗号文Ｃ”の接頭ｋブロック要素とよび、Ｃ”[k]と表すとする。この時、もし２つの平文が最初のｋ個まで同一であるならば、それ平文の暗号文も最初ｋ個まで等しいものとなる。このように、部分的な一致を暗号文のまま判別できる。なお、あるｋに関して最初のｋ個のブロック要素が２つの平文で一致するとき、一致する接頭がある、あるいは、ｋ個の接頭が一致すると言うこととする。
【００２８】  この暗号方式を使って暗号文の順序を比較する場合、特に複数の数の暗号文の集合から、ある数値ａより小さな数を暗号化した暗号文を復号することなく全て選びだしたい場合には、次のようにする。あるｋに関して、数値ａより小さな数の暗号文の接頭と比較対象の暗号文のｋ個の接頭が一致するが、数値ａより大きな数の暗号文の接頭と比較対象の暗号文のｋ個の接頭は一致しない、暗号文Ｃ”の接頭ｋブロック要素Ｃ”[k]の全ての集合をＰ(a)とする。この集合の大きさは数値ａより小さい数の個数より小さい。鍵を保持するものがＰ(a)を生成して、複数の暗号文の集合を保持するものに渡せば、後者は暗号文を復号することなくその所持する暗号文の集合から数値ａより小さな数を暗号化した暗号文を選びだすことができる。
【００２９】  （前提技術の課題）  しかしながら、前提技術においては、暗号文の最初のｋ個の一致を知ることができても、大小を直接判別することはできない。そのため、最初のｋ個の一致する、候補となる暗号文を全て送らねばならない。また、２つの暗号文の最初のｋ個が一致する判定は暗号化のための鍵を保持せずとも直接行うことができるので、これをデータベースに用いた場合、データベースから情報の漏洩する機会を増加させることになる。
【００３０】  以下の本実施形態の暗号方式によれば、暗号化された数値の列が与えられているとき、これらの数値だけからはそれらの大小を比較することはできないが、ある数値の暗号文に関して対応する比較の要求文を用いると、この暗号化された数値と列中の暗号化された数値との大小比較が可能になる。
【００３１】  《本実施形態で使用される関数および変数の定義》  まず、本実施形態で使用される関数および変数を定義する。文書には、全て識別子が割り当てられているとする。識別子と文書の組を(ＩＤ，Ｍ)のように表す。文書Ｍを、２進展開して、Ｍ＝Σi=0n-1ｂ[i]×2iとなるようなｂ[i]∈｛0,1｝を用いＭ＝(ｂ[0],ｂ[1],…,ｂ[n-1])と書き記すとする。ここで、ｎは文書Ｍのビット長である。ここで、kを安全変数とする。
【００３２】  本実施形態で用いるハッシュ関数Hash, Hash3, Hash2 をそれぞれ、Hash: ｛0,1｝* →｛0,1｝k, Hash3:｛0,1｝* →｛0,1,2｝, Hash2:｛0,1｝* →｛0,1｝ とする。
【００３３】  また、Ｋ∈｛0,1｝kを主鍵とする。各p=0,…,n-1 に関して、安全変数Ｌ[p]∈自然数、が定義されているとする。
【００３４】  《暗号文比較システム》  図２Ａおよび図２Ｂを参照して、本実施形態の暗号文生成装置２１０について説明する。
【００３５】  （システム構成）  図２Ａは、本実施形態に係る暗号文生成装置２１０を含む暗号文比較システム２００の構成を示すブロック図である。暗号文比較システム２００は、暗号文生成装置２１０と暗号文比較装置２２０とを含む。
【００３６】  暗号文生成装置２１０は、導出鍵生成部２１１と、補助導出鍵生成部２１２と、暗号文生成部２１３とを備える。導出鍵生成部２１１は、主鍵Ｋ２０１と文書Ｍ２０２とに基づいて導出鍵Ｄ２０４を生成する。補助導出鍵生成部２１２は、主鍵Ｋ２０１と文書Ｍ２０２と導出鍵Ｄ２０４とに基づいて補助導出鍵Ｇ２０５を生成する。暗号文生成部２１３は、主鍵Ｋ２０１と文書Ｍ２０２と導出鍵Ｄ２０４と補助導出鍵Ｇ２０５と識別子ＩＤ２０３とに基づいて、暗号文Ｃ，Ｆ２０６を生成する。なお、識別子ＩＤ２０３は、文書Ｍ２０２の識別子である。
【００３７】  暗号文生成装置２１０は、暗号文比較装置２２０に対して、識別子ＩＤ２０３と暗号文Ｃ，Ｆ２０６と導出鍵Ｄ２０４とを通知する。なお、暗号文生成装置２１０と暗号文比較装置２２０とは、その間を通信回線で接続していても、あるいは、一体化した装置であってもよい。また、通信回線は無線であっても有線であってもよい。
【００３８】  暗号文比較装置２２０は、暗号文比較部２２１を備える。暗号文比較部２２１は、暗号文生成装置２１０から、文書Ｍ２０２の識別子ＩＤ２０３、暗号文Ｃ,Ｆ２０６および導出鍵Ｄ２０４を取得する。暗号文比較部２２１は、識別子ＩＤ２０３、暗号文Ｃ,Ｆ２０６および導出鍵Ｄ２０４と、他の文書Ｍ’の識別子ＩＤ’２０７およびその暗号文Ｃ’,Ｆ’２０８とに基づいて、暗号文のままで文書Ｍと文書Ｍ’との大小関係を比較する。そして、暗号文比較部２２１は、暗号文比較部２２１の判定結果Ｒ２０９を出力する。
【００３９】  （暗号文比較システムを適用したサービス）  図２Ｂは、本実施形態に係る暗号文生成装置２１０を含む暗号文比較システム２００を適用したサービスを示す図である。なお、図２Ｂには、暗号文比較装置２２０としてのサービスサーバが保持するサービスを、暗号文生成装置２１０としての通信端末から暗号文で要求すると、要求されたサービスを暗号文のままで比較することで検索して応答する例を示す。
【００４０】  暗号文比較システム２００は、ネットワーク２４０を介して接続された、暗号文生成装置２１０としての複数の通信端末と、暗号文比較装置２２０としてのサービスサーバとを備える。また、暗号文比較システム２００は、細かい破線で示したように、サービスサーバがサービス情報データベース（以下、ＤＢ）に格納するサービス情報を提供するサービス情報提供サーバ２３０を備えてもよい。
【００４１】  暗号文生成装置２１０としての複数の通信端末から、実線矢印で示したように、主鍵を用いて本実施形態の暗号化を行なったサービス要求文の暗号文がサービスサーバに送信される。このサービス要求文の暗号文には、サービス利用者２５０が漏洩を望まない個人情報が含まれる。暗号文比較装置２２０としてのサービスサーバの暗号文比較部２２１は、サービス利用者２５０から取得した個人情報を含むサービス要求文を暗号文のまま、サービス情報ＤＢの同じ暗号化方式で暗号化されたサービス情報と比較して、検索をする。見付かったサービス情報は、破線矢印のように、暗号文で暗号文生成装置２１０としての複数の通信端末に送信される。サービス情報の暗号文は主鍵を用いて復号され、サービス利用者２５０にサービス情報が提供される。
【００４２】  このように、本実施形態を適用することで、暗号文のままで比較して検索が実行されるので、個人情報が漏洩する機会が無くなる。
【００４３】  なお、本実施形態の適用例は、図２Ｂに限定されない。例えば、あらかじめサービス利用者２５０がサービスサーバに登録した暗号化情報も、暗号文のままでデータベースからのデータ検索や、受信情報の判定に使用されることになり、情報が漏洩する機会を無くすことができる。そのため、クラウドサーバでもあるサービスサーバへの個人情報の登録を安心して行なえることになる。
【００４４】  《暗号文生成装置の機能構成》  図３乃至図５Ｂを参照して、本実施形態の暗号文生成装置２１０の各構成要素の機能構成を順に説明する。
【００４５】  （導出鍵生成部）  図３は、本実施形態に係る暗号文生成装置２１０の導出鍵生成部２１１の機能構成を示すブロック図である。導出鍵生成部２１１は、主鍵と文書とに基づいて導出鍵を生成する。
【００４６】  導出鍵生成部２１１は、導出部３１１を有する。導出部３１１の動作を次のようになる。主鍵Ｋ２０１と文書Ｍ２０２がＭ＝(ｂ[0],…,ｂ[n-1])としてブロックごとに与えられた場合、導出鍵Ｄ２０４を次のように生成する。初期値として、要素ｄ[n]＝Ｋとする。カウンタｉ＝n-1,…,0に関して降順に要素ｂ[i]３０１を選びだし、主鍵Ｋ２０１と導出鍵Ｄの要素ｄ[i+1]３０３も併せて利用して、導出部３１１を再帰的に用い、導出鍵Ｄの要素ｄ[i]３０２を、ｄ[i]＝Hash(K,(d[i+1],b[i]))、により生成する。その繰り返しの結果として、導出鍵Ｄ２０４をＤ＝(ｄ[0],ｄ[1],…,ｄ[n-1])とする。
【００４７】  （補助導出鍵生成部）  図４は、本実施形態に係る暗号文生成装置２１０の補助導出鍵生成部２１２の機能構成を示すブロック図である。補助導出鍵生成部２１２は、主鍵と文書と導出鍵とに基づいて、補助導出鍵を生成する。
【００４８】  補助導出鍵生成部２１２は、補助導出部４１１を有する。補助導出部４１１の動作を次のようになる。主鍵Ｋ２０１と文書Ｍ２０２のＭ＝(ｂ[0],…,ｂ[n-1])、導出鍵Ｄ２０４のＤ＝(ｄ[0],ｄ[1],…,ｄ[n-1])が与えられたとき、補助導出鍵Ｇを、次のように生成する。カウンタｊ＝0,…,n-1に関して昇順に、主鍵Ｋ２０１と、導出鍵Ｄのj+1番目の要素ｄ[j+1]４０３と、文書Ｍのj番目の要素ｂ[j]をビット反転した結果の1-b[j]４０１とを用いて、補助導出鍵Ｇのj番目の要素ｇ[j]４０２を、ｇ[j]＝Hash(K,d[j+1],1-b[j])、により生成する。導出補助鍵ＧをＧ＝(ｇ[0],ｇ[1],…,ｇ[n-1])とする。
【００４９】  （暗号文生成部）  図５Ａは、本実施形態に係る暗号文生成装置２１０の暗号文生成部２１３の機能構成を示すブロック図である。
【００５０】  暗号文生成部２１３は、相対値生成部５１１と、識別子別暗号文生成部５１２と、相対値隠蔽部５１３とを有する。ここで、相対値生成部５１１と相対値隠蔽部５１３とは、相対値暗号文生成部を構成する。相対値暗号文生成部は、識別子と導出鍵とに基づいて、主鍵と文書と導出鍵とから生成された相対値を暗号化した相対値暗号文を生成する。
【００５１】  相対値生成部５１１は、カウンタｑ＝0,…,n-1に関して昇順に相対値生成処理を繰り返し、主鍵Ｋ２０１と文書Ｍ２０２と導出鍵Ｄとを用いて、相対値の要素ｅ[q]５０１を、ｅ[q]＝Hash3(0,K,d[q+1])＋b[q] mod 3、により生成する。そして、相対値隠蔽部５１３は、ｄ[n]=Ｋとして、カウンタｑ＝0,…,n-1に関して相対値隠蔽処理を繰り返し、識別子ＩＤ２０３と導出鍵Ｄ２０４と相対値の要素ｅ[q]５０１とを用いて、相対値暗号文の要素ｆ[q]を、ｆ[q]＝Hash3(1,ID,d[q+1])＋e[q] mod 3、により生成する。相対値暗号文Ｆ５０３をＦ＝(ｆ[0],…,ｆ[n-1])とする。
【００５２】  また、識別子別暗号文生成部５１２は、文書の識別子と導出鍵と補助導出鍵とに基づいて、識別子を暗号化した識別子別暗号文を生成する。すなわち、識別子別暗号文生成部５１２は、カウンタｐ＝n-1,…,0に関して降順に、識別子ＩＤ２０３と導出鍵Ｄと補助導出鍵Ｇとを用いて、識別子別暗号文Ｃ５０２をＣ＝(ｃ[0],…,ｃ[n-1])として生成する。
【００５３】  そして、相対値生成部５１１は、暗号文Ｃ,Ｆ２０６をＣ,Ｆ＝((ｃ[0],…,ｃ[n-1]),(ｆ[0],…,ｆ[n-1]))として出力する。
【００５４】  （識別子別暗号文生成部）  図５Ｂは、本実施形態に係る識別子別暗号文生成部５１２の機能構成を示すブロック図である。
【００５５】  識別子別暗号文生成部５１２は、識別子別暗号文異常候補生成部５２１と導出鍵陽性検査部５２２と補助導出鍵陰性検査部５２３とを有する。識別子別暗号文生成部５１２は、識別子別暗号文Ｃ５０２を次のように生成する。識別子別暗号文異常候補生成部５２１は、カウンタｐ＝n-1,…,0に関して、要素ｃ[p]の候補をランダムに｛0,1｝L[p]から選ぶ。そして、次の２つの検査を通ることを確認する。どちらか一方でも通らなかったならばランダムに選んだ要素ｃ[p]は一度破棄して、ランダムに新たな候補を選び直す。両検査に通ればこれを要素ｃ[p]として採用する。導出鍵陽性検査部５２２は、導出鍵陽性検査として、識別子ＩＤと導出鍵Ｄとを用いて、０＝Hash2(ID,d[p],c[p]) mod 2が成り立つことを検査する。補助導出鍵陰性検査部５２３は、補助導出鍵陰性検査として、識別子ＩＤと補助導出鍵Ｇとを用いて、１＝Hash2(ID,g[p],c[p]) mod 2、が成り立つことを検査する。
【００５６】  《暗号文比較装置の機能構成》  図６は、本実施形態に係る暗号文比較装置２２０の暗号文比較部２２１の機能構成を示すブロック図である。
【００５７】  暗号文比較装置２２０は、図示しないが、暗号文生成装置２１０により暗号化された第１暗号文と第１識別子と第１導出鍵とを取得する第１暗号文取得部を備える。また、暗号文比較装置２２０は、図示しないが、暗号文生成装置２１０と同様の暗号化機能を有する装置により暗号化された第２暗号文と第２識別子とを取得する第２暗号文取得部を備える。そして、暗号文比較装置２２０は、第１暗号文、第１識別子、第１導出鍵、第２暗号文および第２識別子を用いて、第１暗号文の元である第１文書と第２暗号文の元である第２文書との大小関係を暗号文のままで判定する暗号文比較部２２１を備える。
【００５８】  図６においては、次の２つの暗号文を比較する例を説明する。識別子ＩＤ２０３の文書からは、本実施形態の暗号文生成方式で生成された、識別子ＩＤ２０３と、暗号文Ｃ,Ｆ＝((ｃ[0],…,ｃ[n-1]),(ｆ[0],…,ｆ[n-1]))の内の相対値暗号文Ｆ＝(ｆ[0],…,ｆ[n-1])と、導出鍵Ｄ２０４＝(ｄ[0],ｄ[1],…,ｄ[n-1])とが用いられる。比較対象としての識別子ＩＤ’２０７の文書からは、本実施形態の暗号文生成方式で生成された、識別子ＩＤ’２０７と、暗号文Ｃ’,Ｆ’＝((ｃ'[0],…,ｃ'[n-1]),(ｆ'[0],…,ｆ'[n-1]))とが用いられる。
【００５９】  暗号文比較部２２１は、最大不一致カウンタ決定部６１１と、相対値復元部６１２と、相対値比較判定部６１３とを備える。
【００６０】  最大不一致カウンタ決定部６１１は、カウンタｒ＝n-1から0まで降順に、識別子ＩＤ’２０７と、識別子ＩＤの導出鍵Ｄ２０４と、識別子ＩＤ’の識別子別暗号文Ｃ’６０１とを用いて、等式０＝Hash(ID',d[r],c’[r])、が成り立つかを確認していく。そして、始めてこの等式が成り立たなくなったカウンタｒを最大不一致カウンタｒ６０３とする。
【００６１】  相対値復元部６１２は、最大不一致カウンタｒにおいて、ｅ,ｅ'∈｛0,1,2｝なるｅ,ｅ'に関して、識別子ＩＤ２０３と、識別子ＩＤの相対値暗号文Ｆ５０３と、識別子ＩＤ’と、識別子ＩＤ’の相対値暗号文Ｆ’６０２とを用いて、ｆ [r]＝Hash3(1,ID,d[r+1])＋ｅ mod 3ｆ'[r]＝Hash3(1,ID',d[r+1])＋ｅ' mod 3が成り立つかを確認する。そして、成り立つ場合のｅとｅ'とからなる相対値の組６０４を生成する。
【００６２】  相対値比較判定部６１３はｅとｅ'との組に関して、ｅ−ｅ'＝(1 mod 3)であれば、識別子ＩＤの文書が識別子ＩＤ’の文書より大きいことを表す信号(例えば“０”)を判定結果Ｒ２０９として出力する。一方、ｅ−ｅ'＝(2 mod 3)であれば、識別子ＩＤ’の文書が識別子ＩＤの文書より大きいことを表す信号(例えば“１”)を判定結果Ｒ２０９として出力する。
【００６３】  《暗号文生成装置のハードウェア構成》  図７は、本実施形態に係る暗号文生成装置２１０のハードウェア構成を示すブロック図である。
【００６４】  図７で、ＣＰＵ７１０は演算制御用のプロセッサであり、プログラムを実行することで図２Ａの暗号文生成装置２１０の各機能構成部を実現する。ＲＯＭ７２０は、初期データおよびプログラムなどの固定データおよびプログラムを記憶する。また、通信制御部７３０は、ネットワークを介して暗号文比較装置２２０としてのサービスサーバと通信する。なお、ＣＰＵ７１０は１つに限定されず、複数のＣＰＵであっても、あるいは画像処理用のＧＰＵを含んでもよい。
【００６５】  ＲＡＭ７４０は、ＣＰＵ７１０が一時記憶のワークエリアとして使用するランダムアクセスメモリである。ＲＡＭ７４０には、本実施形態の実現に必要なデータを記憶する領域が確保されている。変数記憶部７４１は、ＣＰＵ７１０が処理する対象の平文の文書や暗号文、あるいは鍵など、あるいは、カウンタｉ，ｊなどの一時記憶部である。暗号文生成テーブル７４２は、変数記憶部７４１のデータおよびパラメータから本実施形態の暗号文を生成するために使用するテーブルである。入出力データ記憶部７４３は、入出力インタフェース７６０を介して入出力される入出力データを記憶する。送受信データ記憶部７４４は、通信制御部７３０を介して送受信される送受信データを記憶する。
【００６６】  ストレージ７５０には、データベースや各種のパラメータ、あるいは本実施形態の実現に必要な以下のデータまたはプログラムが記憶されている。データ記憶領域７５１は、本実施形態の暗号文生成装置２１０としての通信端末の処理に必要なデータを記憶する。かかるデータ記憶領域７５１には、本実施形態の暗号化アルゴリズム７５２が記憶される。暗号化アルゴリズム７５２には、Hash,Hash2,Hash3などのハッシュ関数も含まれる。ストレージ７５０には、以下のプログラムが格納される。通信端末制御プログラム記憶領域７５３は、通信端末制御用のプログラムを記憶する。導出鍵生成モジュール７５４は、主鍵と暗号化する文書とを用いて導出鍵を生成するモジュールである。補助導出鍵生成モジュール７５５は、主鍵と暗号化する文書と導出鍵とを用いて補助導出鍵を生成するモジュールである。識別子別暗号文生成モジュール７５６は、導出鍵と補助導出鍵と文書の識別子とを用いて識別子別暗号文を生成するモジュールである。相対値暗号文生成モジュール７５７は、主鍵と暗号化する文書と導出鍵と補助導出鍵と文書の識別子とを用いて相対値暗号文を生成するモジュールである。
【００６７】  入出力インタフェース７６０は、入出力機器との入出力データをインタフェースする。入出力インタフェース７６０には、表示部７６１と、キーボード、タッチパネル、ポインティンデバイスなどの操作部７６２と、本通信端末の他の周辺機器７６３とが接続される。さらに、スピーカやマイクなどの音声入出力部、ＧＰＳ（Global Positioning System)位置生成部やカメラなどを接続することができる。
【００６８】  なお、図７のＲＡＭ７４０やストレージ７５０には、暗号文生成装置が有する汎用の機能や他の実現可能な機能に関連するプログラムやデータは図示されていない。
【００６９】  （暗号文生成テーブル）  図８は、本実施形態に係る暗号文生成テーブル７４２の構成を示す図である。暗号文生成テーブル７４２は、暗号化される文書から暗号文比較装置に送信する暗号文を生成するために使用される。
【００７０】  暗号文生成テーブル７４２は、識別子ＩＤ２０３と対応付けて、文書Ｍ２０２と主鍵Ｋ２０１とを記憶する。また、暗号文生成テーブル７４２は、識別子ＩＤ２０３と対応付けて、導出された導出鍵Ｄ２０４と補助導出鍵Ｇ２０５とを記憶する。さらに、暗号文生成テーブル７４２は、識別子ＩＤ２０３と対応付けて、暗号化された識別子別暗号文Ｃと相対値暗号文Ｆとを含む暗号文Ｃ，Ｆ２０６を記憶する。
【００７１】  《暗号文生成装置の処理手順》  図９は、本実施形態に係る暗号文生成装置２１０の処理手順を示すフローチャートである。このフローチャートは、図７のＣＰＵ７１０がＲＡＭ７４０を使用しながら実行し、図２Ａの暗号文生成装置２１０の各機能構成部を実現する。なお、図９の処理順序はこれに限定されない。
【００７２】  暗号文生成装置２１０は、ステップＳ９０１において、主鍵と暗号化する文書とから導出鍵Ｄを生成する。次に、暗号文生成装置２１０は、ステップＳ９０３において、主鍵と暗号化する文書と導出鍵とから補助導出鍵Ｇを生成する。暗号文生成装置２１０は、ステップＳ９０５において、暗号化する文書の識別子と、導出鍵および補助導出鍵とから識別子別暗号文Ｃを生成する。暗号文生成装置２１０は、ステップＳ９０７において、主鍵と、暗号化する文書と、暗号化する文書の識別子と、導出鍵とから相対値暗号文Ｆを生成する。そして、暗号文生成装置２１０は、ステップＳ９０９において、識別子別暗号文Ｃと相対値暗号文Ｆとからなる暗号文を出力する。
【００７３】  （導出鍵生成処理）  図１０Ａは、本実施形態に係る導出鍵生成処理（Ｓ９０１）の手順を示すフローチャートである。
【００７４】  暗号文生成装置２１０は、ステップＳ１０１１において、降順の再帰ループを行なうためにカウンタｉ＝ｎとする。暗号文生成装置２１０は、ステップＳ１０１３において、カウンタｉを１つデクリメントする。暗号文生成装置２１０は、ステップＳ１０１５において、文書Ｍ２０２からブロックｂ[i]を抽出する。暗号文生成装置２１０は、ステップＳ１０１７において、主鍵Ｋ２０１と、ブロック鍵１０１１に記憶された１つ前の導出鍵の要素ｄ[i+1]と、要素ｂ[i]とを用いて、ｄ[i]＝Hash(K,(d[i+1],b[i]))、により導出鍵の要素ｄ[i]を算出する。そして、算出された導出鍵の要素ｄ[i]をブロック鍵１０１１に記憶する。暗号文生成装置２１０は、ステップＳ１０１９において、カウンタｉ＝０か否かを判定し、ｉ＝０になるまでステップＳ１０１３〜Ｓ１０１９を繰り返す。カウンタｉ＝０になると、暗号文生成装置２１０は、ステップＳ１０２１において、導出鍵Ｄ＝(ｄ[0],ｄ[1],…,ｄ[n-1])を記憶する。
【００７５】  （補助導出鍵生成処理）  図１０Ｂは、本実施形態に係る補助導出鍵生成処理（Ｓ９０３）の手順を示すフローチャートである。
【００７６】  暗号文生成装置２１０は、ステップＳ１０３１において、昇順の再帰ループを行なうためにカウンタｊ＝０とする。暗号文生成装置２１０は、ステップＳ１０３３において、導出鍵Ｄ２０４の要素ｄ[j+1]を抽出する。暗号文生成装置２１０は、ステップＳ１０３５において、文書Ｍ２０２からブロック要素ｂ[j]を抽出して、１−ｂ[j]と反転する。暗号文生成装置２１０は、ステップＳ１０３７において、主鍵Ｋと、導出鍵の要素ｄ[i+1]と、反転ブロック要素（１−ｂ[i]）とを用いて、ｇ[j]＝Hash(K,d[j+1],1-b[j])、により補助導出鍵の要素ｇ[j]を算出する。そして、算出された補助導出鍵の要素ｇ[j]をブロック鍵１０２１に記憶する。暗号文生成装置２１０は、ステップＳ１０３９において、カウンタｊを１つインクリメントする。暗号文生成装置２１０は、ステップＳ１０４１において、カウンタｊ＝ｎか否かを判定し、ｊ＝ｎになるまでステップＳ１０３３〜Ｓ１０４１を繰り返す。カウンタｊ＝ｎになると、暗号文生成装置２１０は、ステップＳ１０４３において、補助導出鍵Ｇ＝(ｇ[0],ｇ[1],…,ｇ[n-1])を記憶する。
【００７７】  （識別子別暗号文生成処理）  図１０Ｃは、本実施形態に係る識別子別暗号文生成処理（Ｓ９０５）の手順を示すフローチャートである。
【００７８】  暗号文生成装置２１０は、ステップＳ１０５１において、降順の再帰ループを行なうためにカウンタｐ＝ｎとする。暗号文生成装置２１０は、ステップＳ１０５３において、カウンタｐを１つデクリメントする。暗号文生成装置２１０は、ステップＳ１０５５において、安全変数（Ｌ[p]∈自然数）による｛0,1｝L[p]から要素ｃ[p]の候補をランダムに選択する。暗号文生成装置２１０は、ステップＳ１０５７において、識別子ＩＤと導出鍵Ｄとを用いて、ランダムに選択した要素ｃ[p]が第１条件：０＝Hash2(ID,d[p],c[p]) mod 2を満足しているか否かを判定する。第１条件を満たしてないのであれば、ステップＳ１０５５に戻って、他の要素ｃ[p]をランダムに選択する。第１条件を満たしていれば、暗号文生成装置２１０は、ステップＳ１０５７において、識別子ＩＤと補助導出鍵Ｇとを用いて、ランダムに選択した要素ｃ[p]が第２条件：１＝Hash2(ID,g[p],c[p]) mod 2を満足しているか否かを判定する。第２条件を満たしてないのであれば、ステップＳ１０５５に戻って、他の要素ｃ[p]をランダムに選択する。第２条件を満たしていれば、暗号文生成装置２１０は、ステップＳ１０６１において、要素ｃ[p]を識別子別暗号文Ｃの要素として採用する。暗号文生成装置２１０は、ステップＳ１０６３において、カウンタｐ＝０か否かを判定し、ｐ＝０になるまでステップＳ１０５３〜Ｓ１０６３を繰り返す。カウンタｐ＝０になると、暗号文生成装置２１０は、ステップＳ１０６５において、識別子別暗号文Ｃ＝(ｃ[0],ｃ[1],…,ｃ[n-1])を記憶する。
【００７９】  （相対値暗号文生成処理）  図１０Ｄは、本実施形態に係る相対値暗号文生成処理（Ｓ９０７）の手順を示すフローチャートである。
【００８０】  暗号文生成装置２１０は、ステップＳ１０７１において、昇順の再帰ループを行なうためにカウンタｑ＝０とする。暗号文生成装置２１０は、ステップＳ１０７３において、主鍵Ｋ２０１と導出鍵Ｄ２０４と暗号化する文書Ｍ２０２とを用いて、相対値の要素ｅ[q]＝Hash3(0,K,d[q+1])＋b[q] mod 3、を算出する。次に、暗号文生成装置２１０は、ステップＳ１０７５において、識別子ＩＤ２０３と導出鍵Ｄ２０４とを用いて、相対値暗号文Ｆの要素ｆ[i]＝Hash3(1,ID,d[q+1])＋e[q] mod 3、を算出する。暗号文生成装置２１０は、ステップＳ１０７７において、カウンタｑを１つインクリメントする。暗号文生成装置２１０は、ステップＳ１０７９において、カウンタｑ＝ｎか否かを判定し、ｑ＝ｎになるまでステップＳ１０７３〜Ｓ１０７９を繰り返す。カウンタｑ＝ｎになると、暗号文生成装置２１０は、ステップＳ１０８１において、相対値暗号文Ｆ＝(ｆ[0],ｆ[1],…,ｆ[n-1])を記憶する。
【００８１】  《暗号文比較装置のハードウェア構成》  図１１は、本実施形態に係る暗号文比較装置２２０のハードウェア構成を示すブロック図である。
【００８２】  図１１で、ＣＰＵ１１１０は演算制御用のプロセッサであり、プログラムを実行することで図２Ａの暗号文比較装置２２０の各機能構成部を実現する。ＲＯＭ１１２０は、初期データおよびプログラムなどの固定データおよびプログラムを記憶する。また、通信制御部１１３０は、ネットワークを介して暗号文生成装置２１０としての通信端末と通信する。なお、ＣＰＵ１１１０は１つに限定されず、複数のＣＰＵであっても、あるいは画像処理用のＧＰＵを含んでもよい。
【００８３】  ＲＡＭ１１４０は、ＣＰＵ１１１０が一時記憶のワークエリアとして使用するランダムアクセスメモリである。ＲＡＭ１１４０には、本実施形態の実現に必要なデータを記憶する領域が確保されている。変数記憶部１１４１は、ＣＰＵ１１１０が処理する対象の暗号文、識別子あるいは相対値など、あるいは、カウンタｒなどの一時記憶部である。暗号文比較テーブル１１４２は、変数記憶部１１４１のデータおよびパラメータから本実施形態の暗号文を比較するために使用するテーブルである。送受信データ記憶部１１４３は、通信制御部１１３０を介して送受信される送受信データを記憶する。
【００８４】  ストレージ１１５０には、データベースや各種のパラメータ、あるいは本実施形態の実現に必要な以下のデータまたはプログラムが記憶されている。データ記憶領域１１５１は、本実施形態の暗号文比較装置２２０としてのサービスサーバの処理に必要なデータを記憶する。かかるデータ記憶領域１１５１は、サービス情報ＤＢ１１５２と本実施形態の暗号文比較アルゴリズム１１５３とが記憶される。サービス情報ＤＢ１１５２には、暗号文のままで検索されて提供されるサービス情報が格納されている。暗号文比較アルゴリズム１１５３には、Hash,Hash2,Hash3などのハッシュ関数も含まれる。ストレージ１１５０には、以下のプログラムが格納される。サービスサーバ制御プログラム記憶領域１１５４は、サービスサーバ制御用のプログラムを記憶する。暗号文比較モジュール１１５５は、以下の３つのモジュールを含む。最大不一致カウンタ決定モジュール１１５６は、識別子ＩＤの導出鍵Ｄと、識別子ＩＤ’と、識別子ＩＤ’の識別子別暗号文Ｃ’とを用いて、等式０＝Hash(ID',d[r],c’[r])が成り立たなくなる最大の不一致となるカウンタを決定するモジュールである。相対値復元モジュール１１５７は、識別子ＩＤと、識別子ＩＤの導出鍵Ｄと、識別子ＩＤの相対値暗号文Ｆと、識別子ＩＤ’と、識別子ＩＤ’の相対値暗号文Ｆ’とを用いて、相対値の組みｅ，ｅ’を復元するモジュールである。相対値比較判定モジュール１１５８は、相対値の組みｅ，ｅ’から識別子ＩＤの文書と識別子ＩＤ’の文書との大小関係を暗号文のままで比較して判定するモジュールである。
【００８５】  なお、図１１のＲＡＭ１１４０やストレージ１１５０には、暗号文比較装置が有する汎用の機能や他の実現可能な機能に関連するプログラムやデータは図示されていない。
【００８６】  （暗号文比較テーブル）  図１２は、本実施形態に係る暗号文比較テーブル１１４２の構成を示す図である。暗号文比較テーブル１１４２は、識別子ＩＤの文書と識別子ＩＤ’の文書との大小関係を暗号文のままで比較して判定するために使用される。
【００８７】  暗号文比較テーブル１１４２は、文書の識別子１２０１に対応付けて、大小判定に使用される、導出鍵１２０２と、ＩＤおよびＩＤ’のそれぞれの識別子別暗号文と相対値暗号文とからなる暗号文１２０３とを記憶する。また、暗号文比較テーブル１１４２は、比較する文書の組みに対応付けて、最大不一致カウンタｒ６０３と、相対値の組みｅ，ｅ’６０４と、判定結果Ｒ２０９とを記憶する。判定結果Ｒ２０９には、例えば、識別子ＩＤの文書Ｍが識別子ＩＤ’の文書Ｍ’より大きいと判定されたら“１”をセットし、識別子ＩＤ’の文書Ｍ’が識別子ＩＤの文書Ｍより大きいと判定されたら“０”をセットする。なお、判定結果の提示に制限はない。さらに、暗号文比較テーブル１１４２は、求められた比較結果となった暗号文を、判定結果通知暗号文１２０４として記憶してもよい。
【００８８】  なお、図１２には、暗号文比較テーブル１１４２に使用するため、暗号文比較部２２１が取得する識別子ＩＤの暗号文１２１０と識別子ＩＤ’の暗号文１２２０とも図示している。
【００８９】  《暗号文比較装置の処理手順》  図１３は、本実施形態に係る暗号文比較装置２２０の処理手順を示すフローチャートである。このフローチャートは、図１１のＣＰＵ１１１０がＲＡＭ１１４０を使用しながら実行し、図２Ａの暗号文比較装置２２０の各機能構成部を実現する。
【００９０】  暗号文比較装置２２０は、ステップＳ１３０１において、識別子ＩＤの導出鍵Ｄ２０４と識別子ＩＤ’２０７と識別子ＩＤ’の識別子別暗号文Ｃ’６０１とを用いて、最大不一致カウンタを決定する。すなわち、カウンタｒ＝n-1から0まで降順に、等式０＝Hash(ID',d[r],c’[r])、が成り立つかを確認していき、始めてこの等式が成り立たなくなったカウンタｒを最大不一致カウンタとする。
【００９１】  暗号文比較装置２２０は、ステップＳ１３０３において、識別子ＩＤ２０３と識別子ＩＤの導出鍵Ｄ２０４と識別子ＩＤの相対値暗号文Ｆ５０３と識別子ＩＤ’２０７と識別子ＩＤ’の相対値暗号文Ｆ’６０２とを用いて、相対値を復元する。すなわち、最大不一致カウンタｒにおいて、ｅ,ｅ'∈｛0,1,2｝なるｅ,ｅ'に関して、ｆ [r]＝Hash3(1,ID,d[r+1])＋ｅ mod 3ｆ'[r]＝Hash3(1,ID',d[r+1])＋ｅ' mod 3が成り立つかを確認する。そして、成り立つ場合のｅとｅ'とからなる相対値の組を生成する。
【００９２】  暗号文比較装置２２０は、ステップＳ１３０５において、ｅとｅ'とからなる相対値の組に基づいて相対値を比較する。そして、暗号文比較装置２２０は、ステップＳ１３０７において、相対値の比較に基づいて比較結果を出力する。すなわち、ｅとｅ'との組に関して、ｅ−ｅ'＝(1 mod 3)であれば、識別子ＩＤの文書が識別子ＩＤ’の文書より大きいことを表す信号(例えば“０”)を出力する。一方、ｅ−ｅ'＝(2 mod 3)であれば、識別子ＩＤ’の文書が識別子ＩＤの文書より大きいことを表す信号(例えば“１”)を出力する。
【００９３】  本実施形態によれば、導出鍵と補助導出鍵とを生成して暗号文生成に使用することにより、暗号化された数値の大小比較をすることができると共に、隠匿性を維持して情報の漏洩する機会を大幅に減らすことができる。
【００９４】  例えば、数値データを含む文書から鍵情報を用いて相対値を生成し、異なる暗号文それぞれに対応した相対値を復元する構成を有することにより、暗号化された異なる文書の隠匿性を維持しつつ文書の大小比較を行うことができる。
【００９５】  また、文書を特定する識別子に基づく識別子別暗号文を生成して、相対値に付加することにより、文書の一部が同じであっても異なる識別子により異なる暗号文が生成されるので、暗号化された異なる文書の隠匿性を維持しつつ文書の大小比較を行うことができる。すなわち、導出鍵と補助導出鍵とを用いた２つの条件に従って、識別子に基づく識別子別暗号文を生成したので、さらに、暗号化された異なる文書の隠匿性を維持しつつ文書の大小比較を行うことができる。
【００９６】  具体的には、次のような効果が期待できる。例えば、暗号文の集合が与えられたとし、全ての要素には異なる識別子が割り振られているとする。また、主鍵は与えられていないとする。なお、以下で使用する“ｉ”や“ｋ”は、上記実施形態の説明中と必ずしも一致しない。
【００９７】  このような条件において、導出鍵も与えられていない場合には、如何なる平文に対応する導出鍵も分からないため、第三者には各暗号文がどのような平文に対応するかは分からない。また、同じ平文に対応する、あるいは接頭の一致する平文に対応する２つの暗号文が与えられたとしても、それぞれに対応する導出鍵の接頭は一致するが、それらから異なる識別子を用いて暗号化されているため両者の一致あるいは接頭の一致を判別することはできない。
【００９８】  しかし、ある暗号文とこれに対応する導出鍵が与えられている場合、ある暗号文とこの暗号文とでそれらの対応する平文の接頭が一致するかを、本実施形態の比較の方法を用いて判別することができる。すなわち、導出鍵陽性検査から２つの平文のｉ番目以上のビットが一致すれば、片方の暗号文に関する導出鍵を用いた識別子別暗号文のi番目のビットが導出鍵陽性検査を通過する。また、ｉ＋１番目以上のビットは一致するが、ｉ番目のビットが一致しない場合、片方の暗号文（暗号文Ａとする）の導出鍵を用いた、他方の暗号文（暗号文Ｂとする）の識別子別暗号文のｉ番目のビットの導出鍵陽性検査は通らないことが保障されている。なぜなら、この検査の結果は、暗号文Ｂの補助導出鍵を用いて暗号文Ｂのｉ番目のビットの補助導出鍵陰性検査に通ることと同値であるからである。暗号文Ｂの識別子別暗号文はそのように生成されている。
【００９９】  一方、２つのカウンタｋ個まで接頭の一致する平文の暗号文があったとして、その対応する導出鍵があった得られているとする。ｋ以上のカウンタｉに関する要素ｂ[i]が一致するため各要素ｅ[i]とｄ[i]とｆ[i]も一致する。しかし、ｆ[k-1]に関しては一致せず、その２つのｆ[k-1]の値から両者の大小を判定することができる。ここで重要なのは、２つのｆ[i]が一致しないと、それらの値から２つのｂ[i]を決定することができるが、ｆ[i]が一致するとこの値からｂ[i]を決定することができないことである。すなわち、接頭ｋが一致する２つの平文の暗号からそのｋブロック目での不一致と大小関係、すなわちそれらの値も知ることができるが、ｋ番目以下のブロックでの値を知ることはできない。従って、本実施形態の暗号文生成によれば、例えば、同一の平文（文書）に対応する、あるいは接頭部分が一致する平文（文書）に対応する２つの暗号文が与えられた場合であっても、それぞれに対応する導出鍵の接頭は一致するが、異なる識別子を用いて暗号化がなされる。そのため、両平文の一致、あるいは両平文における接頭の一致が判別できないように暗号化することができる。
【０１００】  このように、本実施形態では、暗号化された異なる複数の暗号文について、暗号文に含まれる文字列からそれぞれの暗号文に対応する平文の大小判定がなされるのを有効に抑制することができる。このため、暗号文の鍵に関する知識を全く持たない第３者が平文である数値データの大小関係を調べることを有効に抑制することが可能となる。
【０１０１】  以上のように、本実施形態では、数値データが暗号化された暗号文が与えられたときに、これらの暗号文だけからはそれらの元の数値データの大小を比較することを抑制できる。且つ、本実施形態では、データベースに対して正規利用者からある数値の暗号文に関して対応する数値データの大小比較の要求がなされた場合に、暗号かされた異なる暗号文に含まれる文字列から元の数値データと大小の比較を行うことができる。
【０１０２】  このため、本実施形態のデータベースシステムでは、データベース利用者は、暗号化される前の数値データを管理者等に知られることなく、データベースに含まれる、特定の暗号化された数値より大きい（または小さい）数値データを取得することができる。また、本実施形態では、２つの暗号文に含まれる文字列（例えば、接頭文字列）が一致する場合でも、暗号化のための鍵を知らない第３者がこの接頭文字列の一致に基づいて暗号文に対応する平文を探り当てることを有効に抑制することができる。このため、例えば、暗号化キーを知らない第三者が、データベースを構成する数値データとデータベース内の暗号化された数値データとの、数値データ同士の大小関係を利用して特定の数値データを抽出したり、取得したりするのを抑制することができる。これにより、データベースに含まれるデータのセキュリティを有効に高めることができる。
【０１０３】  ［他の実施形態］  例えば、本発明を用いてデータベースの利用者が要素を暗号化してデータベースに登録した場合、データベースの管理者は各要素の値を知ることができない。一方、利用者がある値の暗号文およびその対応する導出鍵を生成してデータベースに送付すれば、管理者はこの数より大きいあるいは小さな数の暗号文を選びだして利用者に返送することができる。そしてこの時、管理者は送られてきた暗号文とそれぞれの暗号文とが、それらの対応する平文がどのブロックで一致しなくなり、本実施形態の暗号文生成方式は、どちらが大きいかを知ることはできるが、その他の情報を得ることができない性質を持つ。
【０１０４】  以上、実施形態を参照して本発明を説明したが、本発明は上記実施形態に限定されるものではない。本発明の構成や詳細には、本発明のスコープ内で当業者が理解し得る様々な変更をすることができる。また、それぞれの実施形態に含まれる別々の特徴を如何様に組み合わせたシステムまたは装置も、本発明の範疇に含まれる。
【０１０５】  また、本発明は、複数の機器から構成されるシステムに適用されてもよいし、単体の装置に適用されてもよい。さらに、本発明は、実施形態の機能を実現する制御プログラムが、システムあるいは装置に直接あるいは遠隔から供給される場合にも適用可能である。したがって、本発明の機能をコンピュータで実現するために、コンピュータにインストールされる制御プログラム、あるいはその制御プログラムを格納した媒体、その制御プログラムをダウンロードさせるＷＷＷ(Worl、Wid、Web)サーバも、本発明の範疇に含まれる。特に、少なくとも、上述した実施形態に含まれる処理ステップをコンピュータに実行させる制御プログラムを格納した非一時的コンピュータ可読媒体（non-transitor、compute、readabl、medium）は本発明の範疇に含まれる。
【０１０６】  ［実施形態の他の表現］  上記の実施形態の一部または全部は、以下の付記のようにも記載されうるが、以下には限られない。（付記１）  主鍵と文書とに基づいて、導出鍵を生成する導出鍵生成手段と、  前記主鍵と前記文書と前記導出鍵とに基づいて、補助導出鍵を生成する補助導出鍵生成手段と、  前記文書の識別子と前記導出鍵と前記補助導出鍵とに基づいて、前記識別子を暗号化した識別子別暗号文を生成する識別子別暗号文生成手段と、  前記識別子と前記導出鍵とに基づいて、前記主鍵と前記文書と前記導出鍵とから生成された相対値を暗号化した相対値暗号文を生成する相対値暗号文生成手段と、  を備え、  前記識別子別暗号文と前記相対値暗号文とを含む文字列を前記文書に対する暗号文とする暗号文生成装置。（付記２）  前記導出鍵生成手段は、ｉ＝n-1から0の降順に従い、前記主鍵と前記文書の要素ｂ[i]と前記導出鍵の既に生成された要素ｄ[i+1]とを用いて、第１ハッシュ関数のHash：｛0,1｝*→｛0,1｝kに従ったHash(K,(d[i+1],b[i]))により前記導出鍵の要素ｄ[i]を生成し、  前記補助導出鍵生成手段は、ｊ＝0からn-1の昇順に従い、前記主鍵と前記文書の要素ｂ[j]のビット反転（１−ｂ[j]）と前記導出鍵の要素ｄ[j+1]とを用いて、前記第１ハッシュ関数に従ったHash(Ｋ,ｄ[j+1],1-ｂ[j])により補助導出鍵の要素ｇ[j]を生成する付記１に記載の暗号文生成装置。（付記３）  前記識別子別暗号文生成手段は、ｐ＝n-1,…,0の降順に従い、安全変数Ｌ[p]∈自然数の場合に｛0,1｝L[p]から識別子別暗号文の要素ｃ[p]の候補をランダムに選び、識別子ＩＤと前記導出鍵の要素ｄ[p]とを用いて、第２ハッシュ関数のHash2：｛0,1｝*→｛0,1｝において、０＝Hash2(ID,d[p],c[p]) mod 2が成り立ち、かつ、前記識別子ＩＤと前記補助導出鍵の要素ｇ[p]とを用いて、前記第２ハッシュ関数において、１＝Hash2(ID,g[p],c[p]) mod 2が成り立つ場合に、前記識別子別暗号文の要素ｃ[p]として採用する付記１または２に記載の暗号文生成装置。（付記４）  前記相対値暗号文生成手段は、    前記主鍵と前記導出鍵と前記文書とを用いて、相対値を生成する相対値生成手段と、    前記識別子と前記導出鍵と前記相対値とを用いて、相対値暗号文を生成する相対値隠蔽手段と、  を備え、  前記相対値生成手段は、ｑ＝0からn-1の昇順に従い、前記主鍵と前記文書と前記導出鍵とを用いて、相対値の要素ｅ[q]を第３ハッシュ関数のHash3：｛0,1｝*→｛0,1,2｝に従ってｅ[q]＝Hash3(0,K,d[q+1])＋b[q] mod 3により生成し、  前記相対値隠蔽手段は、ｄ[n]=Ｋとして、ｑ＝0からn-1の昇順に従い、識別子ＩＤと前記導出鍵の要素ｄ[q]と前記相対値の要素ｅ[q]とを用いて、相対値暗号文の要素ｆ[q]を前記第３ハッシュ関数に従ってｆ[q]＝Hash3(1,ID,d[q+1])＋e[q] mod 3により生成する、付記１乃至３のいずれか１項に記載の暗号文生成装置。（付記５）  主鍵と文書とに基づいて、導出鍵を生成する導出鍵生成ステップと、  前記主鍵と前記文書と前記導出鍵とに基づいて、補助導出鍵を生成する補助導出鍵生成ステップと、  前記文書の識別子と前記導出鍵と前記補助導出鍵とに基づいて、前記識別子を暗号化した識別子別暗号文を生成する識別子別暗号文生成ステップと、  前記識別子と前記導出鍵とに基づいて、前記主鍵と前記文書と前記導出鍵とから生成された相対値を暗号化した相対値��号文を生成する相対値暗号文生成ステップと、  を含み、  前記識別子別暗号文と前記相対値暗号文とを含む文字列を前記文書に対する暗号文とする暗号文生成装置の制御方法。（付記６）  主鍵と文書とに基づいて、導出鍵を生成する導出鍵生成ステップと、  前記主鍵と前記文書と前記導出鍵とに基づいて、補助導出鍵を生成する補助導出鍵生成ステップと、  前記文書の識別子と前記導出鍵と前記補助導出鍵とに基づいて、前記識別子を暗号化した識別子別暗号文を生成する識別子別暗号文生成ステップと、  前記識別子と前記導出鍵とに基づいて、前記主鍵と前記文書と前記導出鍵とから生成された相対値を暗号化した相対値暗号文を生成する相対値暗号文生成ステップと、  をコンピュータに実行させる暗号文生成装置の制御プログラムであって、  前記識別子別暗号文と前記相対値暗号文とを含む文字列を前記文書に対する暗号文とする暗号文生成装置の制御プログラム。（付記７）  付記１乃至４のいずれか１項に記載の暗号文生成装置により暗号化された第１暗号文と第１識別子と第１導出鍵とを取得する第１暗号文取得手段と、  付記１乃至４のいずれか１項に記載の暗号文生成装置により暗号化された第２暗号文と第２識別子とを取得する第２暗号文取得手段と、  前記第１暗号文、前記第１識別子、前記第１導出鍵、前記第２暗号文および前記第２識別子を用いて、前記第１暗号文の元である第１文書と前記第２暗号文の元である第２文書との大小関係を暗号文のままで判定する暗号文比較手段と、  を備える暗号文比較装置。（付記８）  前記暗号文比較手段は、    最大不一致カウンタ決定手段と、    相対値復元手段と、    相対値比較判定手段と、  を有し、  前記最大不一致カウンタ決定手段は、ｒ＝n-1から0まで降順に従い、第２識別子ＩＤ’と、第１識別子ＩＤの導出鍵の要素ｄ[r]と、前記第２識別子ＩＤ’の識別子別暗号文の要素ｃ’[r]とを用いて、第１ハッシュ関数のHash：｛0,1｝*→｛0,1｝kに従った等式０＝Hash(ID',d[r],c’[r])が成り立つか否かを確認し、始めてこの等式が成り立たなくなったｒを最大不一致カウンタｒとし、  前記相対値復元手段は、前記最大不一致カウンタｒにおいて、ｅ,ｅ'∈｛0,1,2｝なるｅ,ｅ'に関して、前記第１識別子ＩＤと、前記導出鍵の要素ｄ[r+1}、前記第１識別子ＩＤの相対値暗号文の要素ｆ[r]と、前記第２識別子ＩＤ’と、前記第２識別子ＩＤ’の相対値暗号文の要素ｆ’[r]とを用いて、第３ハッシュ関数のHash3：｛0,1｝*→｛0,1,2｝に従って、ｆ [r]＝Hash3(1,ID,d[r+1])＋ｅ mod 3ｆ'[r]＝Hash3(1,ID',d[r+1])＋ｅ' mod 3が成り立つか否かを確認し、成り立つ場合のｅとｅ'とからなる相対値の組を生成し、  前記相対値比較判定手段は、前記ｅとｅ'との組に関して、ｅ−ｅ'＝(1 mod 3)であれば、前記第１識別子ＩＤの文書が前記第２識別子ＩＤ’の文書より大きいことを表す信号を判定結果として出力し、一方、ｅ−ｅ'＝(2 mod 3)であれば、前記第２識別子ＩＤ’の文書が前記第１識別子ＩＤの文書より大きいことを表す信号を判定結果として出力する、付記７に記載の暗号文比較装置。（付記９）  付記１乃至４のいずれか１項に記載の暗号文生成装置により暗号化された第１暗号文と第１識別子と第１導出鍵とを取得する第１暗号文取得ステップと、  付記１乃至４のいずれか１項に記載の暗���文生成装置により暗号化された第２暗号文と第２識別子とを取得する第２暗号文取得ステップと、  前記第１暗号文、前記第１識別子、前記第１導出鍵、前記第２暗号文および前記第２識別子を用いて、前記第１暗号文の元である第１文書と前記第２暗号文の元である第２文書との大小関係を暗号文のままで判定する暗号文比較ステップと、  を含む暗号文比較装置の制御方法。（付記１０）  付記１乃至４のいずれか１項に記載の暗号文生成装置により暗号化された第１暗号文と第１識別子と第１導出鍵とを取得する第１暗号文取得ステップと、  付記１乃至４のいずれか１項に記載の暗号文生成装置により暗号化された第２暗号文と第２識別子とを取得する第２暗号文取得ステップと、  前記第１暗号文、前記第１識別子、前記第１導出鍵、前記第２暗号文および前記第２識別子を用いて、前記第１暗号文の元である第１文書と前記第２暗号文の元である第２文書との大小関係を暗号文のままで判定する暗号文比較ステップと、  をコンピュータに実行させる暗号文比較装置の制御プログラム。（付記１１）  主鍵と文書とに基づいて、導出鍵を生成する導出鍵生成手段と、  前記主鍵と前記文書と前記導出鍵とに基づいて、補助導出鍵を生成する補助導出鍵生成手段と、  前記文書の識別子と前記導出鍵と前記補助導出鍵とに基づいて、前記識別子を暗号化した識別子別暗号文を生成する識別子別暗号文生成手段と、  前記識別子と前記導出鍵とに基づいて、前記主鍵と前記文書と前記導出鍵とから生成された相対値を暗号化した相対値暗号文を生成する相対値暗号文生成手段と、  前記導出鍵生成手段が第１文書から生成した第１導出鍵と、前記第１文書の第１識別子と、前記識別子別暗号文生成手段が前記第１識別子を暗号化した第１識別子別暗号と前記相対値暗号文生成手段が第１相対値を暗号化した第１相対値暗号文とを有する第１暗号文と、第２文書の第２識別子と、前記識別子別暗号文生成手段が前記第２識別子を暗号化した第２識別子別暗号と前記相対値暗号文生成手段が第２相対値を暗号化した第２相対値暗号文とを有する第２暗号文と、を用いて、前記第１暗号文の元である前記第１文書と前記第２暗号文の元である前記第２文書との大小関係を暗号文のままで判定する暗号文比較手段と、  を備える暗号文比較システム。（付記１２）  主鍵と文書とに基づいて、導出鍵を生成する導出鍵生成ステップと、  前記主鍵と前記文書と前記導出鍵とに基づいて、補助導出鍵を生成する補助導出鍵生成ステップと、  前記文書の識別子と前記導出鍵と前記補助導出鍵とに基づいて、前記識別子を暗号化した識別子別暗号文を生成する識別子別暗号文生成ステップと、  前記識別子と前記導出鍵とに基づいて、前記主鍵と前記文書と前記導出鍵とから生成された相対値を暗号化した相対値暗号文を生成する相対値暗号文生成ステップと、  前記導出鍵生成ステップにおいて第１文書から生成した第１導出鍵と、前記第１文書の第１識別子と、前記識別子別暗号文生成ステップにおいて前記第１識別子を暗号化した第１識別子別暗号と前記相対値暗号文生成ステップにおいて第１相対値を暗号化した第１相対値暗号文とを有する第１暗号文と、第２文書の第２識別子と、前記識別子別暗号文生成ステップにおいて前記第２識別子を暗号化した第２識別子別暗号と前記相対値暗号文生成ステップにおいて第２相対値を暗号化した第２相対値暗号文とを有する第２暗号文と、を用いて、前記第１暗号文の元である前記第１文書と前記第２暗号文の元である前記第２文書との大小関係を暗号文のままで判定する暗号文比較ステップと、  を含む暗号文比較方法。（付記１３）  主鍵と文書とに基づいて、導出鍵を生成する導出鍵生成手段と、  前記主鍵と前記文書と前記導出鍵とに基づいて、補助導出鍵を生成する補助導出鍵生成手段と、  を備え  前記導出鍵生成手段は、ｉ＝n-1から0の降順に従い、前記主鍵と前記文書の要素ｂ[i]と前記導出鍵の既に生成された要素ｄ[i+1]とを用いて、第１ハッシュ関数のHash：｛0,1｝*→｛0,1｝kに従ったHash(K,(d[i+1],b[i]))により前記導出鍵の要素ｄ[i]を生成し、  前記補助導出鍵生成手段は、ｊ＝0からn-1の昇順に従い、前記主鍵と前記文書の要素ｂ[j]のビット反転（１−ｂ[j]）と前記導出鍵の要素ｄ[j+1]とを用いて、前記第１ハッシュ関数に従ったHash(Ｋ,ｄ[j+1],1-ｂ[j])により補助導出鍵の要素ｇ[j]を生成する鍵導出装置。
【０１０７】  この出願は、２０１３年１０月８日に出願された日本国特許出願  特願２０１３−２１１２１４号を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【図１】
0006504405.tif 000002
【図２Ａ】
0006504405.tif 000003
【図２Ｂ】
0006504405.tif 000004
【図３】
0006504405.tif 000005
【図４】
0006504405.tif 000006
【図５Ａ】
0006504405.tif 000007
【図５Ｂ】
0006504405.tif 000008
【図６】
0006504405.tif 000009
【図７】
0006504405.tif 000010
【図８】
0006504405.tif 000011
【図９】
0006504405.tif 000012
【図１０Ａ】
0006504405.tif 000013
【図１０Ｂ】
0006504405.tif 000014
【図１０Ｃ】
0006504405.tif 000015
【図１０Ｄ】
0006504405.tif 000016
【図１１】
0006504405.tif 000017
【図１２】
0006504405.tif 000018
【図１３】
0006504405.tif 000019
【図１４】
0006504405.tif 000020
【図１５】
0006504405.tif 000021