暗号化された信号に適用された関数の安全な評価のための方法
【課題】２つ以上の暗号化された信号に適用された関数の安全な評価の方法を提供する。
【解決手段】第１の信号の暗号化された結果の第１の暗号化された信号及び第２の信号の暗号化された結果の第２の暗号化された信号に関数を適用した結果を安全に求めるためのシステム及び方法を示す。関数を準同型成分の線形結合として表現する。準同型成分は、第１の信号及び第２の信号の代数的結合であって、準同型特性を使用して、該代数的結合の暗号化された結果を、第１の暗号化された信号及び第２の暗号化された信号から直接計算するのに適している、代数的結合である。次に、第１の暗号化された信号及び第２の暗号化された信号から準同型成分の暗号化された結果を求め、該準同型成分の暗号化された結果を線形結合に従って結合して、関数の暗号化された結果を生成し、複数のプロセッサによって実行される。
【解決手段】第１の信号の暗号化された結果の第１の暗号化された信号及び第２の信号の暗号化された結果の第２の暗号化された信号に関数を適用した結果を安全に求めるためのシステム及び方法を示す。関数を準同型成分の線形結合として表現する。準同型成分は、第１の信号及び第２の信号の代数的結合であって、準同型特性を使用して、該代数的結合の暗号化された結果を、第１の暗号化された信号及び第２の暗号化された信号から直接計算するのに適している、代数的結合である。次に、第１の暗号化された信号及び第２の暗号化された信号から準同型成分の暗号化された結果を求め、該準同型成分の暗号化された結果を線形結合に従って結合して、関数の暗号化された結果を生成し、複数のプロセッサによって実行される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、２つ以上の暗号化された信号に適用された関数の安全な評価に関し、より詳細には２つの暗号化された信号の準同型に変換可能な関数の暗号化された結果を求めることに関する。
【背景技術】
【０００２】
暗号化された信号に関数を適用した結果を安全に求めることが多くの場合に必要とされている。たとえば、２つの暗号化された信号間の差分は、二乗誤差又はハミング距離のような様々な関数を使用して測定することができる。
【０００３】
従来の方法は通常、暗号学的ハッシュ関数を使用して、２つの信号が異なっているか否かを判断する。ハッシュの衝突が発生する確率が無視できるほど低いことを前提とすれば、信号ｘ及び信号ｙのハッシュが等しい場合、信号ｘは信号ｙと同じである。このような暗号学的ハッシュの比較は、ほとんどのパスワード管理アプリケーション及び鍵管理アプリケーションにおいて基本となっている。
【０００４】
従来の暗号学的ハッシュ関数の本質的な特性は、ハッシュ関数が、評価される信号の基礎構造を保たないことである。特に、２つの信号が幾らかの雑音を除いて概ね類似している場合であっても、それらの２つの概ね類似した信号の暗号学的ハッシュは、雑音が非常に小さいものであっても大きく異なる。したがって、暗号学的ハッシュ関数は、雑音が多い環境、たとえば記憶装置及び通信チャネル内で信号の類似性を評価するのに、単独では使用することができない。同じ理由で、暗号学的ハッシュ関数を２つの信号間の差分を求めるのに使用することができない。これは、信号間の小さな差分が、結果としてそれぞれの暗号学的ハッシュ間の大きな差分となるためである。
【０００５】
安全に信号を評価することは、多くの用途において重要である。たとえば、個人の医療データは多くの場合に第三者によって分析及び分類される。個人の医療データを第三者に明らかにしないことが重要である。加えて、第三者は分類方法も、分類に使用されるデータベースも明らかにすることを望まない。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
この問題は、多くの場合に安全な複数者間計算(ＳＭＣ)として定義される。紛失通信(ＯＴ)、安全な内積(secure inner product)(ＳＩＰ)のような計算的に安全な方法を原形として使用して、より複雑な演算を実施することができる。米国特許出願第１１／００５，２９３号はそのような方法を記載している。その方法は、ユーザによって分類器に供給される画像を明らかにすることなく物体検出を実施する。同様に、分類器によって使用される分類方法はユーザに明らかにされない。しかしながら、この方法は、ユーザと分類器との間で多数のやりとりを必要とする。やりとり及び鍵管理の観点からの通信オーバヘッドは非常に大きい。
【０００７】
本発明の目的は、信号に関数を適用した結果を安全に求めるためのシステム及び方法を提供することである。
【課題を解決するための手段】
【０００８】
本発明の実施の形態は、信号の準同型に変換可能な関数が固有の特性を有し、該特性によって暗号化領域内のこれらの関数の解を見つけるのが容易になるという認識に基づく。第１の信号及び第２の信号の準同型に変換可能な関数は、準同型成分(homomorphic component)の線形結合に変換することができる。準同型成分は、入力、すなわち信号の代数的結合であって、該準同型成分の暗号化値を、信号の暗号化値から直接、すなわち復号することなく計算することができるような、代数的結合である。したがって、準同型成分の暗号化された結果の計算は、信号の機密性を守る暗号化領域内で実施される。
【０００９】
暗号化準同型成分は、準同型特性を使用して処理することができる。準同型成分の例は、限定ではないが、第１の信号の関数、第２の信号の関数、第１の信号及び第２の信号の積の線形関数等を含む。たとえば、
二乗距離関数：ｄ(ｘ，ｙ)＝(ｘ−ｙ)２＝ｘ２＋ｙ２−２ｘｙ、ただしｘ及びｙは実数又は整数である。ｄ(ｘ，ｙ)の二乗根は、信号ｘと信号ｙとの間のユークリッド距離と称される。
ハミング距離関数：ｄ(ｘ，ｙ)＝ｘ＋ｙ−２ｘｙ、ただしｘ及びｙは２進数であり、すなわち値０又は１をとる。
何らかの任意関数：ｆ(ｘ，ｙ)＝ｓｉｎ(ｘ)＋ｃｏｓ(ｙ)＋４ｘ２ｙ３。
【００１０】
本発明の実施の形態は、第１の信号の暗号化された結果の第１の暗号化された信号及び第２の信号の暗号化された結果の第２の暗号化された信号に関数を適用した結果を安全に求めるためのシステム及び方法を説明する。本方法は、関数を準同型成分の線形結合として表現する。準同型成分は、第１の信号及び第２の信号の代数的結合であって、準同型特性を使用して、該代数的結合の暗号化された結果を、第１の暗号化された信号及び第２の暗号化された信号から直接計算するのに適しているような、代数的結合である。次に、本方法は、第１の暗号化された信号及び第２の暗号化された信号から準同型成分の暗号化された結果を求め、該準同型成分の暗号化された結果を線形結合に従って結合して、関数の暗号化された結果を生成する。本方法は複数のプロセッサによって実行される。
【発明の効果】
【００１１】
本発明の実施の形態は、準同型暗号化の特性を使用して、２つのプロセッサが、２つの暗号化された信号に関数を適用した結果を計算することを可能にする。１つの実施の形態では、関数は指紋を認証し、ここでクライアントは指紋を明らかにすることなく遠隔認証サーバと対話する。サーバは、該サーバにおけるデータベース内に記憶されている指紋を明らかにすることなく認証を実施する。
【図面の簡単な説明】
【００１２】
【図１】本発明の一実施の形態による、２つの暗号化された信号に適用した準同型に変換可能な関数の暗号化された結果を安全に求めるための方法のブロック図である。
【図２】本発明の一実施の形態による２つの信号間の暗号化された差分を求めるための方法のブロック及び動作の図である。
【図３】本発明の一実施の形態による２つの信号間の暗号化された差分を求めるための方法のブロック及び動作の図である。
【図４】本発明の別の実施の形態による生体認証に関する安全な差分計算のための方法の概略図である。
【発明を実施するための形態】
【００１３】
本発明の実施の形態は、幾つかの関数が固有の特性を有し、該特性によって、それらの関数が暗号化された信号に適用されるときに、該関数の結果を見つけるのが容易になるという認識に基づく。本明細書及び添付の特許請求の範囲のために、これらの関数を準同型に変換可能な関数として定義する。
【００１４】
準同型に変換可能な関数は、準同型成分の線形結合に変換することができる関数である。本明細書において定義されるように、準同型成分は信号の代数的結合であって、該準同型成分の暗号化された結果を、暗号化された信号から直接、すなわち復号することなく計算することができるような、代数的結合である。したがって、準同型成分の暗号化された結果の計算は、信号の機密性を守る。
【００１５】
暗号化準同型成分は、準同型特性を使用して処理することができる。準同型成分の例は、第１の信号の関数、第２の信号の関数、並びに第１の信号及び第２の信号の積の線形関数である。
【００１６】
準同型に変換可能な関数の幾つかの例は以下である。
二乗距離関数：ｄ(ｘ，ｙ)＝(ｘ−ｙ)２＝ｘ２＋ｙ２−２ｘｙ、ただしｘ及びｙは実数又は整数である。上述したように、ｄ(ｘ，ｙ)の二乗根は、信号ｘと信号ｙとの間のユークリッド距離である。
ハミング距離関数：ｄ(ｘ，ｙ)＝ｘ＋ｙ−２ｘｙ、ただしｘ及びｙは２進数であり、すなわち値０又は１をとる。
何らかの任意関数：ｆ(ｘ，ｙ)＝ｓｉｎ(ｘ)＋ｃｏｓ(ｙ)＋４ｘ２ｙ３又はｆ(ｘ，ｙ，ｚ)＝ｓｉｎ(ｘ)＋ｓｉｎ(ｙ)＋ｓｉｎ(ｚ)。
【００１７】
準同型特性を使用した処理の例を下記で説明する。
【００１８】
図１は、準同型に変換可能な関数１１０を、第１の信号２１０及び第２の信号２１５(図２参照)に適用した結果１２０を安全に求めるための方法１００を示している。暗号化された結果を、安全に通信すると共に、公開鍵１５０に関連付けられる秘密鍵を用いて復号することができる。
【００１９】
本発明の実施の形態は、関数１１０を、準同型成分、たとえば１４１、１４２、及び１４３の線形結合１４０に変換する(１３０)。線形結合の例は、準同型成分の加算及び減算である。準同型成分は公開鍵１５０を用いて暗号化される。暗号化された信号を使用して、準同型成分の暗号化された結果を個々に評価する(１６０)。準同型暗号化及び線形結合の特性に起因して、個々の暗号化された結果１６５を結合して(１７０)関数の最終的な暗号化された結果１２０を生成することができる。
【００２０】
図２及び図３は、本発明の一実施の形態による、２つの信号に異なる関数を適用した結果を安全に求めるための方法を示している。この実施の形態では、システムは、第１のプロセッサ２０１及び第２のプロセッサ２０２を備える。本発明は、３つ以上の信号及び１つ又は複数のプロセッサを用いて機能することができることを理解されたい。
【００２１】
第１のプロセッサは第１の信号ｘｎ＝(ｘ１，ｘ２，…，ｘｎ)２１０を記憶し、第２のプロセッサは第２の信号ｙｎ＝(ｙ１，ｙ２，…，ｙｎ)２１５を記憶する。ただし、ｎは信号の長さである。２つのプロセッサは、いかなる段階においても互いに信号を共有しない。下記で説明するように、１つの実施の形態では、評価される関数はハミング距離関数である。別の実施の形態では、関数は二乗ユークリッド距離関数である。
【００２２】
本発明では、関数を３つの成分Ａ、Ｂ、及びＣの線形結合に変換し、第１の成分Ａが第１の信号の関数であり、第２の成分Ｂが第２の信号の関数であり、第３の成分Ｃが第１の信号及び第２の信号の積の線形関数であるようにする。
【００２３】
したがって、第１のプロセッサは、第１の成分Ａを第１の信号ｘｎから評価することができる。準同型特性を使用して、成分Ａをｘｎ又は暗号化されたｘｉから評価することができる。ただし、ｉ＝１，２，３，…，ｎである。
【００２４】
第２のプロセッサは、第２の成分Ｂを第２の信号ｙｎから評価する。準同型特性を使用して、成分Ｂをｙｎ又は暗号化されたｙｉから評価することができる。ただし、ｉ＝１，２，３，…，ｎである。
【００２５】
一方、２つのプロセッサは、ｘｎが第２のプロセッサから秘密にされ、ｙｎが第１のプロセッサから秘密にされるように、共同で第３の成分Ｃを評価する。本発明の実施の形態は、準同型暗号化の特性を使用して、成分Ｃを安全に求める。
【００２６】
図２に示すように、第１のプロセッサ２０１は、第１の信号の暗号化された要素２２５を第２のプロセッサ２０２に送信する(２２０)。下記でより詳細に説明するように、第２のプロセッサは第１の信号を復号することなく、第２の成分及び第３の成分の線形結合２３５を求める(２３０)。第２の成分及び第３の成分の線形結合２３５を、第１のプロセッサに送信する(２４０)。第１のプロセッサは、その結合２３５を暗号化された第１の成分２５５と結合して、暗号化された結果２６０を求める(２５０)。
【００２７】
準同型暗号化
準同型暗号化は、平文に対して実施される代数的演算が、暗号文に対して実施される別の既知の代数的演算に対応する暗号化の形式をとる。この特性は、暗号化された入力を使用する計算を、これらの入力を復号する必要なく暗号化領域内で直接実施することを可能にするため、有用である。Ｐを、二値演算子・Ｐに関連付けられる平文のセットとし、Ｈを、二値演算子・Ｈに関連付けられる暗号文のセットとする。
【００２８】
定義１．１
暗号化関数ξ：Ｐ→Ｈは、全てのａ，ｂ∈Ｐについてξ(ａ・Ｐｂ)＝ξ(ａ)・Ｈξ(ｂ)である場合に準同型である。ただし、ξは暗号化演算子である。
【００２９】
多くの公開鍵暗号システムは準同型特性を使用する。本発明の実施の形態は、強秘匿の(semantically secure)準同型暗号化方式、たとえばPaillier準同型暗号化システムを用いて機能する。
【００３０】
Paillier準同型暗号化システム
Paillier準同型暗号化システムを使用する好ましい実施の形態を説明する。Paillier暗号化システムは、公開鍵暗号方式のための確率的非対称手順である。
【００３１】
構成
２つの素数ｐ、ｑを選択し、Ｎ＝ｐｑとする。ｇｃｄ(Ｌ(ｇλ ｍｏｄ Ｎ２)，Ｎ)＝１となるように
【００３２】
【数１】
【００３３】
を選択する。ただし、λ＝ｌｃｍ(ｐ−１，ｑ−１)、及びＬ(ｘ)＝(ｘ−１)／Ｎである。ここで、ｇｃｄは最大公約数を指し、ｌｃｍは最小公倍数を指す。(Ｎ，ｇ)を公開鍵として使用し、(ｐ，ｑ)を秘密鍵として使用し、上述したように
【００３４】
【数２】
【００３５】
は、Ｎ２を法とする逆数を有する非負整数のセットである。
【００３６】
暗号化
ｍ∈ＺＮを平文とすると、暗号文は以下である。
【００３７】
【数３】
【００３８】
ただし、
【００３９】
【数４】
【００４０】
はランダムに選択された整数であり、ＺＮ＝{０，１，２，…，Ｎ−１}であり、
【００４１】
【数５】
【００４２】
は、Ｎを法とする逆数を有する非負整数のセットである。整数ｒはPaillier暗号化関数のパラメータである。暗号化された結果はこのランダムパラメータに依拠する。メッセージｍが異なるｒを用いて複数回暗号化される場合、対応する暗号文は異なる。したがって、暗号化値はランダムに選択される定数ｒに依拠するため、Paillier暗号化の性質は、確率的である。
【００４３】
復号
【００４４】
【数６】
【００４５】
を暗号文とすると、対応する平文は以下である。
【００４６】
【数７】
【００４７】
関数Ｌ(．)は、Ｌ(ｘ)＝(ｘ−１)／Ｎとして定義される。復号は、暗号化中に使用されるｒの値に関わらず結果ｍを与える。
【００４８】
準同型特性は、平文セット(ＺＮ，＋)から暗号文セット
【００４９】
【数８】
【００５０】
へのPaillier暗号化関数、すなわち
【００５１】
【数９】
【００５２】
にも当てはまる。
【００５３】
したがって、総和暗号化値は暗号化値の積である。上記の関係において、ｒ１及びｒ２はPaillier暗号化において使用されるパラメータである。式(１)のように、これらのパラメータはセットＺ＊Ｎからランダムに選択される。
【００５４】
上記の特性に加えて、Paillier暗号化の以下の特性も有する。
【００５５】
【数１０】
【００５６】
したがって、２つの信号の積の暗号化値は、１つの信号の暗号化値の累乗法によって得られる。
【００５７】
安全なハミング距離推定
図３は、第１のプロセッサ２０１及び第２のプロセッサ２０２を使用して第１の信号２１０と第２の信号２１５との間の暗号化差分測定値２６０を求めるための方法を示している。
【００５８】
第１のプロセッサは第１の信号ｘｎ＝(ｘ１，ｘ２，…，ｘｎ)２１０を記憶し、第２のプロセッサは第２の信号ｙｎ＝(ｙ１，ｙ２，…，ｙｎ)２１５を記憶する。１つの実施の形態では、差分測定値は二値ベクトル間のハミング距離関数によって定義される。信号ｘｎ及びｙｎのハミング距離関数ｄ(ｘｎ，ｙｎ)を以下の準同型成分の線形結合に変換する。
【００５９】
【数１１】
【００６０】
ただし、
【００６１】
【数１２】
【００６２】
であり、演算子
【００６３】
【数１３】
【００６４】
は、２を法とする加算である。
【００６５】
式(３)のハミング距離関数は、準同型に変換可能な関数である。これは、成分Ａ、Ｂ、及びＣの総和、すなわち加算及び減算によって、線形結合１４０が形成されるためである。成分Ａは第１の信号の関数であり、成分Ｂは第２の信号の関数であり、成分Ｃは第１の信号及び第２の信号の積の線形関数である。
【００６６】
第１のプロセッサは、公開鍵１５０を使用して第１の信号の個々の要素を暗号化して(３２０)、暗号化された要素の第１のセット２２５を生成し、該暗号化された要素のセットを第２のプロセッサに送信する。
【００６７】
第２のプロセッサは、暗号化された要素の第１のセットの対応する要素と、第２の信号との暗号化された積３３５を求める(３３０)。ｉ∈{１，２，…，ｎ}毎に、第２のプロセッサは以下を求める。
【００６８】
【数１４】
【００６９】
次に、第２のプロセッサは、公開鍵１５０を使用して、上記の暗号化された積の暗号化された和３４０を求めて(３３５)、第１の暗号化された総和３４５を生成する。
【００７０】
【数１５】
【００７１】
ただし、
【００７２】
【数１６】
【００７３】
であり、
【００７４】
【数１７】
【００７５】
は積演算子である。第２のプロセッサは暗号化値に対してしか演算しない。したがって、値Ｃ及びｒｃは第２のプロセッサには知られない。
【００７６】
次に、第２のプロセッサは、第２の信号の個々の要素を合計して(３５０)、第２の総和３５５を生成する。第２のプロセッサは第２の総和と第１の暗号化された総和とを合計して(３６０)、第３の暗号化された総和２３５を生成する。第２のプロセッサは、ｒｂ∈Ｚ＊Ｎをランダムに選択し、以下を求める。
【００７７】
【数１８】
【００７８】
ただし、ｒｄ＝ｒｂｒｃ ｍｏｄ Ｎ∈Ｚ＊Ｎである。第２のプロセッサは第３の総和２３５を第１のプロセッサに送信する。ｒｄの値は暗号化計算内に内在するが、第２のプロセッサには知られない。
【００７９】
第１のプロセッサは、鍵１５０に従って第１の信号の個々の暗号化された要素を合計して(３７０)、第４の暗号化された総和２５５を生成し、第３の暗号化された総和と第４の暗号化された総和との暗号化された和を求めて(２５０)、暗号化された歪み２６０を生成する。第１のプロセッサは、ｒａ∈Ｚ＊Ｎをランダムに選択し、以下を求める。
【００８０】
【数１９】
【００８１】
ただし、ｒ＝ｒａｒｄ ｍｏｄ Ｎ∈Ｚ＊Ｎである。
【００８２】
幾つかの実施の形態では、暗号化された差分測定値２６０を第２のプロセッサに送信する(３９０)。
【００８３】
安全な二乗距離計算
代替的な一実施の形態では、距離測定値は、第１の信号ｘｎと第２の信号ｙｎとの間の二乗ユークリッド距離関数、すなわち二乗誤差である。
【００８４】
【数２０】
【００８５】
ただし、
【００８６】
【数２１】
【００８７】
である。
【００８８】
式(８)の二乗ユークリッド距離関数は、準同型に変換可能な関数である。これは、成分Ａ、Ｂ、及びＣの加算及び減算によって、線形結合１４０が形成されるためである。そして、成分Ａは第１の信号の関数であり、成分Ｂは第２の信号の関数であり、成分Ｃは第１の信号及び第２の信号の積の線形関数である。
【００８９】
この実施の形態では、式(３)の成分Ａ、Ｂ、及びＣの値を、式(８)からの対応する値で置き換え、方法３００をさらに変更することなく実施する。
【００９０】
個人指紋認証
図４は、本発明の別の実施の形態による、生体データを安全に認証するための方法を示している。この実施の形態では、プロセッサ２０１及び２０２は、第３のプロセッサ４０３、たとえば遠隔認証サーバと対話する。プロセッサ２０２は、生体信号をプロセッサ２０１から秘密にしておき、プロセッサ２０１は、生体データベースをプロセッサ２０２から秘密にしておく。
【００９１】
指紋のような未知の生体計測４０５から、信号２１５を抽出する(４１０)。遠隔認証サーバ４０３は、信号がデータベース４２０内の信号のうちの少なくとも１つ、たとえば信号２１０と、閾値Ｄｔｈ４５５、たとえばハミング距離未満でマッチする場合、信号２１５を承認する。
【００９２】
プロセッサ２０１及び２０２は、信号２１５と信号２１０との間の暗号化されたハミング距離を求める。公開鍵１５０は、第３のプロセッサ４０３によって提供される。暗号化された差分２６０を、第３のプロセッサに送信し、秘密鍵４５１を用いて復号(４４０)した後、閾値と比較する(４５０)。比較結果をプロセッサ２０２に送信する(４６０)。１つの実施態様では、プロセッサ２０１は、暗号化された指紋のみを記憶することによって、データベース４２０をさらに保護する。
【００９３】
発明の効果
本発明の実施の形態は、準同型暗号化の特性を使用して、２つのプロセッサが、２つの暗号化された信号に関数を適用した結果を計算することを可能にする。１つの実施の形態では、関数は指紋を認証し、ここでクライアントは指紋を明らかにすることなく遠隔認証サーバと対話する。サーバは、該サーバにおけるデータベース内に記憶されている指紋を明らかにすることなく認証を実施する。
【００９４】
本発明を好ましい実施の形態の例として説明してきたが、本発明の精神及び範囲内で様々な他の適応及び変更を行うことができることは理解されたい。したがって、添付の特許請求の範囲の目的は、本発明の真の精神及び範囲内に入るすべての変形及び変更を包含することである。
【技術分野】
【０００１】
本発明は、包括的には、２つ以上の暗号化された信号に適用された関数の安全な評価に関し、より詳細には２つの暗号化された信号の準同型に変換可能な関数の暗号化された結果を求めることに関する。
【背景技術】
【０００２】
暗号化された信号に関数を適用した結果を安全に求めることが多くの場合に必要とされている。たとえば、２つの暗号化された信号間の差分は、二乗誤差又はハミング距離のような様々な関数を使用して測定することができる。
【０００３】
従来の方法は通常、暗号学的ハッシュ関数を使用して、２つの信号が異なっているか否かを判断する。ハッシュの衝突が発生する確率が無視できるほど低いことを前提とすれば、信号ｘ及び信号ｙのハッシュが等しい場合、信号ｘは信号ｙと同じである。このような暗号学的ハッシュの比較は、ほとんどのパスワード管理アプリケーション及び鍵管理アプリケーションにおいて基本となっている。
【０００４】
従来の暗号学的ハッシュ関数の本質的な特性は、ハッシュ関数が、評価される信号の基礎構造を保たないことである。特に、２つの信号が幾らかの雑音を除いて概ね類似している場合であっても、それらの２つの概ね類似した信号の暗号学的ハッシュは、雑音が非常に小さいものであっても大きく異なる。したがって、暗号学的ハッシュ関数は、雑音が多い環境、たとえば記憶装置及び通信チャネル内で信号の類似性を評価するのに、単独では使用することができない。同じ理由で、暗号学的ハッシュ関数を２つの信号間の差分を求めるのに使用することができない。これは、信号間の小さな差分が、結果としてそれぞれの暗号学的ハッシュ間の大きな差分となるためである。
【０００５】
安全に信号を評価することは、多くの用途において重要である。たとえば、個人の医療データは多くの場合に第三者によって分析及び分類される。個人の医療データを第三者に明らかにしないことが重要である。加えて、第三者は分類方法も、分類に使用されるデータベースも明らかにすることを望まない。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
この問題は、多くの場合に安全な複数者間計算(ＳＭＣ)として定義される。紛失通信(ＯＴ)、安全な内積(secure inner product)(ＳＩＰ)のような計算的に安全な方法を原形として使用して、より複雑な演算を実施することができる。米国特許出願第１１／００５，２９３号はそのような方法を記載している。その方法は、ユーザによって分類器に供給される画像を明らかにすることなく物体検出を実施する。同様に、分類器によって使用される分類方法はユーザに明らかにされない。しかしながら、この方法は、ユーザと分類器との間で多数のやりとりを必要とする。やりとり及び鍵管理の観点からの通信オーバヘッドは非常に大きい。
【０００７】
本発明の目的は、信号に関数を適用した結果を安全に求めるためのシステム及び方法を提供することである。
【課題を解決するための手段】
【０００８】
本発明の実施の形態は、信号の準同型に変換可能な関数が固有の特性を有し、該特性によって暗号化領域内のこれらの関数の解を見つけるのが容易になるという認識に基づく。第１の信号及び第２の信号の準同型に変換可能な関数は、準同型成分(homomorphic component)の線形結合に変換することができる。準同型成分は、入力、すなわち信号の代数的結合であって、該準同型成分の暗号化値を、信号の暗号化値から直接、すなわち復号することなく計算することができるような、代数的結合である。したがって、準同型成分の暗号化された結果の計算は、信号の機密性を守る暗号化領域内で実施される。
【０００９】
暗号化準同型成分は、準同型特性を使用して処理することができる。準同型成分の例は、限定ではないが、第１の信号の関数、第２の信号の関数、第１の信号及び第２の信号の積の線形関数等を含む。たとえば、
二乗距離関数：ｄ(ｘ，ｙ)＝(ｘ−ｙ)２＝ｘ２＋ｙ２−２ｘｙ、ただしｘ及びｙは実数又は整数である。ｄ(ｘ，ｙ)の二乗根は、信号ｘと信号ｙとの間のユークリッド距離と称される。
ハミング距離関数：ｄ(ｘ，ｙ)＝ｘ＋ｙ−２ｘｙ、ただしｘ及びｙは２進数であり、すなわち値０又は１をとる。
何らかの任意関数：ｆ(ｘ，ｙ)＝ｓｉｎ(ｘ)＋ｃｏｓ(ｙ)＋４ｘ２ｙ３。
【００１０】
本発明の実施の形態は、第１の信号の暗号化された結果の第１の暗号化された信号及び第２の信号の暗号化された結果の第２の暗号化された信号に関数を適用した結果を安全に求めるためのシステム及び方法を説明する。本方法は、関数を準同型成分の線形結合として表現する。準同型成分は、第１の信号及び第２の信号の代数的結合であって、準同型特性を使用して、該代数的結合の暗号化された結果を、第１の暗号化された信号及び第２の暗号化された信号から直接計算するのに適しているような、代数的結合である。次に、本方法は、第１の暗号化された信号及び第２の暗号化された信号から準同型成分の暗号化された結果を求め、該準同型成分の暗号化された結果を線形結合に従って結合して、関数の暗号化された結果を生成する。本方法は複数のプロセッサによって実行される。
【発明の効果】
【００１１】
本発明の実施の形態は、準同型暗号化の特性を使用して、２つのプロセッサが、２つの暗号化された信号に関数を適用した結果を計算することを可能にする。１つの実施の形態では、関数は指紋を認証し、ここでクライアントは指紋を明らかにすることなく遠隔認証サーバと対話する。サーバは、該サーバにおけるデータベース内に記憶されている指紋を明らかにすることなく認証を実施する。
【図面の簡単な説明】
【００１２】
【図１】本発明の一実施の形態による、２つの暗号化された信号に適用した準同型に変換可能な関数の暗号化された結果を安全に求めるための方法のブロック図である。
【図２】本発明の一実施の形態による２つの信号間の暗号化された差分を求めるための方法のブロック及び動作の図である。
【図３】本発明の一実施の形態による２つの信号間の暗号化された差分を求めるための方法のブロック及び動作の図である。
【図４】本発明の別の実施の形態による生体認証に関する安全な差分計算のための方法の概略図である。
【発明を実施するための形態】
【００１３】
本発明の実施の形態は、幾つかの関数が固有の特性を有し、該特性によって、それらの関数が暗号化された信号に適用されるときに、該関数の結果を見つけるのが容易になるという認識に基づく。本明細書及び添付の特許請求の範囲のために、これらの関数を準同型に変換可能な関数として定義する。
【００１４】
準同型に変換可能な関数は、準同型成分の線形結合に変換することができる関数である。本明細書において定義されるように、準同型成分は信号の代数的結合であって、該準同型成分の暗号化された結果を、暗号化された信号から直接、すなわち復号することなく計算することができるような、代数的結合である。したがって、準同型成分の暗号化された結果の計算は、信号の機密性を守る。
【００１５】
暗号化準同型成分は、準同型特性を使用して処理することができる。準同型成分の例は、第１の信号の関数、第２の信号の関数、並びに第１の信号及び第２の信号の積の線形関数である。
【００１６】
準同型に変換可能な関数の幾つかの例は以下である。
二乗距離関数：ｄ(ｘ，ｙ)＝(ｘ−ｙ)２＝ｘ２＋ｙ２−２ｘｙ、ただしｘ及びｙは実数又は整数である。上述したように、ｄ(ｘ，ｙ)の二乗根は、信号ｘと信号ｙとの間のユークリッド距離である。
ハミング距離関数：ｄ(ｘ，ｙ)＝ｘ＋ｙ−２ｘｙ、ただしｘ及びｙは２進数であり、すなわち値０又は１をとる。
何らかの任意関数：ｆ(ｘ，ｙ)＝ｓｉｎ(ｘ)＋ｃｏｓ(ｙ)＋４ｘ２ｙ３又はｆ(ｘ，ｙ，ｚ)＝ｓｉｎ(ｘ)＋ｓｉｎ(ｙ)＋ｓｉｎ(ｚ)。
【００１７】
準同型特性を使用した処理の例を下記で説明する。
【００１８】
図１は、準同型に変換可能な関数１１０を、第１の信号２１０及び第２の信号２１５(図２参照)に適用した結果１２０を安全に求めるための方法１００を示している。暗号化された結果を、安全に通信すると共に、公開鍵１５０に関連付けられる秘密鍵を用いて復号することができる。
【００１９】
本発明の実施の形態は、関数１１０を、準同型成分、たとえば１４１、１４２、及び１４３の線形結合１４０に変換する(１３０)。線形結合の例は、準同型成分の加算及び減算である。準同型成分は公開鍵１５０を用いて暗号化される。暗号化された信号を使用して、準同型成分の暗号化された結果を個々に評価する(１６０)。準同型暗号化及び線形結合の特性に起因して、個々の暗号化された結果１６５を結合して(１７０)関数の最終的な暗号化された結果１２０を生成することができる。
【００２０】
図２及び図３は、本発明の一実施の形態による、２つの信号に異なる関数を適用した結果を安全に求めるための方法を示している。この実施の形態では、システムは、第１のプロセッサ２０１及び第２のプロセッサ２０２を備える。本発明は、３つ以上の信号及び１つ又は複数のプロセッサを用いて機能することができることを理解されたい。
【００２１】
第１のプロセッサは第１の信号ｘｎ＝(ｘ１，ｘ２，…，ｘｎ)２１０を記憶し、第２のプロセッサは第２の信号ｙｎ＝(ｙ１，ｙ２，…，ｙｎ)２１５を記憶する。ただし、ｎは信号の長さである。２つのプロセッサは、いかなる段階においても互いに信号を共有しない。下記で説明するように、１つの実施の形態では、評価される関数はハミング距離関数である。別の実施の形態では、関数は二乗ユークリッド距離関数である。
【００２２】
本発明では、関数を３つの成分Ａ、Ｂ、及びＣの線形結合に変換し、第１の成分Ａが第１の信号の関数であり、第２の成分Ｂが第２の信号の関数であり、第３の成分Ｃが第１の信号及び第２の信号の積の線形関数であるようにする。
【００２３】
したがって、第１のプロセッサは、第１の成分Ａを第１の信号ｘｎから評価することができる。準同型特性を使用して、成分Ａをｘｎ又は暗号化されたｘｉから評価することができる。ただし、ｉ＝１，２，３，…，ｎである。
【００２４】
第２のプロセッサは、第２の成分Ｂを第２の信号ｙｎから評価する。準同型特性を使用して、成分Ｂをｙｎ又は暗号化されたｙｉから評価することができる。ただし、ｉ＝１，２，３，…，ｎである。
【００２５】
一方、２つのプロセッサは、ｘｎが第２のプロセッサから秘密にされ、ｙｎが第１のプロセッサから秘密にされるように、共同で第３の成分Ｃを評価する。本発明の実施の形態は、準同型暗号化の特性を使用して、成分Ｃを安全に求める。
【００２６】
図２に示すように、第１のプロセッサ２０１は、第１の信号の暗号化された要素２２５を第２のプロセッサ２０２に送信する(２２０)。下記でより詳細に説明するように、第２のプロセッサは第１の信号を復号することなく、第２の成分及び第３の成分の線形結合２３５を求める(２３０)。第２の成分及び第３の成分の線形結合２３５を、第１のプロセッサに送信する(２４０)。第１のプロセッサは、その結合２３５を暗号化された第１の成分２５５と結合して、暗号化された結果２６０を求める(２５０)。
【００２７】
準同型暗号化
準同型暗号化は、平文に対して実施される代数的演算が、暗号文に対して実施される別の既知の代数的演算に対応する暗号化の形式をとる。この特性は、暗号化された入力を使用する計算を、これらの入力を復号する必要なく暗号化領域内で直接実施することを可能にするため、有用である。Ｐを、二値演算子・Ｐに関連付けられる平文のセットとし、Ｈを、二値演算子・Ｈに関連付けられる暗号文のセットとする。
【００２８】
定義１．１
暗号化関数ξ：Ｐ→Ｈは、全てのａ，ｂ∈Ｐについてξ(ａ・Ｐｂ)＝ξ(ａ)・Ｈξ(ｂ)である場合に準同型である。ただし、ξは暗号化演算子である。
【００２９】
多くの公開鍵暗号システムは準同型特性を使用する。本発明の実施の形態は、強秘匿の(semantically secure)準同型暗号化方式、たとえばPaillier準同型暗号化システムを用いて機能する。
【００３０】
Paillier準同型暗号化システム
Paillier準同型暗号化システムを使用する好ましい実施の形態を説明する。Paillier暗号化システムは、公開鍵暗号方式のための確率的非対称手順である。
【００３１】
構成
２つの素数ｐ、ｑを選択し、Ｎ＝ｐｑとする。ｇｃｄ(Ｌ(ｇλ ｍｏｄ Ｎ２)，Ｎ)＝１となるように
【００３２】
【数１】
【００３３】
を選択する。ただし、λ＝ｌｃｍ(ｐ−１，ｑ−１)、及びＬ(ｘ)＝(ｘ−１)／Ｎである。ここで、ｇｃｄは最大公約数を指し、ｌｃｍは最小公倍数を指す。(Ｎ，ｇ)を公開鍵として使用し、(ｐ，ｑ)を秘密鍵として使用し、上述したように
【００３４】
【数２】
【００３５】
は、Ｎ２を法とする逆数を有する非負整数のセットである。
【００３６】
暗号化
ｍ∈ＺＮを平文とすると、暗号文は以下である。
【００３７】
【数３】
【００３８】
ただし、
【００３９】
【数４】
【００４０】
はランダムに選択された整数であり、ＺＮ＝{０，１，２，…，Ｎ−１}であり、
【００４１】
【数５】
【００４２】
は、Ｎを法とする逆数を有する非負整数のセットである。整数ｒはPaillier暗号化関数のパラメータである。暗号化された結果はこのランダムパラメータに依拠する。メッセージｍが異なるｒを用いて複数回暗号化される場合、対応する暗号文は異なる。したがって、暗号化値はランダムに選択される定数ｒに依拠するため、Paillier暗号化の性質は、確率的である。
【００４３】
復号
【００４４】
【数６】
【００４５】
を暗号文とすると、対応する平文は以下である。
【００４６】
【数７】
【００４７】
関数Ｌ(．)は、Ｌ(ｘ)＝(ｘ−１)／Ｎとして定義される。復号は、暗号化中に使用されるｒの値に関わらず結果ｍを与える。
【００４８】
準同型特性は、平文セット(ＺＮ，＋)から暗号文セット
【００４９】
【数８】
【００５０】
へのPaillier暗号化関数、すなわち
【００５１】
【数９】
【００５２】
にも当てはまる。
【００５３】
したがって、総和暗号化値は暗号化値の積である。上記の関係において、ｒ１及びｒ２はPaillier暗号化において使用されるパラメータである。式(１)のように、これらのパラメータはセットＺ＊Ｎからランダムに選択される。
【００５４】
上記の特性に加えて、Paillier暗号化の以下の特性も有する。
【００５５】
【数１０】
【００５６】
したがって、２つの信号の積の暗号化値は、１つの信号の暗号化値の累乗法によって得られる。
【００５７】
安全なハミング距離推定
図３は、第１のプロセッサ２０１及び第２のプロセッサ２０２を使用して第１の信号２１０と第２の信号２１５との間の暗号化差分測定値２６０を求めるための方法を示している。
【００５８】
第１のプロセッサは第１の信号ｘｎ＝(ｘ１，ｘ２，…，ｘｎ)２１０を記憶し、第２のプロセッサは第２の信号ｙｎ＝(ｙ１，ｙ２，…，ｙｎ)２１５を記憶する。１つの実施の形態では、差分測定値は二値ベクトル間のハミング距離関数によって定義される。信号ｘｎ及びｙｎのハミング距離関数ｄ(ｘｎ，ｙｎ)を以下の準同型成分の線形結合に変換する。
【００５９】
【数１１】
【００６０】
ただし、
【００６１】
【数１２】
【００６２】
であり、演算子
【００６３】
【数１３】
【００６４】
は、２を法とする加算である。
【００６５】
式(３)のハミング距離関数は、準同型に変換可能な関数である。これは、成分Ａ、Ｂ、及びＣの総和、すなわち加算及び減算によって、線形結合１４０が形成されるためである。成分Ａは第１の信号の関数であり、成分Ｂは第２の信号の関数であり、成分Ｃは第１の信号及び第２の信号の積の線形関数である。
【００６６】
第１のプロセッサは、公開鍵１５０を使用して第１の信号の個々の要素を暗号化して(３２０)、暗号化された要素の第１のセット２２５を生成し、該暗号化された要素のセットを第２のプロセッサに送信する。
【００６７】
第２のプロセッサは、暗号化された要素の第１のセットの対応する要素と、第２の信号との暗号化された積３３５を求める(３３０)。ｉ∈{１，２，…，ｎ}毎に、第２のプロセッサは以下を求める。
【００６８】
【数１４】
【００６９】
次に、第２のプロセッサは、公開鍵１５０を使用して、上記の暗号化された積の暗号化された和３４０を求めて(３３５)、第１の暗号化された総和３４５を生成する。
【００７０】
【数１５】
【００７１】
ただし、
【００７２】
【数１６】
【００７３】
であり、
【００７４】
【数１７】
【００７５】
は積演算子である。第２のプロセッサは暗号化値に対してしか演算しない。したがって、値Ｃ及びｒｃは第２のプロセッサには知られない。
【００７６】
次に、第２のプロセッサは、第２の信号の個々の要素を合計して(３５０)、第２の総和３５５を生成する。第２のプロセッサは第２の総和と第１の暗号化された総和とを合計して(３６０)、第３の暗号化された総和２３５を生成する。第２のプロセッサは、ｒｂ∈Ｚ＊Ｎをランダムに選択し、以下を求める。
【００７７】
【数１８】
【００７８】
ただし、ｒｄ＝ｒｂｒｃ ｍｏｄ Ｎ∈Ｚ＊Ｎである。第２のプロセッサは第３の総和２３５を第１のプロセッサに送信する。ｒｄの値は暗号化計算内に内在するが、第２のプロセッサには知られない。
【００７９】
第１のプロセッサは、鍵１５０に従って第１の信号の個々の暗号化された要素を合計して(３７０)、第４の暗号化された総和２５５を生成し、第３の暗号化された総和と第４の暗号化された総和との暗号化された和を求めて(２５０)、暗号化された歪み２６０を生成する。第１のプロセッサは、ｒａ∈Ｚ＊Ｎをランダムに選択し、以下を求める。
【００８０】
【数１９】
【００８１】
ただし、ｒ＝ｒａｒｄ ｍｏｄ Ｎ∈Ｚ＊Ｎである。
【００８２】
幾つかの実施の形態では、暗号化された差分測定値２６０を第２のプロセッサに送信する(３９０)。
【００８３】
安全な二乗距離計算
代替的な一実施の形態では、距離測定値は、第１の信号ｘｎと第２の信号ｙｎとの間の二乗ユークリッド距離関数、すなわち二乗誤差である。
【００８４】
【数２０】
【００８５】
ただし、
【００８６】
【数２１】
【００８７】
である。
【００８８】
式(８)の二乗ユークリッド距離関数は、準同型に変換可能な関数である。これは、成分Ａ、Ｂ、及びＣの加算及び減算によって、線形結合１４０が形成されるためである。そして、成分Ａは第１の信号の関数であり、成分Ｂは第２の信号の関数であり、成分Ｃは第１の信号及び第２の信号の積の線形関数である。
【００８９】
この実施の形態では、式(３)の成分Ａ、Ｂ、及びＣの値を、式(８)からの対応する値で置き換え、方法３００をさらに変更することなく実施する。
【００９０】
個人指紋認証
図４は、本発明の別の実施の形態による、生体データを安全に認証するための方法を示している。この実施の形態では、プロセッサ２０１及び２０２は、第３のプロセッサ４０３、たとえば遠隔認証サーバと対話する。プロセッサ２０２は、生体信号をプロセッサ２０１から秘密にしておき、プロセッサ２０１は、生体データベースをプロセッサ２０２から秘密にしておく。
【００９１】
指紋のような未知の生体計測４０５から、信号２１５を抽出する(４１０)。遠隔認証サーバ４０３は、信号がデータベース４２０内の信号のうちの少なくとも１つ、たとえば信号２１０と、閾値Ｄｔｈ４５５、たとえばハミング距離未満でマッチする場合、信号２１５を承認する。
【００９２】
プロセッサ２０１及び２０２は、信号２１５と信号２１０との間の暗号化されたハミング距離を求める。公開鍵１５０は、第３のプロセッサ４０３によって提供される。暗号化された差分２６０を、第３のプロセッサに送信し、秘密鍵４５１を用いて復号(４４０)した後、閾値と比較する(４５０)。比較結果をプロセッサ２０２に送信する(４６０)。１つの実施態様では、プロセッサ２０１は、暗号化された指紋のみを記憶することによって、データベース４２０をさらに保護する。
【００９３】
発明の効果
本発明の実施の形態は、準同型暗号化の特性を使用して、２つのプロセッサが、２つの暗号化された信号に関数を適用した結果を計算することを可能にする。１つの実施の形態では、関数は指紋を認証し、ここでクライアントは指紋を明らかにすることなく遠隔認証サーバと対話する。サーバは、該サーバにおけるデータベース内に記憶されている指紋を明らかにすることなく認証を実施する。
【００９４】
本発明を好ましい実施の形態の例として説明してきたが、本発明の精神及び範囲内で様々な他の適応及び変更を行うことができることは理解されたい。したがって、添付の特許請求の範囲の目的は、本発明の真の精神及び範囲内に入るすべての変形及び変更を包含することである。
【特許請求の範囲】
【請求項１】
第１の暗号化された信号及び第２の暗号化された信号に関数を適用した結果を求めるための方法であって、前記第１の暗号化された信号および前記第２の暗号化された信号は第１の信号および第２の信号をそれぞれ暗号化した結果生じ、該方法は、前記第１の信号が第２のプロセッサから秘密にされ、且つ前記第２の信号が第１のプロセッサから秘密にされるように該方法のステップを実施するための前記第１のプロセッサ及び前記第２のプロセッサを使用し、該方法は、
前記関数を準同型成分の線形結合として表現するステップであって、各該準同型成分は、前記第１の信号及び前記第２の信号の代数的結合であって、該代数的結合の準同型特性を使用して、該代数的結合の暗号化された結果を、前記第１の暗号化された信号及び前記第２の暗号化された信号から直接計算するのに適しているような代数的結合であるものと、
前記第１の暗号化された信号及び前記第２の暗号化された信号から前記準同型成分の前記暗号化された結果を求めるステップと、
前記線形結合に従って、前記準同型成分の前記暗号化された結果を結合し、前記第１の信号及び前記第２の信号の機密性が守られるように前記関数の前記暗号化された結果を生成するステップと、
を含む、方法。
【請求項２】
前記準同型成分は、前記第１の信号の第１の関数と、前記第２の信号の第２の関数と、前記第１の信号及び前記第２の信号の積の線形関数とを含む、請求項１に記載の方法。
【請求項３】
前記関数は差分関数であり、前記方法は、
前記関数を第１の成分、第２の成分、及び第３の成分の総和に変換することであって、前記第１の成分が前記第１の信号の関数であり、前記第２の成分が前記第２の信号の関数であり、前記第３の成分が前記第１の信号及び前記第２の信号の積の線形関数であるようにするものと、
前記第１の信号の要素を鍵を用いて個々に暗号化し、暗号化された要素の第１のセットを生成することであって、該暗号化は前記第１のプロセッサによって実施されるものと、
前記暗号化された要素の第１のセット及び前記第２の信号に基づいて、前記第２の成分及び前記第３の成分の線形結合を求めることであって、該求めることは、前記線形結合が前記鍵を用いて暗号化されるように、暗号化領域内で前記第２のプロセッサによって実施されるものと、及び
前記線形結合を前記鍵を用いて暗号化された前記第１の成分と結合し、前記関数の前記暗号化された結果を生成することであって、該結合は前記第１のプロセッサによって実施されるものと、
を含む、請求項１に記載の方法。
【請求項４】
前記関数は差分関数であり、前記方法は、
前記関数を第１の成分、第２の成分、及び第３の成分の総和に変換することであって、前記第１の成分が前記第１の信号の関数であり、前記第２の成分が前記第２の信号の関数であり、前記第３の成分が前記第１の信号及び前記第２の信号の積の線形関数であるようにするものと、
前記第１の信号の要素を鍵を用いて個々に暗号化し、暗号化された要素の第１のセットを生成することと、
前記暗号化された要素の第１のセットの対応する要素及び前記第２の信号の暗号化された積を求めることと、
前記暗号化された積の暗号化された和を求め、第１の暗号化された総和を生成することと、
暗号化領域内で前記第２の信号の要素を合計し、第２の暗号化された総和を生成することと、
前記第２の暗号化された総和及び前記第１の暗号化された総和を乗算し、第３の暗号化された総和を生成することと、
前記鍵に従って、暗号化領域内で、前記第１の信号の要素を合計し、第４の暗号化された総和を生成することと、及び
前記第３の暗号化された総和及び前記第４の暗号化された総和の積を求め、前記暗号化された結果を生成することと、
を含む、請求項１に記載の方法。
【請求項５】
前記第１の信号を前記第１のプロセッサに記憶することと、及び
前記第２の信号を前記第２のプロセッサに記憶することと、
をさらに含む、請求項４に記載の方法。
【請求項６】
前記第１のプロセッサから前記第２のプロセッサに前記暗号化された要素のセットを送信することと、及び
前記第２のプロセッサから前記第１のプロセッサに前記第３の暗号化された総和を送信することと、
をさらに含む、請求項５に記載の方法。
【請求項７】
前記第１のプロセッサから第３のプロセッサに前記暗号化された結果を送信することと、
前記暗号化された結果を閾値と比較し、認証結果を生成することと、及び、
前記認証結果に基づいて前記第２の信号を認証することと、
をさらに含む、請求項４に記載の方法。
【請求項８】
前記暗号化された結果を前記第３のプロセッサによって復号することをさらに含む、請求項７に記載の方法。
【請求項９】
前記第２の信号は未知の指紋から抽出され、前記第１の信号は既知の指紋を表す、請求項７に記載の方法。
【請求項１０】
前記第１の信号はｘｎ＝{ｘ１，ｘ２，…，ｘｎ｝であり、前記第２の信号はｙｎ＝{ｙ１，ｙ２，…，ｙｎ｝であり、Ｎ＝ｐｑであり、ｐ及びｑは素数であり、前記差分関数はハミング距離関数ｄ(ｘｎ，ｙｎ)であり、前記変換は以下に従い、
【数１】
であり、ｉは指数ｉ∈１，２，…，ｎであり、Ａは前記第１の成分であり、Ｂは前記第２の成分であり、Ｃは前記第３の成分であり、
【数２】
は二値ＸＯＲ演算子である、請求項４に記載の方法。
【請求項１１】
前記第１の信号はｘｎ＝{ｘ１，ｘ２，…，ｘｎ｝であり、前記第２の信号はｙｎ＝{ｙ１，ｙ２，…，ｙｎ｝であり、Ｎ＝ｐｑであり、ｐ及びｑは素数であり、前記差分関数は二乗ユークリッド距離関数ｄ(ｘｎ，ｙｎ)であり、前記変換は以下に従い、
【数３】
であり、ｉは指数ｉ∈１，２，…，ｎであり、Ａは前記第１の成分であり、Ｂは前記第２の成分であり、Ｃは前記第３の成分である、請求項４に記載の方法。
【請求項１２】
下記に従って要素ｘｉを前記鍵を用いて暗号化することと、
【数４】
ただしｒｉは乱数、
下記に従って前記暗号化された積を求めることと、
【数５】
ただしξは暗号化演算子、
下記に従って前記暗号化された積の前記暗号化された和を求めることと、
【数６】
Πは積演算子、ＺＮ＊はＮを法とする逆数を有する非負整数のセット、
下記に従って前記第２の総和と前記第１の暗号化された総和とを合計することと、
【数７】
ただし、ｒｄｄ＝ｒｂｒｃ ｍｏｄ Ｎ∈Ｚ＊Ｎであり、ｒｂは、ｒｂ∈Ｚ＊Ｎとなるようにランダムに選択される、及び
下記に従って前記暗号化された結果を求めることと、
【数８】
ただし、ｒ＝ｒａｒｄ ｍｏｄ Ｎ∈Ｚ＊Ｎであり、ｒａは、ｒａ∈Ｚ＊Ｎとなるようにランダムに選択される、
を含む、請求項１０に記載の方法。
【請求項１３】
第１の暗号化された信号及び第２の暗号化された信号に関数を適用した結果を求めるためのシステムであって、前記第１の暗号化された信号および前記第２の暗号化された信号は第１の信号および第２の信号をそれぞれ暗号化した結果生じ、該システムは、前記第１の信号が第２のプロセッサから秘密にされ、且つ前記第２の信号が第１のプロセッサから秘密にされるように動作を実施するための前記第１のプロセッサ及び前記第２のプロセッサを備え、
前記関数を準同型成分の線形結合として表現する手段であって、該準同型成分は、前記第１の信号及び前記第２の信号の代数的結合であって、準同型特性を使用して、前記代数的結合の暗号化された結果を、前記第１の暗号化された信号及び前記第２の暗号化された信号から直接計算するのに適しているような、代数的結合であるものと、
前記第１の暗号化された信号及び前記第２の暗号化された信号から前記準同型成分の前記暗号化された結果を求める手段と、
前記線形結合に従って、前記準同型成分の前記暗号化された結果を結合し、前記関数の前記暗号化された結果を生成する手段と、
を備える、システム。
【請求項１４】
前記準同型成分は、前記第１の信号の関数と、前記第２の信号の関数と、前記第１の信号及び前記第２の信号の積の線形関数とを含む、請求項１３に記載のシステム。
【請求項１５】
前記関数は差分関数であり、前記システムは、
前記関数を第１の成分、第２の成分、及び第３の成分の総和に変換する手段であって、前記第１の成分が前記第１の信号の関数であり、前記第２の成分が前記第２の信号の関数であり、前記第３の成分が前記第１の信号及び前記第２の信号の積の線形関数であるようにするものと、
前記第１の信号の要素を前記鍵を用いて個々に暗号化する手段であって、暗号化された要素の第１のセットを生成し、該暗号化は前記第１のプロセッサによって実施されるものと、
前記暗号化された要素の第１のセット及び前記第２の信号に基づいて、前記第２の成分及び前記第３の成分の線形結合を求める手段であって、該求めることは、前記線形結合が前記鍵を用いて暗号化されるように、暗号化領域内で前記第２のプロセッサによって実施されるものと、
前記線形結合を前記鍵を用いて暗号化された前記第１の成分と結合する手段であって、前記関数の前記暗号化された結果を生成し、該結合は前記第１のプロセッサによって実施されるものと、
を備える、請求項１３に記載のシステム。
【請求項１６】
前記関数は差分関数であり、前記システムは、
前記関数を第１の成分、第２の成分、及び第３の成分の総和に変換する手段であって、前記第１の成分が前記第１の信号の関数であり、前記第２の成分が前記第２の信号の関数であり、前記第３の成分が前記第１の信号及び前記第２の信号の積の線形関数であるようにするものと、
前記第１の信号の要素を前記鍵を用いて個々に暗号化する手段であって、暗号化された要素の第１のセットを生成するものと、
前記暗号化された要素の第１のセットの対応する要素及び前記第２の信号の暗号化された積を求める手段と、
前記暗号化された積の暗号化された和を求める手段であって、第１の暗号化された総和を生成するものと、
前記第２の信号の要素を合計する手段であって、第２の総和を生成するものと、
を備える、請求項１３に記載のシステム。
【請求項１７】
複数の暗号化されていない信号に対応する複数の暗号化された信号の関数の暗号化された結果を求めるための方法であって、該複数の暗号化された信号は、各対応する暗号化されていない信号が、関連しないプロセッサから秘密にされるように、それぞれ複数のプロセッサに関連付けられ、該方法は、
前記関数を準同型成分の線形結合として表現するステップであって、該準同型成分は、前記複数の暗号化されていない信号の代数的結合であって、準同型特性を使用して、前記代数的結合の暗号化された結果を、前記複数の暗号化された信号から直接計算するのに適しているような、代数的結合であるものと、
前記複数の暗号化された信号から前記準同型成分の前記暗号化された結果を求めるステップと、
前記線形結合に従って、前記準同型成分の前記暗号化された結果を結合するステップであって、前記関数の前記暗号化された結果を生成するものと、
を含む、方法。
【請求項１】
第１の暗号化された信号及び第２の暗号化された信号に関数を適用した結果を求めるための方法であって、前記第１の暗号化された信号および前記第２の暗号化された信号は第１の信号および第２の信号をそれぞれ暗号化した結果生じ、該方法は、前記第１の信号が第２のプロセッサから秘密にされ、且つ前記第２の信号が第１のプロセッサから秘密にされるように該方法のステップを実施するための前記第１のプロセッサ及び前記第２のプロセッサを使用し、該方法は、
前記関数を準同型成分の線形結合として表現するステップであって、各該準同型成分は、前記第１の信号及び前記第２の信号の代数的結合であって、該代数的結合の準同型特性を使用して、該代数的結合の暗号化された結果を、前記第１の暗号化された信号及び前記第２の暗号化された信号から直接計算するのに適しているような代数的結合であるものと、
前記第１の暗号化された信号及び前記第２の暗号化された信号から前記準同型成分の前記暗号化された結果を求めるステップと、
前記線形結合に従って、前記準同型成分の前記暗号化された結果を結合し、前記第１の信号及び前記第２の信号の機密性が守られるように前記関数の前記暗号化された結果を生成するステップと、
を含む、方法。
【請求項２】
前記準同型成分は、前記第１の信号の第１の関数と、前記第２の信号の第２の関数と、前記第１の信号及び前記第２の信号の積の線形関数とを含む、請求項１に記載の方法。
【請求項３】
前記関数は差分関数であり、前記方法は、
前記関数を第１の成分、第２の成分、及び第３の成分の総和に変換することであって、前記第１の成分が前記第１の信号の関数であり、前記第２の成分が前記第２の信号の関数であり、前記第３の成分が前記第１の信号及び前記第２の信号の積の線形関数であるようにするものと、
前記第１の信号の要素を鍵を用いて個々に暗号化し、暗号化された要素の第１のセットを生成することであって、該暗号化は前記第１のプロセッサによって実施されるものと、
前記暗号化された要素の第１のセット及び前記第２の信号に基づいて、前記第２の成分及び前記第３の成分の線形結合を求めることであって、該求めることは、前記線形結合が前記鍵を用いて暗号化されるように、暗号化領域内で前記第２のプロセッサによって実施されるものと、及び
前記線形結合を前記鍵を用いて暗号化された前記第１の成分と結合し、前記関数の前記暗号化された結果を生成することであって、該結合は前記第１のプロセッサによって実施されるものと、
を含む、請求項１に記載の方法。
【請求項４】
前記関数は差分関数であり、前記方法は、
前記関数を第１の成分、第２の成分、及び第３の成分の総和に変換することであって、前記第１の成分が前記第１の信号の関数であり、前記第２の成分が前記第２の信号の関数であり、前記第３の成分が前記第１の信号及び前記第２の信号の積の線形関数であるようにするものと、
前記第１の信号の要素を鍵を用いて個々に暗号化し、暗号化された要素の第１のセットを生成することと、
前記暗号化された要素の第１のセットの対応する要素及び前記第２の信号の暗号化された積を求めることと、
前記暗号化された積の暗号化された和を求め、第１の暗号化された総和を生成することと、
暗号化領域内で前記第２の信号の要素を合計し、第２の暗号化された総和を生成することと、
前記第２の暗号化された総和及び前記第１の暗号化された総和を乗算し、第３の暗号化された総和を生成することと、
前記鍵に従って、暗号化領域内で、前記第１の信号の要素を合計し、第４の暗号化された総和を生成することと、及び
前記第３の暗号化された総和及び前記第４の暗号化された総和の積を求め、前記暗号化された結果を生成することと、
を含む、請求項１に記載の方法。
【請求項５】
前記第１の信号を前記第１のプロセッサに記憶することと、及び
前記第２の信号を前記第２のプロセッサに記憶することと、
をさらに含む、請求項４に記載の方法。
【請求項６】
前記第１のプロセッサから前記第２のプロセッサに前記暗号化された要素のセットを送信することと、及び
前記第２のプロセッサから前記第１のプロセッサに前記第３の暗号化された総和を送信することと、
をさらに含む、請求項５に記載の方法。
【請求項７】
前記第１のプロセッサから第３のプロセッサに前記暗号化された結果を送信することと、
前記暗号化された結果を閾値と比較し、認証結果を生成することと、及び、
前記認証結果に基づいて前記第２の信号を認証することと、
をさらに含む、請求項４に記載の方法。
【請求項８】
前記暗号化された結果を前記第３のプロセッサによって復号することをさらに含む、請求項７に記載の方法。
【請求項９】
前記第２の信号は未知の指紋から抽出され、前記第１の信号は既知の指紋を表す、請求項７に記載の方法。
【請求項１０】
前記第１の信号はｘｎ＝{ｘ１，ｘ２，…，ｘｎ｝であり、前記第２の信号はｙｎ＝{ｙ１，ｙ２，…，ｙｎ｝であり、Ｎ＝ｐｑであり、ｐ及びｑは素数であり、前記差分関数はハミング距離関数ｄ(ｘｎ，ｙｎ)であり、前記変換は以下に従い、
【数１】
であり、ｉは指数ｉ∈１，２，…，ｎであり、Ａは前記第１の成分であり、Ｂは前記第２の成分であり、Ｃは前記第３の成分であり、
【数２】
は二値ＸＯＲ演算子である、請求項４に記載の方法。
【請求項１１】
前記第１の信号はｘｎ＝{ｘ１，ｘ２，…，ｘｎ｝であり、前記第２の信号はｙｎ＝{ｙ１，ｙ２，…，ｙｎ｝であり、Ｎ＝ｐｑであり、ｐ及びｑは素数であり、前記差分関数は二乗ユークリッド距離関数ｄ(ｘｎ，ｙｎ)であり、前記変換は以下に従い、
【数３】
であり、ｉは指数ｉ∈１，２，…，ｎであり、Ａは前記第１の成分であり、Ｂは前記第２の成分であり、Ｃは前記第３の成分である、請求項４に記載の方法。
【請求項１２】
下記に従って要素ｘｉを前記鍵を用いて暗号化することと、
【数４】
ただしｒｉは乱数、
下記に従って前記暗号化された積を求めることと、
【数５】
ただしξは暗号化演算子、
下記に従って前記暗号化された積の前記暗号化された和を求めることと、
【数６】
Πは積演算子、ＺＮ＊はＮを法とする逆数を有する非負整数のセット、
下記に従って前記第２の総和と前記第１の暗号化された総和とを合計することと、
【数７】
ただし、ｒｄｄ＝ｒｂｒｃ ｍｏｄ Ｎ∈Ｚ＊Ｎであり、ｒｂは、ｒｂ∈Ｚ＊Ｎとなるようにランダムに選択される、及び
下記に従って前記暗号化された結果を求めることと、
【数８】
ただし、ｒ＝ｒａｒｄ ｍｏｄ Ｎ∈Ｚ＊Ｎであり、ｒａは、ｒａ∈Ｚ＊Ｎとなるようにランダムに選択される、
を含む、請求項１０に記載の方法。
【請求項１３】
第１の暗号化された信号及び第２の暗号化された信号に関数を適用した結果を求めるためのシステムであって、前記第１の暗号化された信号および前記第２の暗号化された信号は第１の信号および第２の信号をそれぞれ暗号化した結果生じ、該システムは、前記第１の信号が第２のプロセッサから秘密にされ、且つ前記第２の信号が第１のプロセッサから秘密にされるように動作を実施するための前記第１のプロセッサ及び前記第２のプロセッサを備え、
前記関数を準同型成分の線形結合として表現する手段であって、該準同型成分は、前記第１の信号及び前記第２の信号の代数的結合であって、準同型特性を使用して、前記代数的結合の暗号化された結果を、前記第１の暗号化された信号及び前記第２の暗号化された信号から直接計算するのに適しているような、代数的結合であるものと、
前記第１の暗号化された信号及び前記第２の暗号化された信号から前記準同型成分の前記暗号化された結果を求める手段と、
前記線形結合に従って、前記準同型成分の前記暗号化された結果を結合し、前記関数の前記暗号化された結果を生成する手段と、
を備える、システム。
【請求項１４】
前記準同型成分は、前記第１の信号の関数と、前記第２の信号の関数と、前記第１の信号及び前記第２の信号の積の線形関数とを含む、請求項１３に記載のシステム。
【請求項１５】
前記関数は差分関数であり、前記システムは、
前記関数を第１の成分、第２の成分、及び第３の成分の総和に変換する手段であって、前記第１の成分が前記第１の信号の関数であり、前記第２の成分が前記第２の信号の関数であり、前記第３の成分が前記第１の信号及び前記第２の信号の積の線形関数であるようにするものと、
前記第１の信号の要素を前記鍵を用いて個々に暗号化する手段であって、暗号化された要素の第１のセットを生成し、該暗号化は前記第１のプロセッサによって実施されるものと、
前記暗号化された要素の第１のセット及び前記第２の信号に基づいて、前記第２の成分及び前記第３の成分の線形結合を求める手段であって、該求めることは、前記線形結合が前記鍵を用いて暗号化されるように、暗号化領域内で前記第２のプロセッサによって実施されるものと、
前記線形結合を前記鍵を用いて暗号化された前記第１の成分と結合する手段であって、前記関数の前記暗号化された結果を生成し、該結合は前記第１のプロセッサによって実施されるものと、
を備える、請求項１３に記載のシステム。
【請求項１６】
前記関数は差分関数であり、前記システムは、
前記関数を第１の成分、第２の成分、及び第３の成分の総和に変換する手段であって、前記第１の成分が前記第１の信号の関数であり、前記第２の成分が前記第２の信号の関数であり、前記第３の成分が前記第１の信号及び前記第２の信号の積の線形関数であるようにするものと、
前記第１の信号の要素を前記鍵を用いて個々に暗号化する手段であって、暗号化された要素の第１のセットを生成するものと、
前記暗号化された要素の第１のセットの対応する要素及び前記第２の信号の暗号化された積を求める手段と、
前記暗号化された積の暗号化された和を求める手段であって、第１の暗号化された総和を生成するものと、
前記第２の信号の要素を合計する手段であって、第２の総和を生成するものと、
を備える、請求項１３に記載のシステム。
【請求項１７】
複数の暗号化されていない信号に対応する複数の暗号化された信号の関数の暗号化された結果を求めるための方法であって、該複数の暗号化された信号は、各対応する暗号化されていない信号が、関連しないプロセッサから秘密にされるように、それぞれ複数のプロセッサに関連付けられ、該方法は、
前記関数を準同型成分の線形結合として表現するステップであって、該準同型成分は、前記複数の暗号化されていない信号の代数的結合であって、準同型特性を使用して、前記代数的結合の暗号化された結果を、前記複数の暗号化された信号から直接計算するのに適しているような、代数的結合であるものと、
前記複数の暗号化された信号から前記準同型成分の前記暗号化された結果を求めるステップと、
前記線形結合に従って、前記準同型成分の前記暗号化された結果を結合するステップであって、前記関数の前記暗号化された結果を生成するものと、
を含む、方法。
【図１】
【図２】
【図３】
【図４】
【図２】
【図３】
【図４】
【公開番号】特開２０１１−１３６７２（Ｐ２０１１−１３６７２Ａ）
【公開日】平成２３年１月２０日（２０１１．１．２０）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１０−１２７４７８（Ｐ２０１０−１２７４７８）
【出願日】平成２２年６月３日（２０１０．６．３）
【出願人】（５９７０６７５７４）ミツビシ・エレクトリック・リサーチ・ラボラトリーズ・インコーポレイテッド (484)
【住所又は居所原語表記】２０１ ＢＲＯＡＤＷＡＹ， ＣＡＭＢＲＩＤＧＥ， ＭＡＳＳＡＣＨＵＳＥＴＴＳ ０２１３９， Ｕ．Ｓ．Ａ．
【Ｆターム（参考）】
【公開日】平成２３年１月２０日（２０１１．１．２０）
【国際特許分類】
【出願番号】特願２０１０−１２７４７８（Ｐ２０１０−１２７４７８）
【出願日】平成２２年６月３日（２０１０．６．３）
【出願人】（５９７０６７５７４）ミツビシ・エレクトリック・リサーチ・ラボラトリーズ・インコーポレイテッド (484)
【住所又は居所原語表記】２０１ ＢＲＯＡＤＷＡＹ， ＣＡＭＢＲＩＤＧＥ， ＭＡＳＳＡＣＨＵＳＥＴＴＳ ０２１３９， Ｕ．Ｓ．Ａ．
【Ｆターム（参考）】
[ Back to top ]