(57)【特許請求の範囲】
【請求項１】
クライアントにおいて記憶される観測値系列に基づいてサーバーにおいて記憶される隠れマルコフモデル(ＨＭＭ)のパラメーターを求めるための方法であって、前記クライアントは加法準同型性暗号システムの解読鍵及び暗号鍵を有し、前記サーバーは前記暗号鍵のみを有し、該方法は、
前記ＨＭＭのパラメーターを初期化するステップと、
Ｈ−ＳＭＣを用いて、前記ＨＭＭの前記パラメーターに対する前記観測値系列の確率を暗号化したものを求めるステップであって、該Ｈ−ＳＭＣは、加法準同型の少なくとも１つの性質を用いる、前記サーバーと前記クライアントとの間のセキュアマルチパーティ計算(ＳＭＣ)を含むものと、
前記ＨＭＭの状態ごとに、前記ＳＭＣを用いて、前記ＨＭＭの前記パラメーターに対する前記観測値系列の暗号化された前向き確率を求めるステップと、
前記ＨＭＭの状態ごとに、前記Ｈ−ＳＭＣを用いて、前記観測値系列の暗号化された後向き確率を求めるステップと、
前記ＨＭＭの前記パラメーターを与えられた場合に、前記観測値系列の要素ごとに、状態の各対の暗号化された条件付き結合確率を求め、１組の暗号化された条件付き結合確率を生成するステップであって、前記観測値系列の対数確率を暗号化したもの、前記暗号化された前向き確率、及び前記暗号化された後向き確率に基づき求められ、加法準同型の少なくとも１つの性質を用いて、暗号化されたドメインにおいて実行されるものと、
入力として前記１組の暗号化された条件付き結合確率を有する前記Ｈ−ＳＭＣを用いて、前記ＨＭＭの前記パラメーターを更新するステップと、
を含み、
該方法の前記各ステップは前記サーバーによって実行される、クライアントにおいて記憶される観測値系列に基づいてサーバーにおいて記憶される隠れマルコフモデルのパラメーターを求めるための方法。
【請求項２】
前記観測値系列の前記確率を暗号化したものを求めることと、前記暗号化された前向き確率を求めることと、前記暗号化された後向き確率を求めることと、前記暗号化された条件付き結合確率を求めることと、前記パラメーターを前記更新することとを、現在の反復の前記観測値系列の前記確率と先行する反復の前記観測値系列の前記確率との間の差がしきい値を超えるまで反復的に繰り返すことを更に含む、請求項１に記載の方法。
【請求項３】
前記初期化することは、前記ＨＭＭの前記パラメーターをランダムに生成することを含む、請求項１に記載の方法。
【請求項４】
Ｈ−前向き法を用いて、暗号化された対数前向き確率ξ(ｌｏｇαｔ(ｉ))、前記対数確率を暗号化したものξ(−ｌｏｇＰｒ{ｘ１，…，ｘＴ|λ})及び前記観測値系列の要素ｘｔ＋１の対数確率ξ(ｌｏｇｂｊ(ｘｔ＋１))を求めることであって、ここで、ξ(・)は前記加法準同型性暗号システムの暗号化関数であり、ｌｏｇαｔ(ｉ)は、現在の要素ｘｔまでの状態Ｓｉにおける前記観測値系列の前記前向き確率の対数であり、ｌｏｇＰｒ{ｘ１，…，ｘＴ|λ}はパラメーターλ＝{Ａ，Ｂ，Π}に対する前記観測値系列ｘｔ、ｔ＝１，２，…，Ｔの確率の対数であり、Ａ＝(ａｉｊ)は状態遷移行列であり、ａｉｊは状態Ｓｉから状態Ｓｊへの遷移確率であり、１≦ｉ、ｊ≦Ｎであり、Ｎは前記ＨＭＭの状態の数であり、Ｂ＝(ｂ１，ｂ２，…，ｂＮ)は観測値の確率の行列であり、ｂｊは前記観測値系列のアルファベットにわたる確率の行列の列ベクトルであり、ｊ＝１，２，…，Ｎであり、Π＝{π１，π２，…，πＮ}は前記ＨＭＭの初期状態確率ベクトルであるものと、
Ｈ−後向き法を用いて、前記暗号化された後向き確率ξ(ｌｏｇβｔ＋１(ｊ))を求めることと、
【数１】
0005579327.tif 000093
に従って、条件付き確率の暗号化された対数ξ(ｌｏｇζｔ(ｉ，ｊ))を求めることと、
Ｈ−指数法を用いて、前記暗号化された条件付き結合確率を求めることと、
を更に含む請求項１に記載の方法。
【請求項５】
【数２】
0005579327.tif 000094
に従って加法準同型の少なくとも１つの性質を用いて、全条件付き確率γｔ(ｉ)を暗号化したものξ(γｔ(ｉ))を求めることを更に含む、請求項４に記載の方法。
【請求項６】
変更ベクトルを求めることと、
前記ＨＭＭの状態ごとに、暗号化されたドメインにおいて前記変更ベクトルを用いて変更された状態の初期確率を暗号化したものを前記クライアントに送信することと、
前記ＨＭＭの状態ごとに、暗号化されていないドメインにおいて前記変更ベクトルを用いて変更された前記状態の初期確率を受信することと、
前記変更ベクトルを除去することであって、前記暗号化されていないドメインにおいて前記初期確率を生成するものと、
を更に含む、請求項５に記載の方法。
【請求項７】
前記初期確率に基づいて、初期状態確率ベクトル
【数３】
0005579327.tif 000095
を更新することを更に含む、請求項６に記載の方法。
【請求項８】
【数４】
0005579327.tif 000096
に従って前記暗号化されたドメインにおいて前記条件付き確率の総和を暗号化したものξ(Σｔ＝１Ｔ−１ζｔ(ｉ，ｊ))を求めることと、
【数５】
0005579327.tif 000097
に従って前記暗号化されたドメインにおいて前記全条件付き確率の総和を暗号化したものξ(Σｔ＝１Ｔ−１γｔ(ｉ))を求めることと、
Ｈ−対数法を用いて、前記条件付き確率の前記総和の対数を暗号化したものξ(ｌｏｇ(Σｔ＝１Ｔ−１ζｔ(ｉ，ｊ)))を求めることと、
前記Ｈ−対数法を用いて、前記全条件付き確率の前記総和の対数を暗号化したものξ(ｌｏｇ(Σｔ＝１Ｔ−１γｔ(ｉ)))を求めることと、
【数６】
0005579327.tif 000098
に従って前記加法準同型の性質を用いて、前記遷移確率の対数を暗号化したもの
【数７】
0005579327.tif 000099
を求めることと、
前記ＨＭＭの状態の対ごとに、前記遷移確率の対数を暗号化したものに基づいて前記ＳＭＣを用いて、更新済み遷移確率
【数８】
0005579327.tif 000100
を求めることと、
を更に含む請求項５に記載の方法。
【請求項９】
アルファベットｖｋの観測値シンボルごとに、Ｈ−総和分割法を用いて、暗号化された総和
【数９】
0005579327.tif 000101
を求めることと、
前記ＳＭＣを用いて、観測値の更新済み確率
【数１０】
0005579327.tif 000102
を求めることと、を更に含む、請求項５に記載の方法。
【請求項１０】
現在の反復中にＨ−前向き方法を用いて、前記ＨＭＭの更新済みパラメーター
【数１１】
0005579327.tif 000103
に基づいて前記現在の反復の前記観測値系列の前記確率
【数１２】
0005579327.tif 000104
を求めることであって、ここで、ｘｔは前記観測値系列、ｔ＝１，２，…，Ｔであるものと、
Ｈ−比較法を用いて前記差を求めることと、
を更に含む、請求項２に記載の方法。
【請求項１１】
前記差が前記しきい値以下であるときに、前記ＨＭＭの前記パラメーターを最終的なパラメーターとして選択することを更に含む、請求項２に記載の方法。
【請求項１２】
クライアントにおいて記憶される観測値系列に基づいて隠れマルコフモデル(ＨＭＭ)のパラメーターを求めるためのサーバーであって、前記クライアントは加法準同型性暗号システムの解読鍵及び暗号鍵を有し、該サーバーは前記暗号鍵のみを有し、該サーバーは、
前記ＨＭＭのパラメーターを初期化し、
現在の反復の前記観測値系列の確率と先行する反復の前記観測値系列の確率との間の差がしきい値を超えるまで、前記パラメーターを反復的に更新する、
ために構成されるプロセッサを備え、
反復する度に、前記パラメーターは、前記観測値系列及び前記ＨＭＭの前記パラメーターが与えられた場合に、状態の各対の暗号化された条件付き結合確率に基づいて更新され、該暗号化された条件付き確率は、Ｈ−ＳＭＣを用いて暗号化されたドメインにおいて求められ、前記Ｈ−ＳＭＣは、加法準同型の少なくとも１つの性質を用いる該サーバーと前記クライアントとの間のセキュアマルチパーティ計算(ＳＭＣ)を含み、
前記プロセッサは、
Ｈ−ＳＭＣを用いて前記ＨＭＭの前記パラメーターに対する前記先行する反復の前記観測値系列の確率を暗号化したものを求め、前記該Ｈ−ＳＭＣは、加法準同型の少なくとも１つの性質を用いる前記サーバーと前記クライアントとの間のセキュアマルチパーティ計算(ＳＭＣ)を含み、
前記ＨＭＭの状態ごとに、前記ＳＭＣを用いて前記ＨＭＭの前記パラメーターに対する前記観測値系列の暗号化された前向き確率を求め、
前記ＨＭＭの状態ごとに、前記Ｈ−ＳＭＣを用いて前記観測値系列の暗号化された後向き確率を求め、
前記観測値系列の要素ごとに、前記ＨＭＭの前記パラメーターを与えられた場合に、状態の各対の暗号化された条件付き結合確率を求め、１組の暗号化された条件付き結合確率を生成し、前記観測値系列の対数確率を暗号化したもの、前記暗号化された前向き確率及び前記暗号化された後向き確率に基づき求められ、
入力として前記１組の暗号化された条件付き結合確率を有する前記Ｈ−ＳＭＣを用いて、前記ＨＭＭの前記パラメーターを更新し、
Ｈ−ＳＭＣを用いて前記ＨＭＭの更新済みパラメーターに対する現在の反復の前記観測値系列の確率を暗号化したものを求め、
前記Ｈ−ＳＭＣを用いて、前記現在の反復の前記観測値系列の前記暗号化された確率と、前記先行する反復の前記観測値系列の前記暗号化された確率との間の差を求める、
ために構成される、クライアントにおいて記憶される観測値系列に基づいて隠れマルコフモデル(ＨＭＭ)のパラメーターを求めるためのサーバー。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は包括的には隠れマルコフモデルに基づく確率的推論に関し、より詳細には、隠れマルコフモデルに基づく確率的推論のための、サーバーコンピューターとクライアントコンピューターとの間のプライバシー保護計算に関する。
【背景技術】
【０００２】
隠れマルコフモデル(ＨＭＭ)に基づく確率的推論は、機械学習、音声処理及び遺伝子配列解析において一般的である。プライバシー制約を伴う確率的推論は、比較的未開拓の研究領域であり、データ及びＨＭＭが異なる関係者に属し、データ及びＨＭＭを共有することができないマルチパーティのシナリオに当てはまる。例えば、クライアントコンピューター(アリス)が、通話からの音声データを解析する必要がある。アリスは、トレーニングされたデータベースから得られたＨＭＭを所有するサーバーコンピューター(ボブ)に音声認識タスクを外注する。アリスは、プライバシーへの懸念から、ボブと音声データを共有することができず、一方、ボブは、トレーニングデータベースについての情報を暴露する可能性があるＨＭＭパラメーターを開示することができない。
【０００３】
ＨＭＭを介しての安全な推論のための１つの方法は、プライバシー保護２パーティ最大化法に基づいており、その方法では、いずれの関係者も厳密に同じプロトコルオーバーヘッドを被る。しかしながら、その方法は、計算量が多いタスクの大部分を実行するために、シンクライアントがデータを暗号化し、暗号化されたデータをサーバーに送信するような応用形態には適していない。
【０００４】
ＨＭＭ及びＨＭＭの３つの基本的な問題
ＨＭＭはマルコフ連鎖の一般化であり、ＨＭＭの状態が直接は不明であるが、解析可能な出力を生成する。それらの出力は「観測値」とも呼ばれる。観測値はＨＭＭの隠れ状態によって決まるので、観測値は隠れ状態についての情報を明らかにすることができる。
【０００５】
ＨＭＭλは三つ組のパラメーターλ＝(Ａ，Ｂ，Π)である。行列Ａ、Ａ＝(ａｉｊ)は状態遷移行列であり、ａｉｊは状態ＳｉからＳｉへの遷移確率であり、ただし、１≦ｉ，ｊ≦Ｎであり、ＮはＨＭＭの状態の数であり、ａｉｊ＝Ｐｒ{ｑｔ＋１＝Ｓｊ|ｑｔ＝Ｓｉ}、１≦ｉ，ｊ≦Ｎであり、{Ｓ１，Ｓ２，…，ＳＮ}は１組の状態であり、ｑｔは時刻ｔにおける状態であり、Ｐｒは結合確率である。
【０００６】
行列Ｂ、Ｂ＝(ｂ１，ｂ２，…，ｂＮ)は観測値の確率の行列であり、ｂｊは観測値系列の既知のアルファベットにわたる確率の行列の列ベクトルである。ただし、ｊ＝１，２，…，Ｎである。したがって、ｂｊ(ｖｋ)＝Ｐｒ{ｘｔ＝ｖｋ|ｑｔ＝Ｓｊ}、１≦ｊ≦Ｎ，１≦ｋ≦Ｍであり、ただし、{ｖ１，ｖ２，…，ｖＭ}は観測シンボルのアルファベットであり、ｘｔは時刻ｔにおける観測値である。ベクトルΠ、Π＝{π１，π２，…，πＮ}はＨＭＭの初期状態確率ベクトルであり、ただし、πｉ＝Ｐｒ{ｑ１＝Ｓｉ}である。
【０００７】
観測値系列ｘ１，ｘ２，…，ｘＴ及びＨＭＭλ＝(Ａ，Ｂ，Π)の場合、１つの問題はＨＭＭに対する観測値系列の確率、すなわち、Ｐｒ{ｘ１，ｘ２，…，ｘＴ|λ}を求めることである。非安全ドメインにおけるこの問題のための解決策は前向きアルゴリズム及び後向きアルゴリズムを含む。
【０００８】
統計的構文解析、例えば、遺伝子配列解析及び自然言語処理では、主な問題は、ＨＭＭに対する、観測値系列に対応する状態の最も起こり得る系列を求めることである。その問題は、ＨＭＭλ＝(Ａ，Ｂ，Π)の場合に、結合確率Ｐｒ{ｑ１，ｑ２，…，ｑＴ，ｘ１，ｘ２，…，ｘＴ|λ}を効率的に計算することである。その問題は通常、非安全ドメインにおいてビタビアルゴリズムによって解かれる。
【０００９】
別の問題は、観測値系列に基づいてＨＭＭのパラメーターを求めることである。非安全ドメインにおけるこの問題に対する１つの解決策は、バウム−ウェルチアルゴリズムを含む。
【００１０】
前向きアルゴリズム
時刻ｔにおいて状態Ｓｊにある観測値系列の結合確率は以下の通りである。
【００１１】
【数１】
0005579327.tif 000002
【００１２】
非安全ドメインにおける前向きアルゴリズムは以下のステップを含む。
１．α１(ｊ)＝πｊｂｊ(ｘ１)、１≦ｊ≦Ｎを初期化する
２．状態Ｓｊ、１≦ｊ≦Ｎごとに、かつ全ての観測値ｔ、１≦ｔ≦Ｔ−１の場合に、以下の式に従って、観測値系列の尤度を計算する。
３．
【００１３】
【数２】
0005579327.tif 000003
【００１４】
４．以下の式に従って、確率を求める。
５．
【００１５】
【数３】
0005579327.tif 000004
【００１６】
後向きアルゴリズム
後向き確率は以下の式に従って定義される。
６．
【００１７】
【数４】
0005579327.tif 000005
【００１８】
非安全ドメインにおける後向きアルゴリズムは、以下のことを含む。
７．βＴ(ｊ)＝１、１≦ｊ≦Ｎを初期化する
８．１≦ｉ≦Ｎごとに、かつ全ての１≦ｔ≦Ｔ−１の場合に、以下の式を求める。
９．
【００１９】
【数５】
0005579327.tif 000006
【００２０】
１０．以下の式に従って確率を求める。
１１．
【００２１】
【数６】
0005579327.tif 000007
【００２２】
ビタビアルゴリズム
時刻ｔにおいて状態Ｓｊで終了する、観測値系列のための最も確からしい状態系列の確率は以下の式に従って求められる。
【００２３】
【数７】
0005579327.tif 000008
【００２４】
ただし、ｍａｘは最大値の関数である。
【００２５】
非安全ドメインにおけるビタビアルゴリズムは、以下のステップを含む。
１２．全ての１≦ｊ≦Ｎの場合に、δ１(ｊ)＝πｊｂｊ(ｘ１)に従って最も確からしい状態系列を初期化し、確からしい状態のインデックスの行列をφ１(ｊ)＝０として初期化する。
１３．全ての１≦ｊ≦Ｎの場合に、かつ１≦ｔ≦Ｔ−１ごとに、以下の式に従って、次の時刻ｔ＋１の場合に状態Ｓｊにおいて終了する最も確からしい状態系列の確率、及びインデックスの行列を求める。
【００２６】
【数８】
0005579327.tif 000009
【００２７】
以下の式に従って、最も起こり得る最終的な状態のインデックスを求め、
【００２８】
【数９】
0005579327.tif 000010
【００２９】
インデックス
【００３０】
【数１０】
0005579327.tif 000011
【００３１】
をバックトラックする。ただし、ｔ＝１，２，…，Ｔ−１である。
【００３２】
最も確からしい状態系列
【００３３】
【数１１】
0005579327.tif 000012
【００３４】
を求める。
【００３５】
バウム−ウェルチアルゴリズム
バウム−ウェルチアルゴリズムは、前向き−後向きアルゴリズムとしても知られており、所与の観測値系列ｘ１，ｘ２，…，ｘＴの場合に最適なＨＭＭパラメーターを推定し、全ての隠れマルコフモデルにわたる観測値の確率を最大化する、すなわち、ｍａｘλＰｒ{ｘ１，ｘ２，…，ｘＴ|λ}を求める。
【００３６】
所与のＨＭＭλ＝(Ａ，Ｂ，Π)の場合に、時刻ｔにおいて状態Ｓｉにあり、時刻ｔ＋１において状態Ｓｊにある確率は、以下の式に従って、条件付き確率ζｔ(ｉ，ｊ)として定義される。
【００３７】
【数１２】
0005579327.tif 000013
【００３８】
ただし、その式は以下の式に等しい。
【００３９】
【数１３】
0005579327.tif 000014
【００４０】
式(１)及び式(３)において定義されるαｔ(ｉ)及びβｔ(ｉ)の表記を利用することによって、条件付き確率ζｔ(ｉ，ｊ)は以下のようになる。
【００４１】
【数１４】
0005579327.tif 000015
【００４２】
以下の式に従って、時刻ｔにおいて状態Ｓｉにある全条件付き確率γｔ(ｉ)が求められる。
【００４３】
【数１５】
0005579327.tif 000016
【００４４】
バウム−ウェルチアルゴリズムは、非安全ドメインにおいて、以下のようにＨＭＭλを更新する。
ＨＭＭλ＝(Ａ，Ｂ，Π)をランダムに初期化する
以下の式に従って状態の初期確率に基づいて初期状態確率ベクトルを求める。
【００４５】
【数１６】
0005579327.tif 000017
【００４６】
以下の式に従って、遷移確率を求める。
【００４７】
【数１７】
0005579327.tif 000018
【００４８】
アルファベットの観測値シンボルｖｋに基づいて、以下の式に従って観測値の確率を求める。
【００４９】
【数１８】
0005579327.tif 000019
【００５０】
以下の式に従って、更新済みＨＭＭに対する観測値系列の確率を求める。
【００５１】
【数１９】
0005579327.tif 000020
【００５２】
ただし、
【００５３】
【数２０】
0005579327.tif 000021
【００５４】
である。
【００５５】
【数２１】
0005579327.tif 000022
【００５６】
である場合には、中止し、そのＨＭＭのパラメーターを最終的なパラメーターとして選択する。ただし、Ｄは所定のしきい値である。そうでない場合には、
【００５７】
【数２２】
0005579327.tif 000023
【００５８】
を用いてＨＭＭλを更新し、ステップ２に戻る。
【００５９】
したがって、当該技術分野において、安全ドメインにおける前向きアルゴリズム、後向きアルゴリズム、ビタビアルゴリズム及バウム−ウェルチアルゴリズムを定めることが必要とされている。
【発明の概要】
【発明が解決しようとする課題】
【００６０】
この発明の実施の形態の目的は、プライバシー保護確率的推論のための方法を提供することである。
【００６１】
この発明の目的は、安全ドメインにおける前向きアルゴリズム、後向きアルゴリズム、ビタビアルゴリズム及バウム−ウェルチアルゴリズムを提供することである。
【００６２】
この発明の更なる目的は、クライアントコンピューターがデータを暗号化し、暗号化されたデータをサーバーコンピューターに送信し、サーバーが計算量の多いタスクの大部分を実行するような応用形態に適している方法を提供することである。
【課題を解決するための手段】
【００６３】
この発明の幾つかの実施の形態は、隠れマルコフモデルに基づく安全な確率的推論のためのサーバーとクライアントとの間のプライバシー保護計算を、加法準同型の性質を用いて非同期に実行できるという認識に基づいている。
【００６４】
したがって、一実施の形態は、クライアントにおいて記憶される観測値系列に基づいてサーバーにおいて記憶される隠れマルコフモデル(ＨＭＭ)のパラメーターを求めるための方法であって、前記クライアントは加法準同型性暗号システムの解読鍵及び暗号鍵を有し、前記サーバーは前記暗号鍵のみを有し、該方法は、前記ＨＭＭのパラメーターを初期化することと、Ｈ−ＳＭＣを用いて、前記ＨＭＭの前記パラメーターに対する前記観測値系列の確率を暗号化したものを求めることであって、該Ｈ−ＳＭＣは、加法準同型の少なくとも１つの性質を用いる、前記サーバーと前記クライアントとの間のセキュアマルチパーティ計算(ＳＭＣ)を含むものと、前記ＨＭＭの状態ごとに、前記ＳＭＣを用いて、前記ＨＭＭの前記パラメーターに対する前記観測値系列の暗号化された前向き確率を求めることと、前記ＨＭＭの状態ごとに、前記Ｈ−ＳＭＣを用いて、前記観測値系列の暗号化された後向き確率を求めることと、前記ＨＭＭの前記パラメーターを与えられた場合に、前記観測値系列の要素ごとに、状態の各対の暗号化された条件付き結合確率を求め、１組の暗号化された条件付き結合確率を生成することであって、前記観測値系列の前記対数確率を暗号化したもの、前記暗号化された前向き確率、及び前記暗号化された後向き確率に基づき求められ、加法準同型の少なくとも１つの性質を用いて、暗号化されたドメインにおいて実行されることと、入力として前記１組の暗号化された条件付き結合確率を有する前記Ｈ−ＳＭＣを用いて、前記ＨＭＭの前記パラメーターを更新することと、を含む、方法を開示する。
【００６５】
前記観測値系列の前記確率を暗号化したものを求めることと、前記暗号化された前向き確率を求めることと、前記暗号化された後向き確率を求めることと、前記暗号化された条件付き結合確率を求めることと、前記パラメーターを更新することと、は前記現在の反復の前記観測値系列の前記確率と先行する反復の前記観測値系列の前記確率との間の差がしきい値を超えるまで反復的に繰り返すことができる。
【００６６】
別の実施の形態は、クライアントにおいて記憶される観測値系列に基づいてサーバーにおいて記憶される隠れマルコフモデル(ＨＭＭ)のパラメーターを求めるための方法であって、前記クライアントは加法準同型性暗号システムの解読鍵及び暗号鍵を有し、前記サーバーは前記暗号鍵のみを有し、該方法は、前記ＨＭＭのパラメーターを初期化することと、現在の反復の前記観測値系列の確率と先行する反復の前記観測値系列の確率との間の差がしきい値を超えるまで、前記パラメーターを反復的に更新することであって、反復する度に、前記パラメーターは、前記観測値系列及び前記ＨＭＭの前記パラメーターが与えられた場合に、状態の各対の暗号化された条件付き結合確率に基づいて更新され、該暗号化された条件付き確率は、前記サーバーと前記クライアントとの間のセキュアマルチパーティ計算(ＳＭＣ)を用いて暗号化されたドメインにおいて求められるものと、を含み、該方法のステップは前記サーバーによって実行される、方法を開示する。
【００６７】
更に別の実施の形態は、クライアントにおいて記憶される観測値系列に基づいて隠れマルコフモデル(ＨＭＭ)のパラメーターを求めるためのサーバーであって、前記クライアントは加法準同型性暗号システムの解読鍵及び暗号鍵を有し、該サーバーは前記暗号鍵のみを有し、該サーバーは、前記ＨＭＭのパラメーターを初期化し、現在の反復の前記観測値系列の確率と先行する反復の前記観測値系列の確率との間の差がしきい値を超えるまで、前記パラメーターを反復的に更新するために構成されるプロセッサを備え、反復する度に、前記パラメーターは、前記観測値系列及び前記ＨＭＭの前記パラメーターが与えられた場合に、状態の各対の暗号化された条件付き結合確率に基づいて更新され、該暗号化された条件付き確率は、Ｈ−ＳＭＣを用いて暗号化されたドメインにおいて求められ、前記Ｈ−ＳＭＣは、加法準同型の少なくとも１つの性質を用いる該サーバーと前記クライアントとの間のセキュアマルチパーティ計算(ＳＭＣ)を含む、サーバーを開示する。
【図面の簡単な説明】
【００６８】
【図１】この発明の幾つかの実施の形態によるシステムのブロック図である。
【図２】この発明の幾つかの実施の形態によるＨ−対数法のブロック図である。
【図３】この発明の幾つかの実施の形態によるＨ−指数法のブロック図である。
【図４】この発明の幾つかの実施の形態によるＨ−対数総和法のブロック図である。
【図５】この発明の幾つかの実施の形態によるＨ−比較法のブロック図である。
【図６】この発明の幾つかの実施の形態によるＨ−総和分割法のブロック図である。
【図７Ａ】Ｈ−前向き法の種々の実施の形態のブロック図を示す図である。
【図７Ｂ】Ｈ−前向き法の種々の実施の形態のブロック図を示す図である。
【図７Ｃ】Ｈ−前向き法の種々の実施の形態の擬似コードを示す図である。
【図７Ｄ】Ｈ−前向き法の種々の実施の形態のブロック図を示す図である。
【図７Ｅ】Ｈ−前向き法の種々の実施の形態のブロック図を示す図である。
【図８Ａ】Ｈ−後向き法の種々の実施の形態のブロック図を示す図である。
【図８Ｂ】Ｈ−後向き法の種々の実施の形態の擬似コードを示す図である。
【図９Ａ】Ｈ−ビタビ法の種々の実施の形態のブロック図を示す図である。
【図９Ｂ】Ｈ−ビタビ法の種々の実施の形態の擬似コードを示す図である。
【図１０Ａ】Ｈ−バウム−ウェルチ法の種々の実施の形態のブロック図を示す図である。
【図１０Ｂ】Ｈ−バウム−ウェルチ法の種々の実施の形態のブロック図を示す図である。
【図１０Ｃ】Ｈ−バウム−ウェルチ法の種々の実施の形態のブロック図を示す図である。
【図１０Ｄ】Ｈ−バウム−ウェルチ法の種々の実施の形態のブロック図を示す図である。
【図１０Ｅ】Ｈ−バウム−ウェルチ法の種々の実施の形態のブロック図を示す図である。
【図１０Ｆ】Ｈ−バウム−ウェルチ法の種々の実施の形態の擬似コードを示す図である。
【発明を実施するための形態】
【００６９】
システム概説
図１は、この発明の幾つかの実施の形態を利用するシステム１００を示す。クライアント１１０が観測値系列１１５を記憶する。サーバー１２０が隠れマルコフモデル(ＨＭＭ)１２５を記憶する。また、クライアントは加法準同型性暗号システムのための解読鍵１５０及び暗号鍵１４０も記憶する。サーバーは暗号鍵１４０のみを有する。
【００７０】
クライアント及びサーバーは、ＨＭＭに対する観測値系列の安全な確率的推論を行うために、加法準同型の少なくとも１つの性質を用いるセキュアマルチパーティ計算(ＳＭＣ)、すなわち、Ｈ−ＳＭＣを実行する。本明細書において参照されるときに、接頭語「Ｈ−」は、通信、計算又は方法が、加法準同型の少なくとも１つの性質を用いて安全ドメインにおいて実行されることを示す。例えば、Ｈ−ＳＭＣ１３０は、後に更に詳細に説明されるように、少なくとも１つのＨ−方法１６０を使用することができる。クライアント及びサーバーは、プロセッサ１０１及び／又はプロセッサ１０２のようなプロセッサを用いて実現することができる。
【００７１】
加法準同型性暗号システム
任意の２つのメッセージｍ１、ｍ２及び加法準同型性暗号化関数ξ(・)の場合、加法準同型性は、ξ(ｍ１＋ｍ２)＝ξ(ｍ１)ξ(ｍ２)を確実にする。この性質のため、幾つかの演算は暗号化されたメッセージ(暗号文)において直接実行することができ、それにより、根底を成す暗号化されていないメッセージ(平文)における幾つかの操作を可能にする。この発明の実施の形態は、任意の加法準同型性暗号システムを用いることができる。例えば、１つの実施の形態は、以下に説明されるパイエ(Paillier)暗号を使用する。
【００７２】
構成：Ｎ＝ｐｑとなるような２つの大きな素数ｐ、ｑを選択する。Ｎ２を法とする逆数を有する１組の非負の整数を
【００７３】
【数２３】
0005579327.tif 000024
【００７４】
によって表す。ｇｃｄ(Ｌ(ｇλｍｏｄＮ２)，Ｎ)＝１であるような
【００７５】
【数２４】
0005579327.tif 000025
【００７６】
を選択する。ただし、λ＝１ｃｍ(ｐ−１，ｑ−１)及びＬ(ｘ)＝(ｘ−１)／Ｎである。(Ｎ，ｇ)を暗号鍵とし、(ｐ，ｑ)を解読鍵とする。
【００７７】
暗号化：ｍ∈ＺＮを平文とする。その際、暗号文は以下の式によって与えられる。
【００７８】
【数２５】
0005579327.tif 000026
【００７９】
ただし、ｒ∈Ｚ＊Ｎはランダムに選択された数である。
【００８０】
解読：
【００８１】
【数２６】
0005579327.tif 000027
【００８２】
を暗号文とする。その際、対応する平文は以下の式によって与えられる。
【００８３】
【数２７】
0005579327.tif 000028
【００８４】
加法準同型性暗号システムでは、解読は、暗号化中に用いられるｒの値に関係なく機能する。ｒは暗号化のたびにランダムに選択されるので、パイエ暗号システムは確率的であり、意味的に安全であり、すなわち、同じ平文を繰り返し暗号化しても、結果として異なる暗号文が生成される。
【００８５】
さらに、加法準同型は、以下の性質を含む。
【００８６】
【数２８】
0005579327.tif 000029
【００８７】
ただし、一般的に、ｒ１、ｒ２∈Ｚ＊Ｎ及びｒ１≠ｒ２である。明確にするために、本開示では以後、下付きの確率パラメーターを省略する。
【００８８】
紛失通信
この発明の幾つかの実施の形態は、１−ｏｆ−ｎ紛失通信(ＯＴ)を用いる。
【００８９】
例えば、サーバーはｎ個のメッセージｍ１，ｍ２，…ｍｎを有することができ、クライアントはインデックス１≦ｉ≦ｎを有することができる。ＯＴは、以下のことを成し遂げる方法である。クライアントはメッセージｍｉを特定したが、他のメッセージについては何も発見せず、サーバーはインデックスｉを発見しない。ＯＴは、多くの既知の方法において実施することができる。ＯＴは十分に原始的であり、すなわち、関数を代数回路として表すことができるなら、任意の関数の安全な数値計算(evaluation)のために用いることができる。しかしながら、ＯＴのみを用いて一般関数を数値計算するのは、計算及びデータ転送の観点から複雑である。
【００９０】
Ｈ−方法
この発明の種々の実施の形態は、以下に説明されるＨ−方法１６０の少なくとも１つ又は組み合わせを使用する。全てのＨ−方法において、クライアントは加法準同型性暗号システムの解読鍵及び暗号鍵、例えば、パイエ暗号化関数ξ(・)のための鍵対を有する。サーバーは暗号鍵のみを有する。Ｈ−方法は、加法準同型の少なくとも１つの性質を用いるＨ−ＳＭＣに基づく。この説明を明確にするために、対数を含む全ての計算において、対数の底は
【００９１】
【数２９】
0005579327.tif 000030
【００９２】
であり、それはパイエ暗号のために用いられるパラメーターである。表記上の混乱を避けるために、対数の底は明示されない。
【００９３】
安全なＨ−対数法
図２は、Ｈ−対数法２００の流れ図を示す。その方法への入力は、サーバーにおいて記憶される暗号化された変数ξ(θ)２０５である。出力において、サーバーは暗号化された変数θの対数を暗号化したものξ(ｌｏｇθ)２３５を求める。クライアントは変数θについての情報を入手しない。
【００９４】
サーバーは整数βをランダムに選択し、暗号化された変更済み変数２１５ξ(θ)β＝ξ(βθ)をクライアントに送信する(２１０)。クライアントはβθを解読し、サーバーが変更済み変数の暗号化された対数ξ(ｌｏｇβθ)２２５を受信する(２２０)ように変更済み変数を処理する。
【００９５】
サーバーはＨ−性質、すなわち、以下の式による加法準同型の性質を用いて、変数の暗号化された対数２３５を求める(２３０)。
【００９６】
【数３０】
0005579327.tif 000031
【００９７】
幾つかの実施の形態では、対数ｌｏｇβ及びｌｏｇβθは整数ではなく、それらの実施の形態は整数近似を用いる。例えば、サーバーがクライアントから
【００９８】
【数３１】
0005579327.tif 000032
【００９９】
を受信する。ただし、Ｌは大きな整数であり、例えば、Ｌ＝１０６である。整数Ｌとの全ての乗算は、全ての解読時に対応する除算によって補償される。幾つかの実施の形態では、整数近似は種々のＨ−方法によって用いられる。
【０１００】
この例では、Ｈ−方法は小数第６位まで正確である。同様に、サーバーは以下の式を求める。
【０１０１】
【数３２】
0005579327.tif 000033
【０１０２】
安全なＨ−指数法
図３は、Ｈ−指数法３００の流れ図を示す。その方法への入力は、サーバーにおいて記憶される暗号化された対数ξ(ｌｏｇθ)３０５である。出力において、サーバーは変数を暗号化したものξ(θ)３３５を求め、クライアントは変数θについての情報を入手しない。
【０１０３】
サーバーは整数βをランダムに選択し、以下の式に従って暗号化された変更済み対数３１５をクライアントに送信する(３１０)。
【０１０４】
【数３３】
0005579327.tif 000034
【０１０５】
クライアントは暗号化された対数を解読し、対数ｌｏｇβθを受信し、サーバーが暗号化された変更済み変数ξ(βθ)３２５を受信する(３２０)ように、その対数を処理する。サーバーは、以下の式に従って、暗号化された変数３３５を求める(３３０)。
【０１０６】
【数３４】
0005579327.tif 000035
【０１０７】
ただし、１／βは
【０１０８】
【数３５】
0005579327.tif 000036
【０１０９】
内の整数βの逆数である。
【０１１０】
安全なＨ−対数総和法
図４は、Ｈ−対数総和法４００の流れ図を示す。その方法への入力は、サーバーにおいて記憶される１組の暗号化された対数(ξ(ｌｏｇθ１)，ξ(ｌｏｇθ２)，…，ξ(ｌｏｇθｎ))４０５及び定数ベクトル(ａ１，ａ２，…，ａｎ)４０６である。出力において、サーバーは、対数総和を暗号化したものξ(ｌｏｇΣｎｉ＝１ａｉθｉ)４３５を求め、クライアントは変数θｉ及びａｉについての情報を特定しない。
【０１１１】
サーバー及びクライアントは、サーバーが１組の暗号化された変数４１５
【０１１２】
【数３６】
0005579327.tif 000037
【０１１３】
を求めるように、入力として１組の暗号化された対数４０５を有するＨ−指数法３００を実行する(４１０)。
【０１１４】
サーバーはＨ−性質を用いて、以下の式に従って、定数ベクトルの要素の累乗において暗号化された変数の積４２５を求める(４２０)。
【０１１５】
【数３７】
0005579327.tif 000038
【０１１６】
サーバー及びクライアントは、Ｈ−対数法２００を実行して(４３０)、対数総和を暗号化したものξ(ｌｏｇΣｎｉ＝１ａｉθｉ)４３５を求める。
【０１１７】
安全なＨ−比較法
図５は、Ｈ−比較法５００の流れ図を示す。その方法への入力は、サーバーにおいて記憶される少なくとも２つの暗号化された変数、例えば、第１の変数を暗号化したものξ(θ１)５０５及び第２の変数を暗号化したものξ(θ２)５０６である。出力において、サーバーはθ１≦θ２５３５であるか否かを判断し、クライアントは変数θ１及びθ２についての情報を特定しない。
【０１１８】
サーバーは正又は負の整数αをランダムに選択し、以下の式による、変更済みの差を暗号化したもの５１５をクライアントに送信する(５１０)。
【０１１９】
【数３８】
0005579327.tif 000039
【０１２０】
クライアントは解読し、変更済みの差α(θ１−θ２５２５)を受信し、変更済みの差をサーバーに返送する。サーバーは変更済みの差５２５を受信し(５２０)、整数αの正負符号に基づいて、θ１≦θ２であるか否かを比較する(５３０)。
【０１２１】
安全なＨ−総和分割法
図６は、Ｈ−総和分割法６００の流れ図を示す。その方法への入力は、クライアントにおいて記憶される一連の要素ｘ１，ｘ２，…，ｘＴである。各要素ｘｔはアルファベットＶ＝{ｖ１，ｖ２，…，ｖＭ}から選択される。また、その方法への入力は、サーバーにおいて記憶される一連の変数を暗号化したものξ(ｙ１)，ξ(ｙ２)，…，ξ(ｙＴ)６０５である。サーバー及びクライアントは共通の要素ｖ∈Ｖを有する。出力において、サーバーは、サーバーが一連の要素について何も特定せず、かつクライアントが一連の暗号化されたものについて何も特定しないように、総和を暗号化したもの
【０１２２】
【数３９】
0005579327.tif 000040
【０１２３】
６３５を求める。ただし、ｔ＝１，２，…，Ｔである。
【０１２４】
サーバーは、暗号化ξ(ｙｔ)ごとに、整数αｔをランダムに選択し、以下の式に従って、変更済みの暗号したものを和６１５としてクライアントに送信する(６１０)。
【０１２５】
【数４０】
0005579327.tif 000041
【０１２６】
クライアントはその和を解読し、和の積を暗号化したものξ(δｔ(ｖ)(ｙｔ＋αｔ))６２５及び指示子系列を暗号化したものξ(δｔ(ｖ))６２６を求め、暗号化したもの６２５及び６２６をサーバーに送信する。ただし、共通の要素ｖの場合のｘ１，ｘ２，…，ｘＴの指示子系列δｔ(ｖ)は、ｘｔ＝ｖの場合にはδｔ(ｖ)＝１に従って、及びｘｔ≠ｖの場合にはδｔ(ｖ)＝０に従って求められる。
【０１２７】
サーバーは積を暗号化したもの６２５及び指示子系列を暗号化したもの６２６を受信し(６２０)、変更を除去して、以下の式に従って、変数ｙｔと指示子系列との積を暗号化したもの６２７を求める。
【０１２８】
【数４１】
0005579327.tif 000042
【０１２９】
次に、サーバーは
【０１３０】
【数４２】
0005579327.tif 000043
【０１３１】
に従って、総和
【０１３２】
【数４３】
0005579327.tif 000044
【０１３３】
を暗号化したもの６３５を求める(６３０)。
【０１３４】
安全なＨ−前向き法
図７Ａは、この発明の幾つかの実施の形態によるＨ−前向き法７００の流れ図を示す。方法７００は、サーバー、例えば、サーバー１２０において記憶されるＨＭＭに対する、クライアント、例えば、クライアント１１０において記憶される観測値系列の確率を数値計算するのに適している。それらの実施の形態によれば、クライアントは加法準同型性暗号システムの解読鍵及び暗号鍵を有し、サーバーは暗号鍵のみを有する。
【０１３５】
その方法は、サーバーによって実行されるステップに基づいて説明される。しかしながら、その方法のうちの少なくとも１つのステップは、サーバーとクライアントとの間のＨ−ＳＭＣを含む。その方法の種々のステップは、ＨＭＭの状態ごとに、及び／又は観測値系列ｘ１，ｘ２，…，ｘＴの観測値ごとに反復的に実行される。その方法の出力において、サーバーはξ(ｌｏｇＰｒ{ｘ１，ｘ２，…，ｘＴ|λ)}に従って、観測値系列の対数確率を暗号化したものを求める。
【０１３６】
ＨＭＭλは、例えば、λ＝{Ａ，Ｂ，Π}に従って定義される。ただし、Ａ＝(ａｉｊ)は状態遷移行列であり、ａｉｊはＳｉからＳｊへの遷移確率であり、ただし、１≦ｉ、ｊ≦Ｎであり、ＮはＨＭＭの状態の数であり、Ｂ＝(ｂ１，ｂ２，…，ｂＮ)は観測値の確率の行列であり、ｂｊは観測値系列のアルファベットにわたる確率の行列の列ベクトルであり、ｊ＝１，２，…，Ｎであり、Π＝(π１，π２，…，πＮ)はＨＭＭの初期状態確率ベクトルである。
【０１３７】
サーバーは、ＨＭＭの状態ごとに、観測値系列の現在の要素の対数確率を暗号化したもの７１５を求める(７１０)。例えば、対数確率を暗号化したものは以下の式に従って求めることができる。
【０１３８】
【数４４】
0005579327.tif 000045
【０１３９】
ただし、ｘｔ＋１は観測値系列の現在の要素であり、ξ(・)は加法準同型性暗号システムの暗号化関数である。
【０１４０】
また、サーバーは、ＨＭＭの状態ごとに、観測値系列の先行する要素に基づく観測値系列の尤度とＨＭＭの状態への遷移確率との積の対数総和を暗号化したもの７２５を求める(７２０)。対数総和はＨ−ＳＭＣを用いて求めることができ、Ｈ−ＳＭＣは加法準同型の少なくとも１つの性質を用いるセキュアマルチパーティ計算を含む。例えば、１つの実施の形態はＨ−対数総和法４００を用いる。
【０１４１】
例えば、幾つかの実施の形態は、以下の式に従って、対数総和を暗号化したものを求める。
【０１４２】
【数４５】
0005579327.tif 000046
【０１４３】
ただし、ｌは状態Ｓｌのインデックス、ｌ＝１，２，…，Ｎであり、αｔ(ｌ)は状態Ｓｌにおける先行する要素ｘｔの観測値系列の尤度であり、ａｌｊはＨＭＭの状態Ｓｌから状態Ｓｊへの遷移確率である。
【０１４４】
１つの実施の形態は、以下の式に従って、対数総和を暗号化したものを初期化する。ただし、ｊ＝１，２，…，Ｎである。
【０１４５】
【数４６】
0005579327.tif 000047
【０１４６】
サーバーは、対数総和を暗号化したものと、観測値系列の現在の要素の対応する対数確率を暗号化したものとの積として、状態ごとの観測値系列の対数尤度を暗号化したもの７３５を求める(７３０)。
【０１４７】
例えば、１つの実施の形態は、以下の式に従って、加法準同型の性質に基づいて観測値系列の対数尤度を暗号化したものξ(ｌｏｇαｔ＋１(ｊ))を求める。
【０１４８】
【数４７】
0005579327.tif 000048
【０１４９】
観測値系列の対数確率を暗号化したもの７４５は、以下の式に従って、状態ごとの観測値系列の対数尤度に基づいて求められる(７４０)。
【０１５０】
【数４８】
0005579327.tif 000049
【０１５１】
例えば、１つの実施の形態は、入力として状態ごとの観測値系列の対数尤度を有するＨ−対数総和法を用いて、観測値系列の対数確率を暗号化したものを求める。観測値系列の対数確率を暗号化したものは、メモリ(図示せず)に記憶することができ、及び／又はクライアントに送信することができる(７５０)。
【０１５２】
図７Ｂは、１−ｏｆ−Ｍ紛失通信を用いて、観測値系列の現在の要素の対数確率を暗号化したものを求めるための１つの実施の形態による方法の流れ図を示す。
【０１５３】
サーバーは変更ベクトルγｔｊ７６１を求める(７６０)。例えば、１つの実施の形態では、変更ベクトルはランダムに生成される。変更ベクトルを用いて変更された観測値系列のアルファベットの対数確率の列ベクトルｌｏｇｂｊ＋γｔｊ７６３がクライアントに送信される(７６２)。１−ｏｆ−Ｍ  ＯＴを用いてクライアントがｌｏｇｂｊ(ｘｔ)＋γｔｊを求めた後に、サーバーは、変更ベクトルを用いて変更された観測値系列の各要素の対数確率を暗号化したもの７６５を受信し(７６４)、変更ベクトルを除去して(７６６)、各要素の対数確率を暗号化したもの７１５を生成する。
【０１５４】
例えば、サーバーはξ(ｌｏｇｂｊ(ｘｔ)＋γｔｊ)を受信し、ξ(ｌｏｇｂｊ(ｘｔ)＋γｔｊ)・ξ(−γｔｊ)に従って、各要素ｘｔの対数確率を暗号化したものξ(ｌｏｇｂｊ(ｘｔ))を求める。
【０１５５】
例示のみを目的として、図７Ｃは、Ｈ−前向き法の１つの実施の形態の擬似コード７６８を示す。この擬似コードは付録Ａにも記述される。
【０１５６】
安全なキーワード認識
この発明の幾つかの実施の形態は、プライバシー保護キーワード認識のためにＨ−前向き法を用いる。これらの実施の形態では、観測値系列は、サンプリングされた音声信号を含む。通常、クライアントは音声信号をＴ個のフレームに変換し、各フレームはメル周波数ケプストラム係数(ＭＦＣＣ)のｄ次元ベクトルによって表され、例えば、ｄ＝３９である。音声信号からのＭＦＣＣの導出は既知である。したがって、クライアントはｘｔ、ｔ＝１，２，…，Ｔを格納する。ただし、各ｘｔ∈Ｒｄである。
【０１５７】
サーバーは１組のサイズΔの異なるＨＭＭを記憶する。各ＨＭＭは単一のキーワードに対してトレーニングされる。この実施の形態のＨ−前向き法は、音声信号内に含まれる可能性が最も高いキーワードを求める。
【０１５８】
状態Ｓｊにおいて、ＭＦＣＣのｄ次元ベクトルｘｔは、平均ベクトルμｊ及び共分散行列Ｃｊを有する多変量ガウス分布、すなわち、ｂｊ(ｘｔ)＝Ｎ(μｊ，Ｃｊ)を有する。ただし、ｊ＝１，２，…，Ｎは、ＨＭＭλの状態をインデックス付けする。観測値ベクトルｚｔ＝［ｘｔＴ，ｌ］Ｔである場合には、ｌｏｇｂｊ(ｘｔ)＝ｚｔＴＷｊｚｔ、ｚｔ＝［ｘｔＴ，ｌ］Ｔである。ただし、Ｔは転置演算子であり、１≦ｊ≦Ｎであり、ＮはＨＭＭの状態の数であり、Ｗｊは以下の式による多変量ガウス分布の行列であり、
【０１５９】
【数４９】
0005579327.tif 000050
【０１６０】
ｗｊ＝(１／２)μｊＴＣｊ−１μｔ−(１／２)ｌｏｇ|Ｃｊ−１|−(ｄ／２)ｌｏｇ２πである。この実施の形態では、ベクトルｘｔは単一の多変量ガウス確率変数であるが、多変量ガウスの混合への拡張もこの発明の範囲内にある。行列Ｗｊはサーバーにおいて記憶される。さらに、対数確率ｌｏｇｂｊ(ｘｔ)は積ｚｍ(ｔ)ｚｎ(ｔ)の線形関数である。ただし、ｚｍ(ｔ)、ｚｎ(ｔ)はベクトルｚｔの要素であり、ｍ，ｎ∈{１，２，…，ｄ＋１}である。
【０１６１】
図７Ｄにおいて示されるように、この実施の形態は、観測値ベクトルの要素の積ｚｍ(ｔ)ｚｎ(ｔ)７７３を暗号化したものを受信する(７７２)のに応答して、加法準同型の少なくとも１つの性質を用いて、以下の式に従って、対数確率を暗号化したものξ(ｌｏｇｂｊ(ｘｔ))７１５を求める(７７４)。
【０１６２】
【数５０】
0005579327.tif 000051
【０１６３】
ただし、ｚｍ(ｔ)、ｚｎ(ｔ)は観測値ベクトルｚｔの要素であり、ｍ，ｎ∈{１，２，…，ｄ＋１}である。
【０１６４】
図７Ｅはこの発明の幾つかの実施の形態による安全なキーワード認識のための方法の流れ図を示す。サーバーにおいて記憶されたＨＭＭごとの観測値系列の対数確率を求めて(７８２)、１組の暗号化された対数確率を生成する。対数確率は、サーバーが以下の式を求めるように、Ｈ−前向き法の任意の実施態様を用いて求められる。
【０１６５】
【数５１】
0005579327.tif 000052
【０１６６】
サーバーは、順序保存行列を用いて１組の対数確率を難読化し(７８４)、難読化済みの１組の暗号化された対数確率を生成する。例えば、サーバーは順序保存行列Ｒ＝(ｒｉｊ)Δ×Δを求める。加法準同型の性質を用いて、サーバーは、以下の式に従って、難読化した要素を暗号化したものを求める。
【０１６７】
【数５２】
0005579327.tif 000053
【０１６８】
サーバーは、難読化済みの１組の対数確率をクライアントに送信し(７８６)、難読化済みの１組の対数確率に基づいてクライアントによって選択された特定の対数確率に対応するＨＭＭのキーワードをクライアントに送信する(７８８)。例えば、Ｒは順序保存写像であるので、クライアントは解読し、以下の式に従って、各ＨＭＭに対する観測値系列の最大確率を求めることができる。
【０１６９】
【数５３】
0005579327.tif 000054
【０１７０】
サーバーは紛失通信法を用いて最大確率に対応するキーワードを送信することができる。
【０１７１】
安全なＨ−後向き法
図８Ａは、この発明の幾つかの実施の形態による、観測値系列の確率を求めるためのＨ−後向き法８００の流れ図を示す。サーバーは、観測値系列の現在の要素の後向き確率を暗号化したもの８０５に基づいて、Ｈ−指数法を用いて、以下の式に従って、観測値系列の暗号化された後向き確率８１５を求める(８１０)。
【０１７２】
【数５４】
0005579327.tif 000055
【０１７３】
Ｈ−対数法を用いて、サーバーは、対数後向き確率を暗号化したものξ(ｌｏｇβｔ(ｉ))８２５を求める(８２０)。サーバーがξ(ｌｏｇβｔ(ｉ))を求めるまで、サーバーは、ＨＭＭの状態ごとに対数後向き確率を暗号化したものを再帰的に求める。
【０１７４】
加法準同型の性質及びＨ−指数法を用いて、サーバーは、観測値系列と初期状態Ｓｊとの結合確率を暗号化したものξ(πｊβ１(ｊ)ｂｊ(ｘ１))８３５と、観測値系列の確率を暗号化したもの
【０１７５】
【数５５】
0005579327.tif 000056
【０１７６】
８３６と、を求める(８３０)。Ｈ−対数法を用いて、サーバーは観測値系列の対数確率を暗号化したもの８４５を求める(８４０)。図８Ｂは、Ｈ−後向き法の１つの実施の形態の擬似コード８５０を示す。その擬似コードは付録Ｂにも記述される。
【０１７７】
安全なＨ−ビタビ法
図９Ａは、この発明の幾つかの実施の形態によるＨ−ビタビ法９００のブロック図を示す。方法９００は、クライアントにおいて記憶される観測値系列に対応する最も起こり得る一連の状態を求めるのに適しており、その一連の状態はサーバーにおいて記憶されるＨＭＭに対して求められる。クライアントは、加法準同型性暗号システムの解読鍵１５０及び暗号鍵１４０を有し、サーバーは暗号鍵１４０のみを有する。
【０１７８】
上記のように、ＨＭＭλはλ＝(Ａ，Ｂ，Π)に従って定義され、ただし、Ａ＝(ａｉｊ)は状態遷移行列であり、ａｉｊはＳｉからＳｊへの遷移確率であり、ただし、１≦ｉ、ｊ≦Ｎであり、ＮはＨＭＭの状態の数であり、Ｂ＝(ｂ１，ｂ２，…，ｂＮ)は観測値の確率の行列であり、ｂｊは観測値系列のアルファベットにわたる確率の行列の列ベクトルであり、ｊ＝１，２，…，Ｎであり、Π＝(π１，π２，…，πＮ)はＨＭＭの初期状態確率ベクトルである。
【０１７９】
方法９００の種々のステップは、加法準同型性暗号システムの暗号化関数ξ(・)及び加法準同型の少なくとも１つの性質を用いるＨ−ＳＭＣを使用する。その方法の幾つかのステップは、ＨＭＭの状態ごとに、及び／又は観測値系列ｘ１，ｘ２，…，ｘＴの観測値ごとに反復的に実行される。その方法の出力において、クライアントは、最も確からしい状態系列
【０１８０】
【数５６】
0005579327.tif 000057
【０１８１】
を求める。
【０１８２】
サーバーは、ＨＭＭの状態ごとに、観測値系列の現在の要素の対数確率を暗号化したものξ(ｌｏｇｂｊ(ｘｔ))９１５を求める(９１０)。対数確率を暗号化したもの９１５は、任意のＳＭＣを用いて求めることができる。例えば、１つの実施の形態は、図７Ｂに示される実施の形態と同じようにして、Ｈ−ＳＭＣを用いて、対数確率を暗号化したものを求める。
【０１８３】
具体的には、１つの実施の形態は、変更ベクトルを求め、変更ベクトルを用いて変更された観測値系列の要素の対数確率の列ベクトルをクライアントに送信する。例えば、変更ベクトル(γｔｊ)ｔ＝１，２，…，Ｔは、列ベクトルを送信することがｌｏｇｂｊ＋γｔｊを送信することを含むように、ランダムに生成することができる。
【０１８４】
クライアントは列ベクトルを処理し、サーバーは変更ベクトルを用いて変更された観測値系列の各要素の対数確率を暗号化したものを受信し、変更ベクトルを除去して、各要素の対数確率を暗号化したものを生成する。
【０１８５】
例えば、サーバーはξ(ｌｏｇｂｊ(ｘｔ)＋γｔｊ)を受信することができ、ξ(ｌｏｇｂｊ(ｘｔ)＋γｔｊ)・ζ(−γｔｊ)に従って、加法準同型の性質を用いて、各要素ｘｔの対数確率を暗号化したものξ(ｌｏｇｂｊ(ｘｔ))を求めることができる。
【０１８６】
サーバーは、ＨＭＭの状態ごとに、現在の要素のための状態の対数確率を暗号化したものと、その状態への遷移確率を暗号化したものとの積９２５を求め(９２０)、１組の暗号化された積を生成する。例えば、暗号化したものの積９２５は、以下の式に従って、加法準同型を用いて求めることができる。
【０１８７】
【数５７】
0005579327.tif 000058
【０１８８】
ただし、ξ(ｌｏｇδｔ(ｉ))は、現在の要素ｘｔの場合に状態Ｓｉにおいて終了する最も確からしい状態系列の確率の対数を暗号化したものであり、ξ(・)は加法準同型性暗号システムの暗号化関数であり、ξ(ｌｏｇａｉｊ)は状態Ｓｊから状態Ｓｉへの遷移確率の対数を暗号化したものである。
【０１８９】
サーバーは、クライアントとともにＨ−ＳＭＣ、例えば、Ｈ−比較法を用いて、１組の暗号化された積のうちの最大積に対応する暗号化された積９３５と、最大積に対応する状態の暗号化されたインデックスとを求める(９３０)。暗号化されたインデックスは、クライアントが状態のインデックスの行列を入手し、それらのインデックスを追跡して、最も確からしい状態系列を求めることができるように、クライアントに送信することができる(９５０)。
【０１９０】
次に、サーバーは、ＨＭＭの状態ごとに、暗号化された積と、その状態に対応する観測値系列の現在の要素の対数確率を暗号化したものとの積として、次の要素のための状態の暗号化された対数確率９４５を求め(９４０)、観測値系列の全ての要素に対して、暗号化された積及び暗号化されたインデックスを求めること(９３０)、暗号化されたインデックスを送信すること(９５０)及び対数確率を求めること(９４０)を繰り返す。
【０１９１】
例えば、１つの実施の形態は、ξ(ｌｏｇδｔ＋１(ｊ))＝ξ(ｍａｘｉ［ｌｏｇδｔ(ｉ)＋ｌｏｇａｉｊ］)・ξ(ｌｏｇｂｊ(ｘｔ))に従って、暗号化された対数確率ξ(ｌｏｇδｔ＋１(ｊ))を求める。ただし、ｌｏｇδｔ＋１(ｊ)は次の要素ｘｔ＋１の場合に状態Ｓｊにおいて終了する最も確からしい状態系列の確率の対数であり、ξ(・)は加法準同型性暗号システムの暗号化関数であり、ｍａｘは最大値演算であり、ｌｏｇδｔ(ｉ)は、現在の要素ｘｔの場合に状態Ｓｉにおいて終了する最も確からしい状態系列の確率の対数であり、ｌｏｇａｉｊは状態Ｓｉから状態Ｓｊへの遷移確率の対数である。
【０１９２】
図９Ｂは、Ｈ−ビタビ法の１つの実施の形態による擬似コード９６０を示す。
【０１９３】
安全なＨ−バウム−ウェルチ法
図１０Ａは、クライアントにおいて記憶される観測値系列に基づいてサーバーにおいて記憶される隠れマルコフモデル(ＨＭＭ)のパラメーターを求めるためのＨ−バウム−ウェルチ法１０００のブロック図を示す。クライアントは、加法準同型性暗号システムの解読鍵１５０及び暗号鍵１４０を有し、サーバーは暗号鍵１４０のみを有する。
【０１９４】
Ｈ−バウム−ウェルチ法は、１≦ｉ，ｊ≦Ｎ、１≦ｔ≦Ｔの全ての場合にＨＭＭζｔ(ｉ，ｊ)のパラメーターが与えられた場合の、状態の各対の条件付き結合確率の安全な計算に基づく。式(１０)の両辺において対数をとると、以下の式がもたらされる。
【０１９５】
【数５８】
0005579327.tif 000059
【０１９６】
したがって、関数ξ(・)は加法準同型性暗号化関数であるので、式(１５)は以下のように書き換えることができる。
【０１９７】
【数５９】
0005579327.tif 000060
【０１９８】
サーバーはＨＭＭのパラメーター１０１５を初期化する(１０１０)。例えば、パラメーターλ＝{Ａ，Ｂ，Π}はランダムに生成することができる。パラメーター１０１５に基づいて、サーバーは、クライアントとともにＨ−ＳＭＣを用いて、観測値系列の現在の要素の対数確率を暗号化したもの１０２５、及びＨＭＭのパラメーターに対する観測値系列の確率を暗号化したもの１０２６を求める(１０２０)。また、サーバーは、ＨＭＭの状態ごとに、ＨＭＭのパラメーターに対する観測値系列の暗号化された前向き確率１０３５、及び観測値系列の暗号化された後向き確率１０３６も求める(１０３０)。
【０１９９】
次に、サーバーは、ＨＭＭのパラメーターが与えられた場合に、観測値系列の要素ごとに、状態の各対の暗号化された条件付き結合確率を求め(１０４０)、１組の条件付き結合確率１０４５を生成する。幾つかの実施の形態では、求めることは、観測値系列の対数確率を暗号化したもの、暗号化された前向き確率及び暗号化された後向き確率に基づいて、式(１６)に従って実行される。１組の暗号化された条件付き結合確率は、加法準同型の少なくとも１つの性質を用いて、暗号化されたドメインにおいて求められる。
【０２００】
１組の暗号化された条件付き結合確率に基づいて、ＨＭＭのパラメーターが更新される(１０４５)。幾つかの実施の形態は、現在の反復のパラメーター１０５５の場合に求められた観測値系列の確率と、先行する反復のパラメーター１０１５の場合に求められた観測値系列の確率との間の差１０５６がしきい値Ｄ１０５７を超えるまで、観測値系列の確率を暗号化したものを求めること、暗号化された前向き確率を求めること、暗号化された後向き確率を求めること、暗号化された条件付き結合確率を求めること、及びパラメーターを更新することを反復的に繰り返す。
【０２０１】
１つの実施の形態では、図１０Ｂに示されるように、Ｈ−前向き法７００を用いて、暗号化された対数前向き確率ξ(ｌｏｇαｔ(ｉ))、対数確率を暗号化したものξ(−ｌｏｇＰｒ{ｘ１，…，ｘＴ|λ})及び観測値系列の要素ｘｔ＋１の対数確率を暗号化したものξ(ｌｏｇｂｊ(ｘｔ＋１))が求められる(１０６２)。
【０２０２】
上記の説明において、ξ(・)は加法準同型性暗号システムの暗号化関数であり、ｌｏｇαｔ(ｉ)は、現在の要素ｘｔまでの状態Ｓｉにおける観測値系列の前向き確率の対数であり、ｌｏｇＰｒ{ｘ１，…，ｘＴ|λ}はパラメーターλ＝{Ａ，Ｂ，Π}に対する観測値系列ｘｔ、ｔ＝１，２，…，Ｔの確率の対数であり、Ａ＝(ａｉｊ)は状態遷移行列であり、ａｉｊは状態Ｓｉから状態Ｓｊへの遷移確率であり、１≦ｉ，ｊ≦Ｎであり、ＮはＨＭＭの状態の数であり、Ｂ＝(ｂ１，ｂ１，…，ｂＮ)は観測値の確率の行列であり、ｂｊは観測値系列のアルファベットにわたる確率の行列の列ベクトルであり、ｊ＝１，２，…，Ｎであり、Π＝(π１，π２，…，πＮ)はＨＭＭの初期状態確率ベクトルである。
【０２０３】
暗号化された対数後向き確率ξ(ｌｏｇβｔ＋１(ｊ))は、Ｈ−後向き法８００を用いて求められる(１０６４)。条件付き確率の暗号化された対数ξ(ｌｏｇζｔ(ｉ，ｊ))は、以下の式に従って、加法準同型を用いて求められ(１０６６)、
【０２０４】
【数６０】
0005579327.tif 000061
【０２０５】
暗号化された条件付き結合確率は、Ｈ−指数法３００を用いて求められる(１０６８)。同様に、全条件付き確率γｔ(ｉ)を暗号化したものξ(γｔ(ｉ))は、以下の式に従って、加法準同型の少なくとも１つの性質を用いて求められる(１０６９)。
【０２０６】
【数６１】
0005579327.tif 000062
【０２０７】
図１０Ｃは、１つの実施の形態による、初期状態確率ベクトル
【０２０８】
【数６２】
0005579327.tif 000063
【０２０９】
を更新するための方法の流れ図を示す。サーバーは変更ベクトルを求め(１０７２)、ＨＭＭの状態ごとに、暗号化されたドメインにおいて変更ベクトルを用いて変更された初期確率を暗号化したものをクライアントに送信する(１０７４)。サーバーが、ＨＭＭの状態ごとに、暗号化されていないドメインにおいて変更ベクトルを用いて変更された状態の初期確率を受信する(１０７６)ように、クライアントは暗号を解読する。サーバーは、変更ベクトルを除去し(１０７８)、暗号化されていないドメインにおいて初期確率を生成し、その初期確率に基づいて初期状態確率ベクトル
【０２１０】
【数６３】
0005579327.tif 000064
【０２１１】
を更新する(１０７９)。
【０２１２】
図１０ＤはＨＭＭの遷移確率パラメーターを更新するための方法の流れ図を示す。条件付き確率ξ(Σｔ＝１Ｔ−１ζｔ(ｉ，ｊ))の総和を暗号化したものξ(Σｔ＝１Ｔ−１ζｔ(ｉ，ｊ))が、以下の式に従って、暗号化されたドメインにおいて求められる(１０８１)。
【０２１３】
【数６４】
0005579327.tif 000065
【０２１４】
全条件付き確率の総和を暗号化したものξ(Σｔ＝１Ｔ−１γｔ(ｉ))が、以下の式に従って、暗号化されたドメインにおいて求められる(１０８２)。
【０２１５】
【数６５】
0005579327.tif 000066
【０２１６】
条件付き確率の総和の対数を暗号化したものが、以下の式に従って、Ｈ−対数法を用いて求められ(１０８３)、
【０２１７】
【数６６】
0005579327.tif 000067
【０２１８】
全条件付き確率の総和の対数を暗号化したものが、以下の式に従って、Ｈ−対数法を用いて求められる(１０８４)。
【０２１９】
【数６７】
0005579327.tif 000068
【０２２０】
遷移確率の対数を暗号化したもの
【０２２１】
【数６８】
0005579327.tif 000069
【０２２２】
が、以下の式に従って、加法準同型の性質を用いて求められ(１０８５)、
【０２２３】
【数６９】
0005579327.tif 000070
【０２２４】
ＨＭＭの状態の対ごとに、遷移確率の対数を暗号化したものに基づいて、ＳＭＣを用いて、更新済み遷移確率
【０２２５】
【数７０】
0005579327.tif 000071
【０２２６】
が求められる(１０８６)。
【０２２７】
図１０Ｅは、観測値の確率
【０２２８】
【数７１】
0005579327.tif 000072
【０２２９】
を更新するための方法の流れ図を示す。アルファベットｖｋの観測値シンボルごとに、Ｈ−総和分割法６００を用いて(１０９３)、暗号化された総和
【０２３０】
【数７２】
0005579327.tif 000073
【０２３１】
が求められ(１０９１)、ＳＭＣを用いて(１０９４)、観測値の更新済み確率
【０２３２】
【数７３】
0005579327.tif 000074
【０２３３】
が求められる(１０９２)。
【０２３４】
ＨＭＭのパラメーターが更新された後に、ＨＭＭの更新済みパラメーター
【０２３５】
【数７４】
0005579327.tif 000075
【０２３６】
に基づいて、例えば、Ｈ−前向き法を用いて、現在の反復の観測値系列の確率
【０２３７】
【数７５】
0005579327.tif 000076
【０２３８】
が求められる。その確率は、例えば、Ｈ−比較法を用いて、前回の反復中に求められた確率と比較される。それらの確率間の差がしきい値以下である場合には、ＨＭＭのパラメーターが最終的なパラメーターとして選択される。
【０２３９】
図１０Ｆは、この発明の１つの実施の形態による、Ｈ−バウム−ウェルチ法の擬似コード１０９９を示す。
【０２４０】
この発明の上述した実施の形態は、数多くの方法のいずれにおいても実施することができる。例えば、実施の形態は、ハードウェア、ソフトウェア又はそれらの組合せを用いて実施することができる。ソフトウェアで実施される場合、ソフトウェアコードは、単一のコンピューターに設けられるのか又は複数のコンピューター間に分散されるのかにかかわらず、任意の適したプロセッサ又はプロセッサの集合体において実行することができる。そのようなプロセッサは、１つ又は複数のプロセッサを集積回路部品に有する集積回路として実装することができる。ただし、プロセッサは、任意の適したフォーマットの回路類を用いて実装することができる。
【０２４１】
さらに、コンピューターは、ラックマウント型コンピューター、デスクトップコンピューター、ラップトップコンピューター、ミニコンピューター又はタブレットコンピューター等の複数の形態のいずれにおいても具現化できることが理解されるべきである。また、コンピューターは、１つ又は複数の入力デバイス及び出力デバイスを有することもできる。そのようなコンピューターは、ローカルエリアネットワーク又はワイドエリアネットワークとしてエンタープライズネットワーク又はインターネット等を含む１つ又は複数のネットワークによって任意の適した形態で相互接続することができる。そのようなネットワークは、任意の適した技術に基づくことができ、任意の適したプロトコルに従って動作することができ、無線ネットワーク、有線ネットワーク又は光ファイバーネットワークを含むことができる。
【０２４２】
また、本明細書において概説される様々な方法又はプロセスは、様々なオペレーティングシステム又はプラットフォームのうちの任意のものを用いる１つ又は複数のプロセッサ上で実行可能なソフトウェアとして符号化することができる。加えて、そのようなソフトウェアは、複数の適切なプログラミング言語及び／又はプログラミングツール若しくはスクリプティングツールのうちの任意のものを用いて書くことができ、フレームワーク又は仮想マシン上で実行される実行可能な機械語コード又は中間コードとしてコンパイルすることもできる。
【０２４３】
これに関して、この発明は、単数又は複数のコンピューター可読記憶媒体、例えばコンピューターメモリ、コンパクトディスク(ＣＤ)、光ディスク、デジタルビデオディスク(ＤＶＤ)、磁気テープ、及びフラッシュメモリとして実現することができる。代替的に又は付加的に、この発明は、伝播信号等の、コンピューター可読記憶媒体以外のコンピューター可読媒体として具現化することもできる。
【０２４４】
「プログラム」又は「ソフトウェア」という用語は、本明細書において、包括的な意味で、上記で検討したこの発明の様々な態様を実施するようにコンピューター又は他のプロセッサをプログラムするのに用いることができる任意のタイプのコンピューターコード又は１組のコンピューター実行可能命令を指す。
【０２４５】
コンピューター実行可能命令は、１つ若しくは複数のコンピューター又は他のデバイスによって実行された、プログラムモジュール等の多くの形式をとることができる。一般に、プログラムモジュールは、特定のタスクを実行するか又は特定の抽象データタイプを実装するルーチン、プログラム、オブジェクト、コンポーネント、データ構造を含む。通常、プログラムモジュールの機能は、様々な実施の形態において所望に応じて組み合わせることも分散することもできる。
【０２４６】
また、この発明の実施の形態は、例が提供された方法として実施することができる。本方法の一部として実行される動作は、任意の適切な方法で順序付けすることができる。したがって、動作が示したものと異なる順序で実行される実施の形態を構築することができ、これには、例示の実施の形態では一連の動作として示されたにもかかわらず、幾つかの動作を同時に実行することを含めることもできる。
【０２４７】
付録Ａ
Ｈ−前向き法を実施する１つの実施の形態の擬似コード
入力：クライアントが観測値系列ｘ１，ｘ２，…，ｘＴを記憶する。サーバーがＨＭＭλ＝(Ａ，Ｂ，Π)を記憶する。
出力：ボブがξ(ｌｏｇＰｒ{ｘ１，ｘ２，…，ｘＴ|λ)}を求める。
１．ｔ＝１，２，…，Ｔ及びｊ＝１，２，…，Ｎごとに、サーバーがγｔｊをランダムに選択し、列ベクトルｌｏｇｂｊ＋γｔｊを生成する。
２．観測値ｘｔに基づいて、クライアントが１−ｏｆ−Ｍ  ＯＴを用いて、ｌｏｇｂｊ(ｘｔ)＋γｔｊを求める。
３．クライアントがξ(ｌｏｇｂｊ(ｘｔ)＋γｔｊ)をサーバーに送信する。
４．γｔｊ及び準同型性を用いて、ｊ＝１，２，…，Ｎ及びｔ＝１，２，…，Ｔの場合に、サーバーがξ(ｌｏｇｂｊ(ｘｔ)＋γｔｊ)・ξ(−γｔｊ)＝ξ(ｌｏｇｂｊ(ｘｔ))を求める。
５．サーバーが、ｊ＝１，２，…，Ｎの場合に、ξ(ｌｏｇα１(ｊ))＝ξ(ｌｏｇπｉ)・ξ(ｌｏｇｂｊ(ｘ１))を求める。
６．帰納ステップ：ｊ＝１，２，…，Ｎの場合に、入力ξ(ｌｏｇαｔ(ｊ))、ｊ＝１，２，…，Ｎ及び遷移行列Ａ＝(ａｉｊ)を用いて、サーバー及びクライアントがＨ−対数総和法を実行し、その終了時に、サーバーがξ(ｌｏｇΣｌ＝１Ｎαｔ(ｌ)ａｌｊ)を求める。
７．全ての１≦ｔ≦Ｔ−１の場合に、サーバーが以下の式を求める。
【０２４８】
【数７６】
0005579327.tif 000077
【０２４９】
８．サーバー及びクライアントがＨ−対数総和法を実行し、その終了時に、サーバーがξ(ｌｏｇΣｊ＝１ＮαＴ(ｊ))＝ξ(ｌｏｇＰ(ｘ１，ｘ２，…，ｘＴ|λ))を求める。
【０２５０】
付録Ｂ
Ｈ−後向き法を実施する１つの実施の形態の擬似コード
１．ｊ＝１，２，…，Ｎ及びｔ＝１，２，…，Ｔの場合に、サーバーがξ(ｌｏｇｂｊ(ｘｔ))を求める。
２．暗号化したものξ(ｌｏｇβｔ＋１(ｊ))が与えられた場合に、サーバーが以下の式を求める。
【０２５１】
【数７７】
0005579327.tif 000078
【０２５２】
３．Ｈ−指数法を用いて、サーバーがξ(βｔ＋１(ｊ)ａｉｊｂｊ(ｘｔ＋１))及び
【０２５３】
【数７８】
0005579327.tif 000079
【０２５４】
を求める。
４．Ｈ−対数法を用いて、サーバーがξ(ｌｏｇβ１(ｉ))、ｉ＝１，２，…，Ｎを有するまで、サーバーが暗号化したものξ(ｌｏｇβｔ(ｉ))を求める。
５．準同型性及びＨ−指数法を用いて、サーバーがξ(πｊβ１(ｊ)ｂｊ(ｘ１))及び
【０２５５】
【数７９】
0005579327.tif 000080
【０２５６】
を求める。
６．Ｈ−対数法を用いて、サーバーがξ(ｌｏｇＰ(ｘ１，ｘ２，…，ｘＴ|λ))を求める。
【０２５７】
付録Ｃ
Ｈ−ビタビ法を実施する１つの実施の形態の擬似コード
入力：クライアントが観測値系列ｘ１，ｘ２，…，ｘＴを記憶する。サーバーがＨＭＭλ＝(Ａ，Ｂ，Π)を記憶する。
出力：クライアントが最も確からしい状態系列
【０２５８】
【数８０】
0005579327.tif 000081
【０２５９】
を求める。
１．ｔ＝１，２，…，Ｔ及びｊ＝１，２，…，Ｎごとに、サーバーがγｔｊを選択し、列ベクトルｌｏｇｂｊ＋γｔｊを生成し、列ベクトルをクライアントに送信する。
２．１−ｏｆ−Ｍ  ＯＴを用いて、クライアントがｌｏｇｂｊ(ｘｔ)＋γｔｊを求める。
３．クライアントがξ(ｌｏｇｂｊ(ｘｔ)＋γｔｊ)をサーバーに送信する。
４．ｊ＝１，２，…，Ｎ、ｔ＝１，２，…，Ｔの場合に、γｔｊ及び準同型性を用いて、サーバーがξ(ｌｏｇｂｊ(ｘｔ)＋γｔｊ)・ξ(−γｔｊ)＝ξ(ｌｏｇｂｊ(ｘｔ))を求める。
５．サーバーが、ｊ＝１，２，…，Ｎの場合に、ξ(ｌｏｇδ１(ｊ))＝ξ(ｌｏｇπｊ)・ξ(ｌｏｇｂｊ(ｘ１))を求める。
６．反復：全てのｉ，ｊ＝１，２，…，Ｎ及びｔの場合に、サーバーがξ(ｌｏｇδｔ(ｉ)＋ｌｏｇａｉｊ)＝ξ(ｌｏｇδｔ(ｉ))・ξ(ｌｏｇａｉｊ)求める。
対(ｔ，ｊ)ごとに、サーバー及びクライアントが入力{ξ(ｌｏｇδｔ(ｉ)＋ｌｏｇａｉｊ)：ｉ＝１，２，…，Ｎ}
を用いて安全な最大値発見プロトコルを実行し、その後、サーバーが最大値を暗号化したものξ(ｍａｘｉ［ｌｏｇδｔ(ｉ)＋ｌｏｇａｉｊ］)及びξ(ｌｏｇδｔ＋１(ｊ))＝ξ(ｍａｘｉ［ｌｏｇδｔ(ｉ)＋ｌｏｇａｉｊ］)・ξ(ｌｏｇｂｊ(ｘｔ))を求める。
７．サーバーがインデックスφｔ＋１(ｊ)を送信する。
８．反復の最後に、クライアントが最後のインデックス行列［φｔ(ｊ)］ｔｊを受信するので、クライアントは後向きに追跡し、状態系列を求めることができる。
【０２６０】
付録Ｄ
Ｈ−バウム−ウェルチ法を実施する１つの実施の形態の擬似コード
入力：クライアントが観測値系列ｘ１，…，ｘＴ並びに暗号鍵及び解読鍵を記憶する。サーバーが暗号鍵のみを記憶する。
出力：サーバーがＨＭＭパラメーターを求め、観測値系列については何も発見しない。クライアントはパラメーターについての情報を特定しない。
１．サーバーがＨＭＭパラメーターλ＝(Ａ，Ｂ，Π)を初期化する。
２．入力ｘ１，…，ｘＴ及びλによるＨ−前向き法及びＨ−後向き法を用いて、サーバーがξ(ｌｏｇαｔ(ｉ))、ξ(ｌｏｇβｔ＋１(ｊ))、ξ(ｌｏｇｂｊ(ｘｔ＋１))及びξ(−ｌｏｇＰｒ{ｘ１，…，ｘＴ|λ})を求める。
３．式(１６)からサーバーがξ(ｌｏｇζｔ(ｉ，ｊ))を求める。
４．Ｈ−指数法を用いて、暗号化関数ξの準同型性を用いて、サーバーがξ(ζｔ(ｉ，ｊ))及びξ(γｔ(ｉ))＝Πｊ＝１Ｎξ(ζｔ(ｉ，ｊ))を求める。
５．サーバーがθｉをランダムに選択し、暗号化したものξ(θｉ＋γ１(ｉ))をクライアントに送信する。クライアントは解読し、サーバーにθｉ＋γ１(ｉ)を送信し、サーバーが
【０２６１】
【数８１】
0005579327.tif 000082
【０２６２】
を求める。
６．サーバーが暗号化したものξ(Σｔ＝１Ｔ−１ζｔ(ｉ，ｊ))＝Πｊ＝１Ｔ−１ξ(ζｔ(ｉ，ｊ))及びξ(Σｔ＝１Ｔ−１γｔ(ｉ))＝Πｊ＝１Ｔ−１ξ(γｔ(ｉ)))
を求める。Ｈ−対数法を用いて、サーバーがξ(ｌｏｇΣｔ＝１Ｔ−１ζｔ(ｉ，ｊ))、ξ(ｌｏｇΣｔ＝１Ｔ−１γｔ(ｉ))及び暗号化したもの
【０２６３】
【数８２】
0005579327.tif 000083
【０２６４】
を求め、その後、サーバーが、クライアントとともにＳＭＣを用いて
【０２６５】
【数８３】
0005579327.tif 000084
【０２６６】
を求める。
７．入力系列ｘ１，…，ｘＴ、暗号化したものξ(γｔ(ｉ))、ｔ＝１，２，…，Ｔ及び共通の要素ｖｋによるＨ−総和分割法を用いて、サーバーが、式(１３)に従って、暗号化したもの
【０２６７】
【数８４】
0005579327.tif 000085
【０２６８】
及び
【０２６９】
【数８５】
0005579327.tif 000086
【０２７０】
を求める。したがって、サーバーがＨＭＭのパラメータ
【０２７１】
【数８６】
0005579327.tif 000087
【０２７２】
を更新する。
８．入力として観測値系列及び
【０２７３】
【数８７】
0005579327.tif 000088
【０２７４】
を有するＨ−前向き法を用いて、サーバーが
【０２７５】
【数８８】
0005579327.tif 000089
【０２７６】
を求める。
９．Ｈ−比較法を用いて、差
【０２７７】
【数８９】
0005579327.tif 000090
【０２７８】
がしきい値と比較される。差がしきい値未満である場合には、サーバーはその方法を中止し、最終的なパラメーターとして、パラメーター
【０２７９】
【数９０】
0005579327.tif 000091
【０２８０】
を選択する。そうでない場合には、サーバーはステップ１において
【０２８１】
【数９１】
0005579327.tif 000092
【０２８２】
を用いてλを更新し、上記のステップを繰り返す。
【図１】
0005579327.tif 000105
【図２】
0005579327.tif 000106
【図３】
0005579327.tif 000107
【図４】
0005579327.tif 000108
【図５】
0005579327.tif 000109
【図６】
0005579327.tif 000110
【図７Ａ】
0005579327.tif 000111
【図７Ｂ】
0005579327.tif 000112
【図７Ｃ】
0005579327.tif 000113
【図７Ｄ】
0005579327.tif 000114
【図７Ｅ】
0005579327.tif 000115
【図８Ａ】
0005579327.tif 000116
【図８Ｂ】
0005579327.tif 000117
【図９Ａ】
0005579327.tif 000118
【図９Ｂ】
0005579327.tif 000119
【図１０Ａ】
0005579327.tif 000120
【図１０Ｂ】
0005579327.tif 000121
【図１０Ｃ】
0005579327.tif 000122
【図１０Ｄ】
0005579327.tif 000123
【図１０Ｅ】
0005579327.tif 000124
【図１０Ｆ】
0005579327.tif 000125