安全な閾値復号プロトコル計算
本発明は、暗号化されたデータセットを、前記データセットを表す個々のビットの暗号へと変換する方法に関する。また、本発明は、暗号化されたデータセットを、前記データセットを表す個々のビットの暗号へと変換するシステムに関する。本発明の基本的な考えは、数ｘ、ｘ∈｛０，１，．．．，ｎ−１｝のような、例えば生体特徴の形態のデータセットの暗号を、ｘについての情報やそのビットｘ０，ｘ１，．．．，ｘｔ−１を漏らすことなく、数ｘを形成するビットｘ０，ｘ１，．．．，ｘｔ−１の個々の暗号へと分解することが可能なプロトコルを提供することである。従って、本発明は、暗号化された数ｘ＝Σｉ＝１ｎｘｉ２ｉを形成するそれぞれの暗号化されたビットビット［［ｘ０］］，［［ｘ１］］，．．．，［［ｘｔ−１］］への暗号［［ｘ］］のスプリッティングを可能とする。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号化されたデータセットを、前記データセットを表す個々のビットの暗号へと変換する方法に関する。また、本発明は、暗号化されたデータセットを、前記データセットを表す個々のビットの暗号へと変換するシステムに関する。
【背景技術】
【０００２】
セキュリティ保護型の多数共同計算スキームでは、互いを必ずしも信用していないプレイヤとも称される参加者の集合は、私的なデータを明らかにすることなく、関数の出力が正確に算出されていることを確保しつつ、私的なデータを関数の入力として用いることにより共通の関数を算出したいと望む。例えば、広く知られたミリオネアのプロトコルでは、二人の億万長者は、自身の財産に関する如何なる情報も明らかにすることなく、いずれがお金持ちであるかを知りたい。二人の億万長者は、私的なデータ（即ちそれぞれの億万長者の財産）を公共の関数に与え、関数は、私的なデータに関する如何なることも明らかにすることなく、二人のいずれがお金持ちかを示す変数を出力する。
【０００３】
セキュリティ保護型の多数共同計算スキームで用いられる技術は、プレイヤの集合の間でプライバシーを保護する演算を実行するのに非常に適している。これらの技術は、例えば、セキュリティ保護されたオークション、セキュリティ保護されたプロフィールマッチング、セキュリティ保護された電子投票、セキュリティ保護された生体認証のような技術分野で実行されている。準同型閾値暗号システムに基づくセキュリティ保護型の多数共同計算用の効率的なアルゴリズムは、非特許文献１に記載されている。
【０００４】
物理的対象の認証は、セキュリティ保護された建物への条件付のアクセスやデジタルデータ（例えば、コンピューターや取り外し可能な記憶媒体に記憶されたもの）への条件付アクセス、若しくは、識別目的（例えば、特定の行動に対する識別された個人への課金や、入国のため）のような、多くの用途で使用することができる。指紋、虹彩、耳、顔等のようにユーザに固有な特徴が用いられる識別及び／又は認証のための生物測定学の使用は、パスワードやピンコードのような従来の識別手段や、例えば個人と写真の間の可視的な比較を伴う“マニュアル型”の識別方法に対して、より良い代替物として広く考えられるようになっている。
【非特許文献１】LNCS Springer-Verla 2004出版の B.SchoenmakersとP.TuylsによるAsiacrypt 2004における”Practical Two-Party Computation based on the Conditional Gate” の１１９−１２６頁
【発明の開示】
【発明が解決しようとする課題】
【０００５】
従来における解決すべき問題は、数ｘ、ｘ∈｛０，１，．．．，ｎ−１｝のような、例えば生体特徴の形態でのデータセットの暗号を如何にして、ｘについての情報やそのビットｘ０，ｘ１，．．．，ｘｔ−１を漏らすことなく、数ｘを形成するビットｘ０，ｘ１，．．．，ｘｔ−１の個々の暗号へと分解するかである。ここで、ｔは、数ｎ−１のビットの数である。かかるアルゴリズムの適用は、膨大であり、例えばセキュリティ保護型の共同素数判定法、セキュリティ保護型の階乗、生体センサの計算及び通信の低減、投票プロトコルにおける計算負荷の低減等である。暗号化されたビット［［ｘ０］］，［［ｘ１］］，．．．，［［ｘｔ−１］］へと分割するプロトコルは、ビットスプリッティングプロトコルと称される。
【０００６】
２００５年６月２３日のアーフス（Aahus）大学のI.Damgaard他による“How to Split a Shared Secret into Shared Bits in Constant-Round”では、同様の問題が扱われている。しかし、無条件のセキュリティ保護設定が採用されている。この開示では、ここで記載されるセキュリティ保護型の多数共同計算に参加するプレイヤが、ビット表現が安全に決定されるべきバイナリデータセットのシェアへのアクセスを有していることが、想定されている。その結果、プレイヤは、バイナリデータセットを形成するビットのシェアで終わり、完全なバイナリデータセットを成すために他のプレイヤを伴う必要がある。
【０００７】
本発明の目的は、上述の問題点を解決し、安全なビットスプリッティングを実行する方法／装置、即ち、暗号化された数ｘを、その数を形成するビットの暗号［［ｘ０］］，［［ｘ１］］，．．．，［［ｘｔ−１］］へと準同型暗号化の特性を用いて変換する方法／装置を提供することである。
【課題を解決するための手段】
【０００８】
この目的は、請求項１による、暗号化されたデータセットを、前記データセットを表す個々のビットの暗号へと変換する方法、及び、請求項１１による、暗号化されたデータセットを、前記データセットを表す個々のビットの暗号へと変換するシステムにより達成される。
【０００９】
本発明の第１の局面によれば、乱数を生成し、前記乱数のビット単位の暗号を算出するステップと、
前記暗号化されたデータセットと前記暗号化された乱数とに基づいて、暗号化された合計値を安全に算出するステップと、
前記暗号化された合計値の復号を実行し、前記合計値のビット表現を求めるステップと、
前記暗号化された乱数により前記合計値を処理することによって前記暗号化されたデータセットを表す個々のビットの暗号を生成するステップとを含む、方法が提供される。
【００１０】
本発明の第２の局面によれば、共同して、乱数を生成し、前記乱数のビット単位の暗号を算出するよう構成された少なくとも第１及び第２の計算装置を含むシステムが提供される。前記第１及び第２の計算装置の少なくとも１つの計算装置は、前記暗号化されたデータセットと前記暗号化された乱数とに基づいて、暗号化された合計値を算出するよう構成され、前記第１及び第２の計算装置は、共同して、前記暗号化された合計値の復号を実行し、前記合計値のビット表現を求めるよう構成される。また、前記第１及び第２の計算装置は、共同して、前記暗号化された乱数により前記合計値を処理することによって前記暗号化されたデータセットを表す個々のビットの暗号を生成するよう構成される。
【００１１】
本発明の基本的な考えは、数ｘ、ｘ∈｛０，１，．．．，ｎ−１｝のような、例えば生体特徴の形態のデータセットの暗号を、ｘについての情報やそのビットｘ０，ｘ１，．．．，ｘｔ−１を漏らすことなく、数ｘを形成するビットｘ０，ｘ１，．．．，ｘｔ−１の個々の暗号へと分解することが可能なプロトコルを提供することである。従って、本発明は、暗号化された数ｘ＝Σｉ＝１ｎｘｉ２ｉを形成するそれぞれの暗号化されたビットビット［［ｘ０］］，［［ｘ１］］，．．．，［［ｘｔ−１］］への暗号［［ｘ］］の分割（スプリッティング）を可能とする。
【００１２】
これは、例えば生体認証において、数ｘ＝Σｉ＝１ｎｘｉ２ｉとして表現されるビットストリングの単一の初期の暗号化を可能とするので、効果的である。暗号化されたビットのストリングは、続いて、ユーザを認証するために対応性に対するチェックをなすことができるように、登録中に得られる暗号化された生体特徴と比較されてもよい。暗号化された生体データの実際の比較は、典型的には、２者（若しくは多数者）プロトコルにおいて認証装置と生体センサを係合することにより実行され、このプロトコルでは、暗号化されたデータの２つのセットが、例えばハミング距離を用いて、２つのセット間で（十分な）対応性があるか否かを見るため、互いに比較される。
【００１３】
プロトコルの参加者は、プレイヤと称される。プレイヤは、共同して、この乱数を生成し、この乱数のビット単位の暗号化を実行する。好ましくは、乱数の暗号化は、乱数の暗号が正確に算出されていることを示すように構成された公的に検証可能な証明により実行される。暗号化された乱数と暗号化されたデータセットに基づく合計値は、準同型暗号化スキームを用いて暗号化される。用語“準同型（homomorphic）”は、［［ｘ＋ｙ］］＝［［ｘ］］［［ｙ］］、即ち（ｘ＋ｙ）の暗号がｘの暗号とｙの暗号の積に等しいことを意味する。
【００１４】
暗号化された合計値が算出された後、プレイヤは、閾値復号プロトコルを実行し、乱数の特徴を持つ合計値の平文複写を得、この合計値に対してビット表現が決定される。次いで、プレイヤは、共同して、ビット表現を用いて合計値の平文複写から乱数の暗号化されたビットを減算する。この演算は、データセット［［ｘ］］のビット表現［［ｘ０］］，［［ｘ１］］，．．．，［［ｘｔ−１］］を生成する。
【００１５】
本発明は、暗号［［ｘ０］］，［［ｘ１］］，．．．，［［ｘｔ−１］］が全てのプレイヤに利用可能であるので、効果的であり、これらのプレイヤは、他のプレイヤを伴うことを要せずに、続く計算のためにこれらの暗号を用いることができる。本発明は、無条件の設定に代えて暗号の設定におけるこの問題を解決する。更に、本発明は、暗号化されるデータセットが個人の生体特徴から抽出されることを想定する場合、例えば生体センサの、計算及び通信負荷の低減を可能とする。
【００１６】
本発明の更なる特徴及び効果は、添付の請求項及び次の説明を検討するときに明らかになるだろう。当業者であれば、本発明の異なる特徴は後述以外の実施例を生成するために組み合わせることができることを理解するだろう。
【発明を実施するための最良の形態】
【００１７】
本発明の好ましい実施例が添付図面を参照して詳説される。
【００１８】
本願で説明されるセキュリティ保護型の多数共同計算を実行するために、PaillierやEL Gamalのような、準同型閾値暗号化システムが使用される。用語“準同型”は、［［ｘ＋ｙ］］＝［［ｘ］］［［ｙ］］、即ち（ｘ＋ｙ）の暗号がｘの暗号とｙの暗号の積に等しいことを意味する。また、この用語は、任意のｘとａに対して、［［ｘ］］ａ＝［［ｘ＊ａ］］を意味する。用語“閾値”は、ｔ人以上のプレイヤの任意の集合が一緒になって暗号文を復号できるがより小さい如何なる集合は暗号文を復号できないように、ｌ人のプレイヤの１集合中の各プレイヤが秘密鍵のシェアにアクセス権を有することを意味する。
【００１９】
本発明は、効果的には、ユーザの生体特徴が参照データと比較される生体認証システムで採用されてもよい。整合が生じた場合には、ユーザが識別され、アクセスが得られる。ユーザ用の参照データは、事前に取得されており、例えばセキュリティ保護されたデータベースやスマートカードに、安全に保管される。認証されるべき物理的な対象は、非人間であってもよい。例えば、対象は、保護されたデジタルコンテンツを含む固体メモリやＣＤ，ＤＶＤのような記憶媒体であってもよい。この場合、生体は必ずしも用いられないが、同様の態様で、秘匿に維持されるべき（例えばビットシーケンスの、形態で）識別用特徴が付与され、対応する参照データと比較される。
【００２０】
認証時、ユーザは、ある識別子（アイデンティティー）を有することを要求し、供された生体テンプレートが、要求された識別子にリンクされた記憶された生体テンプレートと比較され、記憶されたテンプレートと記憶されたテンプレートの間の対応性が確認される。識別時、供された生体テンプレートが、記憶された全ての利用可能な生体テンプレートと比較され、記憶されたテンプレートと記憶されたテンプレートの間の対応性が確認される。尚、生体データは、個人の識別子の好適な表現物であり、個人に関連付けられた生体データの未認証の取得は、個人の識別子を盗むことと電子的に等価である。ハッカーは、個人を識別する適切な生体情報を取得した後、ハッカーが取得した識別子の個人を装うことができる。更に、生体データは、健康状態に関する繊細な私的情報を含んでいる場合がある。従って、生体認証／識別システムを採用する個人の保全性は守られなければならない。
【００２１】
生体暗号システムでは、公開鍵暗号が採用され、２人（若しくはそれ以上）のプレイヤ、例えばユーザと認証者（若しくは多数の認証者）は、同一の公開鍵にアクセス権を有する。また、ユーザ及び認証者は、それぞれ、対応する秘密鍵を有する。秘密鍵のシェアが復号に用いられる。
【００２２】
ユーザは、自身のシェアを（例えばスマートカードで）携帯してもよいし、若しくは、シェアは、ユーザが対話する対象の例えば生体識別システムのセンサ内に記憶されてもよい。登録中、生体識別子を現すビット列ｘ０，ｘ１，．．．，ｘｔ−１が取得され、番号ｘに変換され、
【００２３】
【数１】
共有の公開鍵で暗号化される。数ｘの暗号［［ｘ］］は、次いで、認証者に渡り、認証者がそれを保存する。尚、認証者は、秘密鍵の自身のシェアにアクセス権を有するだけでユーザのシェアにアクセス権を有していないので、暗号化された数を復号できない。従って、生体識別子の平文表現ｘは、認証者に対して隠されたままである。尚、認証者は、好ましくは、整合性の計算を共同して安全に実行する幾つかのサーバーからなる。サーバーのそれぞれは、秘密鍵のシェアを有する。十分な数のサーバーが共同する場合だけ、復号を実行することができる。
【００２４】
認証中、生体識別子の雑音のある表現ｙがシステムのセンサで得られる。尚、このセンサは、必ずしも登録で用いたセンサと同一である必要はなく、典型的には、限られた計算資源を有する低コストのセンサである。典型的には、認証用センサは、登録用センサから遠隔にある。例えば、一回だけ実行される登録は、より大きなチェーン店に含まれる任意のＤＶＤ／ビデオ店の形態の登録権限所有者で実行されてもよいが、認証は、典型的には、ユーザがＤＶＤを借りる特定の店で実行される。この店は、実際の認証者として見立てることができ、そこで、ユーザは認証されることになる。ユーザを認証するプロセスは、ユーザがＤＶＤを店で借りる度に毎回実行される。認証用センサは、共有の公開鍵でｙを暗号化する。続いて、安全な認証サーバーは、暗号化された数［［ｙ］］を、数ｙを形成するそれぞれのビットの暗号［［ｙ０］］，．．．，［［ｙｔ−１］］へと変換する。次いで、暗号化されたビット表現［［ｘ０］］，．．．，［［ｘｔ−１］］と［［ｙ０］］，．．．，［［ｙｔ−１］］が安全な方法で比較される。従って、ユーザが認証されることができるに、対応性のチェックがなされる。
【００２５】
本発明の一実施例では、ｘ∈｛０，１，．．．，ｎ−１｝である数ｘが暗号化されることが想定される。暗号化用に採用されるプロトコルの入力は、暗号［［ｘ］］により表され、出力は［［ｘ０］］，．．．，［［ｘｔ−１］］で表され、ここで、ｔは、数ｎ−１のビット長を指す。プロトコルの参加者は、プレイヤと称される。
【００２６】
先ず、典型的には安全なサーバーの集合の形態で具現化される、プレイヤは、共同して、０≦ｒ＜ｎの乱数を生成し、乱数のビット単位の暗号化［［ｒ０］］，．．．，［［ｒｔ−１］］を実行する。
【００２７】
【数２】
従って、ｒ＝９とすると、ｒ０＝１、ｒ１＝０、ｒ２＝０、ｒ３＝１である。その結果、ｒ＝１＊２０＋０＊２１＋０＊２２＋１＊２３＝１＋０＋０＋８＝９である。２つの安全なサーバーが採用される場合、２つのサーバーは、共同して、乱数ビットを生成及び暗号化する。例えば、ｒ０に対して、第１サーバーは、［［ｒ０’］］を算出し、第２サーバーは、［［ｒ０”］］を算出する。次いで、［［ｒ０］］＝［［ｒ０’＾ｒ０”］］が安全に算出され、ここで、記号＾はＸＯＲ（排他的論理和）演算を指す。この手順は、乱数の全てのビット［［ｒ０］］，．．．，［［ｒｔ−１］］に対して実行される。
【００２８】
暗号化は、暗号化されたビットが正確であることを示すように構成された必要なゼロ知識証明により達成される。かかる証明を算出する多数の異なる技術が存在する。EL Gamal（エルガマル）設定では、証明は、次のように算出されてもよい。秘密鍵α＝ｌｏｇｇｈとすると、復号は、あるメッセージｍ∈Ｚｑに対してｇｍに等しいｂ／ａαを計算することにより実行される。暗号化は、共通の秘密鍵ｈで計算される一方、復号は、プレイヤ間の共同プロトコルを用いて実行され、それぞれのプレイヤは、秘密鍵α＝ｌｏｇｇｈのシェアを保持する。プレイヤは、分散型の鍵生成プロトコルを実行することによりシェアを得る。
【００２９】
分散型の鍵生成は、プレイヤＰ１，Ｐ２（例えば生体センサ及び認証者、若しくは、第１及び第２サーバー）に先ずコミットメントｃ＝ｇαｉｈｒｉ（ｉ＝１，２に対してαｉ、ｒｉ∈Ｚｑ）をブロードキャストさせ、次いで、ｌｏｇｇｈｉ（ｉ＝１，２に対してｈｉ＝ｃｉ／ｈｒｉ）知識の証明と共に値ｒｉをブロードキャストさせることによって達成される。共同の公開鍵はｈ＝ｈ１ｈ２であり、秘密鍵α＝α１＋α２である。暗号（ａ，ｂ）を復号するため、プレイヤＰｉは、暗号化されたデータの平文複写に関する情報を明らかにすることなく、ｄｊ＝ａαｉを、ｌｏｇａｄｉ＝ｌｏｇｇｈｉの証明、即ち、暗号化された出力データが正確であることを示すように構成された証明と共に、生成する。次いで、メッセージは、ｂ／（ａ１ａ２）から回復される。尚、Paillierシステムに対しては、手順は異なる。
【００３０】
プレイヤは、暗号化されたビット［［ｒ０］］，．．．，［［ｒｔ−１］］を生成した後、次の通り、暗号［［ｘ＋ｒ］］を算出する。
【００３１】
【数３】
これは、従来ゲートと称される制約付きの乗算ゲートや一般的な安全な乗算を用いて実行される。従来ゲートを用いると、２つの暗号化された値ｒとｘは、ｒが２値の領域、例えばｒ∈｛０，１｝に制約される限り、効率的に乗算されることができる。ｘの値に制約はなく、例えばｘ∈Ｚｎ＊である。暗号［［ｘ＋ｒ］］は、必ずしも全てのプレイヤにより算出されることはなく、唯一のプレイヤ、例えば第１の安全なサーバーにより算出され、他のプレイヤ、例えば第２の安全なサーバーに分散されてもよい。
【００３２】
次いで、プレイヤは、共同して、閾値復号プロトコルを実行し、平文でｙ＝（ｘ＋ｒ）のｎによる剰余（ｍｏｄ）を算出する。数ｙを形成するデータにより、ｙは、また、乱数の特性を有し、平文表現ｘ、ｒは、公開データでないことから、ｙから導出することができない。プレイヤは、ｙのビット表現を求め、共同して、このビット表現から、生成された乱数ｒの暗号［［ｒ］］を減算する。これは、ビット単位の減算、即ちｙ０−［［ｒ０］］，ｙ１−［［ｒ１］］，．．．，ｙｔ−１−［［ｒｔ−１］］により実現される。これは、他の暗号［［ｚ］］を生み、暗号［［ｚ］］は、（暗号化されたビットの）安全な減算回路を用いることによって、［［ｚ］］＝ｙ−［［ｒ］］として算出される。
【００３３】
これは、ｚｔがサインビットであるとき、暗号化されたビット［［ｚ０］］，．．．，［［ｚｔ−１］］により与えられる数ｚ＝ｘ若しくはｚ＝ｘ−ｎのビット表現を生む。従って、サインビットに依存して、［［ｘ０］］，．．．，［［ｘｔ−１］］若しくは［［（ｘ−ｎ）０］］，．．．，［［（ｘ−ｎ）ｔ−１］］が取得される。プレイヤは、ビット表現を用いてｚにｎｚｔを加えることによってｎによるｚの剰余を減らす。従って、ビット表現［［ｘ０］］，．．．，［［ｘｔ−１］］が生成される。
【００３４】
本発明のその他の実施例では、０≦ｘ＜２ｍ≪２ｋ＜ｎ、ｋ≫ｍであり、従って、２ｋ≫２ｍであることが想定される。暗号化用に採用されるプロトコルの入力は、同様に、暗号［［ｘ］］により表され、出力は［［ｘ０］］，．．．，［［ｘｔ−１］］で表される。この例示的な実施例では、ｘの最下位ｍビットｘ０，ｘ１，．．．，ｘｍ−１をどのようにして求めるかが説明される。各プレイヤＰｉ、１≦ｉ≦１は、ｒ＊，ｉ∈Ｒ｛０，１｝でｒ’ｉ∈｛０，．．．，２ｋ−ｍ−１｝である乱数ビットｒ０，ｉ，．．．，ｒｍ−１，ｉを選択し、これらのビットを暗号化し、暗号［［ｒ０，ｉ］］，．．．，［［ｒｍ−１，ｉ］］及び［［ｒ’ｉ］］を、暗号化が正確に完了したことの証明と共に、分散する。
【００３５】
プレイヤは、これらの暗号化されたビットを用いて、共同して、乱数ビットの暗号［［ｒ０］］，．．．，［［ｒｍ−１］］を生成する。この場合、乱数ビットｒの暗号は、安全な乗算ゲート及び乱数ｒ’を用いて、次の通り安全に算出される。
【００３６】
【数４】
ここで、乱数ｒ’は、準同型暗号化特性を用いて、次の通り算出される。
【００３７】
【数５】
プレイヤは、共同して、［［ｘ−ｒ］］を形成し、暗号［［ｘ−ｒ］］は、次いで、共同して、値ｙ＝ｘ−ｒを明らかにするために閾値復号プロトコルを用いて復号される。
【００３８】
【数６】
公開ビットｙ０，．．．，ｙｍ−１は、に２ｍよるｙの剰余を指す。公開入力トｙ０，．．．，ｙｍ−１及び［［ｒ０］］，．．．，［［ｒｍ−１］］用の安全な付加回路は、ｍ個の暗号化されたビット［［ｘ０］］，．．．，［［ｘｍ−１］］の出力を生成するために使用される。２ｍよるｙの剰余を算出することによって、最終のキャリービットは無視される。
【００３９】
図１は、個人に関連する生体データに基づく個人の識別及び認証用の基本的な従来技術のシステムを示し、このシステム内で、本発明が効果的に適用されることができる。指紋、虹彩、網膜、顔若しくは手の幾何学特徴、声の特徴等のような、個人の生の生体データは、センサ１０１にて取得される。典型的には、生体データを表すビット列ｘ０，ｘ１，．．．，ｘｔ−１がセンサにて取得される。取得されたデータ（即ち、生の平文データ）は、典型的には、デジタル信号プロセッサ（ＤＰＳ）のような処理装置１０２で処理される。処理装置は、センサと一体であってよい。この処理は、共通の公開鍵で暗号化される数ｘへのビットの変換を伴う。数ｘの暗号［［ｘ］］（若しくはｘのビットの暗号）は、次いで、サービスプロバイダのデータベース記憶装置１０３内にパス１０５を介して記憶される。これは、個人を登録するために、特定のシステムにアクセスを望む各個人に対して一回実行される初期の手続きである。
【００４０】
続いて、個人がサービスへアクセスを望むとき、その個人は、センサ１０１に、平文の生体データｙ０，．．．，ｙｔ−１を供給する。このデータは、次いで、暗号化の後、パス１０６を介して、データベース内に事前に記憶されている個人の生体データ［［ｘ］］と比較される。比較装置１０４にて実行される比較時に、パス１０６と１０７を解して提供されるデータのセット間に整合があった場合には、その個人は、提供されるサービスへのアクセス権が付与される。比較を実行するとき、上述のビットスプリッティングプロトコルは、［［ｙ０］］，．．．，［［ｙｔ−１］］と［［ｘ０］］，．．．，［［ｘｔ−１］］の間でビット単位の比較をなすことができるように、記憶装置１０３に記憶される暗号化されたデータ［［ｘ］］に対して実行される。
【００４１】
従って、図１を参照するに、センサ１０１は、初期の特徴抽出セッションでは登録者として機能するが、続くセッションでは、センサは、比較装置１０４において、（パス１０６を介して）後に提供される生体情報ｙと（パス１０７を介して）初期登録された生体情報との間の対応性をチェックする認証者として機能する。上述の如く、図１の装置は、互いに遠隔に配置されてもよい。図１に示す種のシステムでは、センサ１０１は、典型的には、暗号化演算を算出するために比較的高出力である。高出力のセンサが用いられる場合、センサ１０１／処理装置１０２及び比較装置１０４は、共同して、本発明のビットスプリッティングプロトコルを実行する。
【００４２】
図２は、個人に関連する生体データに基づく個人の識別及び認証用のその他のシステムを示し、このシステム内で、本発明が適用されることができる。ここで、登録用センサ２１０及び確認若しくは認証用センサ２０８は遠隔に配置される。図１においてと同様、取得されたデータ（即ち、生の平文データ）ｘ０，ｘ１，．．．，ｘｔ−１は、ＤＰＳ２０２にて、数ｘへ変換され、共通の公開鍵で暗号化される。数ｘの暗号［［ｘ］］は、次いで、データベース記憶装置２０３内に記憶される。続いて、個人がシステムにアクセスを望むとき、その個人は、認証用センサ２０８に、平文の生体データｙ０，．．．，ｙｔ−１を供給する。次いで、このデータは、ＤＳＰ２０９により数ｙに変換され暗号化される。従って、図２を参照するに、生体テンプレートｘが事前に登録用センサ２０１に供給され、ＤＳＰ２０２にて暗号化され、データベース記憶装置２０３内に暗号化された形態［［ｘ］］で記憶されていると想定する場合、個人がサービスへアクセスを望むとき、その個人の生体テンプレートｙ（ｘの雑音のある表現）は、確認用センサ２０８（認証用センサとも称される）により抽出され、暗号化された複写［［ｙ］］を生成するため、ＤＳＰ２０９により暗号化される。典型的には、ＤＳＰ２０９は、認証用センサ２０８に含まれる。この特定のシステムでは、センサ２０８が典型的には限られた計算能力しかない低コストのセンサであることから、本発明は、図１に示すシステムよりも効果的である。
【００４３】
数［［ｘ］］は、インターネットのようなネットワーク２１０をおそらくは介して、列を記憶する認証者２１１に渡される。認証者２１１は、また、典型的には、図２に示していないが、ＤＳＰを含む。尚、認証者は、秘密鍵の自身のシェアにアクセス権を有するだけでその個人のシェアにアクセス権を有していないので、暗号化された数を復号できない。従って、生体識別子の平文表現ｘは、認証者２１１に対して隠されたままである。本発明による安全なビットスプリッティングプロトコルは、認証者２１１で実行されることになる。セキュリティ性を改善するため、ビットスプリッティングプロトコルの実行は、安全なサーバー２１２，２１３の集合に外注される。従って、認証者２１１は、それぞれ生体データｘ、ｙの各セットの暗号［［ｘ］］及び［［ｙ］］によりサービスを提供する。
【００４４】
上述の如く、安全なサーバー２１２，２１３は、共同して、０≦ｒ＜ｎの乱数を生成し、乱数のビット単位の暗号化［［ｒ０］］，．．．，［［ｒｔ−１］］を実行する。乱数の暗号化は、暗号化されたビットが正確であることを示すように構成された必要なゼロ知識証明により達成される。サーバー２１２，２１３は、暗号化されたビット［［ｒ０］］，．．．，［［ｒｔ−１］］を生成したとき、サーバー２１２，２１３（若しくは２つのサーバーのうちの少なくとも一方）は、次のように、暗号、［［ｘ＋ｒ］］を算出する。
【００４５】
【数７】
次いで、サーバー２１２，２１３は、共同して、閾値復号プロトコルを実行し、平文でｙ＝（ｘ＋ｒ）のｎによる剰余を算出し、ｙのビット表現を決定し、共同して、このビット表現から、生成された乱数ｒの暗号［［ｒ］］を減算する。結果として、他の暗号［［ｚ］］が、［［ｚ］］＝ｙ−［［ｒ］］として算出される。
【００４６】
これは、ｚｔがサインビットであるとき、暗号化されたビット［［ｚ０］］，．．．，［［ｚｔ−１］］により与えられる数ｚ＝ｘ若しくはｚ＝ｘ−ｎのビット表現を生む。従って、サインビットに依存して、［［ｘ０］］，．．．，［［ｘｔ−１］］若しくは［［（ｘ−ｎ）０］］，．．．，［［（ｘ−ｎ）ｔ−１］］が取得される。サーバー２１２，２１３の一方（若しくは双方）は、ビット表現を用いてｚにｎｚｔを加えることによってｎによるｚの剰余を減らす。従って、ビット表現［［ｘ０］］，．．．，［［ｘｔ−１］］が生成される。ビット表現［［ｙ０］］，．．．，［［ｙｔ−１］］は、同様の態様で生成される。
【００４７】
今度は、ビットスプリッティングプロトコルが実行されたとき、認証者２１１及び人商用センサ２０８は、暗号化された生体データを比較する任意の適切な方法、例えばＩＤ６９５４５９／ＮＬ０４１３３５に開示されるような方法を用いて、暗号化されたビット表現［［ｙ０］］，．．．，［［ｙｔ−１］］と［［ｘ０］］，．．．，［［ｘｔ−１］］の間に対応性があるか否かを見出す。
【００４８】
本発明は、その特別な例示的な実施例を参照して説明されているが、多数の異なる代替、修正等は当業者には明らかである。記載された実施例は、それ故に、添付の請求項により定義される本発明の範囲を制限する意図でない。尚、上述した本発明の例示的な実施例によれば２つの安全なサーバーが共同してビットスプリッティングプロトコルを実行しているが、任意の数の安全なサーバーが、共同してビットスプリッティングプロトコルを実行するために採用されてもよい。
【図面の簡単な説明】
【００４９】
【図１】個人に関連する生体データに基づく個人の識別及び認証用の基本的な従来技術のシステムを示し、このシステム内で、本発明が効果的に適用される。
【図２】個人に関連する生体データに基づく個人の識別及び認証用のその他のシステムを示し、このシステム内で、本発明が効果的に適用される。
【技術分野】
【０００１】
本発明は、暗号化されたデータセットを、前記データセットを表す個々のビットの暗号へと変換する方法に関する。また、本発明は、暗号化されたデータセットを、前記データセットを表す個々のビットの暗号へと変換するシステムに関する。
【背景技術】
【０００２】
セキュリティ保護型の多数共同計算スキームでは、互いを必ずしも信用していないプレイヤとも称される参加者の集合は、私的なデータを明らかにすることなく、関数の出力が正確に算出されていることを確保しつつ、私的なデータを関数の入力として用いることにより共通の関数を算出したいと望む。例えば、広く知られたミリオネアのプロトコルでは、二人の億万長者は、自身の財産に関する如何なる情報も明らかにすることなく、いずれがお金持ちであるかを知りたい。二人の億万長者は、私的なデータ（即ちそれぞれの億万長者の財産）を公共の関数に与え、関数は、私的なデータに関する如何なることも明らかにすることなく、二人のいずれがお金持ちかを示す変数を出力する。
【０００３】
セキュリティ保護型の多数共同計算スキームで用いられる技術は、プレイヤの集合の間でプライバシーを保護する演算を実行するのに非常に適している。これらの技術は、例えば、セキュリティ保護されたオークション、セキュリティ保護されたプロフィールマッチング、セキュリティ保護された電子投票、セキュリティ保護された生体認証のような技術分野で実行されている。準同型閾値暗号システムに基づくセキュリティ保護型の多数共同計算用の効率的なアルゴリズムは、非特許文献１に記載されている。
【０００４】
物理的対象の認証は、セキュリティ保護された建物への条件付のアクセスやデジタルデータ（例えば、コンピューターや取り外し可能な記憶媒体に記憶されたもの）への条件付アクセス、若しくは、識別目的（例えば、特定の行動に対する識別された個人への課金や、入国のため）のような、多くの用途で使用することができる。指紋、虹彩、耳、顔等のようにユーザに固有な特徴が用いられる識別及び／又は認証のための生物測定学の使用は、パスワードやピンコードのような従来の識別手段や、例えば個人と写真の間の可視的な比較を伴う“マニュアル型”の識別方法に対して、より良い代替物として広く考えられるようになっている。
【非特許文献１】LNCS Springer-Verla 2004出版の B.SchoenmakersとP.TuylsによるAsiacrypt 2004における”Practical Two-Party Computation based on the Conditional Gate” の１１９−１２６頁
【発明の開示】
【発明が解決しようとする課題】
【０００５】
従来における解決すべき問題は、数ｘ、ｘ∈｛０，１，．．．，ｎ−１｝のような、例えば生体特徴の形態でのデータセットの暗号を如何にして、ｘについての情報やそのビットｘ０，ｘ１，．．．，ｘｔ−１を漏らすことなく、数ｘを形成するビットｘ０，ｘ１，．．．，ｘｔ−１の個々の暗号へと分解するかである。ここで、ｔは、数ｎ−１のビットの数である。かかるアルゴリズムの適用は、膨大であり、例えばセキュリティ保護型の共同素数判定法、セキュリティ保護型の階乗、生体センサの計算及び通信の低減、投票プロトコルにおける計算負荷の低減等である。暗号化されたビット［［ｘ０］］，［［ｘ１］］，．．．，［［ｘｔ−１］］へと分割するプロトコルは、ビットスプリッティングプロトコルと称される。
【０００６】
２００５年６月２３日のアーフス（Aahus）大学のI.Damgaard他による“How to Split a Shared Secret into Shared Bits in Constant-Round”では、同様の問題が扱われている。しかし、無条件のセキュリティ保護設定が採用されている。この開示では、ここで記載されるセキュリティ保護型の多数共同計算に参加するプレイヤが、ビット表現が安全に決定されるべきバイナリデータセットのシェアへのアクセスを有していることが、想定されている。その結果、プレイヤは、バイナリデータセットを形成するビットのシェアで終わり、完全なバイナリデータセットを成すために他のプレイヤを伴う必要がある。
【０００７】
本発明の目的は、上述の問題点を解決し、安全なビットスプリッティングを実行する方法／装置、即ち、暗号化された数ｘを、その数を形成するビットの暗号［［ｘ０］］，［［ｘ１］］，．．．，［［ｘｔ−１］］へと準同型暗号化の特性を用いて変換する方法／装置を提供することである。
【課題を解決するための手段】
【０００８】
この目的は、請求項１による、暗号化されたデータセットを、前記データセットを表す個々のビットの暗号へと変換する方法、及び、請求項１１による、暗号化されたデータセットを、前記データセットを表す個々のビットの暗号へと変換するシステムにより達成される。
【０００９】
本発明の第１の局面によれば、乱数を生成し、前記乱数のビット単位の暗号を算出するステップと、
前記暗号化されたデータセットと前記暗号化された乱数とに基づいて、暗号化された合計値を安全に算出するステップと、
前記暗号化された合計値の復号を実行し、前記合計値のビット表現を求めるステップと、
前記暗号化された乱数により前記合計値を処理することによって前記暗号化されたデータセットを表す個々のビットの暗号を生成するステップとを含む、方法が提供される。
【００１０】
本発明の第２の局面によれば、共同して、乱数を生成し、前記乱数のビット単位の暗号を算出するよう構成された少なくとも第１及び第２の計算装置を含むシステムが提供される。前記第１及び第２の計算装置の少なくとも１つの計算装置は、前記暗号化されたデータセットと前記暗号化された乱数とに基づいて、暗号化された合計値を算出するよう構成され、前記第１及び第２の計算装置は、共同して、前記暗号化された合計値の復号を実行し、前記合計値のビット表現を求めるよう構成される。また、前記第１及び第２の計算装置は、共同して、前記暗号化された乱数により前記合計値を処理することによって前記暗号化されたデータセットを表す個々のビットの暗号を生成するよう構成される。
【００１１】
本発明の基本的な考えは、数ｘ、ｘ∈｛０，１，．．．，ｎ−１｝のような、例えば生体特徴の形態のデータセットの暗号を、ｘについての情報やそのビットｘ０，ｘ１，．．．，ｘｔ−１を漏らすことなく、数ｘを形成するビットｘ０，ｘ１，．．．，ｘｔ−１の個々の暗号へと分解することが可能なプロトコルを提供することである。従って、本発明は、暗号化された数ｘ＝Σｉ＝１ｎｘｉ２ｉを形成するそれぞれの暗号化されたビットビット［［ｘ０］］，［［ｘ１］］，．．．，［［ｘｔ−１］］への暗号［［ｘ］］の分割（スプリッティング）を可能とする。
【００１２】
これは、例えば生体認証において、数ｘ＝Σｉ＝１ｎｘｉ２ｉとして表現されるビットストリングの単一の初期の暗号化を可能とするので、効果的である。暗号化されたビットのストリングは、続いて、ユーザを認証するために対応性に対するチェックをなすことができるように、登録中に得られる暗号化された生体特徴と比較されてもよい。暗号化された生体データの実際の比較は、典型的には、２者（若しくは多数者）プロトコルにおいて認証装置と生体センサを係合することにより実行され、このプロトコルでは、暗号化されたデータの２つのセットが、例えばハミング距離を用いて、２つのセット間で（十分な）対応性があるか否かを見るため、互いに比較される。
【００１３】
プロトコルの参加者は、プレイヤと称される。プレイヤは、共同して、この乱数を生成し、この乱数のビット単位の暗号化を実行する。好ましくは、乱数の暗号化は、乱数の暗号が正確に算出されていることを示すように構成された公的に検証可能な証明により実行される。暗号化された乱数と暗号化されたデータセットに基づく合計値は、準同型暗号化スキームを用いて暗号化される。用語“準同型（homomorphic）”は、［［ｘ＋ｙ］］＝［［ｘ］］［［ｙ］］、即ち（ｘ＋ｙ）の暗号がｘの暗号とｙの暗号の積に等しいことを意味する。
【００１４】
暗号化された合計値が算出された後、プレイヤは、閾値復号プロトコルを実行し、乱数の特徴を持つ合計値の平文複写を得、この合計値に対してビット表現が決定される。次いで、プレイヤは、共同して、ビット表現を用いて合計値の平文複写から乱数の暗号化されたビットを減算する。この演算は、データセット［［ｘ］］のビット表現［［ｘ０］］，［［ｘ１］］，．．．，［［ｘｔ−１］］を生成する。
【００１５】
本発明は、暗号［［ｘ０］］，［［ｘ１］］，．．．，［［ｘｔ−１］］が全てのプレイヤに利用可能であるので、効果的であり、これらのプレイヤは、他のプレイヤを伴うことを要せずに、続く計算のためにこれらの暗号を用いることができる。本発明は、無条件の設定に代えて暗号の設定におけるこの問題を解決する。更に、本発明は、暗号化されるデータセットが個人の生体特徴から抽出されることを想定する場合、例えば生体センサの、計算及び通信負荷の低減を可能とする。
【００１６】
本発明の更なる特徴及び効果は、添付の請求項及び次の説明を検討するときに明らかになるだろう。当業者であれば、本発明の異なる特徴は後述以外の実施例を生成するために組み合わせることができることを理解するだろう。
【発明を実施するための最良の形態】
【００１７】
本発明の好ましい実施例が添付図面を参照して詳説される。
【００１８】
本願で説明されるセキュリティ保護型の多数共同計算を実行するために、PaillierやEL Gamalのような、準同型閾値暗号化システムが使用される。用語“準同型”は、［［ｘ＋ｙ］］＝［［ｘ］］［［ｙ］］、即ち（ｘ＋ｙ）の暗号がｘの暗号とｙの暗号の積に等しいことを意味する。また、この用語は、任意のｘとａに対して、［［ｘ］］ａ＝［［ｘ＊ａ］］を意味する。用語“閾値”は、ｔ人以上のプレイヤの任意の集合が一緒になって暗号文を復号できるがより小さい如何なる集合は暗号文を復号できないように、ｌ人のプレイヤの１集合中の各プレイヤが秘密鍵のシェアにアクセス権を有することを意味する。
【００１９】
本発明は、効果的には、ユーザの生体特徴が参照データと比較される生体認証システムで採用されてもよい。整合が生じた場合には、ユーザが識別され、アクセスが得られる。ユーザ用の参照データは、事前に取得されており、例えばセキュリティ保護されたデータベースやスマートカードに、安全に保管される。認証されるべき物理的な対象は、非人間であってもよい。例えば、対象は、保護されたデジタルコンテンツを含む固体メモリやＣＤ，ＤＶＤのような記憶媒体であってもよい。この場合、生体は必ずしも用いられないが、同様の態様で、秘匿に維持されるべき（例えばビットシーケンスの、形態で）識別用特徴が付与され、対応する参照データと比較される。
【００２０】
認証時、ユーザは、ある識別子（アイデンティティー）を有することを要求し、供された生体テンプレートが、要求された識別子にリンクされた記憶された生体テンプレートと比較され、記憶されたテンプレートと記憶されたテンプレートの間の対応性が確認される。識別時、供された生体テンプレートが、記憶された全ての利用可能な生体テンプレートと比較され、記憶されたテンプレートと記憶されたテンプレートの間の対応性が確認される。尚、生体データは、個人の識別子の好適な表現物であり、個人に関連付けられた生体データの未認証の取得は、個人の識別子を盗むことと電子的に等価である。ハッカーは、個人を識別する適切な生体情報を取得した後、ハッカーが取得した識別子の個人を装うことができる。更に、生体データは、健康状態に関する繊細な私的情報を含んでいる場合がある。従って、生体認証／識別システムを採用する個人の保全性は守られなければならない。
【００２１】
生体暗号システムでは、公開鍵暗号が採用され、２人（若しくはそれ以上）のプレイヤ、例えばユーザと認証者（若しくは多数の認証者）は、同一の公開鍵にアクセス権を有する。また、ユーザ及び認証者は、それぞれ、対応する秘密鍵を有する。秘密鍵のシェアが復号に用いられる。
【００２２】
ユーザは、自身のシェアを（例えばスマートカードで）携帯してもよいし、若しくは、シェアは、ユーザが対話する対象の例えば生体識別システムのセンサ内に記憶されてもよい。登録中、生体識別子を現すビット列ｘ０，ｘ１，．．．，ｘｔ−１が取得され、番号ｘに変換され、
【００２３】
【数１】
共有の公開鍵で暗号化される。数ｘの暗号［［ｘ］］は、次いで、認証者に渡り、認証者がそれを保存する。尚、認証者は、秘密鍵の自身のシェアにアクセス権を有するだけでユーザのシェアにアクセス権を有していないので、暗号化された数を復号できない。従って、生体識別子の平文表現ｘは、認証者に対して隠されたままである。尚、認証者は、好ましくは、整合性の計算を共同して安全に実行する幾つかのサーバーからなる。サーバーのそれぞれは、秘密鍵のシェアを有する。十分な数のサーバーが共同する場合だけ、復号を実行することができる。
【００２４】
認証中、生体識別子の雑音のある表現ｙがシステムのセンサで得られる。尚、このセンサは、必ずしも登録で用いたセンサと同一である必要はなく、典型的には、限られた計算資源を有する低コストのセンサである。典型的には、認証用センサは、登録用センサから遠隔にある。例えば、一回だけ実行される登録は、より大きなチェーン店に含まれる任意のＤＶＤ／ビデオ店の形態の登録権限所有者で実行されてもよいが、認証は、典型的には、ユーザがＤＶＤを借りる特定の店で実行される。この店は、実際の認証者として見立てることができ、そこで、ユーザは認証されることになる。ユーザを認証するプロセスは、ユーザがＤＶＤを店で借りる度に毎回実行される。認証用センサは、共有の公開鍵でｙを暗号化する。続いて、安全な認証サーバーは、暗号化された数［［ｙ］］を、数ｙを形成するそれぞれのビットの暗号［［ｙ０］］，．．．，［［ｙｔ−１］］へと変換する。次いで、暗号化されたビット表現［［ｘ０］］，．．．，［［ｘｔ−１］］と［［ｙ０］］，．．．，［［ｙｔ−１］］が安全な方法で比較される。従って、ユーザが認証されることができるに、対応性のチェックがなされる。
【００２５】
本発明の一実施例では、ｘ∈｛０，１，．．．，ｎ−１｝である数ｘが暗号化されることが想定される。暗号化用に採用されるプロトコルの入力は、暗号［［ｘ］］により表され、出力は［［ｘ０］］，．．．，［［ｘｔ−１］］で表され、ここで、ｔは、数ｎ−１のビット長を指す。プロトコルの参加者は、プレイヤと称される。
【００２６】
先ず、典型的には安全なサーバーの集合の形態で具現化される、プレイヤは、共同して、０≦ｒ＜ｎの乱数を生成し、乱数のビット単位の暗号化［［ｒ０］］，．．．，［［ｒｔ−１］］を実行する。
【００２７】
【数２】
従って、ｒ＝９とすると、ｒ０＝１、ｒ１＝０、ｒ２＝０、ｒ３＝１である。その結果、ｒ＝１＊２０＋０＊２１＋０＊２２＋１＊２３＝１＋０＋０＋８＝９である。２つの安全なサーバーが採用される場合、２つのサーバーは、共同して、乱数ビットを生成及び暗号化する。例えば、ｒ０に対して、第１サーバーは、［［ｒ０’］］を算出し、第２サーバーは、［［ｒ０”］］を算出する。次いで、［［ｒ０］］＝［［ｒ０’＾ｒ０”］］が安全に算出され、ここで、記号＾はＸＯＲ（排他的論理和）演算を指す。この手順は、乱数の全てのビット［［ｒ０］］，．．．，［［ｒｔ−１］］に対して実行される。
【００２８】
暗号化は、暗号化されたビットが正確であることを示すように構成された必要なゼロ知識証明により達成される。かかる証明を算出する多数の異なる技術が存在する。EL Gamal（エルガマル）設定では、証明は、次のように算出されてもよい。秘密鍵α＝ｌｏｇｇｈとすると、復号は、あるメッセージｍ∈Ｚｑに対してｇｍに等しいｂ／ａαを計算することにより実行される。暗号化は、共通の秘密鍵ｈで計算される一方、復号は、プレイヤ間の共同プロトコルを用いて実行され、それぞれのプレイヤは、秘密鍵α＝ｌｏｇｇｈのシェアを保持する。プレイヤは、分散型の鍵生成プロトコルを実行することによりシェアを得る。
【００２９】
分散型の鍵生成は、プレイヤＰ１，Ｐ２（例えば生体センサ及び認証者、若しくは、第１及び第２サーバー）に先ずコミットメントｃ＝ｇαｉｈｒｉ（ｉ＝１，２に対してαｉ、ｒｉ∈Ｚｑ）をブロードキャストさせ、次いで、ｌｏｇｇｈｉ（ｉ＝１，２に対してｈｉ＝ｃｉ／ｈｒｉ）知識の証明と共に値ｒｉをブロードキャストさせることによって達成される。共同の公開鍵はｈ＝ｈ１ｈ２であり、秘密鍵α＝α１＋α２である。暗号（ａ，ｂ）を復号するため、プレイヤＰｉは、暗号化されたデータの平文複写に関する情報を明らかにすることなく、ｄｊ＝ａαｉを、ｌｏｇａｄｉ＝ｌｏｇｇｈｉの証明、即ち、暗号化された出力データが正確であることを示すように構成された証明と共に、生成する。次いで、メッセージは、ｂ／（ａ１ａ２）から回復される。尚、Paillierシステムに対しては、手順は異なる。
【００３０】
プレイヤは、暗号化されたビット［［ｒ０］］，．．．，［［ｒｔ−１］］を生成した後、次の通り、暗号［［ｘ＋ｒ］］を算出する。
【００３１】
【数３】
これは、従来ゲートと称される制約付きの乗算ゲートや一般的な安全な乗算を用いて実行される。従来ゲートを用いると、２つの暗号化された値ｒとｘは、ｒが２値の領域、例えばｒ∈｛０，１｝に制約される限り、効率的に乗算されることができる。ｘの値に制約はなく、例えばｘ∈Ｚｎ＊である。暗号［［ｘ＋ｒ］］は、必ずしも全てのプレイヤにより算出されることはなく、唯一のプレイヤ、例えば第１の安全なサーバーにより算出され、他のプレイヤ、例えば第２の安全なサーバーに分散されてもよい。
【００３２】
次いで、プレイヤは、共同して、閾値復号プロトコルを実行し、平文でｙ＝（ｘ＋ｒ）のｎによる剰余（ｍｏｄ）を算出する。数ｙを形成するデータにより、ｙは、また、乱数の特性を有し、平文表現ｘ、ｒは、公開データでないことから、ｙから導出することができない。プレイヤは、ｙのビット表現を求め、共同して、このビット表現から、生成された乱数ｒの暗号［［ｒ］］を減算する。これは、ビット単位の減算、即ちｙ０−［［ｒ０］］，ｙ１−［［ｒ１］］，．．．，ｙｔ−１−［［ｒｔ−１］］により実現される。これは、他の暗号［［ｚ］］を生み、暗号［［ｚ］］は、（暗号化されたビットの）安全な減算回路を用いることによって、［［ｚ］］＝ｙ−［［ｒ］］として算出される。
【００３３】
これは、ｚｔがサインビットであるとき、暗号化されたビット［［ｚ０］］，．．．，［［ｚｔ−１］］により与えられる数ｚ＝ｘ若しくはｚ＝ｘ−ｎのビット表現を生む。従って、サインビットに依存して、［［ｘ０］］，．．．，［［ｘｔ−１］］若しくは［［（ｘ−ｎ）０］］，．．．，［［（ｘ−ｎ）ｔ−１］］が取得される。プレイヤは、ビット表現を用いてｚにｎｚｔを加えることによってｎによるｚの剰余を減らす。従って、ビット表現［［ｘ０］］，．．．，［［ｘｔ−１］］が生成される。
【００３４】
本発明のその他の実施例では、０≦ｘ＜２ｍ≪２ｋ＜ｎ、ｋ≫ｍであり、従って、２ｋ≫２ｍであることが想定される。暗号化用に採用されるプロトコルの入力は、同様に、暗号［［ｘ］］により表され、出力は［［ｘ０］］，．．．，［［ｘｔ−１］］で表される。この例示的な実施例では、ｘの最下位ｍビットｘ０，ｘ１，．．．，ｘｍ−１をどのようにして求めるかが説明される。各プレイヤＰｉ、１≦ｉ≦１は、ｒ＊，ｉ∈Ｒ｛０，１｝でｒ’ｉ∈｛０，．．．，２ｋ−ｍ−１｝である乱数ビットｒ０，ｉ，．．．，ｒｍ−１，ｉを選択し、これらのビットを暗号化し、暗号［［ｒ０，ｉ］］，．．．，［［ｒｍ−１，ｉ］］及び［［ｒ’ｉ］］を、暗号化が正確に完了したことの証明と共に、分散する。
【００３５】
プレイヤは、これらの暗号化されたビットを用いて、共同して、乱数ビットの暗号［［ｒ０］］，．．．，［［ｒｍ−１］］を生成する。この場合、乱数ビットｒの暗号は、安全な乗算ゲート及び乱数ｒ’を用いて、次の通り安全に算出される。
【００３６】
【数４】
ここで、乱数ｒ’は、準同型暗号化特性を用いて、次の通り算出される。
【００３７】
【数５】
プレイヤは、共同して、［［ｘ−ｒ］］を形成し、暗号［［ｘ−ｒ］］は、次いで、共同して、値ｙ＝ｘ−ｒを明らかにするために閾値復号プロトコルを用いて復号される。
【００３８】
【数６】
公開ビットｙ０，．．．，ｙｍ−１は、に２ｍよるｙの剰余を指す。公開入力トｙ０，．．．，ｙｍ−１及び［［ｒ０］］，．．．，［［ｒｍ−１］］用の安全な付加回路は、ｍ個の暗号化されたビット［［ｘ０］］，．．．，［［ｘｍ−１］］の出力を生成するために使用される。２ｍよるｙの剰余を算出することによって、最終のキャリービットは無視される。
【００３９】
図１は、個人に関連する生体データに基づく個人の識別及び認証用の基本的な従来技術のシステムを示し、このシステム内で、本発明が効果的に適用されることができる。指紋、虹彩、網膜、顔若しくは手の幾何学特徴、声の特徴等のような、個人の生の生体データは、センサ１０１にて取得される。典型的には、生体データを表すビット列ｘ０，ｘ１，．．．，ｘｔ−１がセンサにて取得される。取得されたデータ（即ち、生の平文データ）は、典型的には、デジタル信号プロセッサ（ＤＰＳ）のような処理装置１０２で処理される。処理装置は、センサと一体であってよい。この処理は、共通の公開鍵で暗号化される数ｘへのビットの変換を伴う。数ｘの暗号［［ｘ］］（若しくはｘのビットの暗号）は、次いで、サービスプロバイダのデータベース記憶装置１０３内にパス１０５を介して記憶される。これは、個人を登録するために、特定のシステムにアクセスを望む各個人に対して一回実行される初期の手続きである。
【００４０】
続いて、個人がサービスへアクセスを望むとき、その個人は、センサ１０１に、平文の生体データｙ０，．．．，ｙｔ−１を供給する。このデータは、次いで、暗号化の後、パス１０６を介して、データベース内に事前に記憶されている個人の生体データ［［ｘ］］と比較される。比較装置１０４にて実行される比較時に、パス１０６と１０７を解して提供されるデータのセット間に整合があった場合には、その個人は、提供されるサービスへのアクセス権が付与される。比較を実行するとき、上述のビットスプリッティングプロトコルは、［［ｙ０］］，．．．，［［ｙｔ−１］］と［［ｘ０］］，．．．，［［ｘｔ−１］］の間でビット単位の比較をなすことができるように、記憶装置１０３に記憶される暗号化されたデータ［［ｘ］］に対して実行される。
【００４１】
従って、図１を参照するに、センサ１０１は、初期の特徴抽出セッションでは登録者として機能するが、続くセッションでは、センサは、比較装置１０４において、（パス１０６を介して）後に提供される生体情報ｙと（パス１０７を介して）初期登録された生体情報との間の対応性をチェックする認証者として機能する。上述の如く、図１の装置は、互いに遠隔に配置されてもよい。図１に示す種のシステムでは、センサ１０１は、典型的には、暗号化演算を算出するために比較的高出力である。高出力のセンサが用いられる場合、センサ１０１／処理装置１０２及び比較装置１０４は、共同して、本発明のビットスプリッティングプロトコルを実行する。
【００４２】
図２は、個人に関連する生体データに基づく個人の識別及び認証用のその他のシステムを示し、このシステム内で、本発明が適用されることができる。ここで、登録用センサ２１０及び確認若しくは認証用センサ２０８は遠隔に配置される。図１においてと同様、取得されたデータ（即ち、生の平文データ）ｘ０，ｘ１，．．．，ｘｔ−１は、ＤＰＳ２０２にて、数ｘへ変換され、共通の公開鍵で暗号化される。数ｘの暗号［［ｘ］］は、次いで、データベース記憶装置２０３内に記憶される。続いて、個人がシステムにアクセスを望むとき、その個人は、認証用センサ２０８に、平文の生体データｙ０，．．．，ｙｔ−１を供給する。次いで、このデータは、ＤＳＰ２０９により数ｙに変換され暗号化される。従って、図２を参照するに、生体テンプレートｘが事前に登録用センサ２０１に供給され、ＤＳＰ２０２にて暗号化され、データベース記憶装置２０３内に暗号化された形態［［ｘ］］で記憶されていると想定する場合、個人がサービスへアクセスを望むとき、その個人の生体テンプレートｙ（ｘの雑音のある表現）は、確認用センサ２０８（認証用センサとも称される）により抽出され、暗号化された複写［［ｙ］］を生成するため、ＤＳＰ２０９により暗号化される。典型的には、ＤＳＰ２０９は、認証用センサ２０８に含まれる。この特定のシステムでは、センサ２０８が典型的には限られた計算能力しかない低コストのセンサであることから、本発明は、図１に示すシステムよりも効果的である。
【００４３】
数［［ｘ］］は、インターネットのようなネットワーク２１０をおそらくは介して、列を記憶する認証者２１１に渡される。認証者２１１は、また、典型的には、図２に示していないが、ＤＳＰを含む。尚、認証者は、秘密鍵の自身のシェアにアクセス権を有するだけでその個人のシェアにアクセス権を有していないので、暗号化された数を復号できない。従って、生体識別子の平文表現ｘは、認証者２１１に対して隠されたままである。本発明による安全なビットスプリッティングプロトコルは、認証者２１１で実行されることになる。セキュリティ性を改善するため、ビットスプリッティングプロトコルの実行は、安全なサーバー２１２，２１３の集合に外注される。従って、認証者２１１は、それぞれ生体データｘ、ｙの各セットの暗号［［ｘ］］及び［［ｙ］］によりサービスを提供する。
【００４４】
上述の如く、安全なサーバー２１２，２１３は、共同して、０≦ｒ＜ｎの乱数を生成し、乱数のビット単位の暗号化［［ｒ０］］，．．．，［［ｒｔ−１］］を実行する。乱数の暗号化は、暗号化されたビットが正確であることを示すように構成された必要なゼロ知識証明により達成される。サーバー２１２，２１３は、暗号化されたビット［［ｒ０］］，．．．，［［ｒｔ−１］］を生成したとき、サーバー２１２，２１３（若しくは２つのサーバーのうちの少なくとも一方）は、次のように、暗号、［［ｘ＋ｒ］］を算出する。
【００４５】
【数７】
次いで、サーバー２１２，２１３は、共同して、閾値復号プロトコルを実行し、平文でｙ＝（ｘ＋ｒ）のｎによる剰余を算出し、ｙのビット表現を決定し、共同して、このビット表現から、生成された乱数ｒの暗号［［ｒ］］を減算する。結果として、他の暗号［［ｚ］］が、［［ｚ］］＝ｙ−［［ｒ］］として算出される。
【００４６】
これは、ｚｔがサインビットであるとき、暗号化されたビット［［ｚ０］］，．．．，［［ｚｔ−１］］により与えられる数ｚ＝ｘ若しくはｚ＝ｘ−ｎのビット表現を生む。従って、サインビットに依存して、［［ｘ０］］，．．．，［［ｘｔ−１］］若しくは［［（ｘ−ｎ）０］］，．．．，［［（ｘ−ｎ）ｔ−１］］が取得される。サーバー２１２，２１３の一方（若しくは双方）は、ビット表現を用いてｚにｎｚｔを加えることによってｎによるｚの剰余を減らす。従って、ビット表現［［ｘ０］］，．．．，［［ｘｔ−１］］が生成される。ビット表現［［ｙ０］］，．．．，［［ｙｔ−１］］は、同様の態様で生成される。
【００４７】
今度は、ビットスプリッティングプロトコルが実行されたとき、認証者２１１及び人商用センサ２０８は、暗号化された生体データを比較する任意の適切な方法、例えばＩＤ６９５４５９／ＮＬ０４１３３５に開示されるような方法を用いて、暗号化されたビット表現［［ｙ０］］，．．．，［［ｙｔ−１］］と［［ｘ０］］，．．．，［［ｘｔ−１］］の間に対応性があるか否かを見出す。
【００４８】
本発明は、その特別な例示的な実施例を参照して説明されているが、多数の異なる代替、修正等は当業者には明らかである。記載された実施例は、それ故に、添付の請求項により定義される本発明の範囲を制限する意図でない。尚、上述した本発明の例示的な実施例によれば２つの安全なサーバーが共同してビットスプリッティングプロトコルを実行しているが、任意の数の安全なサーバーが、共同してビットスプリッティングプロトコルを実行するために採用されてもよい。
【図面の簡単な説明】
【００４９】
【図１】個人に関連する生体データに基づく個人の識別及び認証用の基本的な従来技術のシステムを示し、このシステム内で、本発明が効果的に適用される。
【図２】個人に関連する生体データに基づく個人の識別及び認証用のその他のシステムを示し、このシステム内で、本発明が効果的に適用される。
【特許請求の範囲】
【請求項１】
暗号化されたデータセットを、前記データセットを表す個々のビットの暗号へと変換する方法であって、
乱数を生成し、前記乱数のビット単位の暗号を算出するステップと、
前記暗号化されたデータセットと前記暗号化された乱数とに基づいて、暗号化された合計値を安全に算出するステップと、
前記暗号化された合計値の復号を実行し、前記合計値のビット表現を求めるステップと、
前記暗号化された乱数により前記合計値を処理することによって前記暗号化されたデータセットを表す個々のビットの暗号を生成するステップとを含む、方法。
【請求項２】
前記暗号化されたデータセットを取得するステップを更に含む、請求項１に記載の方法。
【請求項３】
前記乱数の暗号が正確に算出されていることの公的に検証可能な証明を付与するステップとを含む、請求項１に記載の方法。
【請求項４】
前記暗号化された合計値を算出するステップは、前記暗号化されたデータと前記暗号化された乱数とを安全な乗算ゲートを用いて乗算することにより実行される、請求項１に記載の方法。
【請求項５】
前記暗号化された合計値を復号するステップは、閾値復号プロトコルを用いて実行される、請求項１に記載の方法。
【請求項６】
前記暗号化されたデータセットを表す個々のビットの暗号を生成するステップは、前記合計値のビット表現から前記暗号化された乱数を減算することにより実行される、請求項１に記載の方法。
【請求項７】
前記減算は、安全な減算ゲートを用いて実行される、請求項６に記載の方法。
【請求項８】
前記個々のビットの暗号を生成するステップは、更に、前記合計値のビット表現にサインビットを付加するステップを含む、請求項６に記載の方法。
【請求項９】
前記暗号化されたデータセットを表す個々のビットの暗号を生成するステップは、前記合計値のビット表現に前記暗号化された乱数を加算することにより実行される、請求項１に記載の方法。
【請求項１０】
前記暗号化されたデータセットは、個人の生体特徴から抽出される、請求項１に記載の方法。
【請求項１１】
暗号化されたデータセットを、前記データセットを表す個々のビットの暗号へと変換するシステムであって、
共同して、乱数を生成し、前記乱数のビット単位の暗号を算出するよう構成された少なくとも第１及び第２の計算装置を含み、
前記第１及び第２の計算装置の少なくとも１つの計算装置は、前記暗号化されたデータセットと前記暗号化された乱数とに基づいて、暗号化された合計値を算出するよう構成され、
前記第１及び第２の計算装置は、共同して、前記暗号化された合計値の復号を実行し、前記合計値のビット表現を求めるよう構成され、
前記第１及び第２の計算装置は、共同して、前記暗号化された乱数により前記合計値を処理することによって前記暗号化されたデータセットを表す個々のビットの暗号を生成するよう構成される、システム。
【請求項１２】
前記第１及び第２の計算装置は、更に、前記乱数の暗号が正確に算出されていることの公的に検証可能な証明を算出するよう構成される、請求項１１に記載のシステム。
【請求項１３】
前記第１及び第２の計算装置は、共同して閾値復号プロトコルを実行することにより前記暗号化された合計値を復号するよう構成される、請求項１１に記載のシステム。
【請求項１４】
前記第１及び第２の計算装置は、前記合計値のビット表現から前記暗号化された乱数を減算することにより、前記暗号化されたデータセットを表す個々のビットの暗号を生成するよう構成される、請求項１１に記載のシステム。
【請求項１５】
前記第１及び第２の計算装置は、前記合計値のビット表現に前記暗号化された乱数を加算することにより、前記暗号化されたデータセットを表す個々のビットの暗号を生成するよう構成される、請求項１１に記載のシステム。
【請求項１６】
前記第１及び第２の計算装置は、
前記乱数の各ビットに対してそれぞれのビットを生成し、前記乱数の該各ビットを生成するために前記それぞれのビットを排他的論理和演算し、
前記乱数の各ビットを安全に暗号化することによって、
前記のように、共同して、乱数を生成し、前記乱数のビット単位の暗号を算出するよう構成される、請求項１１に記載のシステム。
【請求項１７】
コンピュータープログラムであって、
コンピューター実行可能なコンポーネントが装置内に含まれる処理ユニット上で実行されたときに、該装置をして請求項１に記載の各ステップを実行させるコンピューター実行可能なコンポーネントを含む、コンピュータープログラム。
【請求項１】
暗号化されたデータセットを、前記データセットを表す個々のビットの暗号へと変換する方法であって、
乱数を生成し、前記乱数のビット単位の暗号を算出するステップと、
前記暗号化されたデータセットと前記暗号化された乱数とに基づいて、暗号化された合計値を安全に算出するステップと、
前記暗号化された合計値の復号を実行し、前記合計値のビット表現を求めるステップと、
前記暗号化された乱数により前記合計値を処理することによって前記暗号化されたデータセットを表す個々のビットの暗号を生成するステップとを含む、方法。
【請求項２】
前記暗号化されたデータセットを取得するステップを更に含む、請求項１に記載の方法。
【請求項３】
前記乱数の暗号が正確に算出されていることの公的に検証可能な証明を付与するステップとを含む、請求項１に記載の方法。
【請求項４】
前記暗号化された合計値を算出するステップは、前記暗号化されたデータと前記暗号化された乱数とを安全な乗算ゲートを用いて乗算することにより実行される、請求項１に記載の方法。
【請求項５】
前記暗号化された合計値を復号するステップは、閾値復号プロトコルを用いて実行される、請求項１に記載の方法。
【請求項６】
前記暗号化されたデータセットを表す個々のビットの暗号を生成するステップは、前記合計値のビット表現から前記暗号化された乱数を減算することにより実行される、請求項１に記載の方法。
【請求項７】
前記減算は、安全な減算ゲートを用いて実行される、請求項６に記載の方法。
【請求項８】
前記個々のビットの暗号を生成するステップは、更に、前記合計値のビット表現にサインビットを付加するステップを含む、請求項６に記載の方法。
【請求項９】
前記暗号化されたデータセットを表す個々のビットの暗号を生成するステップは、前記合計値のビット表現に前記暗号化された乱数を加算することにより実行される、請求項１に記載の方法。
【請求項１０】
前記暗号化されたデータセットは、個人の生体特徴から抽出される、請求項１に記載の方法。
【請求項１１】
暗号化されたデータセットを、前記データセットを表す個々のビットの暗号へと変換するシステムであって、
共同して、乱数を生成し、前記乱数のビット単位の暗号を算出するよう構成された少なくとも第１及び第２の計算装置を含み、
前記第１及び第２の計算装置の少なくとも１つの計算装置は、前記暗号化されたデータセットと前記暗号化された乱数とに基づいて、暗号化された合計値を算出するよう構成され、
前記第１及び第２の計算装置は、共同して、前記暗号化された合計値の復号を実行し、前記合計値のビット表現を求めるよう構成され、
前記第１及び第２の計算装置は、共同して、前記暗号化された乱数により前記合計値を処理することによって前記暗号化されたデータセットを表す個々のビットの暗号を生成するよう構成される、システム。
【請求項１２】
前記第１及び第２の計算装置は、更に、前記乱数の暗号が正確に算出されていることの公的に検証可能な証明を算出するよう構成される、請求項１１に記載のシステム。
【請求項１３】
前記第１及び第２の計算装置は、共同して閾値復号プロトコルを実行することにより前記暗号化された合計値を復号するよう構成される、請求項１１に記載のシステム。
【請求項１４】
前記第１及び第２の計算装置は、前記合計値のビット表現から前記暗号化された乱数を減算することにより、前記暗号化されたデータセットを表す個々のビットの暗号を生成するよう構成される、請求項１１に記載のシステム。
【請求項１５】
前記第１及び第２の計算装置は、前記合計値のビット表現に前記暗号化された乱数を加算することにより、前記暗号化されたデータセットを表す個々のビットの暗号を生成するよう構成される、請求項１１に記載のシステム。
【請求項１６】
前記第１及び第２の計算装置は、
前記乱数の各ビットに対してそれぞれのビットを生成し、前記乱数の該各ビットを生成するために前記それぞれのビットを排他的論理和演算し、
前記乱数の各ビットを安全に暗号化することによって、
前記のように、共同して、乱数を生成し、前記乱数のビット単位の暗号を算出するよう構成される、請求項１１に記載のシステム。
【請求項１７】
コンピュータープログラムであって、
コンピューター実行可能なコンポーネントが装置内に含まれる処理ユニット上で実行されたときに、該装置をして請求項１に記載の各ステップを実行させるコンピューター実行可能なコンポーネントを含む、コンピュータープログラム。
【図１】
【図２】
【図２】
【公表番号】特表２００９−５１９４９０（Ｐ２００９−５１９４９０Ａ）
【公表日】平成２１年５月１４日（２００９．５．１４）
【国際特許分類】
【出願番号】特願２００８−５４５１７８（Ｐ２００８−５４５１７８）
【出願日】平成１８年１２月７日（２００６．１２．７）
【国際出願番号】ＰＣＴ／ＩＢ２００６／０５４６４６
【国際公開番号】ＷＯ２００７／０６９１４６
【国際公開日】平成１９年６月２１日（２００７．６．２１）
【出願人】（５９００００２４８）コーニンクレッカ フィリップス エレクトロニクス エヌ ヴィ (12,071)
【Ｆターム（参考）】
【公表日】平成２１年５月１４日（２００９．５．１４）
【国際特許分類】
【出願日】平成１８年１２月７日（２００６．１２．７）
【国際出願番号】ＰＣＴ／ＩＢ２００６／０５４６４６
【国際公開番号】ＷＯ２００７／０６９１４６
【国際公開日】平成１９年６月２１日（２００７．６．２１）
【出願人】（５９００００２４８）コーニンクレッカ フィリップス エレクトロニクス エヌ ヴィ (12,071)
【Ｆターム（参考）】
[ Back to top ]