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