(57)【特許請求の範囲】
【請求項１】
個人又は物体（Ｉ）の認証プロセスであって、
システムは、前記認証される個人（Ｉ）又は物体のデータ（ｂ）を取得するように構成される制御サーバ（ＳＣ）と、Ｎ人の記憶された個人のＮ個のインデックス付き基準データ（ｂｉ）を含むデータベース（ＤＢ）の管理サーバ（ＳＧ）とを備え、前記個人（Ｉ）の前記データ（ｂ）及び前記基準データ（ｂｉ）は、ｎビットで符号化され、
前記個人又は物体（Ｉ）を認証するために、該個人又は物体（Ｉ）の前記データ（ｂ）が、前記ベースの前記Ｎ個のデータ（ｂｉ）のそれぞれと比較されて、該認証される個人又は物体（Ｉ）の前記データ（ｂ）が前記Ｎ人の記憶された個人の前記Ｎ個の基準データ（ｂｉ）のうちの１つに対応するか否かが判断され、
当該プロセスは、前記制御サーバ（ＳＣ）が前記認証される個人又は物体の前記データ（ｂ）を取得する（１００）ステップを含み、
当該プロセスは、
−  前記制御サーバ（ＳＣ）及び前記管理サーバ（ＳＧ）が、前記ベースの前記基準データ（ｂｉ）及び前記認証される個人又は物体（Ｉ）の前記データ（ｂ）を、より小さなサイズの簡略化データ（ｓｉ，ｓ）に変換する（２１０）ステップであって、該簡略化データ（ｓｉ，ｓ）はｔビットで符号化され、ｔはｎ未満であるステップと、
−  前記制御サーバ（ＳＣ）が、前記データベース（ＤＢ）の前記Ｎ個の簡略化データ（ｓｉ）のそれぞれと、前記認証される個人又は物体（Ｉ）の前記簡略化データ（ｓ）との間でセキュアに、前記認証される個人又は物体（Ｉ）の前記簡略化データ（ｓ）と最も多くの類似点を有する前記ベース（ＤＢ）の前記簡略化データ
【数１】
0005676064.tif 000033
の一組のｐ個のインデックス（ｉ０，．．．，ｉｐ−１）を求める（２００）ステップであって、ｐはＮ未満であり、前記一組は、前記管理サーバ（ＳＧ）が評価対象の関数のガーブル計算回路を生成する（２２０）、セキュアなマルチパーティ計算の方法を実行することによって求められ、
・  前記ガーブル回路は、入力として、前記ベース（ＤＢ）の簡略化データ
【数２】
0005676064.tif 000034
のビット及び前記個人（Ｉ）の前記簡略化データ（ｓ）のビットの一組の暗号鍵を有し、
・  前記評価対象の関数は、前記ベース（ＤＢ）の前記簡略化データ
【数３】
0005676064.tif 000035
と前記個人（Ｉ）の前記簡略化データ（ｓ）との間の前記類似率を計算するものであり、その後に、前記個人の前記簡略化データ（ｓ）と最も多くの類似点を有する前記ベースの前記ｐ個の簡略化データの探索ステップが続き、前記回路の評価は、前記個人の前記簡略化データ（ｓ）と最も多くの類似点を有する前記簡略化データ
【数４】
0005676064.tif 000036
のインデックス（ｉ０，．．．，ｉｐ−１）を見つけることを可能にする、
ステップと、
−  前記管理サーバ（ＳＧ）が、前記データベース（ＤＢ）の前記Ｎ個の基準データ（ｂｉ）をスクランブルし（３２０）、事前に識別された前記簡略化データ
【数５】
0005676064.tif 000037
に対応するｐ個のスクランブルされたデータ
【数６】
0005676064.tif 000038
を前記制御サーバに転送するステップと、
−  前記制御サーバ（ＳＣ）が、前記ｐ個のスクランブルされたデータ
【数７】
0005676064.tif 000039
から、該ｐ個のスクランブルされたデータ
【数８】
0005676064.tif 000040
のそれぞれと、前記個人又は物体の前記データ（ｂ）との間のセキュアなマルチパーティ計算によって、対応する基準データ
【数９】
0005676064.tif 000041
）が前記個人又は物体の前記データ（ｂ）との所定の閾値（η）を超える類似率を有する、１つ又は複数のスクランブルされたデータ
【数１０】
0005676064.tif 000042
の単数又は複数のインデックス（ｉＩＤ）を求める（３００）ステップと
を更に含むことを特徴とする、個人又は物体の認証プロセス。
【請求項２】
前記管理サーバ（ＳＧ）から前記制御サーバ（ＳＣ）への前記ｐ個のスクランブルされたデータ
【数１１】
0005676064.tif 000043
の転送は、紛失通信技法を用いる、請求項１に記載の認証プロセス。
【請求項３】
前記制御サーバ（ＳＣ）が、対応する基準データ
【数１２】
0005676064.tif 000044
が、前記個人（Ｉ）又は物体の前記データ（ｂ）との所定の閾値（η）を超える類似率を有する、スクランブルされたデータ
【数１３】
0005676064.tif 000045
の単数又は複数のインデックス（ｉＩＤ）を求めた後、
前記制御サーバ（ＳＣ）は、前記インデックス（ｉＩＤ）を前記管理サーバ（ＳＧ）に通信し（４００）、
前記管理サーバ（ＳＧ）は、前記単数又は複数のインデックス（ｉＩＤ）から、該単数又は複数のインデックスに対応する前記ベースの単数又は複数の基準データ
【数１４】
0005676064.tif 000046
を求め、前記個人（ｉ）又は物体を、前記単数又は複数のインデックス（ｉＩＤ）に対応する前記基準データ
【数１５】
0005676064.tif 000047
を有する、前記ベース（ＤＢ）に記憶された個人又は物体として認証する、請求項１に記載の認証プロセス。
【請求項４】
前記管理サーバ（ＳＧ）は、前記ベース（ＤＢ）の前記Ｎ個のデータ（ｂｉ）をスクランブルするために、選択された前記簡略化データ
【数１６】
0005676064.tif 000048
に対応する前記ｐ個の基準データ
【数１７】
0005676064.tif 000049
のそれぞれについて、前記対応するデータ（ｂｉ）のバイナリ表現におけるビットの可能な位置（ｕ）ごとに、ランダム置換
【数１８】
0005676064.tif 000050
が該位置（ｕ）のビットに適用されるＮ個のスクランブルされたデータ（ｂ’ｉ）を含む対応するスクランブルされたデータベース
【数１９】
0005676064.tif 000051
を生成する、請求項１に記載の認証プロセス。
【請求項５】
前記認証は個人に関するものであり、前記ベース（ＤＢ）の前記基準データ（ｂｉ）及び前記認証される個人（Ｉ）の前記データ（ｂ）はバイオメトリックデータである、請求項１に記載の認証プロセス。
【請求項６】
前記バイオメトリックデータ（ｂ，ｂｉ）は、虹彩画像のバイナリ符号である、請求項５に記載の認証プロセス。
【請求項７】
各データ（ｂ，ｂｉ）は、一組のインデックス付けされたビットを含み、
前記データ（ｂ，ｂｉ）から簡略化データ（ｓ，ｓｉ）への変換ステップ（２１０）において、該データ（ｂ，ｂ）のビットのインデックス番号を含むインデックス集合（Ａ）が定義され、
前記データ（ｂ，ｂｉ）は、前記インデックス集合の番号によってインデックス付けされたビットのみを保持することによって、前記簡略化データ（ｓ，ｓｉ）に変換され、
前記インデックス番号は、最も適切なビットに関係するように選択される、請求項１に記載の認証プロセス。
【請求項８】
前記個人（Ｉ）又は物体の前記簡略化データ（ｓ）と最も多くの類似点を有する前記ベース（ＤＢ）の簡略化データ（ｓｉ）を求めるステップは、前記ベース（ＤＢ）の前記簡略化データ（ｓｉ）と前記個人の前記簡略化データ（ｓ）との間のハミング距離の計算によって実行される、請求項７に記載の認証プロセス。
【請求項９】
前記認証される個人（Ｉ）の前記簡略化データ（ｓ）と最も多くの類似点を有する前記ベース（ＤＢ）のＮ個の簡略化データ（ｓｉ）を求めるステップは、セキュアなマルチパーティ計算によって実行される、請求項１に記載の認証プロセス。
【請求項１０】
前記ベース（ＤＢ）の前記スクランブルされたデータ
【数２０】
0005676064.tif 000052
と前記個人の前記データ（ｂ）との間の前記セキュアなマルチパーティ計算のステップにおいて、
−  各スクランブルされたデータ
【数２１】
0005676064.tif 000053
に対応する前記ベースの各データ
【数２２】
0005676064.tif 000054
と前記個人の前記データ（ｂ）との間の類似率が計算され、
−  得られた類似率は前記所定の閾値（η）と比較され、該閾値（η）を超える類似率を有する前記ベース（ＤＢ）の単数又は複数のデータの単数又は複数のインデックスが選択される、請求項１〜９のいずれか一項に記載の認証プロセス。
【請求項１１】
セキュアなマルチパーティ計算の各ステップは、以下の部分ステップ、すなわち、
−  前記管理サーバ（ＳＧ）が、評価対象の関数（ｆ）の計算をするための少なくとも１つのガーブル回路（Ｃ）を生成する部分ステップであって、
各ガーブル回路（Ｃ）は、入力として前記評価対象の関数（ｆ）の入力データのビットに対応する一組の暗号鍵を有し、出力として前記評価対象の関数（ｆ）の結果のビットに対応する暗号鍵を有し、
・  要素論理演算の形式に分解された前記関数（ｆ）の計算ステップと、
・  各要素論理演算の可能な入力及び出力のそれぞれの一組の符号化鍵（ｋ）と
を含む、部分ステップと、
−  前記管理サーバ（ＳＧ）が前記符号化鍵（ｋ）をランダムに生成する部分ステップと、
−  前記管理サーバ（ＳＧ）が、各ガーブル回路（Ｃ）について、
・  前記評価対象の関数（ｆ）の入力ビットの値に対応する符号化鍵（ｋ）と、
・  各ガーブル回路（Ｃ）の出力又は各ガーブル回路の論理演算の１つ若しくは複数の出力の復号表（Ｔ）と
を、紛失通信技法を用いて前記制御サーバ（ＳＣ）に通信する部分ステップと、
−  前記制御サーバ（ＳＣ）が、得られた鍵（ｋ）から、該得られた鍵を入力として用いて各ガーブル回路（Ｃ）を評価する部分ステップと
を含む、請求項１〜１０のいずれか一項に記載のプロセス。
【請求項１２】
前記スクランブルされたデータ
【数２３】
0005676064.tif 000055
に対応するデータ
【数２４】
0005676064.tif 000056
と、前記個人の前記データ（ｂ）との間の類似率を計算して比較するように、セキュアなマルチパーティ計算が行われ、
前記管理サーバ（ＳＧ）は、前記選択されたベースの各データについて、対応するガーブル回路を生成し（３１０）、
−  各ガーブル回路（Ｃ０．．．Ｃｐ−１）の入力は、前記対応するスクランブルされたデータ
【数２５】
0005676064.tif 000057
の暗号鍵及び前記個人（Ｉ）の前記データ（ｂ）の暗号鍵であり、
−  各ガーブル回路の前記評価対象の関数（ｆ）は、前記対応するベースのデータ
【数２６】
0005676064.tif 000058
と前記個人の前記データ（ｂ）との間の類似率を計算し、該類似率を前記所定の閾値（η）と比較するものであり、
−  各回路（Ｃ０．．．Ｃｐ−１）の出力は、前記類似率を前記所定の閾値（η）と比較した結果であり、
前記管理サーバ（ＳＧ）は、各ガーブル回路（Ｃ０．．．Ｃｐ−１）について、前記スクランブルされたデータ
【数２７】
0005676064.tif 000059
のビットの可能な値に対応するスクランブルされた符号化鍵（ｋ’）と、前記個人のデータ（ｂ）のビットの可能な値に対応する符号化鍵（ｋ）とを生成して前記制御サーバ（ＳＣ）に転送し、また前記スクランブルされたデータのビットの値を前記制御サーバ（ＳＣ）に転送し、
前記スクランブルされたデータのビットの値及び前記対応する符号化鍵の転送は、紛失通信方法を実行する、請求項１１に記載の認証プロセス。
【請求項１３】
各ガーブル回路（Ｃ０．．．Ｃｐ−１）の前記評価対象の関数（ｆ）は、前記スクランブルされたデータ
【数２８】
0005676064.tif 000060
に対応する各データ
【数２９】
0005676064.tif 000061
と前記個人（Ｉ）の前記データ（ｂ）との間の正規化されたハミング距離の計算を含む、請求項１２に記載の認証プロセス。
【請求項１４】
スクランブルされたデータ
【数３０】
0005676064.tif 000062
の符号化鍵（ｋ’）の生成は、前記ベースの対応するデータ
【数３１】
0005676064.tif 000063
のビットごとにランダムに生成される符号化鍵（ｋ）に対して、前記スクランブルされたデータ
【数３２】
0005676064.tif 000064
を得るために前記データ
【数３３】
0005676064.tif 000065
のビットに適用されたものと同じ置換
【数３４】
0005676064.tif 000066
に従った再インデックス付けを適用することによって実行される、請求項４に従属する場合の請求項１１又は請求項１２のいずれか一項に記載の認証プロセス。
【請求項１５】
前記ベース（ＤＢ）の前記データ（ｂ０．．．ｂＮ−１）が前記管理サーバ（ＳＧ）によってランダムに再インデックス付けされる予備ステップ（１０）を含む、請求項１に記載の認証プロセス。
【請求項１６】
認証される個人（Ｉ）の少なくとも１つの制御サーバ（ＳＣ）と、記憶された個人のＮ個の基準データ（ｂ０．．．ｂＮ−１）のベース（ＤＢ）の少なくとも１つの管理サーバ（ＳＧ）とを備える、個人の認証システムであって、
前記制御サーバ（ＳＣ）は、前記個人（Ｉ）のデータ（ｂ）の取得を進めるように構成され、
当該システムにおいて、前記制御サーバ（ＳＣ）及び前記管理サーバ（ＳＧ）は、
−  前記ベースの前記基準データ（ｂｉ）及び前記認証される個人又は物体（Ｉ）の前記データ（ｂ）を、より小さなサイズの簡略化データ（ｓｉ，ｓ）に変換すること（２１０）と、
−  前記データベース（ＤＢ）の前記Ｎ個の簡略化データ（ｓｉ）のそれぞれと、前記認証される個人又は物体（Ｉ）の前記簡略化データ（ｓ）との間でセキュアに、前記認証される個人又は物体（Ｉ）の前記簡略化データ（ｓ）と最も多くの類似点を有する前記ベース（ＤＢ）の簡略化データ
【数３５】
0005676064.tif 000067
の一組のｐ個のインデックス（ｉ０，．．．，ｉｐ−１）を求めることであって（２００）、ｐはＮ未満であり、前記一組は、前記管理サーバ（ＳＧ）が評価対象の関数のガーブル計算回路を生成する（２２０）、セキュアなマルチパーティ計算の方法を実行することによって求められ
・  前記ガーブル回路は、入力として、前記ベース（ＤＢ）の簡略化データ
【数３６】
0005676064.tif 000068
のビット及び前記個人（Ｉ）の前記簡略化データ（ｓ）のビットの一組の暗号鍵を有し、
・  前記評価対象の関数は、前記ベース（ＤＢ）の前記簡略化データ
【数３７】
0005676064.tif 000069
と前記個人（Ｉ）の前記簡略化データ（ｓ）との間の前記類似率を計算するものであり、その後に、前記個人の前記簡略化データ（ｓ）と最も多くの類似点を有する前記ベースの前記ｐ個の簡略化データの探索ステップが続き、前記回路の評価は、前記個人の前記簡略化データ（ｓ）と最も多くの類似点を有する前記簡略化データ
【数３８】
0005676064.tif 000070
のインデックス（ｉ０，．．．，ｉｐ−１）を見つけることを可能にする、
ことと、
−  前記データベース（ＤＢ）の前記Ｎ個の基準データ（ｂｉ）をスクランブルし（３２０）、事前に識別された前記簡略化データ
【数３９】
0005676064.tif 000071
に対応するｐ個のスクランブルされたデータ
【数４０】
0005676064.tif 000072
を前記制御サーバに転送することと、
−  前記ｐ個のスクランブルされたデータ
【数４１】
0005676064.tif 000073
から、該ｐ個のスクランブルされたデータ
【数４２】
0005676064.tif 000074
のそれぞれと、前記個人又は物体の前記データ（ｂ）との間のセキュアなマルチパーティ計算によって、対応する基準データ
【数４３】
0005676064.tif 000075
が、前記個人又は物体の前記データ（ｂ）との所定の閾値（η）を超える類似率を有する、１つ又は複数のスクランブルされたデータ
【数４４】
0005676064.tif 000076
の単数又は複数のインデックス（ｉＩＤ）を求めること（３００）と
を実行するように構成された処理手段を備え、
前記制御サーバ（ＳＣ）は、前記データベース（ＤＢ）に記憶された前記基準データ（ｂ０．．．ｂＮ−１）に関する情報を得ることはなく、前記管理サーバ（ＳＧ）は、前記認証される個人（Ｉ）の前記データ（ｂ）に関する情報を得ることはない、ことを特徴とする、個人の認証システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には個人又は物体の認証に関する。この認証は、認証される個人又は物体のデータを同じ種類の個人又は記憶された物体の一組のデータと比較することによって行われる。これらのデータはベースに記憶されている。
【０００２】
本発明は、特に個人のバイオメトリック認証に適用される。個人のバイオメトリック認証において、個人及びデータベースの比較されるデータは、例えば、その人の虹彩、指紋、更には顔の形状に関するバイオメトリック情報である。
【背景技術】
【０００３】
多くの認証技法が既に知られている。一般的に、それらの技法では、個人又は物体のデータの取得を担当することができる個人又は物体の制御サーバと、同じ種類のＮ個のデータを含むベースのサーバとが組み合わせて用いられる。
【０００４】
制御サーバによって取得された個人又は物体のデータはベースの一組のデータと比較され、ベースの少なくとも１つのデータが取得されたデータに対応するか否かが識別され、その個人又は物体がベースに記憶された個人又は物体として識別される。
【０００５】
この分野には、特に個人のバイオメトリック認証の場合には、２つの主な問題がある。
【０００６】
第１の問題は、認証プロセスのセキュリティ及び機密性に関連するものである。実際、バイオメトリックデータベースは個人情報を含み、制御サーバはベースのこの情報にアクセスできてはならない。同様に、データベースの管理サーバは、認証される個人に関する情報、特に認証される個人のバイオメトリックデータを収集してはならない。
【０００７】
この問題に対応するために、セキュアな計算システムが開発されてきた。特に、数人の参加者の間で計算を行うことからなり、参加者が計算の完了時に計算の結果のみを知るように、各参加者が計算される関数の１つ又は複数のエントリを保持する、セキュアマルチパーティ計算（ＳＭＣ）が知られている。
【０００８】
そのようなシステムは、例えば以下に提案されている。
−  Z. Erkin、M. Franz、J. Guajardo、S. Katzenbeisser、I. Lagendijk、T. Toft「Privacy-preserving face recognition」（Privacy Enhancing Technologies, 2009）
−  A. C.-C. Yao「How to generate and exchange secrets (extended abstract)」（FOCS, 1986）
−  A.-R. Sadeghi、T. Schneider、I. Wehrenberg「Efficient privacy-preserving face recognition」（ICISC, 2009）
【０００９】
２番目の文献は、「Ｙａｏプロトコル」として知られているセキュアな計算方法を記載している。この方法は以下で説明される。
【００１０】
３番目の文献は、このＹａｏプロトコルをバイオメトリック認証の状況で利用する方法を開示している。
【００１１】
これらの方法は、相当のセキュリティを比較関数の計算に与える。しかしながら、これらの方法は、時間及び計算能力を最小にするという第２の主な問題には対応していない。
【００１２】
実際、全てのバイオメトリックデータにＮ回適用されるセキュアな計算は、計算時間及び交換されるデータの数について、非常に多くのコストを要する。
【発明の概要】
【発明が解決しようとする課題】
【００１３】
したがって、バイオメトリックデータから個人をセキュアに認証するとともに、既に提案されている解決策よりも高速にかつ計算能力において安価に認証することが求められている。
J. Bringer等による文献「Extended Private Information Retrieval and Its Application in Biometrics Authentications」（Cryptology and Network Security, Springer Berlin Heidelberg, 08.12.2007）には、ＥＰＩＲと呼ばれるプロトコルが記載されており、当該プロトコルをハミング距離の計算に応用することが述べられている。
M. Blanton等による文献「Secure and Efficient Protocols for Iris and Fingerprint Identification」（International association for cryptologic research, vol. 20110917, Pages 1-25, 17.09.2011）には、ガーバル回路と紛失通信を使用して個人のセキュアな認証を生成することが記載されている。
【課題を解決するための手段】
【００１４】
この点で、本発明は、個人又は物体のデータと最も多くの類似点を有するベースのデータを識別する高速かつセキュアなフィルタリングの第１のフェーズと、個人又は物体のデータとの所定の閾値を超える類似率を有する単数又は複数のデータを識別するためのセキュアな計算の第２のステップとを含む、データベースからのデータとの比較による個人又は物体のセキュアな認証プロセスを提案する。
【００１５】
高速かつセキュアなフィルタリングの第１のステップは、元のデータに関連する削減されたサイズのデータに対して演算が行われるので、計算時間を相当に短縮する。セキュアな計算の第２のステップは、選択されたデータのみに対して実行され、したがって、元のデータベースのサイズ（Ｎ）よりも少ない数の計算動作を含む。
【００１６】
本出願の目的は、個人又は物体の認証プロセスである。システムは、認証される個人又は物体のデータを取得するように構成される制御サーバと、Ｎ人の記憶された個人のＮ個のインデックス付き基準データを含むデータベースの管理サーバとを備える。
個人又は物体を認証するために、個人又は物体のデータが、ベースのＮ個のデータのそれぞれと比較されて、認証される個人又は物体のデータがＮ人の記憶された個人のＮ個の基準データのうちの１つに対応するか否かが判断される。
当該プロセスは、
−  制御サーバが認証される個人又は物体のデータを取得するステップと、
−  ベースの基準データ及び認証される個人又は物体のデータが、より小さなサイズの簡略化データに変換されるステップと、
−  データベースのＮ個の簡略化データのそれぞれと、認証される個人又は物体の簡略化データとの間でセキュアに、認証される個人又は物体の簡略化データと最も多くの類似点を有するベースの簡略化データの一組のｐ個のインデックスが求められ、ただしｐはＮ未満であるステップと、
−  管理サーバが、データベースのＮ個の基準データをスクランブルし、事前に識別された簡略化データに対応するｐ個のスクランブルされたデータを制御サーバに転送するステップと、
−  制御サーバが、ｐ個のスクランブルされたデータから、当該ｐ個のスクランブルされたデータのそれぞれと、個人又は物体のデータとの間のセキュアなマルチパーティ計算によって、対応する基準データが個人又は物体のデータとの所定の閾値を超える類似率を有する、１つ又は複数のスクランブルされたデータの単数又は複数のインデックスを求めるステップと
を含む。
【００１７】
オプションであるが有利には、本発明によるプロセスは、以下の特徴のうちの少なくとも１つを有する。
−  管理サーバから制御サーバへのｐ個のスクランブルされたデータの転送は、紛失通信技法を用いる。
−  このプロセスにおいて、制御サーバが、対応する基準データが個人又は物体のデータとの所定の閾値を超える類似率を有する、スクランブルされたデータの単数又は複数のインデックスを求めた後、
制御サーバは、インデックスを管理サーバに通信し、
管理サーバは、単数又は複数のインデックスから、当該単数又は複数のインデックスに対応するベースの単数又は複数の基準データを求め、個人又は物体を、単数又は複数のインデックスに対応する基準データを有する、ベースに記憶された個人又は物体として認証する。
−  管理サーバは、ベースのＮ個のデータをスクランブルするために、選択された簡略化データに対応するｐ個の基準データのそれぞれについて、対応するデータのバイナリ表現におけるビットの可能な位置ごとに、ランダム置換が当該位置のビットに適用されるＮ個のスクランブルされたデータを含む、対応するスクランブルされたデータベースを生成する。
−  認証は個人に関するものであり、ベースの基準データ及び認証される個人のデータはバイオメトリックデータである。
−  バイオメトリックデータは、虹彩画像のバイナリ符号である。
−  各データは、一組のインデックス付きビットを含み、
データから簡略化データへの変換ステップにおいて、当該データのビットのインデックス番号を含むインデックス集合が定義され、
データは、インデックス集合の番号によってインデックス付けされたビットのみを保持することによって、簡略化データに変換され、
インデックス番号は、最も適切なビットに関係するように選択される。
−  個人又は物体の簡略化データと最も多くの類似点を有するベースの簡略化データは、ベースの簡略化データと個人の簡略化データとの間のハミング距離の計算によって求められる。
−  認証される個人の簡略化データと最も多くの類似点を有するベースのＮ個の簡略化データを求めるステップは、セキュアなマルチパーティ計算によって実行される。
−  ベースのスクランブルされたデータと個人のデータとの間のセキュアなマルチパーティ計算のステップにおいて、
各スクランブルされたデータに対応するベースの各データと個人のデータとの間の類似率が計算され、
得られた類似率は、所定の閾値と比較され、当該閾値を超える類似率を有するベースの単数又は複数のデータの単数又は複数のインデックスが選択される。
−  セキュアなマルチパーティ計算の各ステップは、以下の部分ステップ、すなわち、
・  管理サーバが、評価対象の関数の計算のための少なくとも１つのガーブル回路を生成する部分ステップであって、各ガーブル回路は、入力として評価対象の関数の入力データのビットの一組の暗号鍵を有し、出力として評価対象の関数の結果のビットに対応する暗号鍵を有し、要素論理演算の形式に分解された関数の計算ステップと、各要素論理演算の可能な入力及び出力のそれぞれの一組の符号化鍵と、を含む部分ステップと、
・  管理サーバが符号化鍵をランダムに生成する部分ステップと、
・  管理サーバが、各ガーブル回路について、評価対象の関数の入力ビットの値に対応する符号化鍵と、各ガーブル回路の出力又は各ガーブル回路の論理演算の１つ若しくは複数の出力の復号表とを、紛失通信技法を用いて制御サーバに通信する部分ステップと、
・  制御サーバが、得られた鍵から、当該得られた鍵を入力として用いて各ガーブル回路を評価する部分ステップと
を含む。
−  スクランブルされたデータに対応するデータと、個人のデータとの間の類似率を計算して比較するように、セキュアなマルチパーティ計算が行われ、
管理サーバは、選択されたベースの各データについて、対応するガーブル回路を生成し、
・  各ガーブル回路の入力は、対応するスクランブルされたデータの暗号鍵及び個人のデータの暗号鍵であり、
・  各ガーブル回路の評価対象の関数は、対応するベースのデータと個人のデータとの間の類似率を計算し、当該類似率を所定の閾値と比較するものであり、
・  各回路の出力は、類似率を所定の閾値と比較した結果であり、
管理サーバは、各ガーブル回路について、スクランブルされたデータのビットの可能な値に対応するスクランブルされた符号化鍵と、個人のデータのビットの可能な値に対応する符号化鍵とを生成して制御サーバに転送し、またスクランブルされたデータのビットの値を制御サーバに転送し、スクランブルされたデータのビットの値及び対応する符号化鍵の転送は、紛失通信方法を用いる。
−  各ガーブル回路の評価対象の関数は、スクランブルされたデータに対応する各データと個人のデータとの間の正規化されたハミング距離の計算を含む。
−  スクランブルされたデータの符号化鍵の生成は、ベースの対応するデータのビットごとにランダムに生成される符号化鍵に対して、スクランブルされたデータを得るためにデータのビットに適用されたものと同じ置換に従った再インデックス付けを適用することによって実行される。
−  認証される個人の簡略化データと最も多くの類似点を有するベースのｐ個の簡略化データを選択するために、管理サーバが、ガーブル計算回路を生成するセキュアなマルチパーティ計算の方法が用いられ、
・  ガーブル回路は、入力として、ベースの簡略化データのビット及び個人の簡略化データのビットの一組の暗号鍵を有し、
・評価対象の関数は、ベースの簡略化データと個人の簡略化データとの間の類似率を計算するものであり、その後に、個人の簡略化データと最も多くの類似点を有するベースのｐ個の簡略化データの探索ステップが続き、回路の評価は、個人の簡略化データと最も多くの類似点を有する簡略化データのインデックスを見つけることを可能にする。
−  このプロセスは、ベースのデータが管理サーバによって再インデックス付けされる予備ステップを含む。
【００１８】
また、本発明は、認証される個人の少なくとも１つの制御サーバと、記憶された個人のＮ個の基準データのベースの少なくとも１つの管理サーバとを備える、個人の認証システムに関する。
制御サーバは、個人のデータの取得を進めるように構成され、
制御サーバ及び管理サーバは、
−  ベースの一組のＮ個の基準データの中から、認証される個人のデータと最も多くの類似点を有するｐ個のデータのセキュアなフィルタリングを行い、
−  セキュアな計算を介して、所定の閾値を超える、認証される個人のデータと類似点を有する単数又は複数のデータを識別する、
ように構成された処理手段を備え、
制御サーバは、データベースに記憶された基準データに関する情報を得ることはなく、管理サーバは、認証される個人のデータに関する情報を得ることはない。
【００１９】
本発明の他の特徴、目的、及び利点は、非限定的な例として与えられる、添付図に関する以下の詳細な説明から明らかになる。
【図面の簡単な説明】
【００２０】
【図１】本発明によるプロセスを実行するように構成されたシステムを概略的に示す図である。
【図２】本発明の一実施形態の主要なステップを示す図である。
【図３】ａは、評価対象の論理「ＡＮＤ」関数の例に関して、本発明によるプロセスにおいて用いられるタイプのガーブル回路を示す図である。ｂからｅは、ガーブル回路の真理値表が論理「ＡＮＤ」関数の真理値表の例に関して暗号化される方法を示す図である。
【図４ａ】高速フィルタリングステップにおいて用いられる比較関数の一例を示す図である。
【図４ｂ】高速フィルタリングステップにおいて用いられる比較関数の一例を示す図である。
【図４ｃ】高速フィルタリングステップにおいて用いられる比較関数の一例を示す図である。
【図４ｄ】高速フィルタリングステップにおいて用いられる比較関数の一例を示す図である。
【図５】高速フィルタリングステップの一実施形態を示す図である。
【図６】事前にフィルタリングされたデータの比較ステップ及び選択ステップの実行を示す図である。
【発明を実施するための形態】
【００２１】
図１を参照すると、個人Ｉ又は物体の認証の一実施形態が概略的に示されている。この認証は、例えばセキュアなサイトへのアクセス制御とすることができる。個人のバイオメトリック認証の非限定的な例が以下に述べられる。
【００２２】
データベースＤＢは、例えば、サイトに入ることを認可されているか又は逆にその存在がこのサイト上で禁止されているような、記憶された個人の一組のＮ個のインデックス付きバイオメトリックデータｂｉを含む。ただし、ｉは０〜Ｎ−１である。
【００２３】
このデータベースＤＢは、適切なコンピュータプログラムによって実行される計算手段を装備した管理サーバＳＧにリンクされている。
【００２４】
個人Ｉは制御サーバＳＣを用いて認証される。この制御サーバも、適切なコンピュータプログラムによって実行される計算手段を装備するとともに、個人に特有のデータ、特にバイオメトリックデータｂの取得及び処理のための手段を備えている。
【００２５】
周知のように、データｂは、個人の顔、若しくは指紋、更には虹彩等のバイオメトリック特性のディジタル化されて符号化された画像、又はこれらのデータのうちの幾つかを組み合わせたものに由来することができる。非限定的な例として、個人Ｉの虹彩のディジタル取得の場合が以下に述べられる。
【００２６】
また、データｂを個人の身分証明書にディジタル形式で記憶することもできる。
【００２７】
個人のデータｂ及びベースのデータｂ０〜ｂＮ−１は、比較可能であるように同じ種類でなければならない。特に、それらのデータが含む情報は、同じバイオメトリック特性、本例では虹彩に関するものでなければならない。
【００２８】
この場合、データベースＤＢは、虹彩の各データｂｉについて、対応するマスク符号ｍｉも含むことができる。制御サーバは、虹彩の画像ｂに対応するマスク符号ｍを取得することができるか、又はマスク符号ｍを得ることを考慮してデータｂを処理することができる。これらのマスク符号は、虹彩の可視ゾーン、したがって利用可能なゾーンを示す。これらのゾーンは、通常は瞼によってマスクされないゾーンである。
【００２９】
マスク符号ｍ及びｍｉは、図１、図５、図６では括弧内に示されている。なぜならば、それらのマスク符号はオプションであり、通常は認証プロセスが虹彩データに基づいて行われる場合にのみ用いられるからである。
【００３０】
同様に、制御サーバは、個人Ｉから取得された虹彩の画像から、虹彩の可視部分に対応するマスク符号ｍを生成する。
【００３１】
これらのタイプのデータは、一般に多くの情報を含み、通常は２５６オクテット、すなわち２０４８ビットのフォーマットで符号化される。以下、データｂ及びbｉのビット数はｎと示される。
【００３２】
次に、認証プロセスの一実施形態について、図２を参照して説明する。
【００３３】
各認証プロセスの前に、管理サーバＳＧは、制御サーバＳＣが認証の履歴及び認証と当該認証に用いられたバイオメトリックデータとの対応関係に関する情報を記憶することができないように、ベースからの一組のデータｂｉをランダムに再インデックス付けする（ステップ１０）。
【００３４】
ステップ１００において、制御サーバＳＣは、個人のデータｂの取得を進める。次に、制御サーバＳＣは、ベースのＮ個のバイオメトリックデータの第１の高速フィルタリングステップ２００を開始し、ｂと最も多くの類似点を有するｐ個のデータを識別する。ｐはＮよりも小さく、サーバＳＣとＳＧによって前もって固定されている。
【００３５】
・高速フィルタリング
このステップの計算時間を最小にするために、制御サーバＳＣとデータサーバＳＧは、ステップ２１０において、通常はデータｂ及びｂ０〜ｂＮ−１のサイズを削減することによって、これらのデータを簡略化する。
【００３６】
例として、データが２０４８ビットで符号化された虹彩画像である場合、サーバＳＣとＳＧは、データのサイズを１２８ビットに削減することができる。これを達成するために、サーバＳＣとＳＧは、集合｛１，．．．，ｎ｝の部分集合であるインデックス集合Ａの要素によってインデックス付けされたデータｂ及びｂｉのビットがデータの上位にくるように、Ａについて合意することができる。Ａの基数はｔで示され、ｔはｎより小さい。上記の例の場合、ｎは２０４８であり、ｔは１２８である。
【００３７】
サーバＳＧとＳＣは、Ａによってインデックス付けされたｂ及びｂｉのビットを含む簡略化データｓ及びｓｉを生成し、データｓ及びｓｉはｎの代わりにｔビットでまず符号化される。ただし、ｉは０〜Ｎ−１である。
【００３８】
これらの簡略化データを用いると、サーバＳＣとＳＧは、ｓと各ｓｉとの間で、ベースＤＢにおいてｓに最も近いｐ個の簡略化データｓｉを識別するための１：１のＮ個の比較演算を実行することができる。ただし、ｉは０〜Ｎ−１である。バイオメトリックデータの比較の数学関数は、当業者によって知られている。
【００３９】
データが虹彩画像である場合、例えば、ｓと各ｓｉとの間のハミング距離Ｄｉを計算することが可能である。ハミング距離は、２つの比較されるデータ間のインコヒーレントなビットの数である。同様のフィルタリング技法は、F. Hao、J. Daugman、P. Zielinski「A fast search algorithm for a large fuzzy database」（IEEE Transactions on Information Forensics and Security, 3(2), 2008）という文献に記載されている。
【００４０】
この場合、ｓに最も近いｐ個のデータは、ｓからの最小のハミング距離を有するｐ個のデータである。
【００４１】
フィルタリングステップはセキュアに行われる。すなわち、サーバＳＧとＳＣが相手方のデータに関する情報（各個人のバイオメトリックデータｂ又はベースのバイオメトリックデータｂｉ）を得ることがないように行われる。
【００４２】
そのようにするために、以下の図５に関するフィルタリングステップのセキュア化の説明において説明する、Ｙａｏプロトコルを利用したセキュアなマルチパーティ計算の方法を用いることができる。
【００４３】
最初に、Ｙａｏプロトコルにおいて用いられる２つの前提条件である紛失通信及びガーブル回路を説明する必要がある。
【００４４】
・紛失通信
Ｙａｏプロトコルは、２つのパーティＰ１とＰ２の間の計算動作である紛失通信を用いる。
【００４５】
このタイプの動作では、Ｐ１はＮ個のインデックス付き要素Ｘｉのリストを有している。Ｐ２はこのリストの要素数Ｎを知っており、０〜Ｎ−１の間のインデックスｉを選択する。紛失通信を介して、Ｐ２は、Ｐ１の第ｉ要素、すなわちｉによってインデックス付けされたＰ１の要素を回復する。
【００４６】
Ｐ１は、Ｐ２によって回復される要素のインデックスに関する情報を知ることはない。
【００４７】
Ｐ２自体は、Ｐ１が保持するリストの他の要素に関する情報を取り出すことはない。
【００４８】
・ガーブル回路
また、Ｙａｏプロトコルはガーブル回路を用いる。図３はそのようなガーブル回路の一実施形態を示している。
【００４９】
ガーブル回路の図は、図３のａに例として示されているが、手短に言えば、このガーブル回路は、評価対象の関数のベースバイナリ計算回路から得られる暗号化されたバイナリ回路である。この回路は一連の要素論理ゲートに分解される。図３のａに示すバイナリ回路の図は、それぞれバイナリ値０又は１を取ることができる２つの入力ｘ及びｙと、同様にバイナリ値０又は１を取ることができる出力ｚとを備える要素関数「ＡＮＤ」のみを含む。
【００５０】
慣例として、各論理ゲートは、出力と入力との間の論理的関連を設定する真理値表を用いて属性を与えられる。論理関数「ＡＮＤ」の真理値表は、図３のｂに例として示されている。
【００５１】
この関数の評価のセキュア化を確実にするために、各要素論理ゲートの各可能な入力及び各出力は、ガーブル回路の作成者によって、各入力又は出力に特有の２つの可能なブール値に対応する暗号鍵のランダムな対によって暗号化される。例えば図３のｃでは、ｘが取ることができるバイナリ値０及び１は、対応する鍵ｋｘ０及びｋｘ１によって置き換えられ、ｙ及びｚが取る値についても同様である。
【００５２】
これによって、入力及び出力のバイナリ値が暗号鍵によって置き換えられた真理値表が生成される。
【００５３】
次に、各論理ゲートの出力が、対応する入力の値による暗号鍵によって暗号化され、暗号化された真理値表、すなわち図３のｄのガーブル真理値表が得られる。
【００５４】
したがって、例えば関数ＡＮＤの場合、ｚの値０に対応する暗号鍵ｋｚ０は、ｘ及びｙが１に等しくない全ての場合に現われる。しかしながら、この鍵ｋｚ０は、ｘ及びｙが取る値に従って同じ方法で暗号化されない。実際、ｘ及びｙがともに０である場合、鍵ｋｚ０は、鍵ｋｘ０及びｋｙ０によって暗号化される。この暗号化された鍵は、
【数１】
0005676064.tif 000002
と示される。
【００５５】
最後に、入力鍵が表から除去され、各出力について得られた鍵が図３のｅのようにランダムに並べ替えられ、その結果得られる暗号化及びスクランブルされた真理値表が、実際にガーブル回路と呼ばれるものである。
【００５６】
暗号鍵から回路の関数を評価するために、評価対象の関数の結果の暗号鍵と、ビットの対応する値との間の相関表Ｔが、回路の作成者によって生成される。
【００５７】
・Ｙａｏプロトコル
最後に、Ｙａｏプロトコルは、幾つかのパーティが、彼らが有するデータの性質を互いに共有することなく、これらのデータから計算を行うセキュアな計算の方法である。
【００５８】
これを達成するために、これらのパーティのうちの１つは、上記で説明したように、評価対象の関数のガーブル計算回路と、この回路の論理ゲートの入力ビット及び出力ビットのそれぞれの暗号鍵の対（バイナリ値０について１つ及びバイナリ値１について１つ）とを作成する。ガーブル回路の作成者は、関数の結果の暗号鍵と結果それ自体とから相関表Ｔも生成する。
【００５９】
その後、ガーブル回路の作成者は、ガーブル回路、相関表、及び作成者に属する入力データのビットの暗号鍵を、他のパーティ（又は他の複数のパーティ）に送信する。
【００６０】
このように、回路の作成者の０（１）に等しい各入力ビットｘについて、作成者は暗号鍵ｋｘ０（ｋｘ１）しか送信しない。これらの鍵はランダムであるので、ガーブル回路の各ユーザは、作成者が保持するデータの対応するビットに関する情報を得ることはできない。
【００６１】
また、ガーブル回路の各ユーザは、作成者からの紛失通信によって、彼らが有する関数の入力データのビットに対応する鍵を回復する。
【００６２】
したがって、作成者は、ユーザの各入力ビットｙについてｋｙ０及びｋｙ１からなる２つの要素を有するリストを準備し、紛失通信用にユーザによって選択されるインデックスは、ビットｙの値である。
【００６３】
紛失通信方法に依拠することによって、作成者は回路のユーザのデータのビットの値に関する情報を得ることがなくなる。
【００６４】
最後に、ガーブル回路のユーザは、自身が得た鍵によって関数を評価することができ、自身が関数の出力において得た結果を相関表によって変換することができる。オプションとして、ユーザは結果を回路の作成者に送信することもできる。
【００６５】
再び高速フィルタリングステップ２００を参照すると、ベースの簡略化されたバイオメトリックデータｓｉのフィルタリングを実行するために、制御サーバＳＣと管理サーバＳＧは、フィルタリング関数のセキュアな計算にＹａｏプロトコルを用いる。フィルタリング関数を構成する要素は図４に示されている。このステップの実行は、図５に図式的に表されている。
【００６６】
ステップ２２０において、管理サーバＳＧは、関数ｆを表すガーブル回路Ｃ（図５ではＣ（ｆ）で示されている）を作成する。この回路は、２つのデータ間のハミング距離を計算すること、及び複数のハミング距離を比較してｐ個の最小の距離を識別することの双方を実行する。
【００６７】
ハミング距離を計算する関数は、当業者によって知られている。この関数は
【数２】
0005676064.tif 000003
で示される。
【００６８】
このように計算されるハミング距離は、図４ｄに示す論理演算によって互いに比較される。これらの演算は、図４ａ、図４ｂ、及び図４ｃに示す部分関数を含む。
【００６９】
図４ａにおいて、関数Ｘ’は、３つの入力ビットｘｉ、ｙｉ、及びｃを備える関数であり、ｃが０である場合には出力（ｘｉ，ｙｉ）を生成し、ｃが１である場合には出力（ｙｉ，ｘｉ）を生成する。この関数Ｘ’は、図４ｂにおいては、その入力が複数の入力ビットｘｉ，ｙｉを含むデータである関数ＭＵＸ’に一般化されている。
【００７０】
図４ｃは、「２−１」と呼ばれる比較関数を示している。この比較関数は、入力として、簡略化データs０及びｓ１と個人のデータｓとの比較のための、この場合Ｄ０及びＤ１で示される２つのハミング距離を有する。この比較関数は、出力において、２つの比較されたものの間の最小ハミング距離を与える。
【００７１】
これを行うために、この比較関数は、その出力が連続した関数ＭＵＸ’の入力ｃである（Ｄ０がＤ１よりも大きい場合には１であり、そうでない場合には０である）比較関数「＞」を用いる。
【００７２】
最後に、図４ｄを参照すると、ハミング距離Ｄｉの一般的な比較関数が、全ての距離がケース「２−１」の連続したレベルにおいて２つ一組で互いに比較され、第１のレベルの最小距離が次のレベルの比較の入力である従来のソート方法を実施している。
【００７３】
この論理図の最後において、比較されたＮ個の距離から最小距離Ｄｍｉｎが得られる。この比較ステップはｐ回反復され、各回は先行ステップにおいて識別された最小距離を除外し、最終的にｐ個の最小距離Ｄｉが得られる。
【００７４】
ガーブル回路Ｃが生成されると、管理サーバＳＧは、関数ｆの各入力から暗号鍵をそれぞれ作成するとともに、関数ｆの各要素論理演算の出力の暗号鍵をそれぞれ作成する。或る論理演算の出力は、後続の論理演算の入力である。管理サーバは、特に各簡略化データｓ及びｓｉのビットごとに暗号鍵の対を生成する。
【００７５】
最後に、管理サーバＳＧは相関表Ｔを生成する。ただし、従来のＹａｏプロトコルとは逆に、この相関表は、評価対象の関数の出力の鍵に関係せず、各演算「２−１」のハミング距離の比較ステップ「＞」からの出力に関係している。
【００７６】
管理サーバＳＧは、ガーブル回路Ｃ、相関表Ｔ、及びベースＤＢの簡略化バイオメトリックデータｓｉのビットの暗号鍵を制御サーバＳＣに送信する。これらの暗号鍵は、各データｓｉのビットｕについて、ビットｕの値に応じてｋ０（ｓｕｉ）又はｋ１（ｓｕｉ）で示される。この一組の暗号鍵は、図５では、より単純にｋ（ｓ０），．．．ｋ（ｓＮ−１）で示されている。
【００７７】
また、制御サーバＳＣは、紛失通信によって、個人ｓの簡略化バイオメトリックデータのビットの暗号鍵ｋ（ｓ）を取り出す。
【００７８】
ステップ２３０において、制御サーバＳＣは、ガーブル回路Ｃ及び鍵ｋによって、ベースの簡略化データｓｉと個人の簡略化データｓとの間で比較関数を評価することによって、個人のデータｓと最も多くの類似点を有するｐ個のデータｓｉを識別することができる。
【００７９】
制御サーバＳＣは、比較ステップ「＞」の出力の鍵の相関表Ｔしか有していない。そのため、制御サーバＳＣが得る結果は、適切な場合には、データに関する情報を制御サーバＳＣに提供する種々のハミング距離の値ではなく、選択されたｐ個のデータｓｉ０．．．ｓｉｐ−１のインデックスである。
【００８０】
このフィルタリングステップが完了すると、サーバＳＣは、個人のデータｓとの最小ハミング距離を有するｐ個の簡略化データ｛ｓｉ０，．．．，ｓｉｐ−１｝のインデックスのリスト｛ｉ０，．．．，ｉｐ−１｝のみを知る。そのため、制御サーバＳＣは、選択された簡略化データ｛ｓｉ０，．．．，ｓｉｐ−１｝に関する情報を知ることはなく、ましてや、対応するベースのデータ｛ｂｉ０，．．．，ｂｉｐ−１｝に関する情報を知ることはない。
【００８１】
したがって、管理サーバＳＧは、個人の簡略バイオメトリックデータｓに関する情報を得ることはなく、ましてや、元のデータｂに関する情報を得ることはない。
【００８２】
・比較及び選択
比較及び選択のステップ３００は、高速フィルタリングステップ２００において識別された簡略化データ
【数３】
0005676064.tif 000004
に対応するデータ
【数４】
0005676064.tif 000005
に対して実行される。ただし、ｊは０〜ｐ−１である。その目的は、個人のバイオメトリックデータに最も近いｐ個の簡略化データから、個人のデータとの類似点が所定の閾値ηを超える１つ又は複数のデータが存在するか否かを判断することである。
【００８３】
当業者によって知られているように、この閾値は、誤検出（偽陽性）及び検出漏れ（偽陰性）の最適な比率を有するバイオメトリックデータの対応関係を設定するように選択される。
【００８４】
Ｙａｏプロトコルと同様に、管理サーバＳＧは、ステップ３１０において、対応するスクランブルされたデータのみを用いて、ｐ個のガーブル回路Ｃ０．．．Ｃｐ−１を作成する。各ガーブル回路は、事前に選択されたバイオメトリックデータ
【数５】
0005676064.tif 000006
（ｊは０〜ｐ−１）と、その対応するマスク
【数６】
0005676064.tif 000007
とを用いて、比較関数ｆ’を評価するのに用いられる。
【００８５】
比較及び選択のステップ３００において利用される比較関数ｆ’は、フィルタリング２００に利用される関数ｆとは別個のものである。
【００８６】
バイオメトリックデータが虹彩画像である場合、比較関数ｆ’は正規化されたハミング距離とすることができる。正規化されたハミング距離とは、２０４８ビット符号で計算され、虹彩画像に関連付けられたマスク、すなわち通常は瞼によってマスクされて比較には関係しない虹彩のゾーンを示す符号を考慮に入れたハミング距離である。
【００８７】
正規化されたハミング距離に関するより多くの情報を得るためには、J. Daugman「How Iris Recognition Works」（IEEE transactions on circuits and systems for video technology, Vol. 14, No. 1, JANUARY 2004）という文献に記載されているＤａｕｇｍａｎ法を参照することができる。
【００８８】
Ｘ及びＹが２０４８ビットで符号化された２つの虹彩画像を示し、ｍ（Ｘ）及びｍ（Ｙ）がそれらの虹彩画像に関連付けられたマスクを示す場合、正規化されたハミング距離は、
【数７】
0005676064.tif 000008
となる。
【００８９】
したがって、このステップの目的は、高速フィルタリングステップにおいて事前に選択された全てのデータ
【数８】
0005676064.tif 000009
について、
【数９】
0005676064.tif 000010
を計算し、
【数１０】
0005676064.tif 000011
となるデータを保持することである。ここで、εはハミング距離の比較のための所定の閾値である。もちろん、比較結果が超えなければならない類似閾値ηは、ハミング距離の計算による比較の場合の閾値εと反比例する。なぜならば、後者の閾値は、データ間の類似点ではなく相違点を数え上げるからである。
【００９０】
計算を最適化するために、回路Ｃｊは、好ましくは
【数１１】
0005676064.tif 000012
ではなく、比較
【数１２】
0005676064.tif 000013
を行うように構築される。ただし、ｊは０〜ｐ−１である。
【００９１】
管理サーバＳＧは、各回路Ｃｊについて、各論理ゲートの入力及び出力の暗号鍵ｋ、並びに関数の出力鍵の相関表Ｔを生成する。特に、各論理ゲートの入力及び出力の暗号鍵ｋは、評価対象の関数の各入力ビット、すなわちデータｂ及びベースのデータｂｉの各入力ビットの暗号鍵の対を含む。
【００９２】
管理サーバＳＧは、ガーブル回路Ｃｊと、これらの回路のそれぞれの相関表Ｔｊとを制御サーバＳＣに送信する。
【００９３】
制御サーバＳＣは、紛失通信によって、各ガーブル回路について、個人Ｉのバイオメトリックデータｂのビットの暗号鍵を取り出す。
【００９４】
最後に、制御サーバＳＣは、選択されたベースのデータ
【数１３】
0005676064.tif 000014
の値と、対応する鍵とを、これらのデータに関する情報を知ることなくそれらの値を個人のデータｂと比較することができるように取り出さなければならない。
【００９５】
これを行うために、管理サーバＳＧは、ステップ３２０において、一組のデータｂｉをまずスクランブルし、スクランブルされたデータｂ’ｉを得る。
【００９６】
より正確には、管理サーバＳＧは、選択された簡略化データ
【数１４】
0005676064.tif 000015
に対応するｐ個の基準データ
【数１５】
0005676064.tif 000016
のそれぞれについて、またこのデータのバイナリ表現におけるビットの各可能な位置ｕについて、｛０，１｝のランダム置換
【数１６】
0005676064.tif 000017
を生成し、このランダム置換
【数１７】
0005676064.tif 000018
をベースのＮ個のデータｂｉのそれぞれの位置ｕのビットに適用して、ベースの初期データ（ｂｉ）に対応するスクランブルされたデータのｐ個のベースを作成する。これらのベースは、
【数１８】
0005676064.tif 000019
で示すことができる。ここで、任意のｕ：１〜ｎ及び任意のｋ：０〜Ｎ−１について、
【数１９】
0005676064.tif 000020
となる。
【００９７】
｛０，１｝置換は、データｂｉのビットについて、ビット（１，０）のバイナリ値をそれらの逆の（０，１）に変換するか又はビットの値を維持するかの２つの結果のみを有することができる。
【００９８】
同様に、管理サーバは、マスクｍｉをスクランブルして、スクランブルされたマスクｍ’ｉを作成することができる。
【００９９】
制御サーバＳＣは、紛失通信を通じて、スクランブルされたデータ
【数２０】
0005676064.tif 000021
すなわち、インデックスｉｊのそれぞれの置換によってスクランブルされたインデックスｉｊのデータを取り出す。ただし、ｊは０〜ｐ−１である。選択されたデータ
【数２１】
0005676064.tif 000022
に対応するスクランブルされたデータは、
【数２２】
0005676064.tif 000023
で示される。他のスクランブル方法も実施可能である。
【０１００】
制御サーバは、選択されたデータに関する情報を得ることはなく、管理サーバＳＧは、これらのデータのインデックスに関する情報を得ることはない。
【０１０１】
次に、管理サーバは、制御サーバがスクランブルされたデータ
【数２３】
0005676064.tif 000024
を用いてガーブル回路を評価することができるようにするために、対応する暗号鍵をスクランブルする。
【０１０２】
管理サーバＳＧによってベースのデータｂｉのビットｕについて生成された暗号鍵は、ビットｕのバイナリ値の関数として、それぞれｋ０（ｂｕｉ）又はｋ１（ｂｕｉ）で表される。
【０１０３】
スクランブルされたデータ
【数２４】
0005676064.tif 000025
のビットについて、対応するスクランブルされた鍵は、ビットｕのバイナリ値０又は１の関数として、
【数２５】
0005676064.tif 000026
及び
【数２６】
0005676064.tif 000027
となる。これらの暗号鍵を用いると、
【数２７】
0005676064.tif 000028
という関係が存在するので、制御サーバＳＣは、スクランブルされた関数から計算を実行することができる。
【０１０４】
最後に、管理サーバは、紛失通信によって、スクランブルされたバイオメトリックデータの各ビットのそれぞれについての暗号鍵
【数２８】
0005676064.tif 000029
又は
【数２９】
0005676064.tif 000030
（図６では、より簡単にｋ’（ｂ’ｉ０．．．ｂ’ｉｐ−１）で示されている）を、これらのビットの各バイナリ値の関数として取り出す。
【０１０５】
最後に、管理サーバは、得られた暗号鍵からステップ３３０において関数を評価し、スクランブルされたデータ
【数３０】
0005676064.tif 000031
に対応するバイオメトリックデータ
【数３１】
0005676064.tif 000032
が所定の閾値ηを上回るｂに対応するか否かを出力する。
【０１０６】
ガーブル回路Ｃｊに関して行われた一組の評価の発行時に、制御サーバＳＣは、存在する場合には、個人のデータに対応するベースに記憶されたバイオメトリックデータｂｉのインデックスｉを有する。サーバは、ベースの幾つかのデータが個人Ｉのデータに対応する場合には、幾つかのインデックスを有することもできる。
【０１０７】
制御サーバＳＣは、ステップ４００において、得られたインデックスｉＩＤを管理サーバＳＧに通信し、管理サーバＳＧは、バイオメトリックデータｂＩＤと、個人Ｉとして認証されている記憶された対応する個人とを認証する。
【０１０８】
例えば、この認証システムがアクセス制御の行われるゾーンの上流に配置される場合、制御サーバＳＣ又は管理サーバＳＧは、そのゾーンへの個人Ｉのアクセスを認可又は不認可することができる。
【０１０９】
したがって、本発明によるプロセスによって、簡略化されたバイオメトリックデータに対して実行される高速フィルタリングステップに起因して、これまでに提案されたプロセスよりも高速の認証が可能になる。
【０１１０】
それにもかかわらず、本発明によるプロセスは、高速フィルタリングステップの後の選択されたデータをスクランブルするステップに起因して、全く安全なままである。
【要約】
本発明は、個人又は物体の認証プロセスに関する。システムは、制御サーバと、Ｎ人の記憶された個人のＮ個のインデックス付き基準データを含むデータベースの管理サーバとを備える。
個人又は物体を認証するために、当該個人又は物体のデータが、ベースのＮ個のデータのそれぞれと比較される。
このプロセスは、
−  制御サーバが認証される個人又は物体のデータを取得するステップと、
−  ベースの基準データ及び認証される個人又は物体のデータが、より小さなサイズの簡略化データに変換されるステップと、
−  データベースのＮ個の簡略化データのそれぞれと、認証される個人又は物体の簡略化データとの間でセキュアに、認証される個人又は物体の簡略化データと最も多くの類似点を有するベースの簡略化データの一組のｐ個のインデックス、ただしｐはＮ未満と、
−  管理サーバが、データベースのＮ個の基準データをスクランブルし、事前に識別された簡略化データに対応するｐ個のスクランブルされたデータを制御サーバに転送するステップと、
−  制御サーバが、ｐ個のスクランブルされたデータから、当該ｐ個のスクランブルされたデータのそれぞれと、個人又は物体のデータとの間のセキュアなマルチパーティ計算によって、対応する基準データが個人又は物体のデータとの所定の閾値を超える類似率を有する、１つ又は複数のスクランブルされたデータの単数又は複数のインデックスを求めるステップと
を含む。【図１】
0005676064.tif 000077
【図２】
0005676064.tif 000078
【図３】
0005676064.tif 000079
【図４ａ】
0005676064.tif 000080
【図４ｂ】
0005676064.tif 000081
【図４ｃ】
0005676064.tif 000082
【図４ｄ】
0005676064.tif 000083
【図５】
0005676064.tif 000084
【図６】
0005676064.tif 000085