(57)【要約】      （修正有）【課題】自装置が記憶する第１データ列と、相手装置が記憶する第２データ列を互いに開示することなくデータ列間の移動付き編集距離を算出する情報処理装置を提供する。【解決手段】情報処理装置は、自装置の第１データ列の第１フレーズのハッシュ値を基に決定した位置のビットをオンにしたベクトルを相手装置が復号可能な準同型暗号で暗号化した第１ベクトルと、相手装置の第２データ列の第２フレーズのハッシュ値を基に決定した位置のビットをオンにしたベクトルを相手装置が復号可能な準同型暗号で暗号化した第２ベクトルとを基に、辞書ベクトルを生成する。自装置で復号可能な準同型暗号で暗号化した第１照会ベクトルを送信し、相手装置から受信した暗号ラベル値を復号してラベル値を取得する。相手装置が復号可能な準同型暗号で暗号化した第２照会ベクトルを受信すると、辞書ベクトルと第２照会ベクトルとを基に決定した暗号ラベル値を相手装置に返送する。【選択図】図３
2020188438.tif 000002
【特許請求の範囲】
【請求項１】
複数の第１フレーズを含む第１データ列と準同型暗号の第１秘密鍵とを記憶部に記憶し、相手装置が記憶する複数の第２フレーズを含む第２データ列と前記第１データ列との移動付き編集距離を算出する情報処理装置であって、
入力値に対する出力値を一意に決定する関数を前記複数の第１フレーズの各々に対して適用した出力値を基に決定した第１位置のビットをオンした第１ビットベクトルを、前記相手装置が記憶する準同型暗号の第２秘密鍵に対応する第２公開鍵で暗号化した第１暗号化ビットベクトルを生成するビットベクトル生成部と、
前記複数の第２フレーズの各々に前記関数を適用した出力値を基に決定した第２位置のビットをオンにした第２ビットベクトルを前記第２公開鍵で暗号化した第２暗号化ビットベクトルを前記相手装置から受信すると、前記第１暗号化ビットベクトルと前記第２暗号化ビットベクトルとを基に、前記第１データ列および前記第２データ列の少なくとも一方に含まれるフレーズの各々に対応する位置のビットをオンにした第１辞書ベクトルを生成する辞書生成部と、
前記複数の第１フレーズのうちの特定フレーズに前記関数を適用した出力値を基に決定した要素を所定値としたベクトルを前記第１秘密鍵に対応する第１公開鍵で暗号化した第１照会ベクトルを前記相手装置に送信し、前記相手装置から受信した第１暗号ラベル値を前記第１秘密鍵で復号して前記特定フレーズに対応する第１ラベル値を取得するラベル取得部と、
前記複数の第２フレーズのうちの特定フレーズに前記関数を適用した出力値を基に決定した要素を所定値としたベクトルを前記第２公開鍵で暗号化した第２照会ベクトルを前記相手装置から受信すると、前記第１辞書ベクトルと前記第２照会ベクトルとを基に決定した第２暗号ラベル値を前記相手装置に返送するラベル付与部と、を備える、
情報処理装置。
【請求項２】
前記複数の第１フレーズの各々に対応する第１ラベル値を前記第１位置に配置したベクトルを前記第２公開鍵で暗号化した第１ラベルベクトルを生成する第１ラベルベクトル生成部と、
前記複数の第２フレーズの各々について、前記第２暗号ラベル値を前記第２秘密鍵で復号した第２ラベル値を前記第２位置に配置したベクトルを前記第２公開鍵で暗号化した第２ラベルベクトルを前記相手装置から受信すると、前記第１ラベルベクトルと前記第２ラベルベクトルの要素同士を減算したベクトルにノイズを混入させる第１ノイズ混入処理を行った第１ノイズベクトルを前記相手装置に返送する差分返送部と、
前記第１ノイズベクトルの各要素の絶対値を要素とするベクトルを前記第２公開鍵で暗号化した第２ノイズベクトルを前記相手装置から受信すると、前記第２ノイズベクトルから前記第１ノイズ混入処理で混入させたノイズを除去して暗号化距離ベクトルを生成し、生成した前記暗号化距離ベクトルを前記相手装置に返送する距離返送部と、をさらに備える、
請求項１に記載の情報処理装置。
【請求項３】
前記複数の第１フレーズの各々に対応する第１ラベル値を前記第１位置に配置したベクトルを前記第１公開鍵で暗号化した第３ラベルベクトルを生成し、前記第３ラベルベクトルを前記相手装置に送信する第２ラベルベクトル生成部と、
前記複数の第２フレーズの各々について、前記第２暗号ラベル値を前記第２秘密鍵で復号した第２ラベル値を前記第２位置に配置したベクトルを前記第１公開鍵で暗号化した第４ラベルベクトルと前記第３ラベルベクトルの要素同士を減算したベクトルにノイズを混入させる第２ノイズ混入処理を行った第３ノイズベクトルを前記相手装置から受信すると、前記第３ノイズベクトルを前記第１秘密鍵で復号し、復号したベクトルの各要素の絶対値を要素とするベクトルを前記第１公開鍵で暗号化した第４ノイズベクトルを前記相手装
置に返送する再暗号ベクトル返送部と、
前記第４ノイズベクトルから前記ノイズを除去した暗号化距離ベクトルを前記相手装置から受信すると、前記暗号化距離ベクトルを前記第１秘密鍵で復号して距離ベクトルを生成し、前記距離ベクトルの各要素の和を算出する距離算出部と、をさらに備える、
請求項１または２に記載の情報処理装置。
【請求項４】
前記第２公開鍵は、Ｐａｉｌｌｉｅｒ暗号で用いる第２２公開鍵を含み、
前記第２秘密鍵は、前記第２２公開鍵に対応する第２２秘密鍵を含み、
前記第１ラベルベクトルおよび前記第２ラベルベクトルは、前記第２２公開鍵で暗号化される、
請求項２に記載の情報処理装置。
【請求項５】
前記第１公開鍵は、Ｐａｉｌｌｉｅｒ暗号で用いる第１２公開鍵を含み、
前記第２秘密鍵は、前記第１２公開鍵に対応する第１２秘密鍵を含み、
前記第３ラベルベクトルおよび前記第４ラベルベクトルは、前記第１２公開鍵で暗号化される、
請求項３に記載の情報処理装置。
【請求項６】
前記第２公開鍵は、Ｂｏｎｅｈ−Ｇｏｈ−Ｎｉｓｓｉｍ（ＢＧＮ）暗号で用いる第２１公開鍵を含み、
前記第２秘密鍵は、前記第２１公開鍵に対応する第２１秘密鍵を含み、
前記第１暗号化ビットベクトルと前記第２暗号化ビットベクトルは、前記第２１公開鍵で暗号化されたベクトルであり、
前記辞書生成部が前記第１暗号化ビットベクトルと前記第２暗号化ビットベクトルとを基に前記第１辞書ベクトルを生成する処理は、前記第１暗号化ビットベクトルの要素のそれぞれと前記第２暗号化ビットベクトルの要素のそれぞれとの１回の乗算を含み、
前記辞書生成部は、前記第１辞書ベクトルにノイズを混入させる第３ノイズ混入処理を行った第１ノイズ辞書ベクトルを前記相手装置に送信し、前記第１ノイズ辞書ベクトルを前記第２１秘密鍵で復号したベクトルを前記第２１公開鍵で暗号化した第２ノイズ辞書ベクトルを前記相手装置から受信すると、前記第２ノイズ辞書ベクトルから前記第３ノイズ混入処理で混入させたノイズを除去して前記第１辞書ベクトルを復元する、
請求項１から５のいずれか一項に記載の情報処理装置。
【請求項７】
複数の第１フレーズを含む第１データ列と準同型暗号の第１秘密鍵とを記憶部に記憶し、相手装置が記憶する複数の第２フレーズを含む第２データ列と前記第１データ列との移動付き編集距離を算出する情報処理装置が、
入力値に対する出力値を一意に決定する関数を前記複数の第１フレーズの各々に対して適用した出力値を基に決定した第１位置のビットをオンした第１ビットベクトルを、前記相手装置が記憶する準同型暗号の第２秘密鍵に対応する第２公開鍵で暗号化した第１暗号化ビットベクトルを生成するビットベクトル生成ステップと、
前記複数の第２フレーズの各々に前記関数を適用した出力値を基に決定した第２位置のビットをオンにした第２ビットベクトルを前記第２公開鍵で暗号化した第２暗号化ビットベクトルを前記相手装置から受信すると、前記第１暗号化ビットベクトルと前記第２暗号化ビットベクトルとを基に、前記第１データ列および前記第２データ列の少なくとも一方に含まれるフレーズの各々に対応する位置のビットをオンにした第１辞書ベクトルを生成する辞書生成ステップと、
前記複数の第１フレーズのうちの特定フレーズに前記関数を適用した出力値を基に決定した要素を所定値としたベクトルを前記第１秘密鍵に対応する第１公開鍵で暗号化した第１照会ベクトルを前記相手装置に送信し、前記相手装置から受信した第１暗号ラベル値を前記第１秘密鍵で復号して前記特定フレーズに対応する第１ラベル値を取得するラベル取
得ステップと、
前記複数の第２フレーズのうちの特定フレーズに前記関数を適用した出力値を基に決定した要素を所定値としたベクトルを前記第２公開鍵で暗号化した第２照会ベクトルを前記相手装置から受信すると、前記第１辞書ベクトルと前記照会ベクトルとを基に決定した第２暗号ラベル値を前記相手装置に返送するラベル付与ステップと、を実行する、
情報処理方法。
【請求項８】
複数の第１フレーズを含む第１データ列と準同型暗号の第１秘密鍵とを記憶部に記憶し、相手装置が記憶する複数の第２フレーズを含む第２データ列と前記第１データ列との移動付き編集距離を算出する情報処理装置に、
入力値に対する出力値を一意に決定する関数を前記複数の第１フレーズの各々に対して適用した出力値を基に決定した第１位置のビットをオンした第１ビットベクトルを、前記相手装置が記憶する準同型暗号の第２秘密鍵に対応する第２公開鍵で暗号化した第１暗号化ビットベクトルを生成するビットベクトル生成ステップと、
前記複数の第２フレーズの各々に前記関数を適用した出力値を基に決定した第２位置のビットをオンにした第２ビットベクトルを前記第２公開鍵で暗号化した第２暗号化ビットベクトルを前記相手装置から受信すると、前記第１暗号化ビットベクトルと前記第２暗号化ビットベクトルとを基に、前記第１データ列および前記第２データ列の少なくとも一方に含まれるフレーズの各々に対応する位置のビットをオンにした第１辞書ベクトルを生成する辞書生成ステップと、
前記複数の第１フレーズのうちの特定フレーズに前記関数を適用した出力値を基に決定した要素を所定値としたベクトルを前記第１秘密鍵に対応する第１公開鍵で暗号化した第１照会ベクトルを前記相手装置に送信し、前記相手装置から受信した第１暗号ラベル値を前記第１秘密鍵で復号して前記特定フレーズに対応する第１ラベル値を取得するラベル取得ステップと、
前記複数の第２フレーズのうちの特定フレーズに前記関数を適用した出力値を基に決定した要素を所定値としたベクトルを前記第２公開鍵で暗号化した第２照会ベクトルを前記相手装置から受信すると、前記第１辞書ベクトルと前記照会ベクトルとを基に決定した第２暗号ラベル値を前記相手装置に返送するラベル付与ステップと、を実行させる、
情報処理プログラム。
【請求項９】
複数の第１フレーズを含む第１データ列と準同型暗号の第１秘密鍵とを第１記憶部に記憶する第１装置と、複数の第２フレーズを含む第２データ列と準同型暗号の第２秘密鍵とを第２記憶部に記憶する第２装置とを含む情報処理システムであって、
前記第１装置は、
入力値に対する出力値を一意に決定する関数を前記複数の第１フレーズの各々に対して適用した出力値を基に決定した第１位置のビットをオンした第１ビットベクトルを、前記第２秘密鍵に対応する第２公開鍵で暗号化した第１暗号化ビットベクトルを生成する第１ベクトル生成部と、
第２暗号化ビットベクトルを前記第２装置から受信すると、前記第１暗号化ビットベクトルと前記第２暗号化ビットベクトルとを基に、前記第１データ列および前記第２データ列の少なくとも一方に含まれるフレーズの各々に対応する位置のビットをオンにした第１辞書ベクトルを生成する第１辞書生成部と、
前記第１秘密鍵に対応する第１公開鍵で前記第１ビットベクトルを暗号化した第３暗号化ビットベクトルを生成して前記第２装置に送信する第１送信部と、
前記複数の第１フレーズのうちの特定フレーズに前記関数を適用した出力値を基に決定した要素を所定値としたベクトルを前記第１秘密鍵に対応する第１公開鍵で暗号化した第１照会ベクトルを前記第２装置に送信し、前記第２装置から受信した第１暗号ラベル値を前記第１秘密鍵で復号して前記特定フレーズに対応する第１ラベル値を取得する第１ラベル取得部と、
第２照会ベクトルを前記第２装置から受信すると、前記第１辞書ベクトルと前記第２照会ベクトルとを基に決定した第２暗号ラベル値を前記第２装置に送信する第１ラベル付与部と、
前記複数の第１フレーズの各々に対応する第１ラベル値を前記第１位置に配置したベクトルを前記第２公開鍵で暗号化した第１ラベルベクトルを生成する第１ラベルベクトル生成部と、
第２ラベルベクトルを前記第２装置から受信すると、前記第１ラベルベクトルと前記第２ラベルベクトルの要素同士を減算したベクトルにノイズを混入させる第１ノイズ混入処理を行った第１ノイズベクトルを前記第２装置に返送する差分返送部と、
第２ノイズベクトルを前記第２装置から受信すると、前記第２ノイズベクトルから前記第１ノイズ混入処理で混入させたノイズを除去して暗号化距離ベクトルを生成し、前記暗号化距離ベクトルを前記第２装置に返送する距離返送部と、を備え、
前記第２装置は、
前記複数の第２フレーズの各々に前記関数を適用した出力値を基に決定した第２位置のビットをオンにした第２ビットベクトルを前記第１公開鍵で暗号化した第４暗号化ビットベクトルを生成する第２ベクトル生成部と、
前記第３暗号化ビットベクトルを前記第１装置から受信すると、前記第３暗号化ビットベクトルと前記第４暗号化ビットベクトルとを基に、前記第１データ列および前記第２データ列の少なくとも一方に含まれるフレーズの各々に対応する位置のビットをオンにした第２辞書ベクトルを生成する第２辞書生成部と、
前記第２公開鍵で前記第２ビットベクトルを暗号化した第２暗号化ビットベクトルを生成して前記第１装置に送信する第２送信部と、
前記複数の第２フレーズのうちの特定フレーズに前記関数を適用した出力値を基に決定した要素を所定値としたベクトルを前記第２公開鍵で暗号化した前記第２照会ベクトルを前記第１装置に送信し、前記第１装置から受信した第２暗号ラベル値を前記第２秘密鍵で復号して前記特定フレーズに対応する第２ラベル値を取得する第２ラベル取得部と、
前記第１照会ベクトルを前記第１装置から受信すると、前記第２辞書ベクトルと前記第１照会ベクトルとを基に決定した第１暗号ラベル値を前記第１装置に送信する第２ラベル付与部と、
前記複数の第２フレーズの各々について、前記第２暗号ラベル値を前記第２秘密鍵で復号した第２ラベル値を前記第２位置に配置したベクトルを前記第２公開鍵で暗号化した前記第２ラベルベクトルを前記第１装置に送信する第３送信部と、
前記第１ノイズベクトルを前記第２秘密鍵で復号し、復号したベクトルの各要素の絶対値を要素とするベクトルを前記第２公開鍵で暗号化した第２ノイズベクトルを前記第１装置に返送する再暗号ベクトル返送部と、
前記暗号化距離ベクトルを受信すると、前記暗号化距離ベクトルを前記第２秘密鍵で復号して距離ベクトルを生成し、前記距離ベクトルの各要素の和を算出する距離算出部と、を備える、
情報処理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、情報処理方法、情報処理プログラムおよび情報処理システムに関する。
【背景技術】
【０００２】
データの類似度を距離関数によって算出する様々な技術が提案されている。距離関数としては、例えば、ハミング距離に例示される編集距離やマンハッタン距離を挙げることができる。特許文献１、２では、準同型暗号を利用することで、暗号化した状態で２つのデータ間のハミング距離を算出する技術が提案されている。特許文献３では、マンハッタン距離を近似的に算出する技術が提案されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０１４−１２６８６５号公報
【特許文献２】特開２０１４−１２６８６６号公報
【特許文献３】特許第５５４２４７４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
情報の類似度を算出する場合に、編集距離よりも移動付き編集距離（Ｅｄｉｔ  Ｄｉｓｔａｎｃｅ  ｗｉｔｈ  Ｍｏｖｅｓ、ＥＤＭ）の方が適している場合がある。移動付き編集距離では、編集距離で認められた操作（挿入、削除、置換）に加えて、部分文字列の移動が認められる。移動付き編集距離では長い文字列同士の一致を加味した類似度を計算できるため、文章の剽窃検出やＤｅｏｘｙｒｉｂｏｎｕｃｌｅｉｃ  Ａｃｉｄ（ＤＮＡ）の類似性の判定等への応用が期待できる。自装置と相手装置とが互いに自身の保有する情報を相手に開示することなく移動付き編集距離を算出する技術は未だ提案されていない。
【０００５】
開示の技術の１つの側面は、互いに情報を開示することなく移動付き編集距離を算出できる情報処理装置、情報処理方法、情報処理プログラムおよび情報処理システムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
開示の技術の１つの側面は、次のような情報装置によって例示される。本情報処理装置は、複数の第１フレーズを含む第１データ列と準同型暗号の第１秘密鍵とを記憶部に記憶し、相手装置が記憶する複数の第２フレーズを含む第２データ列と前記第１データ列との移動付き編集距離を算出する情報処理装置である。本情報処理装置は、入力値に対する出力値を一意に決定する関数を前記複数の第１フレーズの各々に対して適用した出力値を基に決定した第１位置のビットをオンした第１ビットベクトルを、前記相手装置が記憶する準同型暗号の第２秘密鍵に対応する第２公開鍵で暗号化した第１暗号化ビットベクトルを生成するビットベクトル生成部と、前記複数の第２フレーズの各々に前記関数を適用した出力値を基に決定した第２位置のビットをオンにした第２ビットベクトルを前記第２公開鍵で暗号化した第２暗号化ビットベクトルを前記相手装置から受信すると、前記第１暗号化ビットベクトルと前記第２暗号化ビットベクトルとを基に、前記第１データ列および前記第２データ列の少なくとも一方に含まれるフレーズの各々に対応する位置のビットをオンにした第１辞書ベクトルを生成する辞書生成部と、前記複数の第１フレーズのうちの特定フレーズに前記関数を適用した出力値を基に決定した要素を所定値としたベクトルを前記第１秘密鍵に対応する第１公開鍵で暗号化した第１照会ベクトルを前記相手装置に送信し、前記相手装置から受信した第１暗号ラベル値を前記第１秘密鍵で復号して前記特定フレーズに対応する第１ラベル値を取得するラベル取得部と、前記複数の第２フレーズのうちの特定フレーズに前記関数を適用した出力値を基に決定した要素を所定値としたベクトルを前記第２公開鍵で暗号化した第２照会ベクトルを前記相手装置から受信すると、前記第１辞書ベクトルと前記第２照会ベクトルとを基に決定した第２暗号ラベル値を前記相手装置に返送するラベル付与部と、を備える。
【発明の効果】
【０００７】
開示の技術は、互いに情報を開示することなく移動付き編集距離の算出ができる。
【図面の簡単な説明】
【０００８】
【図１】図１は、実施形態に係る類似性秘匿検索システムのシステム構成の一例を示す図である。
【図２】図２は、実施形態に係る類似性秘匿検索システムの論理構成の一例を示す図である。
【図３】図３は、実施形態に係る類似性秘匿検索システムによるラベル取得処理の処理フローの一例を示す図である。
【図４】図４は、実施形態におけるフレーズ辞書を構築する処理の処理フローの一例を示す図である。
【図５】図５は、図４のステップＳ２１におけるベクトル初期化処理を模式的に示す図である。
【図６】図６は、図４のステップＳ２２におけるベクトルの乗算処理を模式的に示す図である。
【図７】図７は、図４のステップＳ２３におけるベクトルの加算処理を模式的に示す図である。
【図８】図８は、図４のステップＳ２４におけるベクトルの減算処理を模式的に示す図である。
【図９】図９は、図４のステップＳ２５におけるベクトルを変形する処理を模式的に示す図である。
【図１０】図１０は、ラベル取得処理およびラベル付与処理の処理フローの一例を示す図である。
【図１１】図１１は、実施形態における距離算出処理の処理シーケンスの一例を示す図である。
【発明を実施するための形態】
【０００９】
実施形態では、情報処理装置が記憶する第１データ列を相手装置に開示せず、また、相手装置が記憶する第２データ列を本情報処理装置に開示せずに、第１データ列と第２データ列との間の移動付き編集距離を算出する情報処理装置、情報処理方法、情報処理プログラムおよび情報処理システムについて説明する。
【００１０】
≪情報処理装置の構成≫
実施形態に係る情報処理装置は、例えば、複数の第１フレーズを含む第１データ列と準同型暗号の第１秘密鍵とを記憶部に記憶し、相手装置が記憶する複数の第２フレーズを含む第２データ列と前記第１データ列との移動付き編集距離を算出する情報処理装置である。本情報処理装置は、入力値に対する出力値を一意に決定する関数を前記複数の第１フレーズの各々に対して適用した出力値を基に決定した第１位置のビットをオンした第１ビットベクトルを、前記相手装置が記憶する準同型暗号の第２秘密鍵に対応する第２公開鍵で暗号化した第１暗号化ビットベクトルを生成するビットベクトル生成部と、前記複数の第２フレーズの各々に前記関数を適用した出力値を基に決定した第２位置のビットをオンに
した第２ビットベクトルを前記第２公開鍵で暗号化した第２暗号化ビットベクトルを前記相手装置から受信すると、前記第１暗号化ビットベクトルと前記第２暗号化ビットベクトルとを基に、前記第１データ列および前記第２データ列の少なくとも一方に含まれるフレーズの各々に対応する位置のビットをオンにした第１辞書ベクトルを生成する辞書生成部と、前記複数の第１フレーズのうちの特定フレーズに前記関数を適用した出力値を基に決定した要素を所定値としたベクトルを前記第１秘密鍵に対応する第１公開鍵で暗号化した第１照会ベクトルを前記相手装置に送信し、前記相手装置から受信した第１暗号ラベル値を前記第１秘密鍵で復号して前記特定フレーズに対応する第１ラベル値を取得するラベル取得部と、前記複数の第２フレーズのうちの特定フレーズに前記関数を適用した出力値を基に決定した要素を所定値としたベクトルを前記第２公開鍵で暗号化した第２照会ベクトルを前記相手装置から受信すると、前記第１辞書ベクトルと前記第２照会ベクトルとを基に決定した第２暗号ラベル値を前記相手装置に返送するラベル付与部と、を備える。
【００１１】
（第１データ列、第２データ列）
第１データ列と第２データ列のそれぞれは、例えば、文字列である。文字列は、例えば、文章であってもよいし、Ｄｅｏｘｙｒｉｂｏｎｕｃｌｅｉｃ  Ａｃｉｄ（ＤＮＡ）の塩基配列を示すものであってもよい。第１データ列に含まれる複数の第１フレーズのそれぞれは、例えば、第１データ列を所定文字数ごとに区切った文字列である。第１フレーズは、隣り合った第１フレーズの組み合わせを含んでもよい。第２データ列に含まれる複数の第２フレーズについても同様である。
【００１２】
（移動付き編集距離）
本実施形態に係る情報処理装置は、第１データ列と第２データ列との移動付き編集距離（Ｅｄｉｔ  Ｄｉｓｔａｎｃｅ  ｗｉｔｈ  Ｍｏｖｅｓ、ＥＤＭ）を算出するシステムに適用する情報処理装置である。移動付き編集距離では、編集距離（Ｅｄｉｔ  Ｄｉｓｔａｎｃｅ、ＥＤ）が許容する文字の置換、挿入、削除の各操作に加えて、部分文字列を移動する操作を許容する。移動付き編集距離では、許容された範囲の操作によって、第１データ列および第２データ列のうちの一方のデータ列を他方のデータ列に変形する操作の最小回数によって類似度を示す。
【００１３】
例えば、第１データ列の一例として「ａａａａｉｓｂｂｂｂ」を挙げ、第２データ列の一例として「ｂｂｂｂｉｓａａａａ」を挙げ、これら第１データ列と第２データ列との類似度を編集距離および移動付き編集距離でそれぞれ算出する例について説明する。編集距離では、上記の通り、文字の置換、挿入、削除が許容される。編集距離で許容される操作によって文字列Ｘを文字列Ｙに変形するには、文字列Ｘの文字のうち「ｉｓ」の前に位置する「ａ」４文字のそれぞれを「ｂ」に置換し、「ｉｓ」の後の「ｂ」４文字のそれぞれを「ａ」置換すればよい。すなわち、編集距離で許容される操作によって文字列Ｘを文字列Ｙに変形する操作の最小回数は「８」であるため、編集距離による類似度は「８」となる。
【００１４】
移動付き編集距離では、上記の通り、編集距離で許容される操作に加えて、部分文字列の移動も許容される。移動付き編集距離で許容される操作によって文字列Ｘを文字列Ｙに変形するには、文字列Ｘの文字のうち「ｉｓ」の前に位置する「ａ」４文字を「ｉｓ」の後ろに移動させ、「ｉｓ」の後に位置する「ｂ」４文字を「ｉｓ」の前に移動すればよい。移動付き編集距離で許容される操作によって文字列Ｘを文字列Ｙに変形する操作の最小回数は、「２」であるため、移動付き編集距離による類似度は「２」となる。移動付き編集距離は、複数の文字を含む文字列の移動を許容することにより、文章の剽窃やＤＮＡの塩基配列の類似性の判定等について、編集距離よりも有効な指標となる。
【００１５】
移動付き編集距離は、第１データ列に含まれる第１フレーズのそれぞれと、第２データ
列に含まれる第２フレーズのそれぞれについてラベルを付与し、ラベルを所定位置に配置したベクトル間のＬ１距離（マンハッタン距離）とほぼ等しいことが理論的に保障される。移動付き編集距離とＬ１距離とがほぼ等しいことを示す参考文献としては、Ｇ．  ＣｏｒｍｏｄｅおよびＳ．Ｍｕｔｈｕｋｒｉｓｈｎａｎによる「Ｔｈｅ  ｓｔｒｉｎｇ  ｅｄｉｔ  ｄｉｓｔａｎｃｅ  ｍａｔｃｈｉｎｇ  ｐｒｏｂｌｅｍ  ｗｉｔｈ  ｍｏｖｅｓ．
ＡＣＭ  Ｔｒａｎｓ．  Ａｌｇｏｒ．，  ３（１）：Ａｒｔｉｃｌｅ  ２，  ２００７．」を挙げることができる。
【００１６】
第１データ列に含まれる第１フレーズのそれぞれに対応するラベルを要素とするベクトルをベクトルＶＴ１、第２データ列に含まれる第２フレーズのそれぞれに対応するラベルを要素とするベクトルをベクトルＶＴ２とすると、ベクトルＶＴ１およびベクトルＶＴ２のＬ１距離Ｌ１Ｔ１Ｔ２は、例えば、ベクトルＶＴ１およびベクトルＶＴ２のそれぞれの要素の差の絶対値の和として以下の式（１）によって算出される。
【数１】
2020188438.tif 000003
【００１７】
式（１）において、ＮはベクトルＶＴ１およびベクトルＶＴ２の要素数である。式（１）によって算出したＬ１距離は、移動付き編集距離とほぼ等しいことが理論的に保障される。
【００１８】
本情報処理装置は、ラベル付与の基となる第１辞書ベクトルを生成し、この第１辞書ベクトルを用いてラベルの付与を行う。第１辞書ベクトルの生成において、相手装置から受信する第２暗号化ビットベクトルは、本情報処理装置が秘密鍵を有しない第２公開鍵で暗号化される。また、第１暗号化ビットベクトルおよび第２暗号化ビットベクトルのそれぞれは、準同型暗号を用いて暗号化される。
【００１９】
（準同型暗号）
準同型暗号では、平文に対して所定の演算を行った結果と、当該平文を暗号化したデータに対して所定の演算を行った演算結果を復号した結果とが一致する。すなわち、準同型暗号では、暗号化したデータに対する演算処理を復号せずに実行することができる。準同型暗号としては、Ｅｌｇａｍａｌ暗号、Ｐａｉｌｌｉｅｒ暗号、Ｇｅｎｔｒｙ暗号、Ｂｏｎｅｈ−Ｇｏｈ−Ｎｉｓｓｉｍ（以下、ＢＧＮ）暗号等を挙げることができる。
【００２０】
Ｅｌｇａｍａｌ暗号は、積について準同型性を有する準同型暗号である。Ｐａｉｌｌｉｅｒ暗号は、和について準同型性を有する準同型暗号である。Ｇｅｎｔｒｙ暗号は、任意回数の和と積について準同型性を有する準同型暗号である。ＢＧＮ暗号は、任意回数の和と１回の積について準同型性を有する準同型暗号である。実施形態に係る類似性秘匿検索システム５００は、ラベル付与処理における暗号処理にＢＧＮ暗号を採用し、距離算出処理における暗号処理にＰａｉｌｌｉｅｒ暗号を採用する。ＢＧＮ暗号は、複数回の積については準同型性を有しないため、Ｇｅｎｔｒｙ暗号よりも高速に計算することができる。また、Ｐａｉｌｌｉｅｒ暗号は、乗算について準同型性を有しないため、Ｇｅｎｔｒｙ暗号およびＢＧＮ暗号よりも高速に計算することができる。
【００２１】
（第１辞書ベクトルの生成）
本情報処理装置は、準同型暗号を利用することで、第１暗号化ビットベクトルおよび第２暗号化ビットベクトルを復号せずにこれらに対する演算処理を実行できる。そのため、本情報処理装置は、相手装置が記憶する第２データ列を本情報処理装置に対して秘匿した状態で、第１辞書ベクトルを生成できる。生成した第１辞書ベクトルは第２公開鍵で暗号化されているため、第１辞書ベクトルも本情報処理装置に対して秘匿される。
【００２２】
（ラベルの取得）
本情報処理装置は、第１データ列に含まれる複数の第１フレーズそれぞれのラベルを取得する際に、第１公開鍵で暗号化した第１照会ベクトルを相手装置に送信する。相手装置は、例えば、前記第１データ列および前記第２データ列の少なくとも一方に含まれるフレーズの各々に対応する位置のビットをオンにしたベクトルを第１公開鍵で暗号化した第２辞書ベクトルを記憶する。第１照会ベクトルおよび第２辞書ベクトルは準同型暗号を用いて暗号化されているため、相手装置は、第１照会ベクトルおよび第２辞書ベクトルを復号せずに、ラベルを決定する演算処理を実行できる。そのため、本情報処理装置は、第１公開鍵に対応する秘密鍵を有しない相手装置に対して第１照会ベクトルの内容を開示せずに、ラベルを取得できる。
【００２３】
（ラベルの付与）
本情報処理装置は、第２データ列に含まれる複数の第２フレーズそれぞれのラベルを付与する際に、第２公開鍵で暗号化した第２照会ベクトルを相手装置から受信する。第２照会ベクトルおよび第１辞書ベクトルは準同型暗号を用いて暗号化されているため、本情報処理装置は、第２照会ベクトルおよび第１辞書ベクトルを復号せずに、暗号ラベルを決定する演算処理を実行できる。また、演算処理の結果決定される暗号ラベルも第２公開鍵で暗号化されている。そのため、本情報処理装置は、第２照会ベクトルおよび暗号ラベルの内容を本情報処理装置に対して秘匿した状態で、暗号ラベルを決定できる。
【００２４】
上記の通り、本情報処理装置は、第１データ列を相手装置に対して秘匿し、また、第２データ列を本情報処理装置に対して秘匿した状態で、第１データ列および第２データ列のそれぞれのフレーズに対してラベルを付与することができる。本情報処理装置は、上記処理で付与したラベルを用いることで、第１データ列と第２データ列との移動付き編集距離を算出したり、当該移動付き編集距離を相手装置に算出させたりすることができる。
【００２５】
（距離ベクトルの返送）
実施形態に係る情報処理装置は、次の特徴をさらに有してもよい。前記複数の第１フレーズの各々に対応する第１ラベル値を前記第１位置に配置したベクトルを前記第２公開鍵で暗号化した第１ラベルベクトルを生成する第１ラベルベクトル生成部と、前記複数の第２フレーズの各々について、前記第２暗号ラベル値を前記第２秘密鍵で復号した第２ラベル値を前記第２位置に配置したベクトルを前記第２公開鍵で暗号化した第２ラベルベクトルを前記相手装置から受信すると、前記第１ラベルベクトルと前記第２ラベルベクトルの要素同士を減算したベクトルにノイズを混入させる第１ノイズ混入処理を行った第１ノイズベクトルを前記相手装置に返送する差分返送部と、前記第１ノイズベクトルの各要素の絶対値を要素とするベクトルを前記第２公開鍵で暗号化した第２ノイズベクトルを前記相手装置から受信すると、前記第２ノイズベクトルから前記第１ノイズ混入処理で混入させたノイズを除去して暗号化距離ベクトルを生成し、生成した前記暗号化距離ベクトルを前記相手装置に返送する距離返送部と、をさらに備える。
【００２６】
相手装置から受信する第２ラベルベクトルは第２公開鍵で暗号化されているため、第２ラベルベクトルの内容は本情報処理装置に対して秘匿される。本情報処理装置は、第１ラベルベクトルと第２ラベルベクトルの要素同士を減算したベクトルを生成する。当該ベクトルは、第１ラベルベクトルおよび第２ラベルベクトルが第２公開鍵で暗号化されていることから、第２公開鍵で暗号化されている。相手装置は、第２公開鍵に対応する秘密鍵を有している。そのため、当該ベクトルをそのまま相手装置に返送してしまうと、相手装置は当該ベクトルを復号して当該ベクトルの内容を取得できてしまう。そこで、本情報処理装置は、当該ベクトルに第１ノイズ混入処理を行った第１ノイズベクトルを相手装置に返送する。第１ノイズ混入処理は、例えば、当該ベクトルの各要素に０以外のランダムな整数を乗算する処理を含む。相手装置が第２公開鍵に対応する秘密鍵で第１ノイズベクトルを復号しても、混入したノイズの影響により、当該ベクトルの内容は相手装置に対して秘匿される。
【００２７】
第１ノイズベクトルを受信した相手装置は、第１ノイズベクトルを第２公開鍵に対応する秘密鍵で復号し、復号したベクトルの各要素の絶対値を要素とするベクトルを第２公開鍵で暗号化して第２ノイズベクトルを生成し、生成した第２ノイズベクトルを本情報処理装置に送信する。本情報処理装置は、受信した第２ノイズベクトルから第１ノイズ混入処理で混入させたノイズを除去して暗号化距離ベクトルを生成する。本情報処理装置は、例えば、第１ノイズ混入処理がベクトルの各要素に０以外のランダムな整数を乗算する処理であった場合には、当該整数の逆元を第２ノイズベクトルの各要素に乗算することでノイズを除去できる。本情報処理装置は、暗号化距離ベクトルを相手装置に返送する。相手装置は、暗号化距離ベクトルを第２公開鍵に対応する秘密鍵で復号し、各要素を加算することで、第１データ列と第２データ列との間の移動付き編集距離を算出することができる。換言すれば、本情報処理装置は、暗号化距離ベクトルを相手装置に返送することで、相手装置に移動付き編集距離を算出させることができる。相手装置から受信する第２ノイズベクトルは第２公開鍵で暗号化されているため、第２ノイズベクトルおよび第２ノイズベクトルから生成される暗号化距離ベクトルは、本情報処理装置に対して秘匿される。
【００２８】
（移動付き編集距離の算出）
実施形態に係る情報処理装置は、次の特徴をさらに有してもよい。前記複数の第１フレーズの各々に対応する第１ラベル値を前記第１位置に配置したベクトルを前記第１公開鍵で暗号化した第３ラベルベクトルを生成し、前記第３ラベルベクトルを前記相手装置に送信する第２ラベルベクトル生成部と、前記複数の第２フレーズの各々について、前記第２暗号ラベル値を前記第２秘密鍵で復号した第２ラベル値を前記第２位置に配置したベクトルを前記第１公開鍵で暗号化した第４ラベルベクトルと前記第３ラベルベクトルの要素同士を減算したベクトルにノイズを混入させる第２ノイズ混入処理を行った第３ノイズベクトルを前記相手装置から受信すると、前記第３ノイズベクトルを前記第１秘密鍵で復号し、復号したベクトルの各要素の絶対値を要素とするベクトルを前記第１公開鍵で暗号化した第４ノイズベクトルを前記相手装置に返送する再暗号ベクトル返送部と、前記第４ノイズベクトルから前記ノイズを除去した暗号化距離ベクトルを前記相手装置から受信すると、前記暗号化距離ベクトルを前記第１秘密鍵で復号して距離ベクトルを生成し、前記距離ベクトルの各要素の和を算出する距離算出部と、をさらに備える。
【００２９】
本情報処理装置が相手装置に送信する第３ラベルベクトルと相手装置の第４ラベルベクトルはいずれも第１公開鍵で暗号化される。そのため、相手装置は、準同型暗号の性質を利用して、第３ラベルベクトルと第４ラベルベクトルの復号をせずに、第３ラベルベクトルと第４ラベルベクトルの要素同士を減算することができる。相手装置は、第３ラベルベクトルと第４ラベルベクトルの要素同士を減算したベクトルに第２ノイズ混入処理を行った第３ノイズベクトルを本情報処理装置に送信する。第３ノイズベクトルは、第１公開鍵で暗号化された第１ラベルベクトルと第２ラベルベクトルから生成されたベクトルであるため、第１公開鍵で暗号化されている。本情報処理装置は、第１秘密鍵で第３ノイズベクトルを復号し、復号したベクトルの各要素の絶対値を要素とするベクトルを第１公開鍵で暗号化した第４ノイズベクトルを相手装置に送信する。相手装置は、第４ノイズベクトルからノイズを除去した暗号化距離ベクトルを本情報処理装置に送信する。暗号化距離ベクトルは、第１公開鍵で暗号化された第４ノイズベクトルから生成されるため、第１公開鍵で暗号化されている。本情報処理装置は、第１公開鍵で暗号化距離ベクトルを復号して距離ベクトルを生成し、距離ベクトルの各要素の和を算出する。算出した和が、第１データ列と第２データ列との間の移動付き編集距離となる。すなわち、本情報処理装置によれば、第１データ列を相手装置に開示せず、第２データ列を本情報処理装置に開示せずに、第１データ列と第２データ列との間の移動付き編集距離を算出できる。
【００３０】
なお、第１ラベルベクトル、第２ラベルベクトル、第３ラベルベクトルおよび第４ラベルベクトルは、Ｐａｉｌｌｉｅｒ暗号で暗号化されてもよい。Ｐａｉｌｌｉｅｒ暗号は、和について準同型性を有する準同型暗号である。第１ラベルベクトルおよび第２ラベルベクトルに対する演算処理としては減算が実行され、第３ラベルベクトルおよび第４ラベルベクトルに対する演算処理としても減算が実行される。減算は負の数を加算する演算であることから、第１ラベルベクトル、第２ラベルベクトル、第３ラベルベクトルおよび第４ラベルベクトルの暗号化処理にＰａｉｌｌｉｅｒ暗号を採用することができる。Ｐａｉｌｌｉｅｒ暗号は、任意回数の和と積について準同型性を有する準同型暗号（例えば、Ｇｅｎｔｒｙ暗号）よりも情報処理装置に対する演算負荷が低く、高速に演算することが可能である。そのため、第１ラベルベクトル、第２ラベルベクトル、第３ラベルベクトルおよび第４ラベルベクトルの暗号化処理にＰａｉｌｌｉｅｒ暗号を採用することで、情報処理装置への演算負荷を低減するとともに、処理速度の高速化が可能となる。
【００３１】
（ＢＧＮ暗号による乗算回数制限の回避）
実施形態に係る情報処理装置は、次の特徴をさらに有してもよい。前記第２公開鍵は、Ｂｏｎｅｈ−Ｇｏｈ−Ｎｉｓｓｉｍ（ＢＧＮ）暗号で用いる第２１公開鍵を含み、前記第２秘密鍵は、前記第２１公開鍵に対応する第２１秘密鍵を含み、前記第１暗号化ビットベクトルと前記第２暗号化ビットベクトルは、前記第２１公開鍵で暗号化されたベクトルであり、前記辞書生成部が前記第１暗号化ビットベクトルと前記第２暗号化ビットベクトルとを基に前記第１辞書ベクトルを生成する処理は、前記第１暗号化ビットベクトルの要素のそれぞれと前記第２暗号化ビットベクトルの要素のそれぞれとの１回の乗算を含み、前記辞書生成部は、前記第１辞書ベクトルにノイズを混入させる第３ノイズ混入処理を行った第１ノイズ辞書ベクトルを前記相手装置に送信し、前記第１ノイズ辞書ベクトルを前記第２１秘密鍵で復号したベクトルを前記第２１公開鍵で暗号化した第２ノイズ辞書ベクトルを前記相手装置から受信すると、前記第２ノイズ辞書ベクトルから前記第３ノイズ混入処理で混入させたノイズを除去して前記第１辞書ベクトルを復元する。
【００３２】
ＢＧＮ暗号は、任意回数の和と１回の積について準同型性を有する準同型暗号である。第１辞書ベクトルを生成する処理は１回の乗算を含むため、第１辞書ベクトルの生成処理にＢＧＮ暗号を採用することができる。ＢＧＮ暗号は、任意回数の和と積について準同型性を有する準同型暗号（例えば、Ｇｅｎｔｒｙ暗号）よりも情報処理装置に対する演算負荷が低く、高速に演算することが可能である。そのため、第１辞書ベクトルの生成処理にＢＧＮ暗号を採用することで、情報処理装置への演算負荷を低減するとともに、処理速度の高速化が可能となる。
【００３３】
第１辞書ベクトルの生成において乗算が１回実行しているため、第１辞書ベクトルに対するこれ以上の乗算はＢＧＮ暗号の制限により実行できなくなる。このＢＧＮ暗号の乗算回数の制限を回避するには、第１辞書ベクトルを復号した後にＢＧＮ暗号で暗号化すればよい。ここで、第１辞書ベクトルは第２１公開鍵で暗号化されているため、本情報処理装置では復号できない。そこで、本情報処理装置は、第１辞書ベクトルにノイズを混入させた第１ノイズ辞書ベクトルを相手装置に送信する。相手装置は、第１ノイズ辞書ベクトルを復号した後に第２１公開鍵で再度暗号化した第２ノイズ辞書ベクトルを本情報処理装置に返送する。ノイズが混入されているため、第１ノイズ辞書ベクトルを復号した相手装置に対して第１辞書ベクトルの内容は秘匿される。本情報処理装置は、第１ノイズ辞書ベクトルを復号した後に暗号化した第２ノイズ辞書ベクトルを受信すると、第２ノイズ辞書ベクトルから第３ノイズ混入処理で混入させたノイズを除去して第１辞書ベクトルを復元することで、ＢＧＮ暗号による乗算に対する制限を解除し、第１辞書ベクトルに対する乗算が再び可能になる。
【００３４】
以上説明した実施形態に係る技術は、情報処理方法、情報処理プログラムおよび情報処理システムとして把握することも可能である。
【００３５】
≪実施形態≫
以上説明した実施形態について、図面を参照してさらに説明する。図１は、実施形態に係る類似性秘匿検索システムのシステム構成の一例を示す図である。図１に例示される類似性秘匿検索システム５００は、第１端末１０および第２端末２０を含む。図１では、第１端末１０および第２端末２０のハードウェア構成も示す。第１端末１０は平文の文字列Ｔ１を記憶し、第２端末２０は平文の文字列Ｔ２を記憶する。類似性秘匿検索システム５００は、文字列Ｔ１および文字列Ｔ２を暗号化した状態で、文字列Ｔ１と文字列Ｔ２の類似度を判定する。すなわち、類似性秘匿検索システム５００では、文字列Ｔ１を第２端末２０に開示せず、また、文字列Ｔ２を第１端末１０に開示せずに、文字列Ｔ１および文字列Ｔ２の類似度を判定する。本実施形態では、類似度の尺度として、移動付き編集距離を採用する。以下、図面を参照して、実施形態について説明する。類似性秘匿検索システム５００は、「情報処理システム」の一例である。
【００３６】
第１端末１０および第２端末２０は情報処理装置である。第１端末１０および第２端末２０としては、例えば、パーソナルコンピュータおよびサーバ装置等の各種情報処理装置を挙げることができる。第１端末１０は「第１装置」の一例であり、第２端末２０は「第２装置」の一例である。
【００３７】
ネットワークＮ１は、情報処理装置を相互に通信可能に接続するコンピュータネットワークである。ネットワークＮ１は、例えば、Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ（ＬＡＮ）、インターネット、携帯電話の通信回線等であり、有線であるか無線であるかを問わない。
【００３８】
＜ハードウェア構成＞
図１を参照して、第１端末１０および第２端末２０のハードウェア構成について説明する。
【００３９】
（第１端末１０のハードウェア構成）
第１端末１０は、Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ（ＣＰＵ）１０１、主記憶部１０２、補助記憶部１０３、通信部１０４、入力部１０５、出力部１０６および接続バスＢ１を含む。ＣＰＵ１０１、主記憶部１０２、補助記憶部１０３、通信部１０４、入力部１０５および出力部１０６は、接続バスＢ１によって相互に接続されている。
【００４０】
ＣＰＵ１０１は、マイクロプロセッサユニット（ＭＰＵ）、プロセッサとも呼ばれる。ＣＰＵ１０１は、単一のプロセッサに限定される訳ではなく、マルチプロセッサ構成であってもよい。また、単一のソケットで接続される単一のＣＰＵ１０１がマルチコア構成を有していても良い。ＣＰＵ１０１が実行する処理のうち少なくとも一部は、ＣＰＵ１０１以外のプロセッサ、例えば、Ｄｉｇｉｔａｌ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｏｒ（ＤＳＰ）、Ｇｒａｐｈｉｃｓ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ（ＧＰＵ）、数値演算プロセッサ、ベクトルプロセッサ、画像処理プロセッサ等の専用プロセッサで行われても良い。また、ＣＰＵ１０１が実行する処理のうち少なくとも一部は、集積回路（ＩＣ）、その他のディジタル回路によって実行されてもよい。また、ＣＰＵ１０１の少なくとも一部にアナログ回路が含まれても良い。集積回路は、Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｎｔｅｇｒａｔｅｄ  ＣＩＲＣＵＩＴ（ＬＳＩ）、Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔ
ｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ（ＡＳＩＣ）、プログラマブルロジックデバイス（ＰＬＤ）を含む。ＰＬＤは、例えば、Ｆｉｅｌｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ（ＦＰＧＡ）を含む。ＣＰＵ１０１は、プロセッサと集積回路との組み合わせであっても良い。組み合わせは、例えば、マイクロコントローラユニット（ＭＣＵ）、Ｓｙｓｔｅｍ  ｏｎ  ａ  ｃｈｉｐ（ＳｏＣ）、システムＬＳＩ、チップセットなどと呼ばれる。第１端末１０では、ＣＰＵ１０１が補助記憶部１０３に記憶されたプログラムを主記憶部１０２の作業領域に展開し、プログラムの実行を通じて周辺装置の制御を行う。これにより、第１端末１０は、所定の目的に合致した処理を実行することができる。主記憶部１０２および補助記憶部１０３は、第１端末１０が読み取り可能な記録媒体である。
【００４１】
主記憶部１０２は、ＣＰＵ１０１から直接アクセスされる記憶部として例示される。主記憶部１０２は、Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ（ＲＡＭ）およびＲｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ（ＲＯＭ）を含む。
【００４２】
補助記憶部１０３は、各種のプログラムおよび各種のデータを読み書き自在に記録媒体に格納する。補助記憶部１０３は外部記憶装置とも呼ばれる。補助記憶部１０３は、例えば、Ｅｒａｓａｂｌｅ  Ｐｒｏｇｒａｍｍａｂｌｅ  ＲＯＭ（ＥＰＲＯＭ）、ソリッドステートドライブ（Ｓｏｌｉｄ  Ｓｔａｔｅ  Ｄｒｉｖｅ、ＳＳＤ）、ハードディスクドライブ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ、ＨＤＤ）等である。また、補助記憶部１０３は、例えば、Ｃｏｍｐａｃｔ  Ｄｉｓｃ（ＣＤ）ドライブ装置、Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ（ＤＶＤ）ドライブ装置、Ｂｌｕ−ｒａｙ（登録商標）  Ｄｉｓｃ（ＢＤ）ドライブ装置等である。また、補助記憶部１０３は、Ｎｅｔｗｏｒｋ  Ａｔｔａｃｈｅｄ  Ｓｔｏｒａｇｅ（ＮＡＳ）あるいはＳｔｏｒａｇｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ（ＳＡＮ）によって提供されてもよい。
【００４３】
補助記憶部１０３には、オペレーティングシステム（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ、ＯＳ）、文字列Ｔ１、ハッシュ関数Ｈ１、公開鍵ＰＢ１、秘密鍵ＤＢ１、公開鍵ＰＢ２、公開鍵ＰＰ１、秘密鍵ＤＰ１、公開鍵ＰＰ２、各種プログラム、各種テーブル等が格納される。ＯＳは、通信部１０４を介して接続される外部装置等とのデータの受け渡しを行う通信インターフェースプログラムを含む。外部装置等には、例えば、コンピュータネットワーク等で接続された、他の情報処理装置および外部記憶装置が含まれる。なお、補助記憶部１０３は、例えば、ネットワーク上のコンピュータ群であるクラウドシステムの一部であってもよい。補助記憶部１０３は、「第１記憶部」の一例である。
【００４４】
ハッシュ関数Ｈ１は、同一の入力値に対して一意に定まる演算結果を出力する関数である。ハッシュ関数Ｈ１は、例えば、ＭｅｓｓａｇｅＤｉｇｅｓｔ  Ａｌｇｏｒｉｔｈｍ  ５（ＭＤ５）、Ｓｅｃｕｒｅ  Ｈａｓｈ  Ａｌｇｏｒｉｔｈｍ−１（ＳＨＡ−１）、ＳＨＡ−２等である。ハッシュ関数Ｈ１は、「入力値に対する出力値を一意に決定する関数」の一例である。
【００４５】
公開鍵ＰＢ１、公開鍵ＰＢ２および秘密鍵ＤＢ１は、ＢＧＮ暗号による暗号処理に用いる。公開鍵ＰＢ１および公開鍵ＰＢ２はＢＧＮ暗号による暗号化に用いる鍵であり、秘密鍵ＤＢ１は公開鍵ＰＢ１によって暗号化されたデータの復号に用いる。公開鍵ＰＢ２で暗号化されたデータの復号には、第２端末２０が記憶する秘密鍵ＤＢ２を用いる。公開鍵ＰＢ１は、「第１公開鍵」の一例である。秘密鍵ＤＢ１は、「第１秘密鍵」の一例である。
【００４６】
公開鍵ＰＰ１、公開鍵ＰＰ２および秘密鍵ＤＰ１は、Ｐａｉｌｌｉｅｒ暗号による暗号処理に用いる。公開鍵ＰＰ１および公開鍵ＰＰ２はＰａｉｌｌｉｅｒ暗号による暗号化に用いる鍵であり、秘密鍵ＤＰ１は公開鍵ＰＰ１によって暗号化されたデータの復号に用いる。公開鍵ＰＰ２で暗号化されたデータの復号には、第２端末２０が記憶する秘密鍵ＤＰ２を用いる。公開鍵ＰＰ１は、「第１公開鍵」および「第１２公開鍵」の一例である。秘密鍵ＤＰ１は、「第１秘密鍵」、「第１２秘密鍵」の一例である。
【００４７】
文字列Ｔ１は、文字列データである。文字列Ｔ１は、文字列データであれば特に限定は無い。文字列Ｔ１は、例えば、書籍や論文中の文章を示す文字列データやＤＮＡの塩基配列を示す文字列データである。
【００４８】
通信部１０４は、例えば、ネットワークＮ１とのインターフェースである。通信部１０４は、ネットワークＮ１を介して外部の装置と通信を行う。
【００４９】
入力部１０５は、例えば、利用者等からの操作指示等を受け付ける。入力部１０５は、例えば、キーボード、ポインティングデバイス、タッチパネル等である。
【００５０】
出力部１０６は、例えば、ＣＰＵ１０１で処理されるデータや主記憶部１０２に記憶されるデータを出力する。出力部１０６は、例えば、Ｃａｔｈｏｄｅ  Ｒａｙ  Ｔｕｂｅ（ＣＲＴ）ディスプレイ、Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙ（ＬＣＤ）、Ｐｌａｓｍａ  Ｄｉｓｐｌａｙ  Ｐａｎｅｌ（ＰＤＰ）、Ｅｌｅｃｔｒｏｌｕｍｉｎｅｓｃｅｎｃｅ（ＥＬ）パネル、有機ＥＬパネル等である。
【００５１】
（第２端末２０のハードウェア構成）
第２端末２０は、ＣＰＵ２０１、主記憶部２０２、補助記憶部２０３、通信部２０４、入力部２０５、出力部２０６および接続バスＢ２を含む。ＣＰＵ２０１、主記憶部２０２、補助記憶部２０３、通信部２０４、入力部２０５、出力部２０６および接続バスＢ２のそれぞれは、第１端末１０のＣＰＵ１０１、主記憶部１０２、補助記憶部１０３、通信部１０４、入力部１０５、出力部１０６および接続バスＢ１のそれぞれと同一の構成を有するため、その説明を省略する。なお、補助記憶部２０３は、公開鍵ＰＢ２、秘密鍵ＤＢ２、公開鍵ＰＢ１、公開鍵ＰＰ２、秘密鍵ＤＰ２、公開鍵ＰＰ１、ハッシュ関数Ｈ１を記憶するとともに、文字列Ｔ１に代えて文字列Ｔ２を記憶する。補助記憶部２０３は、「第２記憶部」の一例である。
【００５２】
公開鍵ＰＢ２、公開鍵ＰＢ１および秘密鍵ＤＢ２は、ＢＧＮ暗号による暗号処理に用いる。公開鍵ＰＢ２および公開鍵ＰＢ１はＢＧＮ暗号による暗号化に用いる鍵であり、秘密鍵ＤＢ２は公開鍵ＰＢ２によって暗号化されたデータの復号に用いる。公開鍵ＰＢ１で暗号化されたデータの復号には、上述の通り、第１端末１０が記憶する秘密鍵ＤＢ１を用いる。公開鍵ＰＢ２は、「第２公開鍵」および「第２１公開鍵」の一例である。秘密鍵ＤＢ２および秘密鍵ＰＢ２は、「第２秘密鍵」の一例である。秘密鍵ＰＢ２は、「第２１秘密鍵」の一例である。
【００５３】
公開鍵ＰＰ２、公開鍵ＰＰ１および秘密鍵ＤＰ２は、Ｐａｉｌｌｉｅｒ暗号による暗号処理に用いる。公開鍵ＰＰ２および公開鍵ＰＰ１はＰａｉｌｌｉｅｒ暗号による暗号化に用いる鍵であり、秘密鍵ＤＰ２は公開鍵ＰＰ２によって暗号化されたデータの復号に用いる。公開鍵ＰＰ１で暗号化されたデータの復号には、上述の通り、第１端末１０が記憶する秘密鍵ＤＰ１を用いる。公開鍵ＰＰ２は、「第２公開鍵」および「第２２公開鍵」の一例である。秘密鍵ＤＰ２は、「第２秘密鍵」および「第２２秘密鍵」の一例である。
【００５４】
＜論理構成＞
図２は、実施形態に係る類似性秘匿検索システムの論理構成の一例を示す図である。以下、図２を参照して、実施形態に係る類似性秘匿検索システム５００の論理構成について説明する。
【００５５】
（第１装置１０の論理構成）
第１装置１０は、ビットベクトル生成部１１ａ、ビットベクトル生成部１１ｂ、辞書管理部１２、ラベル付与部１３、ラベル取得部１４、ラベルベクトル生成部１５、第１返送部１６および距離返送部１７備える。第１装置１０は、主記憶部１０２に実行可能に展開されたコンピュータプログラムをＣＰＵ１０１が実行することで、上記第１装置１０の、ビットベクトル生成部１１ａ、ビットベクトル生成部１１ｂ、辞書管理部１２、ラベル付与部１３、ラベル取得部１４、ラベルベクトル生成部１５、第１返送部１６および距離返送部１７等の各部としての処理を実行する。
【００５６】
ビットベクトル生成部１１ａは、文字列Ｔ１に含まれる各フレーズに対してハッシュ関数Ｈ１を適用し、ハッシュ関数Ｈ１の出力値を基に決定した位置のビットをオンにしたビットベクトルを生成する。フレーズは、文字列Ｔ１を所定文字数ごと（例えば、２文字ごと）に区切った文字列である。フレーズは、隣り合ったフレーズの組み合わせを許容してもよい。文字列Ｔ１が「ａａａａｉｓｂｂｂｂ」であり、所定文字数を「２」とした場合を例として、フレーズについて説明する。この例の場合、文字列Ｔ１のフレーズとして、「ａａ」、「ａａ」、「ｉｓ」、「ｂｂ」、「ｂｂ」を挙げることができる。また、隣り合ったフレーズの組み合わせを許容する場合、文字列Ｔ１のフレーズとして、「ａａ」、「ａａ」、「ｉｓ」、「ｂｂ」、「ｂｂ」、「ａａａａ」、「ｉｓｂｂ」、「ａａａａｉｓｂｂｂｂ」を挙げることができる。ビットベクトル生成部１１ａは、生成したビットベクトルを第２端末２０の公開鍵ＰＢ２を用いて暗号化した暗号化ベクトルを生成する。ビットベクトル生成部１１ａは、「ビットベクトル生成部」および「第１ベクトル生成部」の一例である。ハッシュ関数Ｈ１の出力値を基に決定した位置は、「第１位置」の一例である。ビットベクトル生成部１１ａが生成したビットベクトルは、「第１ビットベクトル」の一例である。ビットベクトル生成部１１ａが生成した暗号化ベクトルは、「第１暗号化ビットベクトル」の一例である。
【００５７】
ビットベクトル生成部１１ｂは、文字列Ｔ１に含まれる各フレーズに対してハッシュ関数Ｈ１を適用し、ハッシュ関数Ｈ１の出力値を基に決定した位置のビットをオンにしたビットベクトルを生成する。ビットベクトル生成部１１ｂは、生成したビットベクトルを第１端末１０の公開鍵ＰＢ１を用いて暗号化した暗号化ベクトルを第２端末２０に送信する。ビットベクトル生成部１１ｂは、「第１送信部」の一例である。ビットベクトル生成部１１ｂが生成する暗号化ベクトルは、「第３暗号化ビットベクトル」の一例である。
【００５８】
辞書管理部１２は、第２端末２０と協調して、フレーズ辞書を生成する。辞書管理部１２は、後述する第２端末２０のビットベクトル生成部２１ｂから公開鍵ＰＢ２で暗号化された暗号化ベクトルを受信すると、ビットベクトル生成部１１ａが生成した暗号化ベクトルと第２端末２０から受信した暗号化ベクトルとに対してＢＧＮ暗号が準同型性を有する演算処理を実行し、文字列Ｔ１および文字列Ｔ２の少なくとも一方に含まれるフレーズに対応する位置のビットをオンにしたベクトルであるフレーズ辞書を生成する。ここで、フレーズに対応する位置は、ビットベクトルの生成と同様に、文字列Ｔ１または文字列Ｔ２に含まれる各フレーズに対してハッシュ関数Ｈ１を適用し、ハッシュ関数Ｈ１の出力値を基に決定される。このように生成されるフレーズ辞書は、第２端末２０の公開鍵ＰＢ２で暗号化されており、公開鍵ＰＢ２に対応する秘密鍵ＤＢ２を有しない第１端末１０はその内容を知ることはできない。生成したフレーズ辞書は、例えば、補助記憶部１０３に記憶される。辞書管理部１２は、「辞書生成部」および「第１辞書生成部」の一例である。辞書管理部１２が生成するフレーズ辞書は、「第１辞書ベクトル」の一例である。
【００５９】
ラベル付与部１３は、第２端末２０からラベルの問い合わせを受信すると、受信した問い合わせとフレーズ辞書とを基に暗号ラベルを算出し、算出した暗号ラベルを第２端末２０に返送する。ラベル付与部１３は、「ラベル付与部」および「第１ラベル付与部」の一
例である。ラベル付与部１３が返送する暗号ラベルは、「第２暗号ラベル値」の一例である。
【００６０】
ラベル取得部１４は、文字列Ｔ１に含まれるフレーズに対応付けられたラベルを問い合わせるラベル問い合わせを第２端末２０に送信する。ラベル取得部１４は、文字列Ｔ１に含まれるフレーズのうち、ラベル問い合わせの対象とするフレーズにハッシュ関数Ｈ１を適用し、ハッシュ関数Ｈ１の出力値を基に決定した位置の要素を「１」としたベクトルを公開鍵ＰＢ１で暗号化したベクトルをラベル問い合わせベクトルとして第２端末２０に送信する。ラベル取得部１４は、ラベル問い合わせベクトルの応答として公開鍵ＰＢ１で暗号化された暗号ラベルを取得する。ラベル取得部１４は、取得した暗号ラベルを秘密鍵ＤＢ１で復号することで、フレーズに対応するラベルを取得する。ラベル取得部１４は、このような処理を文字列Ｔ１に含まれる各フレーズについて実行することで、文字列Ｔ１に含まれる各フレーズに対応するラベルを取得する。ラベル取得部１４は、「ラベル取得部」および「第１ラベル取得部」の一例である。ラベル問い合わせの対象とするフレーズは、「特定フレーズ」の一例である。ラベル取得部１４が送信するラベル問い合わせベクトルは、「第１照会ベクトル」の一例である。暗号ラベルは、「第１暗号ラベル値」の一例である。フレーズに対応するラベルは、「第１ラベル値」の一例である。
【００６１】
ラベルベクトル生成部１５は、文字列Ｔ１に含まれるフレーズの各々に対応するラベル値を、文字列Ｔ１に含まれるフレーズの各々にハッシュ関数Ｈ１を適用した出力値を基に決定した位置に配置したベクトルを生成する。ラベルベクトル生成部１５は、生成したベクトルを第２端末２０の公開鍵ＰＢ２で暗号化したラベルベクトルを生成する。ラベルベクトル生成部１５は、「第１ラベルベクトル生成部」の一例である。ラベルベクトル生成部１５が生成するラベルベクトルは、「第３ラベルベクトル」の一例である。
【００６２】
第１返送部１６は、第２装置２０のラベルベクトル生成部２５が生成したラベルベクトルを第２装置２０から受信する。第１返送部１６は、ラベルベクトル生成部１５が生成したラベルベクトルと第２装置２０から受信したラベルベクトルの要素同士を減算したベクトルを生成する。第１返送部１６は、生成したベクトルにノイズを混入させた第１ノイズベクトルを第２装置２０に返送する。第１返送部１６は、「差分返送部」の一例である。第１返送部１６が返送する第１ノイズベクトルは、「第４ノイズベクトル」の一例である。
【００６３】
距離返送部１７は、第２端末２０の第２返送部２６が生成した第２ノイズベクトルを第２装置２０から受信する。距離返送部１７は、受信した第２ノイズベクトルから、差分返送部１６が第１ノイズベクトルに混入させたノイズを除去して暗号化距離ベクトルを生成する。距離返送部１７は、生成した暗号化距離ベクトルを第２装置２０に返送する。距離返送部１７は、「距離返送部」の一例である。
【００６４】
（第２装置２０の論理構成）
第２装置２０は、ビットベクトル生成部２１ａ、ビットベクトル生成部２１ｂ、辞書管理部２２、ラベル付与部２３、ラベル取得部２４、ラベルベクトル生成部２５、第２返送部２６および距離算出部２７を備える。第２装置２０は、主記憶部２０２に実行可能に展開されたコンピュータプログラムをＣＰＵ２０１が実行することで、上記第２装置２０の、ビットベクトル生成部２１ａ、ビットベクトル生成部２１ｂ、辞書管理部２２、ラベル付与部２３、ラベル取得部２４、ラベルベクトル生成部２５、第２返送部２６および距離算出部２７等の各部としての処理を実行する。
【００６５】
ビットベクトル生成部２１ａは、文字列Ｔ２に含まれる各フレーズに対してハッシュ関数Ｈ１を適用し、ハッシュ関数Ｈ１の出力値を基に決定した位置のビットをオンにしたビットベクトルを生成する。ビットベクトル生成部２１ａは、生成したビットベクトルを第１端末１０の公開鍵ＰＢ１を用いて暗号化した暗号化ベクトルを生成する。ビットベクトル生成部２１ａは、「第２ベクトル生成部」の一例である。ハッシュ関数Ｈ１の出力値を基に決定した位置は、「第２位置」の一例である。ビットベクトル生成部２１ａが生成するビットベクトルは「第２ビットベクトル」の一例である。ビットベクトル生成部２１ａが生成する暗号化ベクトルは、「第４暗号化ビットベクトル」の一例である。
【００６６】
ビットベクトル生成部２１ｂは、文字列Ｔ２に含まれる各フレーズに対してハッシュ関数Ｈ１を適用し、ハッシュ関数Ｈ１の出力値を基に決定した位置のビットをオンにしたベクトルを生成する。フレーズは、文字列Ｔ２を所定文字数ごと（例えば、２文字ごと）に区切った文字列であり、文字列Ｔ１のフレーズと同様に考えることができる。ビットベクトル生成部２１ｂは、生成したビットベクトルを第２端末２０の公開鍵ＰＢ２を用いて暗号化した暗号化ベクトルを第１端末１０に送信する。ビットベクトル生成部２１ｂは、「第２送信部」の一例である。ビットベクトル生成部２１ｂが生成する暗号化ベクトルは「第２暗号化ビットベクトル」の一例である。
【００６７】
辞書管理部２２は、第１端末１０と協調して、フレーズ辞書を生成する。辞書管理部２２は、ビットベクトル生成部１１ｂが生成した暗号化ベクトルを第１端末１０から受信すると、ビットベクトル生成部２１ａが生成した暗号化ベクトルと第１端末１０から受信した暗号化ベクトルとに対してＢＧＮ暗号が準同型性を有する演算処理を実行し、文字列Ｔ１および文字列Ｔ２の少なくとも一方に含まれるフレーズに対応する要素のビットをオンにしたベクトルであるフレーズ辞書を生成する。このように生成されるフレーズ辞書は、第１端末１０の公開鍵ＰＢ１で暗号化されており、公開鍵ＰＢ１に対応する秘密鍵ＤＢ１を有しない第２端末２０はその内容を知ることはできない。辞書管理部２２は、「第２辞書生成部」の一例である。辞書管理部２２が生成するフレーズ辞書は、「第２辞書ベクトル」の一例である。
【００６８】
ラベル付与部２３は、第１端末１０からラベルの問い合わせを受信すると、受信した問い合わせとフレーズ辞書とを基に暗号ラベルを算出し、算出した暗号ラベルを第１端末１０に返送する。ラベル付与部２３は、「第２ラベル付与部」の一例である。
【００６９】
ラベル取得部２４は、文字列Ｔ２に含まれるフレーズに対応付けられたラベルを問い合わせるラベル問い合わせを第１端末１０に送信する。ラベル取得部２４は、文字列Ｔ２に含まれるフレーズのうち、ラベル問い合わせの対象とするフレーズにハッシュ関数Ｈ１を適用し、ハッシュ関数Ｈ１の出力値を基に決定した位置の要素を「１」としたベクトルを公開鍵ＰＢ２で暗号化したベクトルをラベル問い合わせベクトルとして第１端末１０に送信する。ラベル取得部２４は、ラベル問い合わせベクトルの応答として公開鍵ＰＢ２で暗号化された暗号ラベルを取得する。ラベル取得部２４は、取得した暗号ラベルを秘密鍵ＤＢ２で復号することで、フレーズに対応するラベルを取得する。ラベル取得部２４は、このような処理を文字列Ｔ２に含まれる各フレーズについて実行することで、文字列Ｔ２に含まれる各フレーズに対応するラベルを取得する。ラベル取得部２４は、「第２ラベル取得部」の一例である。ラベル取得部２４が送信するラベル問い合わせベクトルは、「第２照会ベクトル」の一例である。ラベル取得部２４が暗号ラベルを復号して取得したラベルは、「第２ラベル値」の一例である。
【００７０】
ラベルベクトル生成部２５は、文字列Ｔ２に含まれるフレーズの各々に対応するラベル値を、文字列Ｔ２に含まれるフレーズの各々にハッシュ関数Ｈ１を適用した出力値を基に決定した位置に配置したベクトルを生成する。ラベルベクトル生成部２５は、生成したベクトルを第１端末１０の公開鍵ＰＰ２で暗号化したラベルベクトルを生成する。ラベルベクトル生成部２５は、生成したラベルベクトルを第１装置１０に送信する。ラベルベクトル生成部２５は、「第２ラベルベクトル生成部」および「第３送信部」の一例である。ラベルベクトル生成部２５が生成するラベルベクトルは、「第４ラベルベクトル」の一例である。
【００７１】
第２返送部２６は、第１ノイズベクトルを第１装置１０から受信すると、第１ノイズベクトルを秘密鍵ＤＢ２で復号する。第２返送部２６は、秘密鍵ＤＢ２で復号したベクトルの各要素の絶対値を要素とするベクトルを生成し、生成したベクトルを公開鍵ＰＢ２で暗号化して第２ノイズベクトルを生成する。第２返送部２６は、第２ノイズベクトルを第１装置１０に返送する。第２返送部２６は、「再暗号ベクトル返送部」の一例である。
【００７２】
距離算出部２７は、暗号化距離ベクトルを第１装置１０から受信すると、暗号化距離ベクトルを秘密鍵ＤＢ２で復号して距離ベクトルを生成する。距離算出部２７は、距離ベクトルの各要素の和を算出する。距離ベクトルの各要素の和は、文字列Ｔ１と文字列Ｔ２との間の移動付き編集距離となる。距離算出部２７は、「距離算出部」の一例である。
【００７３】
＜処理フロー＞
以上の構成を有する類似性秘匿検索システム５００による文字列Ｔ１と文字列Ｔ２との間の移動付き編集距離を算出する処理の処理フローについて、図面を参照して説明する。
【００７４】
（ラベル取得処理およびラベル付与処理）
図３は、実施形態に係る類似性秘匿検索システムによるラベル取得処理の処理フローの一例を示す図である。以下、図３を参照して、類似性秘匿検索システム５００が実行するラベル取得処理およびラベル付与処理について説明する。
【００７５】
ステップＳ１では、第１端末１０と第２装置２０とで使用するハッシュ関数を決定する。本実施形態におけるラベル付与処理では、第１端末１０および第２装置２０は同一のハッシュ関数を使用する。ハッシュ関数の決定では、例えば、第１端末１０から第２装置２０に対して使用するハッシュ関数をネットワークＮ１を介して送信し、第２装置２０は受信したハッシュ関数を用いるとしてもよい。また、第１端末１０および第２装置２０のそれぞれが、同一のハッシュ関数をあらかじめ補助記憶部１０３、補助記憶部２０３にそれぞれ記憶していてもよい。また、例えば、第１装置１０および第２装置２０の双方からアクセス可能な記憶装置にハッシュ関数を記憶させてもよい。本実施形態では、ハッシュ関数Ｈ１が、第１端末１０の補助記憶部１０３と第２装置２０の補助記憶部２０３にあらかじめ記憶されているものとする。ハッシュ関数Ｈ１は、ｎ＞ｍ（ｍ、ｎはいずれも正の整数）の条件において、Ｈ１：｛１、２、３、・・・、ｎ｝−＞｛１、２、３、・・・、ｍ｝との変換を行う。
【００７６】
ステップＳ２では、第１端末１０と第２装置２０とでフレーズ辞書を構築する。フレーズ辞書は、文字列Ｔ１、Ｔ２に含まれる各フレーズに対して、一意に決定したラベルを付与する辞書である。フレーズは、文字列Ｔ１、Ｔ２において任意の文字数の連続した文字列である。フレーズ辞書において、同一のフレーズには同一のラベルが対応付けられ、異なるフレーズには異なるラベルが対応付けられる。フレーズ辞書を構築する処理の詳細については、図４を参照して後述する。
【００７７】
ステップＳ３では、ラベルの取得および付与が行われる。例えば、ステップＳ２で構築したフレーズ辞書を第２端末２０が補助記憶部２０３に記憶する場合、第１端末１０は、文字列Ｔ１に含まれるフレーズのうちラベル問い合わせの対象とするフレーズを暗号化して第２端末２０に送信し、第２端末２０から当該フレーズに対応するラベルを取得する。また、例えば、ステップＳ２で構築したフレーズ辞書を第１端末１０が補助記憶部１０３に記憶する場合、第２端末２０は、文字列Ｔ２に含まれるフレーズのうちラベル問い合わせの対象とするフレーズを暗号化して第１端末１０に送信し、第１端末１０から当該フレーズに対応するラベルを第２端末２０に送信する。ラベル取得処理およびラベル付与処理の詳細については、図１０を参照して後述する。
【００７８】
（フレーズ辞書構築処理）
図４は、実施形態におけるフレーズ辞書を構築する処理の処理フローの一例を示す図である。図４は、図３のステップＳ２の処理をより詳細に説明する図である。図５から図９は、各ステップでのベクトルに対する処理を模式的に示す図である。図６から図９に例示される各ベクトルは実際には暗号化されているが、図示の都合上、図６から図９ではベクトルの各要素を復号した状態（平文の状態）で例示する。以下、図４から図９を参照して、フレーズ辞書を構築する処理の処理フローの一例について説明する。
【００７９】
（ステップＳ２１）
ステップＳ２１では、第１端末１０のビットベクトル生成部１１ａは、文字列Ｔ１のフレーズに係る情報を格納するベクトルの初期化処理を行う。図５は、図４のステップＳ２１におけるベクトル初期化処理を模式的に示す図である。ビットベクトル生成部１１ａは、長さｍであり、各要素を０に初期化したベクトルＶ１を生成する（図５（Ａ））。ビットベクトル生成部１１ａは、文字列Ｔ１に含まれるフレーズの各々について、ハッシュ関数Ｈ１を適用してハッシュ値を取得する。ビットベクトル生成部１１ａは、ベクトルＶ１において、取得したハッシュ値に対応する要素（ハッシュ値番目の要素）が１となるように、ベクトルＶ１の初期化を行う。
【００８０】
ビットベクトル生成部１１ａは、例えば、文字列Ｔ１内のフレーズ「ｘｙ」についてのハッシュ値がＨ１（ｘｙ）＝ｋである場合、ｋを添え字としてＶ１（ｋ）（ベクトルＶ１のｋ番目の要素）を１とする（図５（Ｂ））。このような処理を文字列Ｔ１に含まれる各フレーズに対して実行することで、フレーズの各々にハッシュ関数Ｈ１を適用したハッシュ値に対応する要素を「１」としたベクトルＶ１を得ることができる（図５（Ｃ））。
【００８１】
ビットベクトル生成部１１ａは、ベクトルＶ１を第２端末２０の公開鍵ＰＢ２を用いて暗号化した暗号化ベクトルＥ２（Ｖ１）を生成する。第２端末２０のビットベクトル生成部２１ｂは、文字列Ｔ２に対して同様の処理を行い、ベクトルＶ２を得る。ビットベクトル生成部２１ｂは、第２端末２０の公開鍵ＰＢ２を用いて暗号化した暗号化ベクトルＥ２（Ｖ２）を生成する。暗号化ベクトルＥ２（Ｖ１）および暗号化ベクトルＥ２（Ｖ２）の生成は、例えば、ＢＧＮ暗号によって行われる。ステップＳ２１の処理は、「ビットベクトル生成ステップ」の一例である。
【００８２】
（ステップＳ２２）
ステップＳ２２では、第１端末１０の辞書管理部１２は、第１端末１０のビットベクトル生成部１１ａが生成した暗号化ベクトルＥ２（Ｖ１）と第２端末２０のビットベクトル生成部２１ｂが生成した暗号化ベクトルＥ２（Ｖ２）との乗算処理を行う。第２端末２０のビットベクトル生成部２１ｂは、暗号化ベクトルＥ２（Ｖ１）を第１端末１０に送信する。暗号化ベクトルＥ２（Ｖ１）を受信した第１端末１０の処理は、図６を参照して説明する。
【００８３】
図６は、図４のステップＳ２２におけるベクトルの乗算処理を模式的に示す図である。第１端末１０の辞書管理部１２は、暗号化ベクトルＥ２（Ｖ１）と暗号化ベクトルＥ２（Ｖ２）の各要素同士を乗算した長さｍのベクトルＸを生成する。ステップＳ２２において乗算を実行したことでＢＧＮ暗号の準同型性の制限（乗算については１回のみ可能）により、ベクトルＸに対するこれ以上の乗算は実行できなくなる。
【００８４】
（ステップＳ２３）
ステップＳ２３では、第１端末１０の辞書管理部１２は、暗号化ベクトルＥ２（Ｖ１）と暗号化ベクトルＥ２（Ｖ２）との加算処理を行う。図７は、図４のステップＳ２３におけるベクトルの加算処理を模式的に示す図である。第１端末１０の辞書管理部１２は、暗号化ベクトルＥ２（Ｖ１）に暗号化ベクトルＥ２（Ｖ２）の各要素同士を加算して、図７において復号した状態で例示される長さｍのベクトルＹを生成する。
【００８５】
（ステップＳ２４）
ステップＳ２４では、第１端末１０の辞書管理部１２は、ベクトルの減算処理を行う。図８は、図４のステップＳ２４におけるベクトルの減算処理を模式的に示す図である。第１端末１０の辞書管理部１２は、ベクトルＹからベクトルＸを減算して、ベクトルＺを生成する。ベクトルＺは、フレーズ辞書として利用可能な要素を保持するベクトルである。ステップＳ２４の処理は、「辞書生成ステップ」の一例である。
【００８６】
（ステップＳ２５）
ステップＳ２５では、ステップＳ２２における乗算の実行で生じた、ベクトルＺに対する乗算実行不可の制限（ＢＧＮ暗号を採用したことによる制限）を解除する処理が実行される。図９は、図４のステップＳ２５におけるベクトルを変形する処理を模式的に示す図である。第１端末１０の辞書管理部１２は、ベクトルＺの各要素にランダムな値Ｒ（１）、・・・、Ｒ（ｍ）を加算し、さらに、各要素の順番をランダムに入れ替えて変形したベクトルＺ２を生成する。辞書管理部１２は、生成したベクトルＺ２を第２端末２０に送信する。ベクトルＺ２を生成する処理は、「第３ノイズ混入処理」の一例である。ベクトルＺ２は、「第１ノイズ辞書ベクトル」の一例である。
【００８７】
第２端末２０の辞書管理部２２は、ベクトルＺ２を第２端末２０の秘密鍵ＤＢ２で復号したベクトルＺ３を生成する。辞書管理部２２は、ベクトルＺ３を第２端末２０の公開鍵ＰＢ２で暗号化してベクトルＺ４を生成する。辞書管理部２２は、ベクトルＺ４を第１端末１０に送信する。
【００８８】
第１端末１０の辞書管理部１２は、受信したベクトルＺ４の各要素の順番を元の状態に（ベクトルＺと同じ順番に）戻すとともに、各要素に加算したランダムな値Ｒ（１）、・・・、Ｒ（ｍ）をそれぞれの要素から減算することで、ベクトルＺ４をベクトルＺの状態に戻す。すなわち、ベクトルＺの状態に戻す処理は、図９に例示した処理を逆方向に実施することで実現する。この処理によってベクトルＺが復元される。ステップＳ２５の処理によって、ベクトルＺに生じた乗算不可の制限を解除して、ベクトルＺに対して１回の乗算を実行することが可能となる。
【００８９】
図４の処理の主体を第１装置１０と第２装置２０とで入れ替えることで、第２装置２０が記憶するフレーズ辞書を生成することができる。第２装置２０の辞書管理部２２が生成するベクトルＺ２は、「第２ノイズ辞書ベクトル」の一例である。
【００９０】
（ラベル取得処理およびラベル付与処理）
図１０は、ラベル取得処理およびラベル付与処理の処理フローの一例を示す図である。図１０は、図３のステップＳ３の処理をより詳細に説明する図である。ここでは、フレーズ「ｘｙ」のラベルを第２端末２０が第１端末１０から取得する場合について説明する。以下、図１０を参照して、ラベル取得処理の処理フローの一例について説明する。
【００９１】
（ステップＳ３１）
ステップＳ３１では、第２端末２０のラベル取得部２４は、ラベル問い合わせを第１端末１０に送信する。この処理では、ラベル取得部２４は、フレーズ「ｘｙ」にハッシュ関数Ｈ１を適用したハッシュ値がｋである場合（ハッシュ関数Ｈ１（ｘｙ）＝ｋである場合）に、１番目からｋ番目までの要素が１であり、ｋ＋１番目以降の要素が０であるベクトルＶｑ＝（１、・・・、１、１、０、・・・０）を生成する。ラベル取得部２４は、ベクトルＶｑを第２端末２０の公開鍵ＰＢ２で暗号化したＥ２（Ｖｑ）を生成する。ラベル取得部２４は、Ｅ２（Ｖｑ）を第１端末１０宛にラベル問い合わせとして送信する。
【００９２】
（ステップＳ３２）
ステップＳ３２では、第１端末１０のラベル付与部１３は、ベクトルＺと第２端末２０から受信したベクトルＥ２（Ｖｑ）との各要素同士を乗算したベクトルＥ２（ＶＡ）を生成する。ラベル付与部１３は、ベクトルＥ２（ＶＡ）のすべての要素を加算したスカラー値Ｅ２（ＥＡ）を暗号ラベル値として第２端末２０に送信する。ステップＳ３２の処理は、「ラベル付与ステップ」の一例である。
【００９３】
（ステップＳ３３）
第２端末２０のラベル取得部２３は、第１端末１０から暗号ラベル値として受信したスカラー値Ｅ２（ＥＡ）を第２端末２０の秘密鍵ＤＢ２で復号してスカラー値ＥＡを取得する。スカラー値ＥＡが、フレーズ「ｘｙ」に対応するラベルとなる。ステップＳ３１からＳ３３の処理が各フレーズについて実行されることで、ラベル取得部２３は文字列Ｔ２の各フレーズに対応するラベルを取得できる。第１端末１０が文字列Ｔ１に含まれる各フレーズに対応するラベルを取得するには、第１端末１０の公開鍵ＰＢ１で暗号化したベクトルＺを第２端末２０が保持すればよい。ステップＳ３１、Ｓ３２の処理は、「ラベル取得ステップ」の一例である。
【００９４】
（距離算出処理）
距離算出処理では、ラベル付与処理で取得した各フレーズに対応するラベルを要素としたベクトル同士のＬ１距離を算出する。このＬ１距離が、文字列Ｔ１と文字列Ｔ２との間の移動付き編集距離となる。図１１は、実施形態における距離算出処理の処理シーケンスの一例を示す図である。以下、図１１を参照して、実施形態における距離算出処理の処理シーケンスの一例について説明する。
【００９５】
ステップＴ１では、第１端末１０のラベルベクトル生成部１５は、ラベル付与処理で取得した文字列Ｔ１の各フレーズに対応するラベルを要素としたラベルベクトルＶＬＴ１を生成する。ラベルベクトルＶＬＴ１では、例えば、文字列Ｔ１内のフレーズ「ｘｙ」についてのハッシュ値がＨ１（ｘｙ）＝ｋである場合、ｋを添え字としてＶＬＴ１（ｋ）（ラベルベクトルＶＬＴ１のｋ番目の要素）をフレーズ「ｘｙ」のラベルＥＡとする。ステップＴ２では、第２端末２０のラベルベクトル生成部２５は、ラベル付与処理で取得した文字列Ｔ２の各フレーズに対応するラベルを要素としたラベルベクトルＶＬＴ２を生成する。
【００９６】
ステップＴ３では、第２端末２０のラベルベクトル生成部２５は、ステップＴ２で生成したラベルベクトルＶＬＴ２を第２端末２０の公開鍵ＰＰ２で暗号化したラベルベクトルＥ２（ＶＬＴ２）を生成する。ラベルベクトル生成部２５は、暗号化したラベルベクトルＥ２（ＶＬＴ２）を第１端末１０に送信する。
【００９７】
ステップＴ４では、第１端末１０の第１返送部１６は、ラベルベクトルＶＬＴ１を第２端末２０の公開鍵ＰＰ２で暗号化したラベルベクトルＥ２（ＶＬＴ１）を生成する。第１返送部１６は、Ｅ２（ＶＬＴ２）からＥ２（ＶＬＴ１）を減算した差分ベクトルＥ２（Ｖ（ＬＴ２−ＬＴ１））を生成する。第１返送部１６は、差分ベクトルＥ２（Ｖ（ＬＴ２−ＬＴ１））にランダムな整数ｒを乗算したＥ２（ｒ（Ｖ（ＬＴ２−ＬＴ１）））を生成し、生成したＥ２（ｒ（Ｖ（ＬＴ２−ＬＴ１）））を第２端末２０に送信する。ステップＴ
４の処理は、「第１ノイズ混入処理」の一例である。
【００９８】
ステップＴ５では、第２端末２０の第２返送部２６は、受信したＥ２（ｒ（Ｖ（ＬＴ２−ＬＴ１）））を第２端末２０の秘密鍵ＤＰ２で復号したベクトルｒ（Ｖ（ＬＴ２−ＬＴ１））を生成する。第２返送部２６は、ベクトルｒ（Ｖ（ＬＴ２−ＬＴ１））の絶対値｜ｒ（Ｖ（ＬＴ２−ＬＴ１））｜を算出する。第２返送部２６は、算出した絶対値｜ｒ（Ｖ（ＬＴ２−ＬＴ１）））｜を第２端末２０の公開鍵ＰＰ２で暗号化したＥ２（｜ｒ（Ｖ（ＬＴ２−ＬＴ１））｜）を算出する。第２返送部２６は、Ｅ２（｜ｒ（Ｖ（ＬＴ２−ＬＴ１））｜）を第１端末１０に送信する。
【００９９】
ステップＴ６では、第１端末１０の距離返送部１７は、Ｅ２（｜ｒ（Ｖ（ＬＴ２−ＬＴ１））｜）とＴ４で用いたランダムな整数ｒの逆元とを乗算することで、ノイズとして混入させたｒを除去したＥ２（｜（Ｖ（ＬＴ２−ＬＴ１））｜）を算出する。距離返送部１７は、算出したＥ２（｜（Ｖ（ＬＴ２−ＬＴ１））｜）を第２端末２０に送信する。
【０１００】
ノイズとして混入させたｒを除去する処理について、さらに説明する。ａ、ｂ、Ｎを整数とし、以下の式（２）の関係を満たすａ、ｂを互いの逆元という。Ｎとａとが互いに素である場合には、Ｎを法とするａの逆元（以下の式（２）ではｂ）が存在する。
【数２】
2020188438.tif 000004
【０１０１】
実施形態では、Ｎを十分に大きな数としたうえで、｜Ｘ｜Ｎを以下の式（３）で定義する。
【数３】
2020188438.tif 000005
【０１０２】
式（３）の定義に従うと、ｎδ＜Ｎとなるｎ、δに対して、０≦ｐ≦δ、０≦ｑ≦δであり、−δ＜ｐ−ｑ＜δの範囲となる整数ｐ、ｑについて、以下の式（４）のような計算を行うことができる。
【数４】
2020188438.tif 000006
【０１０３】
すなわち、ｐおよびｑが上記した条件を満たす範囲において、Ｅ１（｜ｒ（Ｖ（ＬＴ１−ＬＴ２））｜）とステップＴ４で用いたランダムな整数ｒの逆元とを乗算することで、ノイズとして混入させたｒを除去したＥ１（｜Ｖ（ＬＴ１−ＬＴ２）｜）を算出できることが理解できる。
【０１０４】
ステップＴ７では、第２端末２０の距離算出部２７は、第２端末２０の秘密鍵ＤＰ２でＥ２（｜（Ｖ（ＬＴ２−ＬＴ１））｜）を復号し、｜（Ｖ（ＬＴ２−ＬＴ１））｜（すなわち、ベクトルＶ（ＬＴ２−ＬＴ１）の大きさ）を算出する。算出したＶ（ＬＴ２−ＬＴ１）の大きさ｜Ｖ（ＬＴ２−ＬＴ１）｜が、文字列Ｔ１と文字列Ｔ２とのＬ１距離、すなわち、移動付き編集距離となる。
【０１０５】
＜実施形態の作用効果＞
実施形態では、第２端末２０から第１端末１０に送信するデータは、第２端末２０の公開鍵で暗号化される。第１端末１０は、第２端末２０の公開鍵で暗号化されたデータを復号できる秘密鍵を有しないため、第１端末１０は第２端末２０から受信したデータの内容を知ることはできない。また、第１端末１０から第２端末２０に送信するデータは第２端末２０の公開鍵で暗号化されているが、送信前にノイズが混入される。そのため、第２端末２０が第１端末１０から受信したデータを復号しても、データに含まれるノイズの影響により、第１端末１０がノイズを混入させる前のデータの内容を知ることはできない。そのため、実施形態によれば、第１端末１０と第２端末２０は、互いに自身のデータの内容を開示することなく、フレーズ辞書の構築、フレーズに対応するラベルの取得、文字列Ｔ１と文字列Ｔ２とのＬ１距離の算出を行うことができる。
【０１０６】
実施形態では、構築されたフレーズ辞書（ベクトルＺ）は、フレーズ辞書の構築処理（図３のステップＳ２、図４のステップＳ２４）において暗号化された状態で乗算が行われる。そのため、暗号化のアルゴリズムに乗算について１回のみ準同型性を有するＢＧＮ暗号を採用した場合、フレーズ辞書に対する乗算を行うことができなくなる。実施形態では、構築したフレーズ辞書を一度復号してから再度暗号化することで、暗号化した状態のフレーズ辞書に対する乗算を可能にすることができる（図４のステップＳ２５）。
【０１０７】
実施形態では、ラベル取得処理、ラベル付与処理及びフレーズ辞書生成処理（図３、図４、図１０参照）において、ＢＧＮ暗号を採用する。ＢＧＮ暗号は任意回数の加算と１回の乗算について準同型性を有しており、任意回数の加算および乗算について準同型性を有するＧｅｎｔｒｙ暗号よりも高速に計算できる。そのため、実施形態によれば、Ｇｅｎｔｒｙ暗号をラベル取得処理やラベル付与処理に採用するシステムよりも、ラベル取得処理やラベル付与処理を高速に実行することができる。
【０１０８】
実施形態では、距離算出処理（図１１参照）における暗号化処理にＰａｉｌｌｉｅｒ暗号を採用する。Ｐａｉｌｌｉｅｒ暗号は乗算について準同型性を有しないことでＧｅｎｔｒｙ暗号やＢＧＮ暗号よりも高速に計算できる。そのため、実施形態によれば、Ｇｅｎｔｒｙ暗号やＢＧＮ暗号を距離算出処理に採用するシステムよりも、距離算出処理を高速に実行することができる。
【０１０９】
＜実施形態の変形＞
ステップＳ２１、Ｓ２２における暗号処理において、任意回数の乗算に対して準同型性を有する暗号アルゴリズム（例えば、Ｇｅｎｔｒｙ暗号）を採用した場合には、ベクトルＺをフレーズ辞書として使用可能である。この場合、図４のステップＳ２５の処理を省略することができるが、ＢＧＮを採用した実施形態と比較して計算量は増加する。
【０１１０】
実施形態では、第１端末１０および第２端末２０のそれぞれがハッシュ関数Ｈ１を記憶したが、ハッシュ関数Ｈ１を記憶する手段がこのような手段に限定されるわけではない。ハッシュ関数Ｈ１は、例えば、第１端末１０および第２端末２０の双方がアクセス可能な記憶装置に記憶されてもよい。
【０１１１】
実施形態では、第１端末１０は第２端末２０の公開鍵ＰＢ２およびＰＰ２を記憶し、第２端末２０は第１端末１０の公開鍵ＰＢ１およびＰＰ１を記憶した。しかしながら、公開鍵ＰＢ１、ＰＰ１、ＢＰ２、ＰＰ２を記憶する手段がこのような手段に限定されるわけではない。公開鍵ＰＢ１、ＰＰ１、ＢＰ２、ＰＰ２は、例えば、第１端末１０および第２端末２０の双方からアクセス可能な記憶装置に記憶されてもよい。
【０１１２】
実施形態において、任意回数の加算について準同型性を有するＰａｉｌｌｉｅｒ暗号が距離算出処理において採用されたが、ＢＧＮ暗号を距離算出処理において採用することを除外するものではない。ただし、加算についてのみ準同型性を有するＰａｉｌｌｉｅｒ暗号の方が、加算に加えて一回の乗算についても準同型性を有するＢＧＮ暗号よりも高速に演算できるため、加算のみを行う距離算出処理では、ＢＧＮ暗号よりもＰａｉｌｌｉｅｒ暗号の方が好適である。
【０１１３】
実施形態において、第１端末１０のラベル取得部１４および第２端末２０のラベル取得部２４は、文字列Ｔ１に含まれるフレーズのうち、ラベル問い合わせの対象とするフレーズにハッシュ関数Ｈ１を適用し、ハッシュ関数Ｈ１の出力値を基に決定した位置の要素を１としたベクトルを生成した。しかしながら、ハッシュ関数Ｈ１の出力値を基に決定した位置の要素は１以外の所定値としてもよい。所定値は、ラベル取得部１４とラベル取得部２４とが共通の値を用いれば良い。
【０１１４】
実施形態において、第２装置２０が移動付き編集距離を算出したが、第１装置１０が移動付き編集距離を算出してもよい。この場合、図１１のＴ３からＴ７の処理において、処理の主体を第１装置１０と第２装置２０とで入れ替えればよい。第２装置２０がＴ４の処理を実行することは、「第２ノイズ混入処理」の一例である。また、「第２ノイズ混入処理」が行われたノイズベクトルは「第３ノイズベクトル」の一例である。
【０１１５】
以上で開示した実施形態や変形例はそれぞれ組み合わせる事ができる。
【０１１６】
<<コンピュータが読み取り可能な記録媒体>>
コンピュータその他の機械、装置（以下、コンピュータ等）に上記いずれかの機能を実現させる情報処理プログラムをコンピュータ等が読み取り可能な記録媒体に記録することができる。そして、コンピュータ等に、この記録媒体のプログラムを読み込ませて実行させることにより、その機能を提供させることができる。
【０１１７】
ここで、コンピュータ等が読み取り可能な記録媒体とは、データやプログラム等の情報を電気的、磁気的、光学的、機械的、または化学的作用によって蓄積し、コンピュータ等から読み取ることができる記録媒体をいう。このような記録媒体のうちコンピュータ等から取り外し可能なものとしては、例えばフレキシブルディスク、光磁気ディスク、Ｃｏｍｐａｃｔ  Ｄｉｓｃ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ（ＣＤ−ＲＯＭ）、Ｃｏｍｐａｃｔ  Ｄｉｓｃ−Ｒｅｃｏｒｄａｂｌｅ（ＣＤ−Ｒ）、Ｃｏｍｐａｃｔ  Ｄｉｓｃ−ＲｅＷｒｉｔｅｒａｂｌｅ（ＣＤ−ＲＷ）、Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ（ＤＶＤ）、ブルーレイディスク（ＢＤ）、Ｄｉｇｉｔａｌ  Ａｕｄｉｏ  Ｔａｐｅ（ＤＡＴ）、８ｍｍテープ、フラッシュメモリなどのメモリカード等がある。また、コンピュータ等に固定された記録媒体としてハードディスクやＲＯＭ等がある。
【符号の説明】
【０１１８】
１０・・・第１端末
２０・・・第２端末
１１ａ、１１ｂ、２１ａ、２１ｂ・・・ビットベクトル生成部
１２、２２・・・辞書管理部
１３、２３・・・ラベル付与部
１４、２４・・・ラベル取得部
１５、２５・・・ラベルベクトル生成部
１６・・・第１返送部
２６・・・第２返送部
１７・・・距離返送部
２７・・・距離算出部
１０１、２０１・・・ＣＰＵ
１０２、２０２・・・主記憶部
１０３、２０３・・・補助記憶部
１０４、２０４・・・通信部
１０５、２０５・・・入力部
１０６、２０６・・・出力部
Ｂ１、Ｂ２・・・接続バス
Ｎ１・・・ネットワーク
Ｈ１・・・ハッシュ関数
ＰＢ１、ＰＢ２、ＰＰ１、ＰＰ２・・・公開鍵
ＤＢ１、ＤＢ２、ＤＰ１、ＤＰ２・・・秘密鍵
Ｔ１、Ｔ２・・・文字列
【図１】
2020188438.tif 000007
【図２】
2020188438.tif 000008
【図３】
2020188438.tif 000009
【図４】
2020188438.tif 000010
【図５】
2020188438.tif 000011
【図６】
2020188438.tif 000012
【図７】
2020188438.tif 000013
【図８】
2020188438.tif 000014
【図９】
2020188438.tif 000015
【図１０】
2020188438.tif 000016
【図１１】
2020188438.tif 000017