(57)【特許請求の範囲】
【請求項１】
関係暗号化を用いる近接性検証を実行するシステムの作動方法であって、前記システムは複数の認証サーバとユーザ装置とを有し、複数の認証サーバの各々は通信モジュールと関係認証モジュールとメモリとを有し、前記作動方法は、
前記認証サーバの各々において、前記通信モジュールにより、前記ユーザ装置から、セキュリティパラメータに関連するランダム化レベルに処理され且つ関係線形性暗号化方式を用いて暗号化された情報を表す線形性暗号文を受信するステップと、
前記認証サーバの各々において、前記関係認証モジュールにより、線形性関係秘密キーを用いて、前記線形性暗号文と前記メモリに格納された登録線形性暗号文との間の線形性関係を決定するステップと、
前記認証サーバの各々において、前記通信モジュールにより、前記ユーザ装置から、前記ランダム化レベルに処理され且つ関係近接性暗号化方式を用いて暗号化された前記情報を表す近接性暗号文を受信するステップと、
前記認証サーバの各々において、前記関係認証モジュールにより、近接性関係秘密キーを用いて、前記近接性暗号文と登録近接性暗号文との間の近接性関係を決定するステップと、
前記認証サーバの各々において、前記関係認証モジュールにより、前記セキュリティパラメータ、前記線形性関係、及び前記近接性関係に基づき、第１バイオメトリックテンプレートと第２バイオメトリックテンプレートとの間の概算類似性を決定するステップであって、前記第１バイオメトリックテンプレートは前記登録線形性暗号文及び前記登録近接性暗号文のうちの１つ以上により表され、前記第２バイオメトリックテンプレートは前記線形性暗号文及び前記近接性暗号文のうちの１つ以上により表される、ステップと、
前記ユーザ装置により、信頼できるエンティティサーバから、前記ユーザ装置に割り当てられた第１の検証キーを受信するステップと、
前記認証サーバの各々において、前記通信モジュールにより、前記信頼できるエンティティサーバから、前記複数の認証サーバのうちの１つに割り当てられた第２の検証キーを受信するステップと、
前記複数の認証サーバの前記１つにより、前記第１の検証キーと前記第２の検証キーとの組合せが、前記概算類似性を決定するステップの結果にアクセスすることを許す場合に、前記ユーザ装置へ前記概算類似性が存在するか否かを示す認証信号を通信し、前記第１及び第２の検証キーの前記組合せが前記概算類似性を決定するステップの結果にアクセスすることを許さない場合に、前記認証信号が前記概算類似性が存在することを示すか否かに拘わらず、前記ユーザ装置に前記認証信号を通信しないステップと、
を有する方法。
【請求項２】
前記認証サーバの各々において、前記通信モジュールにより、前記ユーザ装置から、第２の線形性暗号文及び第２の近接性暗号文を受信するステップと、
前記認証サーバの各々において、前記メモリに、前記第２の線形性暗号文を前記登録線形性暗号文として格納するステップと、
前記認証サーバの各々において、前記メモリに、前記第２の近接性暗号文を前記登録近接性暗号文として格納するステップと、
前記認証サーバの各々において、前記通信モジュールにより、前記ユーザ装置から、前記線形性関係秘密キー及び前記近接性関係秘密キーを受信するステップと、
を更に有する請求項１に記載の方法。
【請求項３】
前記情報は、複数のデータアイテム又は単一のデータアイテムの複数のセグメントの組合せを有する、請求項１に記載の方法。
【請求項４】
前記情報は、医療及び生物学的情報、技術情報、金融情報のうちの１つに関連する、請求項１に記載の方法。
【請求項５】
前記医療及び生物学的情報は、臨床データ、健康データ、及び遺伝子データのうちの１つを含む、請求項４に記載の方法。
【請求項６】
請求項１乃至５のいずれか一項に記載の方法をコンピュータに実行させるコンピュータプログラム。
【請求項７】
請求項６に記載のコンピュータプログラムを保存する記憶媒体。
【請求項８】
関係暗号化を用いる近接性検証を実行するシステムの作動方法であって、前記システムは認証サーバとユーザ装置とを有し、前記認証サーバは通信モジュールと関係認証モジュールとメモリとを有し、前記作動方法は、
前記通信モジュールにより、前記ユーザ装置から、セキュリティパラメータに関連するランダム化レベルに処理され且つ関係線形性暗号化方式を用いて暗号化された医療及び生物学的データを表す線形性暗号文を受信するステップと、
前記関係認証モジュールにより、線形性関係秘密キーを用いて、前記線形性暗号文と前記メモリに格納された医療及び生物学的情報を表す登録線形性暗号文との間の線形性関係を決定するステップと、
前記通信モジュールにより、前記ユーザ装置から、前記ランダム化レベルに処理され且つ関係近接性暗号化方式を用いて暗号化された前記医療及び生物学的情報を表す近接性暗号文を受信するステップと、
前記関係認証モジュールにより、近接性関係秘密キーを用いて、前記近接性暗号文と医療及び生物学的情報を表す登録近接性暗号文との間の近接性関係を決定するステップと、
前記関係認証モジュールにより、前記セキュリティパラメータ、前記線形性関係、及び前記近接性関係に基づき、第１バイオメトリックテンプレートと第２バイオメトリックテンプレートとの間の概算類似性を決定するステップであって、前記第１バイオメトリックテンプレートは前記登録線形性暗号文及び前記登録近接性暗号文のうちの１つ以上により表され、前記第２バイオメトリックテンプレートは前記線形性暗号文及び前記近接性暗号文のうちの１つ以上により表される、ステップと、
前記ユーザ装置により、信頼できるエンティティサーバから、前記ユーザ装置に割り当てられた第１の検証キーを受信するステップと、
前記認証サーバの各々において、前記通信モジュールにより、前記信頼できるエンティティサーバから、前記認証サーバに割り当てられた第２の検証キーを受信するステップと、
前記認証サーバにより、前記第１の検証キーと前記第２の検証キーとの組合せが、前記概算類似性を決定するステップの結果にアクセスすることを許す場合に、前記ユーザ装置へ前記概算類似性が存在するか否かを示す認証信号を通信し、前記第１及び第２の検証キーの前記組合せが前記概算類似性を決定するステップの結果にアクセスすることを許さない場合に、前記認証信号が前記概算類似性が存在することを示すか否かに拘わらず、前記ユーザ装置に前記認証信号を通信しないステップと、
を有する方法。
【請求項９】
前記医療及び生物学的情報は、臨床データ、健康データ、及び遺伝子データのうちの１つを含む、請求項８に記載の方法。
【請求項１０】
請求項８又は９に記載の方法をコンピュータに実行させるコンピュータプログラム。
【請求項１１】
請求項１０に記載のコンピュータプログラムを保存する記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願の参照］
本願は、米国特許出願第１４/２８７,０５１号、２０１４年５月２５日出願の一部継続出願である米国特許出願第１４/７９７,０２５号、２０１５年７月１０日出願の一部継続出願である。前記の出願の全内容は、参照により本願明細書に組み込まれる。
【０００２】
本願明細書で議論される実施形態は、関係暗号化に関する。
【背景技術】
【０００３】
ユーザ認証の形式は、生体認証を含み得る。生体認証は、通常、ユーザに対して一意であるユーザのバイオメトリック特徴を測定するステップを含む。測定されたバイオメトリック特徴、又はその表現は、次に、ユーザの同一性を認証する基礎として用いられる。バイオメトリック特徴は、ユーザの指紋、虹彩、静脈、ＤＡＮ（deoxyribonucleic  acid）のセクション、等生体認証は、パスワードを記憶している必要がなく、ユーザを認証することが可能であるという利点を有し得る。バイオメトリック特徴は不変であるので、生体認証システムにおいてプライバシが重要である。
【０００４】
本願明細書で請求される主題は、上述のような欠点を解決する実施形態や上述のような環境でのみ機能する実施形態に限定されない。むしろ、この背景技術は、単に、本願明細書に記載される複数の実施形態が実施される技術分野の一例を説明するために提供される。
【発明の概要】
【課題を解決するための手段】
【０００５】
一実施形態の一態様によると、関係暗号化を用いる近接性検証の方法は、セキュリティパラメータに関連するランダム化レベルに処理され且つ関係線形性暗号化方式を用いて暗号化された情報を表す線形性暗号文を受信するステップと、線形性関係秘密キーを用いて、前記線形性暗号文と登録線形性暗号文との間の線形性関係を決定するステップと、前記ランダム化レベルに処理され且つ関係近接性暗号化方式を用いて暗号化された前記情報を表す近接性暗号文を受信するステップと、近接性関係秘密キーを用いて、前記近接性暗号文と登録近接性暗号文との間の近接性関係を決定するステップと、前記セキュリティパラメータ、前記線形性関係、及び前記近接性関係に基づき、前記近接性暗号文と前記登録近接性暗号文との間の概算類似性を決定するステップと、ユーザ装置に割り当てられた第１の検証キーと前記複数の認証サーバのうちの１つに割り当てられた第２の検証キーとの組合せが、前記概算類似性を決定するステップの結果にアクセスすることを許す場合に、１又は複数の認証サーバから前記ユーザ装置へ、前記近接性暗号文と前記登録近接性暗号文との間の前記概算類似性が存在するか否かを示す認証信号を通信し、前記第１及び第２の検証キーの前記組合せが前記概算類似性を決定するステップの結果にアクセスすることを許さない場合に、前記認証信号が、前記近接性暗号文と前記登録近接性暗号文との間に前記概算類似性が存在することを示すか否かに拘わらず、前記ユーザ装置に前記認証信号を通信しないステップと、を有する。
【０００６】
一実施形態の別の態様によると、方法は、医療及び生物学的情報を受信するステップと、平文ベクトルとしてランダム化レベルに前記医療及び生物学的情報を処理するステップであって、前記ランダム化レベルはセキュリティレベルに関連する、ステップと、を有する。方法は、前記平文ベクトルを表す線形性暗号文を生成するために、関係線形性暗号化方式を用いて前記平文ベクトルを暗号化するステップと、前記平文ベクトルを表す近接性暗号文を生成するために、関係近接性暗号化方式を用いて前記平文ベクトルを暗号化するステップと、前記線形性暗号文及び前記近接性暗号文を認証サーバに通信するステップと、を更に有する。方法は、関係線形性キーを用いて発見された線形性暗号文と登録線形性暗号文との間の線形性関係と、医療及び生物学的情報を表し且つ関係近接性キーを用いて検出された近接性暗号文と登録近接性暗号文との間の近接性と、を示すセキュリティレベルの認証信号を前記認証サーバから受信するステップを更に有しても良い。
【０００７】
実施形態の目的及び利点が理解され、少なくとも特に特許請求の範囲で指摘された要素、特徴及び組合せを用いて達成されるだろう。
【０００８】
上述の全体的説明及び以下の詳細な説明の両方は、例示及び説明のためであり、特許請求の範囲を限定しないことが理解される。
【図面の簡単な説明】
【０００９】
例示的な実施形態は、添付の図面を用いて、更なる特異性及び詳細事項と共に記載され説明される。
【図１】例示的な動作環境のブロック図である。
【図２】例示的な生体認証環境のブロック図である。
【図３】生体認証の例示的な方法のフロー図である。
【図４Ａ】関係暗号化の例示的な方法のフロー図である。
【図４Ｂ】関係暗号化の例示的な方法のフロー図である。
【図５】関係暗号化方式の線形性関係を発見する例示的な方法のフロー図である。
【図６】関係暗号化方式の近接性を検出する例示的な方法のフロー図である。
【図７】関係線形性暗号化方式のキー生成の例示的な方法のフロー図である。
【図８】関係線形性暗号化方式を用いる第１の平文ベクトルを暗号化する例示的な方法のフロー図である。
【図９】関係近接性暗号化方式のキー生成の例示的な方法のフロー図である。
【図１０】関係近接性暗号化方式を用いる第１の平文ベクトルを暗号化する例示的な方法のフロー図である。
【図１１】第１の線形性暗号文を復号化する例示的な方法のフロー図である。
【図１２】第１の線形性暗号文を復号化する別の例示的な方法のフロー図である。
【図１３】例示的な動作環境のブロック図である。
【図１４】関係暗号化方式を用いる不均一分散データを暗号化する例示的な方法のフロー図である。
【図１５】本願明細書に記載の少なくとも１つの実施形態に従って全て構成される、不均一分散データを処理する例示的な方法のフロー図である。
【図１６】別の例示的な動作環境のブロック図である。
【図１７】関係暗号化を用いる近接性検証の方法の第１の例を説明する図である。
【図１８】関係暗号化を用いる近接性検証の方法の第２の例を説明する図である。
【図１９】関係暗号化を用いる近接性検証の方法の第３の例を説明する図である。
【図２０】関係暗号化を用いる近接性検証の方法の第４の例を説明する図である。
【図２１】関係暗号化を用いる近接性検証の方法の第５の例を説明する図である。
【図２２】アクセス制限テーブルの一例を示す。
【図２３】関係暗号化を用いる近接性検証の方法の第６の例を説明する図である。
【図２４】更に別の例示的な動作環境のブロック図である。
【図２５】本願明細書に記載の少なくとも１つの実施形態により配置される更なる例示的な動作環境１００のブロック図を示す。
【発明を実施するための形態】
【００１０】
生体認証の課題は、ユ―ザが認証の基礎として用いられるバイオメトリック特徴を変更できないことであり得る。例えば、ユーザは、ユーザの指紋又はユーザの虹彩パターンのようなユーザの１又は複数のユニークな特徴を表すバイオメトリックデータを含むバイオメトリックテンプレートを登録しても良い。バイオメトリックテンプレートが危険に晒される場合、ユーザは、バイオメトリックテンプレートにより表されるユニークな特徴を変更することができない。したがって、一旦、危険に晒されると、別のバイオメトリックテンプレートが登録されても良く、又は、別のバイオメトリック特徴のバイオメトリックテンプレートが登録されても良い。少なくともこの理由から、生体認証システムは、強力なプライバシ保証の利益を享受し得る。現実のバイオメトリックデータでは、バイオメトリックデータは、著しく不均一であり得る。
【００１１】
幾つかの生体認証システムでは、セキュアな生体認証システムを提供するために種々のアプローチが実施されてきた。例えば、幾つかの生体認証システムは、「特徴変換アプローチ」、「生体暗号システムアプローチ」、及び／又は「同形暗号化アプローチ」を実装する。しかしながら、これらのアプローチの各々は、少なくとも部分的には、バイオメトリックテンプレート、クライアント固有キー、公開キー、等のような各々が危険に晒され得る情報の通信を理由として、限られたプライバシ及びセキュリティしか提供しない。
【００１２】
したがって、本願明細書で議論する幾つかの実施形態は、プライバシ保護生体認証に関連する。プライバシ保護生体認証は、関係暗号化に基づいても良い。関係暗号化（又はリレーショナル暗号化）は、リレーショナルキーを用いた暗号化方法である。関係暗号化は、認証側（authenticator）に平文を復元させずに又は本物の暗号文との特定の関係を有する不正暗号文を生成させずに、認証側に暗号文の間の関係を発見させる。例えば、例示的な実施形態は、生体認証の方法を有する。方法は、登録入力を受信するステップを有しても良い。登録入力は、ユーザの第１のバイオメトリックテンプレートを有しても良い。第１のバイオメトリックテンプレートは、ユーザのバイオメトリック特徴のユニークな特徴を表しても良い。方法は、関係暗号化方式に従って、第１の線形性暗号文及び第１の近接性暗号文を生成するステップを有しても良い。方法は、第１の線形性暗号文及び第１の近接性暗号文を認証サーバに通信するステップを有しても良い。方法は、チャレンジ（challenge）入力を受信するステップを有しても良い。チャレンジ入力は、第２のバイオメトリックテンプレートを有しても良い。第２のバイオメトリックテンプレートは、ユーザのバイオメトリック特徴の１又は複数のユニークな特徴を表しても良い。方法は、関係暗号化方式に従って、第２の線形性暗号文及び第２の近接性暗号文を生成するステップを有しても良い。方法は、第２の線形性暗号文及び第２の近接性暗号文を認証サーバに通信するステップを有しても良い。認証サーバは、第１及び第２の線形性暗号文の間の線形性関係を発見し、第１及び第２の近接性暗号文の間の近接性を検出しても良い。方法は、認証サーバから、認証決定を示す信号を受信するステップを有しても良い。認証決定は、線形性関係及び／又は近接性の存在又は不存在に基づいても良い。
【００１３】
幾つかの実施形態では、基礎データは、線形性又は近接性暗号文を生成する前に、先ず処理されても良い。例えば、基礎データは、基礎にある平文の中のランダム化レベルを提供し得る線形抽出器（linear  extractor）を通されても良い。本開示の実施形態を、添付の図面を参照して以下に説明する。
【００１４】
図１は、本願明細書に記載の少なくとも１つの実施形態により配置される例示的な動作環境１００のブロック図を示す。動作環境１００では、関係暗号化が実行されても良い。関係暗号化は、第１のエンティティ１５２が、第２のエンティティ１５０により提供される２以上の暗号文の間の１又は複数の関係を決定できるようにする暗号プリミティブを有しても良い。特に、関係暗号化は、第１のエンティティ１５２に２以上の暗号文の間の線形性関係を発見させ、２以上の暗号文の間の近接性を検出させる。さらに、関係暗号化は、第１のエンティティ１５２に暗号文から平文を復元させ、又は特定の本物の暗号文との特定の関係を有する不正暗号文を構築させる。
【００１５】
関係暗号化は、種々の環境において実装されても良い。例えば、関係暗号化は、個人が彼らの位置を非公開に保ちたいと望む社会環境において実施されても良いが、半ば信頼できるサービスは、位置同士の近接性の検出を可能にし得る。さらに、関係暗号化は、画像比較環境において実施されても良い。近接性は、画像同士の類似性を決定するために、データベースからの画像の間で検出されても良い。画像のプライバシは維持されても良い。ユーザは、データベースにある画像に触れずに、関係暗号化を用いて画像を検索しても良い。さらに、関係暗号化は、私的データ記憶環境において実施されても良い。ユーザは、そのデータを暗号化し、暗号化データをデータベースに通信しても良い。分析（例えば、記憶、クラスタリング、等）は、暗号化データが解読されるリスクを伴わず、暗号化データに対して実行され得る。
【００１６】
例えば、第２のエンティティ１５０は、第１の平文ベクトル１４２Ａ及び第２の平文ベクトル１４２Ｂ（通常、平文ベクトル１４２又は複数の平文ベクトル１４２）を受信しても良い。平文ベクトル１４２は、バイオメトリックテンプレート、位置情報、等のような任意のデータセットを有しても良い。第２のエンティティ１５０は、第１の平文ベクトル１４２Ａの暗号化バージョンを有する第１の暗号文を第１のエンティティ１５２に通信しても良い。後に、第２のエンティティ１５０は、第２の平文ベクトル１４２Ｂの暗号化バージョンを有する第２の暗号文を第１のエンティティ１５２に通信しても良い。第１のエンティティ１５２は、第１の暗号文と第２の暗号文との間に線形性関係があるか否かを発見しても良く、第１の暗号文と第２の暗号文との間の近接性を検出しても良い。幾つかの実施形態では、近接性は、ハミング距離の観点であっても良い。
【００１７】
しかしながら、関係暗号化は、第１のエンティティ１５２が、第１及び第２の暗号文から平文ベクトル１４２を構築することを許さない。さらに、関係暗号化は、第１のエンティティ１５２が、第１の暗号文及び／又は第２の暗号文と特定の線形性関係及び／又は特定の近接性を有する第３の暗号文を構築することを許さない。図１は、２つの平文ベクトル１４２と、したがって２つの暗号文と、を有する実施形態を示す。幾つかの実施形態では、２つより多い平文ベクトル１４２と、したがって２つより多い暗号文とが、動作環境１００に含まれても良い。
【００１８】
関係暗号化は、１又は複数の関係キーを有しても良い。関係キーは、公開及び／又は署名キーと同様であっても良く、第１のエンティティ１５２に提供され又はそれにより生成されても良い。関係キーは、暗号文の間の関係の決定を可能にし得るが、暗号文の復号化又は平文ベクトル１４２の復元を許さない。さらに、関係キーは、特定の暗号文との特定の関係を有する暗号文の構築を許さない。
【００１９】
幾つかの実施形態では、関係暗号化は、アルゴリズムのタプルを有する関係について、関係暗号化方式に従って定められても良い。アルゴリズムは、キー生成アルゴリズム、第１の暗号化アルゴリズム、第１の復号化アルゴリズム、第１の暗号化アルゴリズム、第２の復号化アルゴリズム、及び検証アルゴリズムを有しても良い。関係は、３つのセットの部分集合として定められても良い。さらに、関係及びアルゴリズムは、１又は複数の正確性条件を満たしても良い。例えば、関係は、以下の例示的な正確性条件を満たしても良い。
【００２０】
Ｒ⊆ＸｘＹｘＺ
（ｐｋｘ，ｓｋｘ，ｐｋｙ，ｓｋｙ，ｓｋＲ）←ＫｅｙＧｅｎ（１λ）
ｃｘ←ＥｎｃＸ（ｐｋｘ，ｘ）
ｃｙ←ＥｎｃＹ（ｐｋｙ，ｙ）
ｂ←Ｖｅｒｉｆｙ（ｓｋＲ，ｃｘ，ｃｙ，ｚ）
ｂ≒Ｒ（ｘ，ｙ，ｚ）
正確性条件では、Ｒは関係を表す。演算子⊆は、部分集合演算子を表す。パラメータＸ、Ｙ、Ｚはセットを表す。パラメータｘは、第１の平文ベクトル１４２Ａを表す。パラメータｙは、第２の平文ベクトル１４２Ｂを表す。ＫｅｙＧｅｎは、キー生成アルゴリズムを表す。ＥｎｃＸは、第１の暗号化アルゴリズムを表す。ＥｎｃＹは、第２の暗号化アルゴリズムを表す。Ｖｅｒｉｆｙは、検証アルゴリズムを表す。演算子←は、出力演算子を表す。パラメータｐｋｘは、第１の公開キーを表す。パラメータｐｋｙは、第２の公開キーを表す。パラメータｓｋｘは、第１の秘密キーを表す。パラメータｓｋｙは、第２の秘密キーを表す。パラメータｓｋＲは、関係秘密キーを表す。パラメータｃｘは、第１の暗号文を表す。パラメータｃｙは、第２の暗号文を表す。パラメータｂは、検証アルゴリズムによる出力を表す。パラメータλは、セキュリティパラメータを表す。パラメータｚは、検証エンティティにより選択され得る特定の値を表す。演算子≒は、合致（congruency）演算子を表す。正確性条件では、検証アルゴリズムからの出力は、圧倒的な確率を有する関係と合致する。
【００２１】
関係暗号化方式は、関係キーが、特定の暗号文との特定の関係を有する暗号文の構築を許さない、及び特定の暗号文からの平文ベクトル１４２Ａの復元を許さない、という意味でセキュアであり得る。例えば、関係暗号化方式は、以下の式が保たれる場合にセキュアであり得る。
１）ＫｅｙＧｅｎ（１λ）を行うアルゴリズムをＫｘ（１λ）として、出力（ｐｋｘ，ｓｋｘ，ｐｋｙ，ｓｋｙ，ｓｋＲ）及び出力（ｐｋｘ，ｓｋｘ）を取り入れる。その結果、（Ｋｘ，ＥｎｃＸ，ＤｅｃＸ）はＩＮＤ−ＣＰＡセキュアである。
２）ＫｅｙＧｅｎ（１λ）を行うアルゴリズムをＫｙ（１λ）として、出力（ｐｋｘ，ｓｋｘ，ｐｋｙ，ｓｋｙ，ｓｋＲ）及び出力（ｐｋｘ，ｓｋｘ）を取り入れる。その結果、（Ｋｙ，ＥｎｃＹ，ＤｅｃＹ）はＩＮＤ−ＣＰＡセキュアである。
３）ＫｅｙＧｅｎ（１λ）を行うアルゴリズムをＫＲ（１λ）として、出力（ｐｋｘ，ｓｋｘ，ｐｋｙ，ｓｋｙ，ｓｋＲ）及び出力（ｐｋｘ，ｓｋｘ，ｓｋＲ）を取り入れる。その結果、ＥｎｃＸ（ｐｋｘ，・）及びＥｎｃＹ（ｐｋｙ，・）は、ｓｋＲが分かる場合に、一方向性関数である。
【００２２】
上述の式では、ｐｋｘ，ｓｋｘ，ｐｋｙ，ｓｋｙ，ｓｋＲ，ＫｅｙＧｅｎ，ＥｎｃＸ（）及びＥｎｃＹ（）は、上述の通りである。ＤｅｃＸは、第１の復号化アルゴリズムを表す。ＤｅｃＹは、第２の復号化アルゴリズムを表す。Ｋｘ（）、Ｋｙ（）、及びＫＲ（）は、上記の式において説明した通りである。記号「・」は任意の値を示す。用語「ＩＮＤ−ＣＰＡ」は、indistinguishability  under  chosen−plaintext  attackの略である。幾つかの他の実施形態では、（Ｋｙ，ＥｎｃＹ，ＤｅｃＹ）及び／又は（Ｋｘ，ＥｎｃＸ，ＤｅｃＸ）は、ＩＮＤ−ＣＣＡ（indistinguishability  under  chosen  ciphertext  attack）（例えば、ＩＮＤ−ＣＣＡ１又はＩＮＤ−ＣＣＡ２）又は任意の他の適切なセキュリティメトリックのような別の計算セキュリティメトリックに従ってセキュアであっても良い。
【００２３】
さらに、幾つかの実施形態では、関係暗号化方式は、関係線形性暗号化方式を有しても良い。関係線形性暗号化方式は、以下の例示的な線形性関係式に従って関係を定めても良い。
【００２４】
Ｒ＝｛（ｘ，ｙ，ｚ）｜ｘ＋ｙ＝ｚ∧ｘ，ｙ，ｚ∈Ｆｎｐ｝
線形性関係式では、Ｒ、ｘ、ｙ、及びｚは、上述の通りである。演算子∈は、メンバーシップ演算子を表す。演算子｜は、「〜の条件を満たす」（ｓｕｃｈ  ｔｈａｔ）演算子を表す。演算子∧は、論理結合演算子を表す。パラメータＦはフィールドを表す。添え字ｎは、通常、フィールドの次元を表す。フィールドの次元は、本願明細書の別の場所で議論するようなキーのうちの１又は複数の長さを有しても良い。添え字ｐは、フィールドの基本数（base−number）を表す。例えば、Ｆ１０３では、フィールドは、１０の次元及び３の基本数を有する。３の基本数は、フィールドの各々の要素が０、１、又は２であることを示す。
【００２５】
さらに、幾つかの実施形態では、関係暗号化方式は、以下の例示的な近接性式に従って関係を定める関係近接性暗号化方式を有しても良い。
【００２６】
Ｒδ＝｛（ｘ，ｙ）｜ｄｉｓｔ（ｘ，ｙ）≦δ∧ｘ，ｙ∈Ｆｋｐ｝
近接性式では、Ｒ、ｘ、∧、∈、及びｙは、上述の通りである。パラメータδは、親密さ（closeness）を定める距離を表す。演算子ｄｉｓｔは、ハミング距離を表す。線形性関係式におけるように、パラメータＦはフィールドを表す。しかしながら、近接性式におけるフィールドは、線形性関係式におけるフィールドとは異なる次元を有しても良い。近接性式におけるフィールドの次元は、線形誤り訂正符号に関連しても良い。
【００２７】
本願明細書で議論する関係暗号化方式は、図１の動作環境１００において実施されても良い。関係暗号化方式は、第２のエンティティ１５０が、暗号化情報を第１のエンティティ１５２へ通信することを可能にし、第１のエンティティ１５２が、暗号化情報の間の線形性関係を発見し及び／又は暗号化情報の間の近接性を決定することを可能にしても良い。
【００２８】
動作環境１００は、第２のエンティティ１５０に関連付けられるユーザ装置１０２と、第１のエンティティ１５２に関連付けられる認証サーバ１４０と、を有しても良い。ユーザ装置１０２及び認証サーバ１４０は、関係暗号化を実行するために、動作環境１００の中に実装されても良い。
【００２９】
ユーザ装置１０２及び認証サーバ１４０は、概して、ネットワーク１０７を介する、関係暗号化に関連する情報及び／又はデータ（例えば、暗号文、キー、平文ベクトル１４２Ａ、等）の生成及び通信を可能にする任意のコンピューティング装置を有しても良い。ユーザ装置１０２の幾つかの例は、携帯電話機、スキャニング装置、スマートフォン、タブレットコンピュータ、ラップトップコンピュータ、デスクトップコンピュータ、セットトップボックス、又はコネクテッドデバイス（例えば、スマートウォッチ、スマート眼鏡、スマート歩数計、又は任意の他のコネクテッドデバイス）を有しても良い。認証サーバ１４０の幾つかの例は、ハードウェアサーバ又はサーバとして機能するよう構成される別のプロセッサに基づくコンピューティング装置を有しても良い。
【００３０】
ネットワーク１０７は、有線又は無線であっても良い。ネットワーク１０７は、スター構成、トークンリング構成若しくは他の構成を含む多数の構成を有しても良い。さらに、ネットワーク１０７は、ＬＡＮ（local  area  network）、ＷＡＮ（wide  area  network）（例えば、インターネット）、及び／又は複数の装置が通信できる他の相互接続されたデータ経路を有しても良い。幾つかの例では、ネットワーク１０７は、ピアツーピアネットワークを有しても良い。ネットワーク１０７は、種々の異なる通信プロトコルでデータを送信する通信ネットワークの一部に結合され又はそれを含んでも良い。幾つかの例では、ネットワーク１０７は、Ｂｌｕｅｔｏｏｔｈ（登録商標）通信ネットワーク又はＳＭＳ（short  messaging  service）、ＭＭＳ（multimedia  messaging  service）、ＨＴＴＰ（hypertext  transfer  protocol）、直接データ接続、ＷＡＰ（wireless  application  protocol）、電子メール等を介することを含むデータを送信及び受信するセルラ通信ネットワークを有しても良い。
【００３１】
ユーザ装置１０２は、関係暗号化／復号化モジュール（ｅｎｃ／ｄｅｃモジュール）１１０、プロセッサ１２４Ａ、メモリ１２２Ａ、及び通信ユニット１２６Ａを有しても良い。ｅｎｃ／ｄｅｃモジュール１１０、プロセッサ１２４Ａ、メモリ１２２Ａ、及び通信ユニット１２６Ａは、バス１２０Ａにより結合されても良い。認証サーバ１４０は、関係認証モジュール１０８、プロセッサ１２４Ｂ、メモリ１２２Ｂ、及び通信ユニット１２６Ｂを有しても良い。関係認証モジュール１０８、プロセッサ１２４Ｂ、メモリ１２２Ｂ、及び通信ユニット１２６Ｂは、バス１２０Ｂにより結合されても良い。
【００３２】
プロセッサ１２４Ａ及び１２４Ｂは、本願明細書では概してプロセッサ１２４又は複数のプロセッサ１２４と表される。メモリ１２２Ａ及び１２２Ｂは、本願明細書では概してメモリ１２２と表される。通信ユニット１２６Ａ及び１２６Ｂは、本願明細書では概して通信ユニット１２６又は複数の通信ユニット１２６と表される。バス１２０Ａ及び１２０Ｂは、本願明細書では概してバス１２０又は複数のバス１２０と表される。
【００３３】
プロセッサ１２４は、計算及びプライバシ保護を実行するためのＡＬＵ（arithmetic  logic  unit）、マイクロプロセッサ、汎用制御部、又は何らかの他のプロセッサ又はプロセッサアレイを有しても良い。プロセッサ１２４は、他のコンポーネント（例えば、１０８、１１０、１２２、及び１２６）との通信のためにバス１２０に結合されても良い。プロセッサ１２４は、概して、データ信号を処理し、ＣＩＳＣ（complex  instruction  set  computer）アーキテクチャ、ＲＩＳＣ（reduced  instruction  set  computer）アーキテクチャ、又は命令セットの組合せを実施するアーキテクチャを含む種々のコンピューティングアーキテクチャを有しても良い。図１では、ユーザ装置１０２及び認証サーバ１４０は、各々、信号プロセッサ１２４を有しても良い。しかしながら、ユーザ装置１０２及び／又は認証サーバ１４０は、複数のプロセッサを有しても良い。他のプロセッサ、オペレーティングシステム、及び物理構成も可能であり得る。
【００３４】
メモリ１２２は、プロセッサ１２４のうちの１又は複数により実行され得る命令及び／又はデータを格納するよう構成されても良い。メモリ１２２は、他のコンポーネントと通信するためにバス１２０に結合されても良い。命令及び／又はデータは、本願明細書に記載の技術又は方法を実行するコードを有しても良い。メモリ１２２は、ＤＲＡＭ素子、ＳＲＡＭ素子、フラッシュメモリ、又は何らかの他のメモリ素子を有しても良い。幾つかの実施形態では、メモリ１２２は、不揮発性メモリ、又はハードディスクドライブ、フロッピディスクドライブ、ＣＤ−ＲＯＭ装置、ＤＶＤ−ＲＯＭ装置、ＤＶＤ−ＲＡＭ装置、ＤＶＤ−ＲＷ装置、フラッシュメモリ装置又は従来知られているより永久的に情報を格納する特定の他の大容量記憶装置を含む同様の永久記憶装置及び媒体も有しても良い。
【００３５】
通信ユニット１２６は、データをユーザ装置１０２及び／又は認証サーバ１４０へ送信し及びそれらから受信するよう構成されても良い。通信ユニット１２６はバス１２０に結合されても良い。幾つかの実施形態では、通信ユニット１２６は、ネットワーク１０７への又は別の通信チャネルへの直接物理接続のためのポートを有しても良い。例えば、通信ユニット１２６は、ＵＳＢ（universal  serial  bus）、ＳＤ（standard  definition）、ＣＡＴ−５、又は図１の動作環境１００のコンポーネントとの有線通信のための同様のポートを有しても良い。幾つかの実施形態では、通信ユニット１２６は、ＩＥＥＥ８０２．１１、ＩＥＥＥ８０２．１６、ＢＬＵＥＴＯＯＴＨ（登録商標）又は別の適切な無線通信方法を含む１又は複数の無線通信方法を用いて通信チャネルによりデータを交換する無線通信機を有する。
【００３６】
幾つかの実施形態では、通信ユニット１２６は、ＳＭＳ、ＭＭＳ、ＨＴＴＰ、直接データ接続、ＷＡＰ、電子メール、又は別の適切な種類の電子通信を含むセルラ通信ネットワークを介してデータを送信及び受信するセルラ通信通信機を有する。幾つかの実施形態では、通信ユニット１２６は、有線ポート及び無線通信機を有する。通信ユニット１２６は、ＴＣＰ／ＩＰ（transmission  control  protocol/internet  protocol）、ＨＴＴＰ、ＨＴＴＰセキュア（ＨＴＴＰＳ）、及びＳＭＴＰ（simple  mail  transfer  protocol）を含む標準ネットワークプロトコルを用いてファイル及び／又は媒体オブジェクトの分配のためにネットワーク１０７への他の接続を提供しても良い。
【００３７】
ｅｎｃ／ｄｅｃモジュール１１０は、上述の関係暗号化方式のような又は上述の特徴のうちの１又は複数を有する、関係暗号化方式を設定するよう構成されても良い。ｅｎｃ／ｄｅｃモジュール１１０は、次に、平文ベクトル１４２を受信し、平文ベクトル１４２を暗号化し、ネットワーク１０７を介して認証サーバ１４０へ暗号文を通信しても良い。さらに、ｅｎｃ／ｄｅｃモジュール１１０は、平文ベクトル１４２のうちの１又は複数を構築するために、暗号文を復号化するよう構成されても良い。ｅｎｃ／ｄｅｃモジュール１１０が暗号化及び／又は復号化処理を実行するよう構成される実施形態では、ｅｎｃ／ｄｅｃモジュール１１０は、本願明細書で議論する暗号化／復号化アルゴリズム及び／又は暗号化／復号化キーを用いて、暗号化及び／又は復号化処理を実行しても良い。
【００３８】
ｅｎｃ／ｄｅｃモジュール１１０が関係暗号化方式を設定するよう構成される実施形態では、ｅｎｃ／ｄｅｃモジュール１１０は、１又は複数の関係秘密キー及び／又は１又は複数の検証アルゴリズムを、認証サーバ１４０の関係認証モジュール１０８へ通信するよう構成されても良い。他の実施形態では、関係認証モジュール１０８は、関係秘密キー及び／又は検証アルゴリズムをローカルに生成しても良く、及び／又は関係秘密キー又は検証アルゴリズムを他のソースから得ても良い。
【００３９】
関係認証モジュール１０８は、暗号文、関係秘密キー、検証アルゴリズム、又はそれらの何らかの組み合わせを、ｅｎｃ／ｄｅｃモジュール１１０又は別のソースから受信するよう構成されても良い。関係認証モジュール１０８は、次に、暗号文の間の線形性関係を発見しても良く、及び／又は暗号文の間の近接性を検出しても良い。関係認証モジュール１０８は、関係秘密キー及び／又は検証アルゴリズムを用いて、暗号文の間の線形性関係を発見し及び近接性を検出しても良い。
【００４０】
図１の動作環境１００では、ｅｎｃ／ｄｅｃモジュール１１０は、線形性暗号化／復号化モジュール１１２、近接性暗号化／復号化モジュール１１４、通信モジュール１１６、及び設定モジュール１１４を有しても良い。さらに、関係認証モジュール１０８は、サーバ通信モジュール１３４、線形性認証モジュール１３２、及び近接性認証モジュール１２８を有しても良い。幾つかの実施形態では、設定モジュール１４４、又は設定モジュール１４４に属する１又は複数の動作を実行するよう構成されるモジュールは、関係認証モジュール１０８に含まれても良い。
【００４１】
ｅｎｃ／ｄｅｃモジュール１１０、線形性暗号化／復号化モジュール１１２、近接性暗号化／復号化モジュール１１４、通信モジュール１１６、設定モジュール１４４、関係認証モジュール１０８、サーバ通信モジュール１３４、線形性認証モジュール１３２、及び近接性認証モジュール１２８は、集合的に、関係モジュールと表されても良い。関係モジュールのうちの１又は複数は、本願明細書に記載の１又は複数の動作を実行するよう構成される１又は複数のルーチンを含むソフトウェアとして実装されても良い。関係モジュールは、本願明細書に記載する機能を提供するためにプロセッサ１２４により実行可能な命令セットを有しても良い。幾つかの例では、関係モジュールは、メモリ１２２に格納され又は少なくとも一時的にそれにロードされても良く、プロセッサ１２４のうちの１又は複数によりアクセス可能又は実行可能であっても良い。関係モジュールのうちの１又は複数は、バス１２０のうちの１又は複数を介するプロセッサ１２４のうちの１又は複数との協働及び通信のために適用されても良い。
【００４２】
概して関係モジュールを参照すると、通信モジュール１１６及び／又はサーバ通信モジュール１３４は、それぞれ、ｅｎｃ／ｄｅｃモジュール１１０又は関係認証モジュール１０８、及びユーザ装置１０２若しくは認証サーバ１４０の他のコンポーネント（例えば、１２２、１２４、及び１２６）との間の通信を扱うよう構成されても良い。通信モジュール１１６及び／又はサーバ通信モジュール１３４は、通信ユニット１２６を介して、ユーザ装置１０２又は認証サーバ１４０へデータを送信し及びそれからデータを受信するよう構成されても良い。幾つかの例では、通信モジュール１１６及び／又はサーバ通信モジュール１３４は、通信ユニット１２６を介して、ユーザ装置１０２又は認証サーバ１４０からのデータを受信し及び／又は転送するために、他の関係モジュールと協働しても良い。
【００４３】
線形性暗号化／復号化モジュール１１２は、線形性暗号文を構築するために平文ベクトル１４２を暗号化することに関連する及び／又は線形性暗号文を復号化することに関連する１又は複数の動作を実行するよう構成されても良い。線形性認証モジュール１３２は、線形性暗号文に関連する１又は複数の動作を実行するよう構成されても良い。例えば、線形性認証モジュール１３２は、線形性暗号文のうちの２以上の間の線形性関係を発見するよう構成されても良い。
【００４４】
線形性暗号化／復号化モジュール１１４は、近接性暗号文を構築するために平文ベクトル１４２を暗号化することに関連する及び／又は近接性暗号文を復号化することに関連する１又は複数の動作を実行するよう構成されても良い。近接性認証モジュール１２８は、近接性暗号文に関連する１又は複数の動作を実行するよう構成されても良い。例えば、近接性認証モジュール１２８は、近接性暗号文のうちの２以上の間の近接性を検出するよう構成されても良い。
【００４５】
設定モジュール１４４は、１又は複数のキー（例えば、公開キー、秘密キー、関係秘密キー）及び／又は１又は複数のアルゴリズム（例えば、暗号化アルゴリズム、復号化アルゴリズム、及び検証アルゴリズム）を生成するよう構成されても良い。設定モジュール１４４は、次に、キー及びアルゴリズムのうちの１又は複数を、通信モジュール１１６及びサーバ通信モジュール１３４により関係認証モジュール１０８に、又は線形性暗号化／復号化モジュール１１２及び近接性暗号化／復号化モジュール１１４に、通信しても良い。
【００４６】
以下の段落で、関係線形性暗号化方式に続き、関係近接性暗号化方式が説明される。関係線形性暗号化方式は、ビットベクトルを参照して、次にｐ−ａｒｙベクトルを参照して、説明される。説明の各々において、設定モジュール１４４はキーを生成する。これは最初に説明される。キーを用いて、線形性暗号化／復号化モジュール１１２又は近接性暗号化／復号化モジュール１１４のうちの１つは、暗号化を実行する。これは、次に説明される。暗号文（例えば、線形性暗号文又は近接性暗号文）は、次に、線形性関係が発見され又は近接性が検出される、線形性認証モジュール１３２及び近接性認証モジュール１２８のうちの１つに通信されても良い。最後に、線形性暗号化／復号化モジュール１１２又は近接性暗号化／復号化モジュール１１４により実行され得る暗号文の復号化が説明される。
【００４７】
＜関係線形性暗号化方式＞
暗号文の間の線形性関係を発見するステップに含まれる１又は複数の動作では、設定モジュール１４４は、平文ベクトル１４２及び／又は暗号文の要素の基本数に少なくとも部分的に基づき得るキーを出力しても良い。例えば、要素の基本数は、２（例えば、バイナリ又はビットベクトル）を有しても良い。したがって、平文ベクトル１４２及び暗号文は、０又は１を有する要素を含んでも良い。代替で、要素の基本数は、３（例えば、ｔｒｉ−ａｒｙ又はベクトル）を有しても良い。したがって、平文ベクトル１４２及び暗号文は、０、１、又は２を有する要素を含んでも良い。概して、基本数は、変数「ｐ」により表される（例えば、ｐ−ａｒｙベクトル）。ｐ−ａｒｙベクトルは、０、１、．．．、ｐ−２、及びｐ−１を有し得る要素を含んでも良い。関係線形性暗号化方式は、平文ベクトル１４２及び／又は暗号文がビットベクトル又はｐ−ａｒｙベクトルであるか否かに基づき、僅かに異なる。先ず、ビットベクトルの関係線形性暗号化方式が議論され、次に、ｐ−ａｒｙベクトルの関係線形性暗号化方式が続く。
【００４８】
ビットベクトル及びｐ−ａｒｙベクトルの関係線形性暗号化方式では、設定モジュール１４４は、関係線形性暗号化方式のキーを生成するよう構成されても良い。図示の実施形態では、設定モジュール１４４は、第１の線形性秘密キー、第２の線形性秘密キー、第１の線形性公開キー、第２の線形性公開キー、及び線形性関係秘密キー（集合的に、「線形性キー」）を生成しても良い。線形性キーは、平文ベクトル１４２を暗号化するため、線形性暗号文を生成するため、線形性暗号文を復号化するため、及び線形性暗号文の間の線形性関係を発見するために用いられても良い。
【００４９】
例えば、第１の線形性公開キーは、第１の平文ベクトル１４２Ａを暗号化して第１の線形性暗号文を生成するために、線形性暗号化／復号化モジュール１１２により使用されても良い。第１の線形性暗号文は、通信モジュール１１６により認証サーバ１４０に通信されても良い。第１の線形性暗号文は、登録暗号文１３０として認証サーバ１４０に格納されても良い。第２の線形性公開キーは、第２の平文ベクトル１４２Ｂを暗号化して第２の線形性暗号文を生成するために、線形性暗号化／復号化モジュール１１２により使用されても良い。第２の線形性暗号文は、通信モジュール１１６により認証サーバ１４０に通信されても良い。線形性関係秘密キーは、認証サーバ１４０において、特に線形性認証モジュール１３２により、第２の線形性暗号文と第１の線形性暗号文との間の線形性関係を発見するために、使用されても良い。この線形性関係は、登録暗号文１３０として格納される。
【００５０】
第１及び第２の線形性秘密キーは、線形性暗号化／復号化モジュール１１２により、線形性暗号文のうちの１又は複数を復号化するために使用されても良い。例えば、第１の線形性暗号文は、第１の秘密キーを用いて復号化されても良い。さらに、第１及び第２の線形性秘密キーは、設定モジュール１４４により、関係線形性キーを生成するために使用されても良い。線形性キー及び上述の動作の幾つかの追加の詳細事項は、ビットベクトルについて及びｐ−ａｒｙベクトルについて以下に提供される。
【００５１】
＜ビットベクトル関係線形性暗号化方式＞
ビットベクトルが実装される実施形態では、線形性キーは、セキュリティパラメータのために生成されても良い。概して、本願明細書で用いられるセキュリティパラメータは、キー長を表しても良い。キーを生成するために、設定モジュール１４４は、３個の双線形素数位数群（bilinear  groups  of  prime  order）を生成しても良い。素数位数は、セキュリティパラメータにおける指数であっても良い。設定モジュール１４４は、３個の双線形群のうちの第１の双線形群の第１の生成元をサンプリングし、３個の双線形群のうちの第２の双線形群の第２の生成元をサンプリングしても良い。
【００５２】
設定モジュール１４４は、整数の集合から特定数の要素をランダムにサンプリングすることにより、第１の線形性秘密キーを生成しても良い。整数の集合は、ゼロから、素数位数−１の値までを有しても良い。設定モジュール１４４は、整数の集合から特定数の要素をランダムにサンプリングすることにより、第２の線形性秘密キーを生成しても良い。
【００５３】
設定モジュール１４４は、第１の線形性公開キーを定めても良い。第１の線形性公開キーは、第１の生成元である要素を有しても良い。第１の線形性公開キーは、第１の線形性秘密キーの対応する要素により冪乗される第１の生成元を含む１又は複数の他の要素を更に有しても良い。幾つかの実施形態では、第１の生成元である要素は、第１の線形性公開キーの第１の要素であっても良い。これは、第１の線形性公開キーと第１の線形性秘密キーとの間の対応で説明できない。例えば、上述の及び他の実施形態では、第１の線形性公開キーの「第６の」要素（例えば、第１の要素を説明する）は、第１の線形性秘密キーの第５の要素により冪乗された第１の生成元を有しても良い。本願を通じて、要素間の対応について同様の慣例が実施されても良い。
【００５４】
設定モジュール１４４は、第２の線形性公開キーを定めても良い。第２の線形性公開キーは、第２の生成元である要素を有しても良い。第２の線形性公開キーは、第２の線形性秘密キーの対応する要素により冪乗される第２の生成元を含む１又は複数の他の要素を更に有しても良い。幾つかの実施形態では、第２の生成元である要素は、第２の線形性公開キーの第１の要素であっても良い。これは、第２の線形性公開キーと第２の線形性秘密キーとの間の対応において考慮されない。
【００５５】
設定モジュール１４４は、線形性関係秘密キーを定めても良い。線形性関係秘密キーの各々の要素は、第２の線形性秘密キーの対応する要素と第１の線形性秘密キーの対応する要素との和を有しても良い。例えば、線形性関係秘密キーの第５の要素は、第１の線形性秘密キーの第５の要素と第２の線形性秘密キーの第５の要素との和を有しても良い。
【００５６】
幾つかの実施形態では、線形性キーの生成は、以下の例示的な線形性ビットベクトルキー式に従っても良い。
【００５７】
λが与えられると、ｑのＧ１，Ｇ２，ＧＴを生成する
【数１】
0006805584.tif 000002
【００５８】
線形性ビットベクトルキー式では、←及びλは、概して上述の通りである。さらに、線形性ビットベクトルキー式では、ｐｋｘｌｉｎは第１の線形性公開キーを表し、ｓｋｘｌｉｎは第１の線形性秘密キーを表し、ｐｋｙｌｉｎは第２の線形性公開キーを表し、ｓｋｙｌｉｎは第２の線形性秘密キーを表し、ｓｋＲｌｉｎは関係線形性キーを表す。さらに、パラメータｐｋｘｌｉｎ、ｓｋｘｌｉｎ、ｐｋｙｌｉｎ、ｓｋｙｌｉｎ、及びｓｋＲｌｉｎは、上述のキー生成アルゴリズム（ＫｅｙＧｅｎ）の出力の少なくとも１つの線形性部分を表しても良い。
【００５９】
パラメータＧ１は、第１の双線形群を表す。パラメータＧ２は、第２の双線形群を表す。パラメータＧＴは、第３の双線形群を表す。パラメータｑは素数位数を表す。パラメータｇ０は、第１の生成元及び第１の線形性公開キーの要素を表す。パラメータｈ０は、第２の生成元及び第２の線形性公開キーの要素を表す。パラメータｇｉは、第１の線形性公開キーの他の要素を表す。パラメータｈｉは、第２の線形性公開キーの他の要素を表す。パラメータｎは、特定数（例えば、特定の要素数）を表す。パラメータｉは、インデックス変数を表す。線形性ビットベクトルキー式では、インデックス変数は、１から特定数までの範囲を有する。パラメータＺｑは、０から、素数位数より１少ない数までの整数の集合を表す。パラメータａｉは、第１の線形性秘密キーの要素を表す。第１の線形性秘密キーの要素は、整数の集合のランダム値であっても良い。パラメータｂｉは、第２の線形性秘密キーの要素を表す。第２の線形性秘密キーの要素は、整数の集合のランダム値であっても良い。演算子＜＞は、簡単な表記法を表す。例えば、＜ｂｉ＞ｎｉ＝１は、ｂ１，ｂ２，．．．，ｂｎを表す。
【００６０】
線形性暗号化／復号化モジュール１１２は、平文ベクトル１４２を暗号化しても良い。線形性暗号化／復号化モジュール１１２は、平文ベクトル１４２を受信しても良い。追加又は代替で、通信モジュール１１６は、平文ベクトル１４２を受信し、平文ベクトル１４２を線形性暗号化／復号化モジュール１１２に通信しても良い。
【００６１】
平文ベクトル１４２は、第１のフィールドのメンバを有しても良い。第１のフィールドは、０及び１の要素、及び特定数の次元を有しても良い。フィールドの要素は、要素の基本数により決定されても良い。例えば、ビットベクトルでは、第１のフィールドは、０及び１の要素を有しても良い。一方、ｐ−ａｒｙベクトルでは、フィールドは、０、１、．．．、ｐ−１の要素を有しても良い。
【００６２】
線形性暗号化／復号化モジュール１１２は、整数の集合から乱数をサンプリングしても良い。線形性暗号化／復号化モジュール１１２は、次に、第１の線形性暗号文及び第２の線形性暗号文を構築しても良い。第１の線形性暗号文は、乱数により冪乗される第１の生成元である第１の要素を有しても良い。第１の線形性暗号文は、線形性暗号化指数により冪乗された第１の線形性公開キーの対応する要素を有する１又は複数の要素を更に有しても良い。第１の線形性暗号文の線形性暗号化指数は、乱数を−１で乗算し、第１の平文ベクトル１４２Ａの対応する要素により冪乗したものを有しても良い。幾つかの実施形態では、第１の線形性暗号文の第１の要素は、対応では説明できない。
【００６３】
第２の線形性暗号文は、乱数により冪乗される第２の生成元である第１の要素を有しても良い。第２の線形性暗号文は、線形性暗号化指数により冪乗された第２の線形性公開キーの対応する要素を有する１又は複数の要素を更に有しても良い。第２の線形性暗号文の線形性暗号化指数は、乱数を−１で乗算し、第２の平文ベクトル１４２Ｂの対応する要素により冪乗したものを有しても良い。幾つかの実施形態では、第２の線形性暗号文の第１の要素は、対応では説明できない。
【００６４】
幾つかの実施形態では、線形性暗号化／復号化モジュール１１２は、以下の例示的な線形性ビットベクトル暗号化に従って、平文ベクトル１４２を暗号化しても良い。
【数２】
0006805584.tif 000003
【００６５】
線形性ビットベクトル暗号化式では、＜＞、ｃｘ，ｃｙ，ｇ０，ｈ０，ｇｉ，ｈｉ，ｉ，及びｎは、上述の通りである。さらに、線形性ビットベクトル暗号化式では、パラメータｃｘは第１の暗号文を表し、パラメータｃｙは第２の暗号文を表す。パラメータｍ１は、第１の平文ベクトル１４２Ａを表す。パラメータｍ１ｉは、第１の平文ベクトル１４２Ａの要素を表す。パラメータｍ２は、第２の平文ベクトル１４２Ｂを表す。パラメータｍ２ｉは、第２の平文ベクトル１４２Ｂの要素を表す。パラメータＦは第１のフィールドを表す。フィールドの隣にある添え字２は、第１のフィールドの基本数を表す。フィールドの隣にある添え字ｎは、第１のフィールドの次元を表す。
【００６６】
線形性ビットベクトル暗号化式は、上述の第１の暗号化アルゴリズム（ＥｎｃＸ）及び第２の暗号化アルゴリズム（ＥｎｃＹ）を定めても良い。例えば、第１の暗号化アルゴリズムは次のように定められても良い。第１の平文ベクトル１４２Ａ及び第１の線形性公開キーが与えられると、第１の暗号化アルゴリズムは、乱数をサンプリングし、ｃｘ＝ｇｒ０，＜ｇｉ（―１）ｍ１ｉｒ＞ｎｉ＝１のように第１の線形性暗号文を構築する。同様に、第２の暗号化アルゴリズムは次のように定められても良い。第１の平文ベクトル１４２Ａ及び第２の線形性公開キーが与えられると、第２の暗号化アルゴリズムは、乱数をサンプリングし、ｃｙ＝ｈｒ０，＜ｈｉ（―１）ｍ２ｉｒ＞ｎｉ＝１のように第２の線形性暗号文を構築する。
【００６７】
第１の線形性暗号文及び第２の線形性暗号文は、線形性認証モジュール１３２に通信されても良い。追加又は代替で、第１の線形性暗号文及び第２の線形性暗号文は、ネットワーク１０７を介して、認証サーバに通信されても良い。サーバ通信モジュール１３４は、第１の線形性暗号文及び第２の線形性暗号文を受信し、第１の線形性暗号文及び第２の線形性暗号文を線形性認証モジュール１３２に通信しても良い。
【００６８】
幾つかの実施形態では、第１の線形性暗号文は、第２の線形性暗号文の通信の前に、線形性認証モジュール１３２に通信されても良い。線形性認証モジュール１３２は、第１の線形性暗号文を登録暗号文１３０としてメモリ１２２Ｂに格納しても良い。第１の線形性暗号文を通信した後に、第２の線形性暗号文は、線形性認証モジュール１３２に通信されても良い。さらに、設定モジュール１４４は、関係線形性キーを線形性認証モジュール１３２に通信しても良い。
【００６９】
認証のために関係暗号化が用いられる幾つかの実施形態では、第１の線形性暗号文は、登録暗号文１３０として格納されても良い。登録暗号文１３０は、第２の線形性暗号文又は任意の他の後続の線形性暗号文との比較の基礎として用いられても良い。関係暗号化を実施する他の実施形態では、第１の線形性暗号文は、登録暗号文１３０として格納されなくても良い。例えば、第１の線形性暗号文及び第２の線形性暗号文は、それらを格納せずに分析しても良く、又は両者とも格納されても良い。
【００７０】
線形性認証モジュール１３２は、第１の線形性暗号文と第２の線形性暗号文との間の線形性関係を発見するよう構成されても良い。線形性関係を発見するために、線形性認証モジュール１３２は、特定ベクトルを定めても良い。特定ベクトルは、第１のフィールドのメンバであっても良い。線形性認証モジュール１３２により決定される認証問題は、特定ベクトルが第１の平文ベクトル１４２Ａと第２の平文ベクトル１４２Ｂとの和であるかどうかを決定することであっても良い。
【００７１】
線形性認証モジュール１３２は、第１の線形性暗号文の第１の要素（例えば、乱数で冪乗された第１の生成元）及び線形性関係秘密キーで冪乗された第２の線形性暗号文の第１の要素（例えば、乱数で冪乗された第２の生成元）のペアリング関数として、第１の値を計算しても良い。
【００７２】
線形性認証モジュール１３２は、第１の線形性暗号文及び−１を特定ベクトルの対応する要素で冪乗したもので冪乗した第２の線形性暗号文の第２の線形性暗号文の中の対応する要素の各々のペアリング関数の結果として、第２の値も計算しても良い。
【００７３】
線形性認証モジュール１３２は、第１の値が第２の値に等しいか否かを決定しても良い。第１の値が第２の値と等しいことに応答して、線形性認証モジュール１３２は、第１の線形性暗号文が第２の線形性暗号文及び定められたベクトルと線形関係にあると結論づけても良い。
【００７４】
幾つかの実施形態では、線形性認証モジュール１３２は、以下の例示的な線形性ビットベクトル検証式に従って、第１の線形性暗号文と第２の線形性暗号文との間の線形性関係を発見する。
【数３】
0006805584.tif 000004
【００７５】
線形性ビットベクトル検証式では、＜＞、ｃｘ，ｃｙ，ｇ０，ｈ０，ｇｉ，ｈｉ，ｉ，ｎ，Ｆ，ｓｋＲ及びｒは、上述の通りである。パラメータｃｘ０は、第１の線形性暗号文の第１の要素を表す。パラメータｃｙ０は、第２の線形性暗号文の第１の要素を表す。パラメータｃｘｉは、第１の線形性暗号文の他の要素を表す。パラメータｃｙｉは、第２の線形性暗号文の他の要素を表す。パラメータｚは、特定ベクトルを表す。パラメータｚｉは、特定ベクトルの要素を表す。演算子ｅは、ペアリング関数を表す。ペアリング関数は、双線形群に関連しても良い。演算子Πは、積演算子を表す。線形性ビットベクトル検証式は、上述の検証アルゴリズム（Ｖｅｒｉｆｙ）を定めても良い。例えば、検証アルゴリズムは、暗号文、特定ベクトル、及び関係線形性キーが与えられると、以下の等式をチェックするよう定められても良い。
【数４】
0006805584.tif 000005
【００７６】
さらに、幾つかの実施形態では、線形性暗号化／復号化モジュール１１２は、第１の及び／又は第２の線形性暗号文を復号化しても良い。線形性暗号化／復号化モジュール１１２は、結果として生じる平文ベクトル１４２の各々の要素を、線形性暗号文の値に基づき、決定しても良い。例えば、値は、第１の線形性暗号文を復号化することにより構築される第１の平文ベクトル（例えば、第１の平文ベクトル１４２Ａ）の各々の要素について決定されても良い。
【００７７】
各々の要素について、線形性暗号化／復号化モジュール１１２は、（１）第１の線形性暗号文の中の対応する要素が、第１の線形性秘密キーの対応する要素により冪乗された第１の線形性暗号文の第１の要素に等しいか、（２）第１の線形性暗号文の中の対応する要素が、第１の線形性秘密キーの対応する要素で−１を乗算したものにより冪乗された、第１の線形性暗号文の第１の要素に等しいか、又は（３）第１の線形性暗号文の中の対応する要素が、別の値に等しいか、を決定しても良い。
【００７８】
第１の線形性暗号文の中の対応する要素が、第１の線形性秘密キーの対応する要素により冪乗された第１の線形性暗号文の第１の要素に等しいことに応答して（例えば、直前の段落の（１））、線形性暗号化／復号化モジュール１１２は、第１の平文ベクトル１４２Ａの要素を０（ゼロ）に設定しても良い。第１の線形性暗号文の中の対応する要素が、−１に第１の線形性秘密キーの対応する要素を乗算したものにより冪乗された第１の線形性暗号文の第１の要素に等しいことに応答して（例えば、直前の段落の（２））、線形性暗号化／復号化モジュール１１２は、第１の平文ベクトル１４２Ａの要素を１に設定しても良い。第１の線形性暗号文の中の対応する要素が別の値に等しいことに応答して（例えば、直前の段落の（３））、線形性暗号化／復号化モジュール１１２は、エラーを返しても良い。第２の線形性暗号文は、第２の線形性秘密キー及び第２の線形性暗号文を用いて同様に復号化されても良い。
【００７９】
幾つかの実施形態では、線形性暗号化／復号化モジュール１１２は、以下の例示的な線形性ビットベクトル復号化式に従って、線形性暗号文を復号化しても良い。
【数５】
0006805584.tif 000006
【００８０】
線形性ビットベクトル復号化式では、ｃｘｉ，ｃｙｉ，ｃｘ０，ｃｙ０，ａｉ，ｂｉ，ｍ１ｉ，及びｍ２ｉは、上述の通りである。パラメータ⊥は、エラーを表す。
【００８１】
線形性ビットベクトル復号化式は、上述の第１の復号化アルゴリズム（ＤｅｃＸ）及び第２の復号化アルゴリズム（ＤｅｃＹ）を定めても良い。例えば、第１の復号化アルゴリズムは次のように定められてもよい。第１の線形性暗号文及び第１の線形性秘密キーが与えられると、第１の復号化アルゴリズムは、次式に従って、ビット毎に、第１の平文ベクトル１４２を構築しても良い。
【数６】
0006805584.tif 000007
【００８２】
同様に、第２の復号化アルゴリズムは次のように定められても良い。第２の線形性暗号文及び第２の線形性秘密キーが与えられると、第２の復号化アルゴリズムは、次式に従って、ビット毎に、第２の平文ベクトル１４２Ｂを構築しても良い。
【数７】
0006805584.tif 000008
【００８３】
＜Ｐ−ＡＲＹベクトル関係線形性暗号化方式＞
ｐ−ａｒｙベクトルが実装される実施形態では（例えば、平文ベクトル１４２及び／又は暗号文がｐ−ａｒｙベクトルである）、線形性キーは、セキュリティパラメータについて生成されても良い。キーを生成するために、設定モジュール１４４は、３個の双線形素数位数群（group  of  prime  order）を生成しても良い。素数位数は、セキュリティパラメータにおける指数であり、１を基本数（ｐ）で割った余り（１  modulo  ｐ）に等しくても良い。したがって、これらの実施形態では、ゼロを削除された整数の集合の中に部分群が存在しても良い。部分群は、基本数の順序を有しても良い。設定モジュール１４４は、部分群の任意の生成元を選択しても良い。
【００８４】
設定モジュール１４４は、第１の生成元及び第２の生成元をサンプリングしても良い。第１の生成元は、第１の双線形群からサンプリングされても良く、第２の生成元は、第２の双線形群からサンプリングされても良い。第１の線形性秘密キー及び第２の線形性秘密キーは、ビットベクトルを実装する実施形態に関して上述したように生成されても良い。
【００８５】
設定モジュール１４４は、第１の生成元である要素を含む第１の線形性公開キーを定めても良い。第１の線形性公開キーは、第１の線形性秘密キーの対応する要素により冪乗される第１の生成元を含む１又は複数の他の要素を更に有しても良い。さらに、第１の線形性公開キーの要素は、任意の生成元を有しても良い。幾つかの実施形態では、第１の線形性公開キーの第１の要素は、任意の生成元であっても良く、第１の線形性公開キーの第２の要素は、第１の生成元であっても良い。第２の線形性公開キーの第１及び第２の要素は、対応において考慮されない。
【００８６】
設定モジュール１４４は、第２の線形性公開キーを定めても良い。第２の線形性公開キーは、第２の生成元である要素を有しても良い。第２の線形性公開キーは、第２の線形性秘密キーの対応する要素により冪乗される第２の生成元を含み得る１又は複数の他の要素を更に有しても良い。さらに、第２の線形性公開キーの要素は、任意の生成元を有しても良い。幾つかの実施形態では、第２の線形性公開キーの第１の要素は、任意の生成元であっても良く、第２の線形性公開キーの第２の要素は、第２の生成元であっても良い。第２の線形性公開キーの第１及び第２の要素は、対応において考慮されない。
【００８７】
設定モジュール１４４は、線形性関係秘密キーを定めても良い。線形性関係秘密キーの各々の要素は、第２の線形性秘密キーの対応する要素と第１の線形性秘密キーの対応する要素との和を有しても良い。
【００８８】
幾つかの実施形態では、線形性キーの生成は、以下の例示的な線形性ｐ−ａｒｙベクトルキー式に従っても良い。
【００８９】
λが与えられると、λにおける指数であり１に等しいｑ（ｍｏｄ  ｐ）のＧ１，Ｇ２，ＧＴを生成する
【数８】
0006805584.tif 000009
【００９０】
線形性ｐ−ａｒｙベクトルキー式では、＜＞，ｇ０，ｈ０，ｇｉ，ｈｉ，ａｉ，ｂｉ，ｉ，ｎ，Ｚ，Ｆ，ｓｋＲ，ｒ，Ｇ１，Ｇ２，ＧＴ，ｑ，ｐｋｘｌｉｎ，ｓｋｘｌｉｎ，ｐｋｙｌｉｎ，ｓｋｙｌｉｎ，ｓｋＲｌｉｎ，←，及びλは、概して上述の通りである。パラメータｐｋｘｌｉｎ、ｓｋｘｌｉｎ、ｐｋｙｌｉｎ、ｓｋｙｌｉｎ、及びｓｋＲｌｉｎは、上述のキー生成アルゴリズムの出力の少なくとも１つの線形性部分を表しても良い。
【００９１】
パラメータｐは、基本数を表す。パラメータＪｐは、次数ｐの部分群を表す。パラメータωは、任意の生成元を表す。演算子ｍｏｄは、モジュロ関数を表す。Ｚの隣にある「＊」は、０（ゼロ）が整数の集合から削除されることを表す。
【００９２】
線形性暗号化／復号化モジュール１１２は、平文ベクトル１４２を受信しても良い。追加又は代替で、通信モジュール１１６は、平文ベクトル１４２を受信しても良く、平文ベクトル１４２を線形性暗号化／復号化モジュール１１２に通信しても良い。平文ベクトル１４２は、第２のフィールドのメンバを有しても良い。第２のフィールドは、０の値から基本数−１の値までを有する要素（例えば、０，１，．．．，ｐ−１）を有しても良い。
【００９３】
線形性暗号化／復号化モジュール１１２は、整数の集合から乱数をサンプリングしても良い。線形性暗号化／復号化モジュール１１２は、次に、第１の線形性暗号文及び第２の線形性暗号文を構築しても良い。第１の線形性暗号文は、乱数により冪乗される第１の生成元である第１の要素を有しても良い。さらに、第１の線形性暗号文は、線形性暗号化指数により冪乗された第１の線形性公開キーの対応する要素を有する１又は複数の他の要素を有しても良い。第１の線形性暗号文の線形性暗号化指数は、乱数を任意の生成元で乗算し、第１の平文ベクトル１４２Ａの対応する要素により冪乗したものを有しても良い。幾つかの実施形態では、第１の線形性暗号文の第１の要素は、対応において考慮されない。
【００９４】
第２の線形性暗号文は、乱数により冪乗される第２の生成元である第１の要素を有しても良い。さらに、第２の線形性暗号文は、線形性暗号化指数により冪乗された第２の線形性公開キーの対応する要素を有する１又は複数の他の要素を有しても良い。第２の線形性暗号文の線形性暗号化指数は、乱数を任意の生成元で乗算し、第２の平文ベクトル１４２Ｂの対応する要素により冪乗したものを有しても良い。幾つかの実施形態では、第２の線形性暗号文の第１の要素は、対応において考慮されない。
【００９５】
幾つかの実施形態では、線形性暗号化／復号化モジュール１１２は、以下の例示的な線形性ｐ−ａｒｙベクトル復号化式に従って、平文ベクトル１４２を暗号化しても良い。
【数９】
0006805584.tif 000010
【００９６】
線形性ｐ−ａｒｙベクトル暗号化式では、＜＞、ｍ１，ｍ１ｉ，ｍ２，ｍ２ｉ，ｃｘ，ｃｙ，ｇ０，ｈ０，ｇｉ，ｈｉ，ｉ，及びｎは、上述の通りである。パラメータＦは第２のフィールドを表す。第２のフィールドの隣にある添え字ｐは、第２のフィールドの基本数を表す。第２のフィールドの隣にある添え字ｎは、第２のフィールドの次元を表す。第２のフィールドの次元は、特定数であっても良い。
【００９７】
線形性ｐ−ａｒｙベクトル暗号化式は、上述の第１の暗号化アルゴリズム（ＥｎｃＸ）及び第２の暗号化アルゴリズム（ＥｎｃＹ）を定めても良い。例えば、第１の暗号化アルゴリズムは次のように定められてもよい。第１の平文ベクトル１４２Ａ及び第１の線形性公開キーが与えられると、第１の暗号化アルゴリズムは、乱数をサンプリングし、次式のように第１の線形性暗号文を構築する。
【数１０】
0006805584.tif 000011
同様に、第２の暗号化アルゴリズムは次のように定められても良い。第１の平文ベクトル１４２Ａ及び第２の線形性公開キーが与えられると、第２の暗号化アルゴリズムは、乱数をサンプリングし、次式のように第２の線形性暗号文を構築する。
【数１１】
0006805584.tif 000012
【００９８】
第１の線形性暗号文及び第２の線形性暗号文は、線形性認証モジュール１３２に通信されても良い。追加又は代替で、第１の線形性暗号文及び第２の線形性暗号文は、ネットワーク１０７を介して、認証サーバに通信されても良い。サーバ通信モジュール１３４は、第１の線形性暗号文及び第２の線形性暗号文を受信し、第１の線形性暗号文及び第２の線形性暗号文を線形性認証モジュール１３２に通信しても良い。
【００９９】
線形性関係を発見するために、線形性認証モジュール１３２は、特定ベクトルを定めても良い。特定ベクトルは、第２のフィールドのメンバであっても良い。；特定ベクトルは、第１の平文ベクトル１４２Ａと第２の平文ベクトル１４２Ｂとの和として定められても良い。線形性認証モジュール１３２は、第１の線形性暗号文の第１の要素（例えば、乱数により冪乗された第１の生成元）及び線形性関係秘密キーで冪乗された第２の線形性暗号文の第１の要素（例えば、乱数により冪乗された第２の生成元）のペアリング関数として、第１の値を計算しても良い。
【０１００】
線形性認証モジュール１３２は、第１の線形性暗号文の各々の要素と、−１及び特定ベクトルの対応する要素の積により冪乗した任意の生成元で冪乗した第２の線形性暗号文の対応する要素と、のペアリング関数の結果として、第２の値も計算しても良い。
【０１０１】
線形性認証モジュール１３２は、第１の値が第２の値に等しいか否かを決定しても良い。第１の値が第２の値と等しいことに応答して、線形性認証モジュール１３２は、第１の線形性暗号文が第２の線形性暗号文と線形関係にあると結論づけても良い。
【０１０２】
幾つかの実施形態では、線形性認証モジュール１３２は、以下の例示的な線形性ｐ−ａｒｙベクトル検証式に従って、第１の線形性暗号文と第２の線形性暗号文との間の線形性関係を発見する。
【数１２】
0006805584.tif 000013
【０１０３】
線形性ｐ−ａｒｙベクトル検証式では、パラメータ及び演算子は上述の通りである。
【０１０４】
線形性ｐ−ａｒｙベクトル検証式は、上述の検証アルゴリズム（Ｖｅｒｉｆｙ）を定めても良い。例えば、検証アルゴリズムは、暗号文、特定ベクトル、及び関係線形性キーが与えられると、以下の等式をチェックするよう定められても良い。
【数１３】
0006805584.tif 000014
【０１０５】
さらに、幾つかの実施形態では、線形性暗号化／復号化モジュール１１２は、第１の及び／又は第２の線形性暗号文を復号化しても良い。線形性暗号化／復号化モジュール１１２は、結果として生じる平文ベクトル１４２の各々の要素を、線形性暗号文の値に基づき、決定しても良い。例えば、値は、第１の線形性暗号文を復号化することにより構築される第１の平文ベクトル（例えば、第１の平文ベクトル１４２Ａ）の各々の要素について決定されても良い。
【０１０６】
暗号文を復号化するために、特定要素値が決定されても良い。特定要素値は、セキュリティパラメータにおいて多項式により結合されても良い。さらに、特定要素値は、基本数を含む要素を有するフィールドのメンバであっても良い。第１の平文ベクトル１４２Ａの各々の要素について、線形性暗号化／復号化モジュール１１２は、第１の線形性暗号文の中の対応する要素が、特定要素値により冪乗された任意の生成元と第１の線形性秘密キーの対応する要素との積により冪乗された第１の線形性暗号文の第１の要素と等しくなるような、特定要素値が存在するか否かを決定しても良い。
【０１０７】
第１の線形性暗号文の中の対応する要素が、特定要素値により冪乗された任意の生成元と第１の線形性秘密キーの対応する要素との積により冪乗された第１の線形性暗号文の第１の要素と等しくなるような、特定要素値が存在することに応答して、線形性暗号化／復号化モジュール１１２は、要素を特定要素値に設定する。
【０１０８】
そのような特定要素値が存在しないことに応答して、線形性暗号化／復号化モジュール１１２は、エラーを出力しても良い。第２の線形性暗号文は、第２の線形性秘密キー及び第２の線形性暗号文を用いて同様に復号化されても良い。
【０１０９】
幾つかの実施形態では、線形性暗号化／復号化モジュール１１２は、以下の例示的な線形性ｐ−ａｒｙベクトル復号化式に従って、線形性暗号文を復号化しても良い。
【数１４】
0006805584.tif 000015
【０１１０】
線形性ｐ−ａｒｙベクトル復号化式では、ｃｘｉ，ｃｙｉ，ｃｘ０，ｃｙ０，ａｉ，ｂｉ，ｍ１ｉ，及びｍ２ｉは、上述の通りである。パラメータ⊥は、エラーを表す。パラメータμは、特定要素値を表す。
【０１１１】
線形性ｐ−ａｒｙベクトル復号化式は、上述の第１の復号化アルゴリズム（ＤｅｃＸ）及び第２の復号化アルゴリズム（ＤｅｃＹ）を定めても良い。例えば、第１の復号化アルゴリズムは次のように定められてもよい。第１の線形性暗号文及び第１の線形性秘密キーが与えられると、第１の復号化アルゴリズムは、次式に従って、ビット毎に、第１の平文ベクトル１４２Ａを構築しても良い。
【数１５】
0006805584.tif 000016
【０１１２】
同様に、第２の復号化アルゴリズムは次のように定められても良い。第２の線形性暗号文及び第２の線形性秘密キーが与えられると、第２の復号化アルゴリズムは、次式に従って、ビット毎に、第２の平文ベクトル１４２Ｂを構築しても良い。
【数１６】
0006805584.tif 000017
【０１１３】
＜関係近接性暗号化方式＞
関係近接性暗号化方式は、近接性暗号文の間の近さ（closeness）を決定するために用いられても良い。幾つかの実施形態では、近接性は、ハミング距離の観点で提供されても良い。関係近接性暗号化方式では、設定モジュール１４４は、キーを生成する。キーを用いて、近接性暗号化／復号化モジュール１１４は、平文ベクトル１４２の暗号化及び／又は復号化を実行する。近接性暗号文は、次に、近接性認証モジュール１２８に通信されても良い。近接性認証モジュール１２８では、近接性暗号文の間の近接性が検出されても良い。
【０１１４】
例えば、設定モジュール１４４は、ＣＰＡ（chosen−plaintext  attack）キー生成アルゴリズム及び線形性キー生成アルゴリズムの出力を生成しても良い。例えば、設定モジュール１４４は、本願明細書の別の場所に記載のように、線形性キーを起動（ｒｕｎ）する。ＣＰＡキー生成アルゴリズムは、ＣＰＡ公開キー及びＣＰＡ秘密キーを出力しても良い。線形性キー生成アルゴリズムは、上述のｐｋｘｌｉｎ，ｓｋｘｌｉｎ，ｐｋｙｌｉｎ，ｓｋｙｌｉｎ，及びｓｋＲｌｉｎを出力しても良い。
【０１１５】
さらに、設定モジュール１４４は、誤り訂正符号（error  correcting  code：ＥＣＣ）を選択しても良い。ＥＣＣは、線形誤り訂正符号方式であっても良い。ＥＣＣは、長さ、ランク、及び距離を有しても良い。さらに、ＥＣＣは、ＥＣＣ符号化演算子（ＥＮＣＯＤＥ）及びＥＣＣ復号化演算子（ＤＥＣＯＤＥ）も有しても良い。設定モジュール１４４は、次に、第１の近接性秘密キー、第２の近接性秘密キー、第１の近接性公開キー、第２の近接性公開キー、及び近接性関係秘密キー（集合的に、「近接性キー」）を生成しても良い。近接性キーは、関係暗号化において、平文ベクトル１４２を暗号化して近接性暗号文を生成するため、近接性暗号文を復号化するため、及び近接性暗号文の間の近接性を検出するために使用される。
【０１１６】
第１の近接性秘密キーは、ＣＰＡ秘密キー及び第１の線形性秘密キーに基づき定められても良い。第２の近接性秘密キーは、ＣＰＡ秘密キー及び第２の線形性秘密キーに基づき定められても良い。第１の近接性公開キーは、ＥＮＣＯＤＥ、ＤＥＣＯＤＥ、ＣＰＡ公開キー及び第１の線形性公開キーに基づき定められても良い。第２の近接性公開キーは、ＥＮＣＯＤＥ、ＤＥＣＯＤＥ、ＣＰＡ公開キー及び第２の線形性公開キーに基づき定められても良い。近接性関係秘密キーは、ＣＰＡ秘密キー及び線形性関係秘密キーに基づき定められても良い。
【０１１７】
幾つかの実施形態では、設定モジュール１４４は、以下の例示的な近接性キー生成式に従って、近接性キーを生成しても良い。
【数１７】
0006805584.tif 000018
【０１１８】
近接性キー生成式において、ｐｋｘｌｉｎ，ｐｋｙｌｉｎ，ｓｋｘｌｉｎ，ｓｋｙｌｉｎ，ｓｋＲｌｉｎ，←，Ｘ，ｍ，及びｎは上述の通りである。パラメータｐｋＣＰＡは、ＣＰＡ公開キーを表す。パラメータｓｋＣＰＡは、ＣＰＡ秘密キーを表す。パラメータＫｅｙＧｅｎＣＰＡは、ＣＰＡキー生成アルゴリズムを表す。パラメータｐｋｘｐｒｏｘは、第１の近接性公開キーを表す。パラメータｐｋｙｐｒｏｘは、第２の近接性公開キーを表す。パラメータｓｋｘｐｒｏｘは、第１の近接性秘密キーを表す。パラメータｓｋｙｐｒｏｘは、第２の近接性秘密キーを表す。パラメータｓｋＲｐｒｏｘは、近接性関係秘密キーを表す。さらに、パラメータｐｋｘｐｒｏｘ、ｓｋｘｐｒｏｘ、ｐｋｙｐｒｏｘ、ｓｋｙｐｒｏｘ、及びｓｋＲｐｒｏｘは、上述のキー生成アルゴリズム（ＫｅｙＧｅｎ）の出力の少なくとも１つの近接性部分を表しても良い。パラメータＸは線形抽出器（extractor）を表す。特定の反復が以上に説明されたが、任意の線形抽出器が使用されても良い。
【０１１９】
第１の線形性公開キーは、第１の平文ベクトル１４２Ａを暗号化して第１の近接性暗号文を生成するために、近接性暗号化／復号化モジュール１１４により使用されても良い。近接性暗号化／復号化モジュール１１４は、平文ベクトル１４２を受信しても良い。追加又は代替で、通信モジュール１１６は、平文ベクトル１４２を受信し、平文ベクトル１４２を近接性暗号化／復号化モジュール１１４に通信しても良い。平文ベクトル１４２は、第１又は第２のフィールドのメンバを有しても良い。
【０１２０】
近接性暗号化／復号化モジュール１１４は、第３のフィールドから近接性乱数をサンプリングしても良い。第３のフィールドは、基本数と、ＥＣＣのランクであっても良い次元と、を有しても良い。近接性暗号化／復号化モジュール１１４は、次に、第１の近接性暗号文及び第２の近接性暗号文を構築しても良い。第１の近接性暗号文及び第２の近接性暗号文の各々は、２つの部分を有しても良い。第１の近接性暗号文の第１の部分は、ＣＰＡ公開キーと第１の平文ベクトル１４２Ａの和とを入力として受信するＣＰＡ暗号化アルゴリズム、及び近接性乱数を入力として受信するＥＮＣＯＤＥを有しても良い。第１の近接性暗号文の第２の部分は、第１の線形性公開キーと近接性乱数とを受信する第１の線形性暗号化アルゴリズムを有しても良い。
【０１２１】
第２の近接性暗号文の第１の部分は、ＣＰＡ公開キーと第２の平文ベクトル１４２Ｂの和とを入力として受信するＣＰＡ暗号化アルゴリズム、及び近接性乱数を入力として受信するＥＮＣＯＤＥを有しても良い。第２の近接性暗号文の第２の部分は、第２の線形性公開キーと近接性乱数とを入力として受信する第２の線形性暗号化アルゴリズムを有しても良い。
【０１２２】
幾つかの実施形態では、近接性暗号文は、以下の例示的な近接性暗号化式に従って生成されても良い。
【数１８】
0006805584.tif 000019
【０１２３】
近接性暗号化式において、ＥＮＣＯＤＥ，ｍ１，ｍ２，ｐｋｃｐａ，ｐｋｘｌｉｎ，及びｐｋｙｌｉｎは、上述の通りである。ＥｎｃＣＰＡは、ＣＰＡ暗号化アルゴリズムを表す。パラメータｃｘｐ１は、第１の近接性暗号文の第１の部分を表す。パラメータｃｘｐ２は、第１の近接性暗号文の第２の部分を表す。パラメータｃｘｐは、第１の近接性暗号文を表す。パラメータｃｙｐ１は、第２の近接性暗号文の第１の部分を表す。パラメータｃｙｐ２は、第２の近接性暗号文の第２の部分を表す。パラメータｃｙｐは、第２の近接性暗号文を表す。パラメータＥｎｃＸＬｉｎｅａｒは、第１の線形性暗号化アルゴリズムを表す。パラメータＥｎｃＹＬｉｎｅａｒは、第２の線形性暗号化アルゴリズムを表す。
【０１２４】
第１の近接性暗号文は、通信モジュール１１６により認証サーバ１４０に通信されても良い。第１の近接性暗号文は、登録暗号文１３０として認証サーバ１４０に格納されても良い。第２の近接性公開キーは、第２の平文ベクトル１４２Ｂを暗号化して第２の近接性暗号文を生成するために、近接性暗号化／復号化モジュール１１４により使用されても良い。第２の近接性暗号文は、通信モジュール１１６により認証サーバ１４０に通信されても良い。近接性関係秘密キーは、認証サーバ１４０において、特に近接性認証モジュール１２８により、第２の近接性暗号文と第１の近接性暗号文との間の近接性を検出するために、使用されても良い。この近接性は、登録暗号文１３０として格納される。
【０１２５】
近接性認証モジュール１２８は、第１の近接性暗号文と第２の近接性暗号文との間の近接性を検出するよう構成されても良い。近接性を検出するために、近接性認証モジュール１２８は、公開キー情報で利用可能なＤＥＣＯＤＥにアクセスしても良い。近接性認証モジュール１２８は、第１の近接性暗号文のランダム性の和（randomness  sum）を復元しても良い。第１の近接性暗号文のランダム性の和は、ＤＥＣＯＤＥとして定められても良い。ＤＥＣＯＤＥは、ＣＰＡ秘密キーと第１の近接性暗号文の第１の部分の和とを入力として受信するＣＰＡ復号化アルゴリズムと、ＣＰＡ秘密キーと第２の近接性暗号文の第１の部分とを入力として受信するＣＰＡ復号化アルゴリズムと、を入力として受信する。
【０１２６】
ＤＥＣＯＤＥがエラーを返す場合、近接性認証モジュール１２８は、拒否を返しても良い。さらに、近接性認証モジュール１２８は、線形性検証アルゴリズムを出力しても良い。線形性検証アルゴリズムは、線形性関係秘密キー、第２の近接性暗号文の第１の部分、第２の近接性暗号文の第２の部分、及びランダム性の和を入力として受信する。
【０１２７】
したがって、近接性検証アルゴリズムは、第１の近接性暗号文、第２の近接性暗号文、及び近接性秘密キーを受信するよう定められても良い。近接性検証アルゴリズムは、ランダム性の和を復元し、拒否又は線形性検証アルゴリズムを出力しても良い。線形性検証アルゴリズムは、線形性関係秘密キー、第２の近接性暗号文の第１の部分、第２の近接性暗号文の第２の部分、及びランダム性の和を入力として受信する。例えば、近接性認証モジュール１２８は、以下の例示的な近接性検証アルゴリズムに従って、もう１度、演算を実行しても良い。
【数１９】
0006805584.tif 000020
【０１２８】
近接性検証アルゴリズムにおいて、ｓｋｃｐａ，ｃｘ１，ｃｘ２，ｃｙ１，ｃｙ２，⊥，ｓｋＲｌｉｎ，Ｘ，及びＤＥＣＯＤＥは、上述の通りである。パラメータＯｕｔｐｕｔは、近接性認証モジュール１２８の出力を示す。パラメータＺｒｓは、ランダム性の和を表す。ＤｅｃＣＰＡは、ＣＰＡ復号化アルゴリズムを表す。ＶｅｒｉｆｙＬｉｎｅａｒは、線形性検証アルゴリズムを表す。
【０１２９】
本願明細書に記載の関係近接性暗号化方式は、以下の条件が真である場合にセキュアであり得る。ＥＣＣは、（ｎ，ｋ，２δ）線形誤り訂正方式である；（ＫｅｙＧｅｎＣＰＡ，ＥｎｃＣＰＡ，ＤｅｃＣＰＡ）は、ＩＮＤ−ＣＰＡセキュア暗号化方式である；（ＫｅｙＧｅｎＬｉｎｅａｒ，ＥｎｃＸＬｉｎｅａｒ，ＤｅｃＸＬｉｎｅａｒ，ＥｎｃＹＬｉｎｅａｒ，ＤｅｃＹＬｉｎｅａｒ，ＶｅｒｉｆｙＬｉｎｅａｒ）は、Ｆｋ２における線形性の関係暗号化方式である。
【０１３０】
条件の中で、ＫｅｙＧｅｎＣＰＡ，ＥｎｃＣＰＡ，ＤｅｃＣＰＡ，ＫｅｙＧｅｎＬｉｎｅａｒ，ＥｎｃＸＬｉｎｅａｒ，ＤｅｃＸＬｉｎｅａｒ，ＥｎｃＹＬｉｎｅａｒ，ＤｅｃＹＬｉｎｅａｒ，ＶｅｒｉｆｙＬｉｎｅａｒ，及びＦは、上述の通りである。ＥＣＣはＥＣＣを表す。パラメータｎは長さを表し、ｋはランクを表し、２δは距離を表す。
【０１３１】
図２は、本願明細書に記載の少なくとも１つの実施形態に従って構成される生体認証システム（バイオメトリックシステム）２００のブロック図を示す。生体認証システム２００は、認証サービスが提供される図１の例示的な動作環境１００に含まれ又はそれを含んでも良い。生体認証システム２００では、ユーザ２０６の認証は、認証サーバ１４０により実行されても良い。生体認証システム２００では、図１を参照して議論した関係暗号化は、ユーザ２０６の同一性を認証するために用いられても良い。
【０１３２】
認証サービスは、登録処理及び認証処理を有しても良い。登録処理は、認証処理において使用され得る情報及びデータをユーザ２０６から得るステップを有しても良い。認証処理は、時間的に後に（例えば、登録処理に続いて）生じても良い。認証処理では、ユーザ２０６の同一性は、図１を参照して議論した関係暗号化動作のうちの１又は複数を用いて認証されても良い。概して、ユーザ２０６の同一性は、本願明細書に記載のように、第１の線形性暗号文と第２の線形性暗号文との間の線形性を発見することにより、及び第１の近接性暗号文と第２の近接性暗号文との間の近接性を検出することにより、認証されても良い。第１の線形性暗号文及び第１の近接性暗号文は、第１のバイオメトリックテンプレートの形式で、ユーザ２０６により提供されても良い。第１のバイオメトリックテンプレートは、図１の第１の平文ベクトル１４２Ａ及び／又は図２の登録入力に含まれても良い。
【０１３３】
ユーザ２０６及び／又は偽者２２２（後述する）は、１又は複数のバイオメトリック特徴を有する個人を有しても良い。バイオメトリック特徴は、１又は複数のユニークな特徴を有しても良い。例えば、バイオメトリック特徴は、畝及び／又畝間のパターンを有する、ユーザ２０６の指紋を有しても良い。幾つかの実施形態では、ユーザ２０６は、ユーザ装置１０２と関連付けられても良い。例えば、ユーザ２０６は、ユーザ装置１０２を所有し又は定期的に操作しても良い。幾つかの実施形態では、ユーザ２０６は、ユーザ装置１０２と具体的に関連付けられなくても良い。例えば、ユーザ装置１０２は、ユーザ２０６を含む複数のユーザにより公的にアクセス可能であっても良い。幾つかの実施形態では、偽者２２２は、バイオメトリック特徴を表し得る入力を供給するエンティティを有しても良い。
【０１３４】
幾つかの実施形態では、ユーザ装置１０２は、センサ２９８を有してもよい。センサ２９８は、例えばユーザ２０６を認証するために使用されるバイオメトリック特徴を測定する又はキャプチャするよう構成されるハードウェア装置を有しても良い。ユーザ２０６のバイオメトリック特徴が測定され又はキャプチャされると、ユーザ装置１０２は、バイオメトリックテンプレートを生成しても良い。バイオメトリックテンプレートは、バイオメトリック特徴を表しても良く、ユーザ２０６のバイオメトリック特徴のユニークな特徴のうちの少なくとも幾つかを有しても良い。バイオメトリックテンプレートは、例えば、バイオメトリック特徴のグラフィカル表現及び／又はアルゴリズム表現を有しても良い。
【０１３５】
センサ２９８の幾つかの例は、指紋スキャナ、虹彩の画像をキャプチャするよう構成されるカメラ、ＤＮＡを測定するよう構成される装置、心拍をキャプチャするよう構成される心拍モニタ、骨格筋により生成される電気的活動をキャプチャするよう構成されるウエアラブル筋電センサ、又はバイオメトリック特徴を測定し又はキャプチャするよう構成される任意の他のセンサ２９８、を有しても良い。
【０１３６】
図示の生体認証システム２００では、センサ２９８は、ユーザ装置１０２に含まれる。他の実施形態では、センサ２９８は、ユーザ装置１０２又はそれに含まれるプロセッサに通信可能に結合されても良い。例えば、センサ２９８は、図１のネットワーク１０７のようなネットワークを介してユーザ装置１０２に信号を通信するよう構成されても良い。図２には１個のみのセンサ２９８が示されるが、幾つかの実施形態では、ユーザ装置１０２は、１又は複数のセンサ２９８を有しても良い。
【０１３７】
ｅｎｃ／ｄｅｃモジュール１１０は、第１の線形性暗号文及び第１の近接性暗号文を登録入力２３２から生成しても良い。ｅｎｃ／ｄｅｃモジュール１１０は、次に、第１の線形性暗号文及び第１の近接性暗号文を登録データ２３４として、認証サーバ１４０に通信しても良い。
【０１３８】
関係認証モジュール１０８は、第１の線形性暗号文及び第１の近接性暗号文を登録暗号文１３０として格納しても良い。登録暗号文１３０は、ユーザ２０６に関連付けられても良い。例えば、ユーザ２０６は、関連付けられたユーザ識別子を有しても良い。幾つかの実施形態では、登録暗号文１３０は、メモリ１２２Ｂに格納されても良い。
【０１３９】
ｅｎｃ／ｄｅｃモジュール１１０は、次に、第１のチャレンジ入力２３６Ａ又は第２のチャレンジ入力２３６Ｂ（概して、チャレンジ入力２３６）を受信しても良い。第１のチャレンジ入力２３６Ａ及び第２のチャレンジ入力２３６Ｂは、ユーザ２０６又は偽者２２２による、彼らの同一性を認証させる試みであっても良い。第１のチャレンジ入力２３６Ａ及び／又は第２のチャレンジ入力２３６Ｂは、例えば、センサ２９８により読み取られた第２のバイオメトリックテンプレートを有しても良い。第２のバイオメトリックテンプレートは、ユーザ２０６又は偽者２２２のバイオメトリック特徴のユニークな特徴を表しても良い。
【０１４０】
ｅｎｃ／ｄｅｃモジュール１１０は、第２の線形性暗号文及び第２の近接性暗号文をチャレンジ入力２３６から生成しても良い。ｅｎｃ／ｄｅｃモジュール１１０は、次に、第２の線形性暗号文及び第２の近接性暗号文をチャレンジデータ２３８として、認証サーバ１４０に通信しても良い。
【０１４１】
関係認証モジュール１０８は、チャレンジデータ２３８を受信しても良い。関係認証モジュール１０８は、次に、ユーザ２０６の登録暗号文１３０を読み出しても良い。
【０１４２】
関係認証モジュール１０８は、登録暗号文１３０として格納された第１の線形性暗号文とユーザ装置１０２から受信した第２の線形性暗号文との間の線形性関係を決定しても良い。さらに、関係認証モジュール１０８は、登録暗号文１３０として格納された第１の近接性暗号文とユーザ装置１０２から受信した第２の近接性暗号文との間の近接性関係を決定しても良い。
【０１４３】
第１の線形性暗号文が第２の線形性暗号文と線形性関係を有し、及び第１の近接性暗号文と第２の近接性暗号文との間の特定の近接性が存在することに応答して、認証サーバ１４０は、第１のバイオメトリックテンプレートと第２のバイオメトリックテンプレートとの間に概算類似性が存在すると決定しても良い。
【０１４４】
したがって、ユーザ２０６により提供される第１のチャレンジ入力２３６Ａが、第２の線形性暗号文及び第２の近接性暗号文の基礎である場合、第１の線形性暗号文と第２の線形性暗号文との間に線形性関係が存在し、第１の近接性暗号文と第２の近接性暗号文との間に近接性が存在し得る。
【０１４５】
しかしながら、偽者２２２により提供される第２のチャレンジ入力２３６Ｂが、第２の線形性暗号文及び第２の近接性暗号文の基礎である場合、第１の線形性暗号文と第２の線形性暗号文との間に線形性関係が存在せず、第１の近接性暗号文と第２の近接性暗号文との間に近接性が存在しない。
【０１４６】
線形性関係及び／又は近接性に基づき、関係認証モジュール１０８は、認証を決定できる。例えば、関係認証モジュール１０８は、チャレンジデータ２３８がユーザ２０６又は偽者２２２に起因するかを決定しても良い。関係認証モジュール１０８は、線形性関係の発見及び／又は近接性の検出に基づき、認証信号２４２を通信しても良い。ｅｎｃ／ｄｅｃモジュール１１０は、認証信号２４２を受信しても良い。
【０１４７】
本開示の範囲から逸脱することなく生体認証システム２００に対し変更、追加又は省略が行われても良い。具体的には、図２に示す実施形態は、１人のユーザ２０６、１つのユーザ装置１０２、及び１つの認証サーバ１４０を有する。しかしながら、本開示は、１又は複数のユーザ２０６、１又は複数のユーザ装置１０２、１又は複数の認証サーバ１４０、又はそれらの任意の組み合わせを有する生体認証システム２００に適用される。
【０１４８】
さらに、本願明細書に記載の実施形態の中の種々のコンポーネントの分割は、分割が全ての実施形態において生じることを意味しない。本開示の利益により、記載のコンポーネントが単一のコンポーネントに統合され又は複数のコンポーネントに分割されても良いことが理解される。例えば、幾つかの実施形態では、ｅｎｃ／ｄｅｃモジュール１１０及び／又はそれに属する１又は複数の機能は、認証サーバ１４０にあるモジュールにより実行されても良い。
【０１４９】
関係認証モジュール１０８及び／又はｅｎｃ／ｄｅｃモジュール１１０は、生体認証のためのコード及びルーチンを有しても良い。幾つかの実施形態では、関係認証モジュール１０８及び／又はｅｎｃ／ｄｅｃモジュール１１０は、例えば、ユーザ装置１０２又は別のコンピューティング装置に格納されても良いシンクライアントアプリケーションとして部分的に動作しても良く、認証サーバ１４０に格納されても良いコンポーネントの一部として動作しても良い。幾つかの実施形態では、関係認証モジュール１０８及び／又はｅｎｃ／ｄｅｃモジュール１１０は、ＦＰＧＡ（field−programmable  gate  array）又はＡＳＩＣ（application−specific  integrated  circuit）を含むハードウェアを用いて実装できる。幾つかの他の例では、関係認証モジュール１０８及び／又はｅｎｃ／ｄｅｃモジュール１１０は、ハードウェア及びソフトウェアの組み合わせを用いて実装されても良い。
【０１５０】
図３は、本願明細書に記載の少なくとも１つの実施形態に従って構成される、生体認証の例示的な方法３００のフロー図である。方法３００は、図２の生体認証システム２００の中で又は図１の動作環境１００の中で実装され得るような生体認証システムにおいて実行されても良い。方法３００は、本願明細書に記載された認証サーバ１４０により幾つかの実施形態においてプログラム制御されて実行されても良い。認証サーバ１４０は、方法３００を実行する又はその実行を制御するためにプロセッサにより実行可能なプログラムコード又は命令を符号化し格納している非一時的コンピュータ可読媒体（例えば、図１のメモリ１２２Ｂ）を含み又はそれに通信可能に結合されても良い。追加又は代替で、認証サーバ１４０は、方法３００を実行する又はその実行を制御するためにコンピュータ命令を実行するよう構成されるプロセッサ（例えば、図１のプロセッサ１２４Ｂ）を有しても良い。別個のブロックとして示したが、所望の実装に依存して、種々のブロックは、更なるブロックに分割され、少ないブロックに結合され、又は除去されても良い。
【０１５１】
方法３００はブロック３０２で開始し得る。ブロック３０２で、第１の線形性暗号文が受信されても良い。第１の線形性暗号文は、関係線形性暗号化方式を用いて暗号化された第１のバイオメトリックテンプレートを表しても良い。ブロック３０４で、第１の近接性暗号文が受信されても良い。第１の近接性暗号文は、関係近接性暗号化方式を用いて暗号化された第１のバイオメトリックテンプレートを表しても良い。
【０１５２】
ブロック３０６で、第１の線形性暗号文及び第１の近接性暗号文は、登録暗号文として格納されても良い。ブロック３０８で、線形性関係秘密キー及び近接性関係秘密キーが受信されても良い。ブロック３１０で、第２の近接性暗号文が受信されても良い。第２の近接性暗号文は、関係近接性暗号化方式を用いて暗号化された第２のバイオメトリックテンプレートを表しても良い。ブロック３１２で、第２の線形性暗号文が受信されても良い。第２の線形性暗号文は、関係線形性暗号化方式を用いて暗号化された第２のバイオメトリックテンプレートを表しても良い。
【０１５３】
ブロック３１４で、第１の線形性暗号文と第２の線形性暗号文との間の線形性関係が、線形性関係秘密キーを用いて発見されても良い。ブロック３１６で、第１の近接性暗号文と第２の近接性暗号文との間の近接性が、近接性関係秘密キーを用いて検出されても良い。近接性は、ハミング距離の観点で決定されても良い。ブロック３１８で、ユーザの同一性は、近接性及び線形性関係に基づき認証されても良い。
【０１５４】
本願明細書に開示した手順及び方法の任意のものについて、処理及び方法の中で実行される機能は、異なる順序で実施されても良い。さらに、概略のステップ及び動作は、単に例として提供され、幾つかのステップ及び動作は、開示の実施形態から逸脱することなく、任意であり、より少ないステップ及び動作に組み合わされ、又は追加ステップ及び動作に拡張されても良い。
【０１５５】
図４Ａ及び４Ｂは、本願明細書に記載の少なくとも１つの実施形態に従って構成される、関係暗号化の例示的な方法４００のフロー図である。方法４００は、図２の生体認証システム２００の中で又は図１の動作環境１００の中で実装され得るような生体認証システムにおいて実行されても良い。方法４００は、本願明細書に記載されたユーザ装置１０２により幾つかの実施形態においてプログラム制御されて実行されても良い。ユーザ装置１０２は、方法４００を実行する又はその実行を制御するためにプロセッサにより実行可能なプログラムコード又は命令を符号化し格納している非一時的コンピュータ可読媒体（例えば、図１のメモリ１２２Ａ）を含み又はそれに通信可能に結合されても良い。追加又は代替で、ユーザ装置１０２は、方法４００を実行する又はその実行を制御するためにコンピュータ命令を実行するよう構成されるプロセッサ（例えば、図１のプロセッサ１２４Ａ）を有しても良い。別個のブロックとして示したが、所望の実装に依存して、種々のブロックは、更なるブロックに分割され、少ないブロックに結合され、又は除去されても良い。
【０１５６】
図４Ａを参照すると、方法４００はブロック４０２で開始し得る。ブロック４０２で、関係線形性暗号化方式のキーが生成されても良い。関係線形性暗号化方式のキーは、セキュリティパラメータについて生成されても良い。ブロック４０３で、第１の不均一分散データは、第１の平文ベクトルとして適切なランダム化レベルにランダム化されても良い。不均一分散データは、バイオメトリックデータであっても良い。適切なランダム化レベルは、以下に詳細に説明される。ブロック４０４で、第１の平文ベクトルは、関係線形性暗号化方式を用いて暗号化されても良い。第１の平文ベクトルの暗号化は、第１の平文ベクトルを表す第１の線形性暗号文を生成しても良い。ブロック４０６で、関係近接性暗号化方式のキーが生成されても良い。関係近接性暗号化方式のキーは、セキュリティパラメータについて生成されても良い。ブロック４０８で、第１の平文ベクトルは、関係近接性暗号化方式を用いて暗号化されても良い。関係近接性暗号化方式を用いる第１の平文ベクトルの暗号化は、第１の平文ベクトルを表す第１の近接性暗号文を生成しても良い。ブロック４１０で、第１の線形性暗号文及び第１の近接性暗号文は、認証サーバに通信されても良い。
【０１５７】
ブロック４１１で、第２の不均一分散データは、第２の平文ベクトルとして適切なランダム化レベルにランダム化されても良い。不均一分散データは、バイオメトリックデータであっても良い。適切なランダム化レベルは、以下に詳細に説明される。ブロック４１２で、第２の平文ベクトルは、関係線形性暗号化方式を用いて暗号化されても良い。第２の平文ベクトルの暗号化は、第２の平文ベクトルを表す第２の線形性暗号文を生成しても良い。図４Ｂを参照すると、ブロック４１４で、第２の平文ベクトルは、関係近接性暗号化方式を用いて暗号化されても良い。関係近接性暗号化方式を用いる第２の平文ベクトルの暗号化は、第２の近接性暗号文を生成しても良い。ブロック４１６で、第２の線形性暗号文及び第２の近接性暗号文は、認証サーバに通信されても良い。ブロック４１８で、ブロック４０２において生成された関係線形性暗号化方式のキーは、認証サーバに通信されても良い。キーは、関係線形性キー及び関係近接性キーを有しても良い。
【０１５８】
ブロック４２０で、認証信号は、認証サーバから受信されても良い。認証信号は、関係線形性キーを用いて発見された第１の線形性暗号文と第２の線形性暗号文との間の線形性関係と、関係近接性キーを用いて検出された第１の近接性暗号文と第２の近接性暗号文との間の近接性と、を示しても良い。幾つかの実施形態では、第１の平文ベクトルは、ユーザから登録入力として受信された第１のバイオメトリックテンプレートを有しても良い。さらに、第２の平文ベクトルは、チャレンジ入力として受信された第２のバイオメトリックテンプレートを有しても良い。上述及び他の実施形態では、認証信号は、第２のバイオメトリックテンプレートがユーザに起因するか否かを示しても良い。
【０１５９】
図５は、本願明細書に記載の少なくとも１つの実施形態に従って構成される、関係暗号化方式において線形性関係を発見する例示的な方法５００のフロー図である。方法５００は、図２の生体認証システム２００の中で又は図１の動作環境１００の中で実装され得るような生体認証システムにおいて実行されても良い。方法５００は、本願明細書に記載された認証サーバ１４０により幾つかの実施形態においてプログラム制御されて実行されても良い。認証サーバ１４０は、方法５００を実行する又はその実行を制御するためにプロセッサにより実行可能なプログラムコード又は命令を符号化し格納している非一時的コンピュータ可読媒体（例えば、図１のメモリ１２２Ｂ）を含み又はそれに通信可能に結合されても良い。追加又は代替で、認証サーバ１４０は、方法５００を実行する又はその実行を制御するためにコンピュータ命令を実行するよう構成されるプロセッサ（例えば、図１のプロセッサ１２４Ｂ）を有しても良い。別個のブロックとして示したが、所望の実装に依存して、種々のブロックは、更なるブロックに分割され、少ないブロックに結合され、又は除去されても良い。
【０１６０】
方法５００はブロック５０２で開始し得る。ブロック５０２で、特定ベクトルが定められても良い。特定ベクトルは、第１のフィールドのメンバを有しても良い。；第１のフィールドは、０及び１の要素、及び線形性秘密キーの長さである特定数の次元を有しても良い。追加又は代替で、特定ベクトルは、第２のフィールドのメンバを有しても良い。；第２のフィールドは、０個から、基本数及び特定数の次元より１少ない数までの要素を有しても良い。
【０１６１】
ブロック５０４で、第１の値が計算されても良い。第１の値は、第１の線形性暗号文の第１の要素と、線形性関係秘密キーにより冪乗された第２の線形性暗号文の第１の要素とのペアリング関数として計算されても良い。ブロック５０６で、第２の値が計算されても良い。幾つかの実施形態では、第２の値は、第１の線形性暗号文の各々の要素と、−１を特定ベクトルの対応する要素で冪乗したもので冪乗した第２の線形性暗号文の対応する要素とのペアリング関数の結果であっても良い。幾つかの実施形態では、第２の値は、第１の線形性暗号文の各々の要素と、−１及び特定ベクトルの対応する要素の積で任意の生成元を冪乗したもので冪乗した第２の線形性暗号文の中の対応する要素とのペアリング関数の結果として計算されても良い。任意の生成元は、０を削除した整数の集合の部分群から選択されても良い。
【０１６２】
ブロック５０８で、第１の値が第２の値に等しいか否かが決定されても良い。第１の値が第２の値に等しいことに応答して（ブロック５０８で「Ｙｅｓ」）、方法５００は、ブロック５１０に進んでも良い。ブロック５１０で、第１の線形性暗号文は第２の線形性暗号文と線形の関係にあると結論づけられても良い。第１の値が第２の値に等しくないことに応答して（ブロック５１８で「Ｎｏ」）、方法５００は、ブロック５１２に進んでも良い。ブロック５１２で、エラーが出力されても良い。これは、第１の線形性暗号文は第２の線形性暗号文と線形の関係にないことを示しても良い。
【０１６３】
図６は、本願明細書に記載の少なくとも１つの実施形態に従って構成される、近接性を検出する例示的な方法６００のフロー図である。方法６００は、図２の生体認証システム２００の中で又は図１の動作環境１００の中で実装され得るような生体認証システムにおいて実行されても良い。方法６００は、本願明細書に記載された認証サーバ１４０により幾つかの実施形態においてプログラム制御されて実行されても良い。認証サーバ１４０は、方法６００を実行する又はその実行を制御するためにプロセッサにより実行可能なプログラムコード又は命令を符号化し格納している非一時的コンピュータ可読媒体（例えば、図１のメモリ１２２Ｂ）を含み又はそれに通信可能に結合されても良い。追加又は代替で、認証サーバ１４０は、方法６００を実行する又はその実行を制御するためにコンピュータ命令を実行するよう構成されるプロセッサ（例えば、図１のプロセッサ１２４Ｂ）を有しても良い。別個のブロックとして示したが、所望の実装に依存して、種々のブロックは、更なるブロックに分割され、少ないブロックに結合され、又は除去されても良い。
【０１６４】
方法６００はブロック６０２で開始し得る。ブロック６０２で、ＤＥＣＯＤＥは、公開キー情報からアクセスされても良い。ブロック６０４で、ランダム性の和が復元されても良い。ランダム性の和は、第１の近接性暗号文について受信されても良い。第１の近接性暗号文のランダム性の和は、ＤＥＣＯＤＥとして定められても良い。ＤＥＣＯＤＥは、（ａ）ＣＰＡ秘密キーと（ｂ）第１の近接性暗号文の第１の部分の和とを入力として受信するＣＰＡ復号化アルゴリズムと、ＣＰＡ秘密キーと第２の近接性暗号文の第１の部分とを入力として受信するＣＰＡ復号化アルゴリズムと、を入力として受信する。
【０１６５】
ブロック６０６で、ＤＥＣＯＤＥがエラーを返すことに応答して、拒否が出力されても良い。或いは、ブロック６０８で、線形性検証アルゴリズムが出力されても良い。線形性検証アルゴリズムは、線形性関係秘密キー、第２の近接性暗号文の第１の部分、第２の近接性暗号文の第２の部分、及びランダム性の和を入力として受信しても良い。
【０１６６】
図７は、本願明細書に記載の少なくとも１つの実施形態に従って構成される、関係線形性暗号化方式のキー生成の例示的な方法７００のフロー図である。方法７００は、図２の生体認証システム２００の中で又は図１の動作環境１００の中で実装され得るような生体認証システムにおいて実行されても良い。方法７００は、本願明細書に記載されたユーザ装置１０２により幾つかの実施形態においてプログラム制御されて実行されても良い。ユーザ装置１０２は、方法７００を実行する又はその実行を制御するためにプロセッサにより実行可能なプログラムコード又は命令を符号化し格納している非一時的コンピュータ可読媒体（例えば、図１のメモリ１２２Ａ）を含み又はそれに通信可能に結合されても良い。追加又は代替で、ユーザ装置１０２は、方法７００を実行する又はその実行を制御するためにコンピュータ命令を実行するよう構成されるプロセッサ（例えば、図１のプロセッサ１２４Ａ）を有しても良い。別個のブロックとして示したが、所望の実装に依存して、種々のブロックは、更なるブロックに分割され、少ないブロックに結合され、又は除去されても良い。
【０１６７】
方法７００はブロック７０２で開始し得る。ブロック７０２で、双線形群が生成されても良い。幾つかの実施形態では、双線形群は素数位数であっても良い。素数位数は、セキュリティパラメータにおける指数であっても良い。追加又は代替で、素数位数は、セキュリティパラメータにおける指数であり、１を基本数（ｐ）で割った余り（１  modulo  ｐ）に等しくても良い。例えば、平文ベクトルがビットベクトルを含む実施形態では、素数位数は、セキュリティパラメータにおける指数であっても良い。平文ベクトルがｐ−ａｒｙベクトルを含む実施形態では、素数位数は、セキュリティパラメータにおける指数であり、１を基本数（ｐ）で割った余り（１  modulo  ｐ）に等しくても良い。
【０１６８】
ブロック７０４で、生成元がサンプリングされても良い。例えば、第１の生成元は、第１の双線形群からサンプリングされても良く、第２の生成元は、第２の双線形群からサンプリングされても良い。ブロック７０６で、線形性秘密キーが生成されても良い。例えば、第１の線形性秘密キー及び第２の線形性秘密キーは、整数の集合から特定数の要素をランダムにサンプリングすることにより生成されても良い。整数の集合は、０から、素数位数より１少ない数までを有しても良い。
【０１６９】
ブロック７０８で、線形性公開キーが定められても良い。例えば、第１の線形性公開キーは、第１の生成元である要素と、第１の線形性秘密キーの対応する要素により冪乗された第１の生成元である１又は複数の他の要素と、を有しても良い。幾つかの実施形態では、第１の線形性公開キーは、任意の生成元を更に有しても良い。任意の生成元は、０を削除した整数の集合の部分群から選択されても良い。さらに、第２の線形性公開キーが定められても良い。第２の線形性公開キーは、第２の生成元である要素と、第２の線形性秘密キーの対応する要素により冪乗された第２の生成元である１又は複数の他の要素と、を有しても良い。幾つかの実施形態では、第２の線形性公開キーは、任意の生成元である要素を更に有しても良い。
【０１７０】
ブロック７１０で、線形性関係秘密キーが定められても良い。線形性関係秘密キーの各々の要素は、第２の線形性秘密キーの対応する要素と第１の線形性秘密キーの対応する要素との和を有しても良い。
【０１７１】
図８は、本願明細書に記載の少なくとも１つの実施形態に従って構成される、関係線形性暗号化方式を用いて第１の平文ベクトルを暗号化する例示的な方法８００のフロー図である。方法８００は、図２の生体認証システム２００の中で又は図１の動作環境１００の中で実装され得るような生体認証システムにおいて実行されても良い。方法８００は、本願明細書に記載されたユーザ装置１０２により幾つかの実施形態においてプログラム制御されて実行されても良い。ユーザ装置１０２は、方法８００を実行する又はその実行を制御するためにプロセッサにより実行可能なプログラムコード又は命令を符号化し格納している非一時的コンピュータ可読媒体（例えば、図１のメモリ１２２Ａ）を含み又はそれに通信可能に結合されても良い。追加又は代替で、ユーザ装置１０２は、方法８００を実行する又はその実行を制御するためにコンピュータ命令を実行するよう構成されるプロセッサ（例えば、図１のプロセッサ１２４Ａ）を有しても良い。別個のブロックとして示したが、所望の実装に依存して、種々のブロックは、更なるブロックに分割され、少ないブロックに結合され、又は除去されても良い。
【０１７２】
方法８００はブロック８０２で開始し得る。ブロック８０２で、乱数がサンプリングされても良い。乱数は、整数の集合からサンプリングされても良い。ブロック８０４で、第１の線形性暗号文が構築されても良い。第１の線形性暗号文の第１の要素は、乱数により冪乗される第１の生成元であっても良い。さらに、第１の線形性暗号文の１又は複数の他の要素は、線形性暗号化指数により冪乗された第１の線形性公開キーの対応する要素を有しても良い。幾つかの実施形態では、線形性暗号化指数は、乱数と、−１を第１の平文ベクトルの対応する要素により冪乗したものとの積を有しても良い。幾つかの実施形態では、線形性暗号化指数は、乱数と、第１の平文ベクトルの対応する要素により冪乗された任意の生成元との積を有しても良い。
【０１７３】
図９は、本願明細書に記載の少なくとも１つの実施形態に従って構成される、関係近接性暗号化方式のキーを生成する例示的な方法９００のフロー図である。方法９００は、図２の生体認証システム２００の中で又は図１の動作環境１００の中で実装され得るような生体認証システムにおいて実行されても良い。方法９００は、本願明細書に記載されたユーザ装置１０２により幾つかの実施形態においてプログラム制御されて実行されても良い。ユーザ装置１０２は、方法９００を実行する又はその実行を制御するためにプロセッサにより実行可能なプログラムコード又は命令を符号化し格納している非一時的コンピュータ可読媒体（例えば、図１のメモリ１２２Ａ）を含み又はそれに通信可能に結合されても良い。追加又は代替で、ユーザ装置１０２は、方法９００を実行する又はその実行を制御するためにコンピュータ命令を実行するよう構成されるプロセッサ（例えば、図１のプロセッサ１２４Ａ）を有しても良い。別個のブロックとして示したが、所望の実装に依存して、種々のブロックは、更なるブロックに分割され、少ないブロックに結合され、又は除去されても良い。
【０１７４】
方法９００はブロック９０２で開始し得る。ブロック９０２で、ＥＣＣが選択されても良い。ＥＣＣは、長さ、セキュリティパラメータの同じ次数のランク、選択された最小距離、を有しても良い。ブロック９０４で、ＣＰＡセキュア暗号化方式のキー生成アルゴリズムが実行されても良い。ＣＰＡセキュア暗号化方式は、ＣＰＡ公開キー及びＣＰＡ秘密キーを出力しても良い。ブロック９０６で、関係線形性キー生成アルゴリズムが実行されても良い。関係線形性キー生成アルゴリズムは、第１の線形性公開キー、第２の線形性公開キー、第１の線形性秘密キー、第２の線形性秘密キー、及び関係線形性秘密キーを出力しても良い。
【０１７５】
ブロック９０７で、近接性公開キーが定められても良い。例えば、第１の近接性公開キーは、ＥＮＣＯＤＥ、ＤＥＣＯＤＥ、ＣＰＡ公開キー及び第１の線形性公開キーに基づき定められても良い。さらに、第２の近接性公開キーは、ＥＮＣＯＤＥ、ＤＥＣＯＤＥ、ＣＰＡ公開キー及び第２の線形性公開キーに基づき定められても良い。ブロック９０８で、近接性秘密キーが定められても良い。例えば、第１の近接性秘密キーは、ＣＰＡ秘密キー及び第１の線形性秘密キーに基づき定められても良い。さらに、第２の近接性秘密キーは、ＣＰＡ秘密キー及び第２の線形性秘密キーに基づき定められても良い。ブロック９１０で、近接性関係秘密キーが定められても良い。例えば、近接性関係秘密キーは、ＣＰＡ秘密キー及び第１の関係線形性秘密キーに基づき定められても良い。
【０１７６】
図１０は、本願明細書に記載の少なくとも１つの実施形態に従って構成される、関係近接性暗号化方式を用いて第１の平文ベクトルを暗号化する例示的な方法１０００のフロー図である。方法１０００は、図２の生体認証システム２００の中で又は図１の動作環境１００の中で実装され得るような生体認証システムにおいて実行されても良い。方法１０００は、本願明細書に記載されたユーザ装置１０２により幾つかの実施形態においてプログラム制御されて実行されても良い。ユーザ装置１０２は、方法１０００を実行する又はその実行を制御するためにプロセッサにより実行可能なプログラムコード又は命令を符号化し格納している非一時的コンピュータ可読媒体（例えば、図１のメモリ１２２Ａ）を含み又はそれに通信可能に結合されても良い。追加又は代替で、ユーザ装置１０２は、方法１０００を実行する又はその実行を制御するためにコンピュータ命令を実行するよう構成されるプロセッサ（例えば、図１のプロセッサ１２４Ａ）を有しても良い。別個のブロックとして示したが、所望の実装に依存して、種々のブロックは、更なるブロックに分割され、少ないブロックに結合され、又は除去されても良い。
【０１７７】
方法１０００はブロック１００２で開始し得る。ブロック１００２で、近接性乱数がサンプリングされても良い。近接性乱数は、第３のフィールドからサンプリングされても良い。第３のフィールドは、基本数と、ＥＣＣのランクである次元と、を有しても良い。ブロック１００４で、第１の近接性暗号文の第１の部分が定められても良い。第１の部分は、ＣＰＡ公開キーと第１の平文ベクトルの和とを入力として受信するＣＰＡ暗号化アルゴリズム、及び近接性乱数を入力として受信するＥＮＣＯＤＥとして定められても良い。
【０１７８】
ブロック１００６で、第１の近接性暗号文の第２の部分が定められても良い。第２の部分は、第１の線形性公開キーと近接性乱数とを入力として受信する第１の線形性暗号化アルゴリズムとして定められても良い。
【０１７９】
図１１は、本願明細書に記載の少なくとも１つの実施形態に従って構成される、第１の線形性暗号文を復号化する例示的な方法１１００のフロー図である。方法１１００は、図２の生体認証システム２００の中で又は図１の動作環境１００の中で実装され得るような生体認証システムにおいて実行されても良い。方法１１００は、本願明細書に記載されたユーザ装置１０２により幾つかの実施形態においてプログラム制御されて実行されても良い。ユーザ装置１０２は、方法１１００を実行する又はその実行を制御するためにプロセッサにより実行可能なプログラムコード又は命令を符号化し格納している非一時的コンピュータ可読媒体（例えば、図１のメモリ１２２Ａ）を含み又はそれに通信可能に結合されても良い。追加又は代替で、ユーザ装置１０２は、方法１１００を実行する又はその実行を制御するためにコンピュータ命令を実行するよう構成されるプロセッサ（例えば、図１のプロセッサ１２４Ａ）を有しても良い。別個のブロックとして示したが、所望の実装に依存して、種々のブロックは、更なるブロックに分割され、少ないブロックに結合され、又は除去されても良い。
【０１８０】
方法１１００はブロック１１０２で開始し得る。ブロック１１０２で、第１の線形性暗号文の中の対応する要素が、特定要素値により冪乗された任意の生成元と第１の線形性秘密キーの対応する要素との積により冪乗された第１の線形性暗号文の第１の要素に等しいような、特定要素値が存在するか否かが決定されても良い。特定要素値が存在することに応答して（ブロック１１０２で「Ｙｅｓ」）、要素は、特定要素値に設定されても良い。特定要素値が存在しないことに応答して（ブロック１１０２で「Ｎｏ」）、エラーが出力されても良い。
【０１８１】
図１２は、本願明細書に記載の少なくとも１つの実施形態に従って構成される、第１の線形性暗号文を復号化する別の例示的な方法１２００のフロー図である。方法１２００は、図２の生体認証システム２００の中で又は図１の動作環境１００の中で実装され得るような生体認証システムにおいて実行されても良い。方法１２００は、本願明細書に記載されたユーザ装置１０２により幾つかの実施形態においてプログラム制御されて実行されても良い。ユーザ装置１０２は、方法１２００を実行する又はその実行を制御するためにプロセッサにより実行可能なプログラムコード又は命令を符号化し格納している非一時的コンピュータ可読媒体（例えば、図１のメモリ１２２Ａ）を含み又はそれに通信可能に結合されても良い。追加又は代替で、ユーザ装置１０２は、方法１２００を実行する又はその実行を制御するためにコンピュータ命令を実行するよう構成されるプロセッサ（例えば、図１のプロセッサ１２４Ａ）を有しても良い。別個のブロックとして示したが、所望の実装に依存して、種々のブロックは、更なるブロックに分割され、少ないブロックに結合され、又は除去されても良い。
【０１８２】
方法１２００はブロック１２０２で開始し得る。ブロック１２０２で、第１の線形性暗号文の中の対応する要素が、第１の線形性秘密キーの対応する要素により冪乗された第１の線形性暗号文の第１の要素と等しいか否かが決定されても良い。第１の線形性暗号文の中の対応する要素が、第１の線形性秘密キーの対応する要素により冪乗された第１の線形性暗号文の第１の要素に等しいことに応答して（ブロック１２０２において「Ｙｅｓ」）、方法１２００は、ブロック１２０８に進んでも良い。ブロック１２０８で、第１の平文ベクトルの要素は、０に設定されても良い。
【０１８３】
第１の線形性暗号文の中の対応する要素が、第１の線形性秘密キーの対応する要素により冪乗された第１の線形性暗号文の第１の要素に等しくないことに応答して（ブロック１２０２において「Ｎｏ」）、方法１２００は、ブロック１２０４に進んでも良い。ブロック１２０４で、第１の線形性暗号文の中の対応する要素が、第１の線形性秘密キーの対応する要素で−１を乗算したものにより冪乗された第１の線形性暗号文の第１の要素と等しいか否かが決定されても良い。第１の線形性暗号文の中の対応する要素が、第１の線形性秘密キーの対応する要素で−１を乗算したものにより冪乗された第１の線形性暗号文の第１の要素に等しいことに応答して（ブロック１２０４において「Ｙｅｓ」）、方法１２００は、ブロック１２１０に進んでも良い。ブロック１２１０で、第１の平文ベクトルの要素は、１に設定されても良い。第１の線形性暗号文の中の対応する要素が、第１の線形性秘密キーの対応する要素で−１を乗算したものにより冪乗された第１の線形性暗号文の第１の要素に等しくないことに応答して（ブロック１２０４において「Ｎｏ」）、方法は、ブロック１２０６に進んでも良い。ブロック１２０６で、第１の線形性暗号文の中の対応する要素が別の値に等しいか否かが決定されても良い。第１の線形性暗号文の対応する要素が別の値に等しいことに応答して（ブロック１２０６で「Ｙｅｓ」）、方法１２００は、ブロック１２１２に進んでも良い。ブロック１２１２で、エラーが返されても良い。
【０１８４】
＜不均一分散データ＞
幾つかの実施形態では、本開示は、一様にランダムではない、バイオメトリックデータのような、基礎データの関係暗号化も提供し得る。基礎データは、不均一に分散されても良く、及び／又は相関を有しても良い。非限定的な例として、米国の人口のより大きな部分集合は、青い目よりも茶色い目を持っている。言い換えると、目の色は、人口全体に不均一に分散し得る。同様に、青い目を持つ個人は、濃い色の髪よりも明るい色の髪を持つ可能性が高い。言い換えると、青い目と明るい色の髪との間には相関が存在し得る。バイオメトリックデータにおける（相関を含む）ランダム性の欠如のために、本開示は、本開示に記載の関係暗号化方式を用いる前に、基礎となるバイオメトリックデータの効率的なランダム化の提供も含み得る。
【０１８５】
適切なランダム化レベルは、データのエントロピ、ノイズ閾、データのドメイン、等を含む、データの特徴の数に依存しても良い。これらの特徴を説明する際の便宜のため、指紋の生体認証特徴の例が用いられるが、非バイオメトリックデータを含む任意の基礎データが使用されても良い。幾つかの実施形態では、適切なランダム化レベルは、Ｘとｒとのドット積、又は基礎データｒと行列Ｘとのドット積により達成され得る。行列Ｘは、従来知られているように強力な線形抽出器であり得る。特徴は、行列Ｘを導出する際の入力であっても良い。幾つかの実施形態では、線形抽出器は、データを適切なレベルにランダム化するために、データの元のサイズを４分の１のサイズまで縮小するために使用されても良い。適切なランダム化レベルは、セキュリティパラメータλに依存しても良い。例えば、セキュリティパラメータが、セキュリティの８０個のビットが必要であることを示す場合、ランダム化レベルは、生データに対して強力な線形抽出器を用いる処理の後に、８０ビットのランダム化データを必要とし得る。別の例では、セキュリティパラメータが、セキュリティの１２８個のビットが必要であることを示す場合、ランダム化レベルは、生データに対して強力な線形抽出器を用いる処理の後に、１２８ビットのランダム化データを必要とし得る。
【０１８６】
データのエントロピの特徴は、データ自体が本来持っている全体的なばらつき又はランダム性を表しても良い。例として、指紋は、人間の人口において、指紋の分布に固有の特定量のばらつき又はランダム性を有する。これは、バイオメトリック特徴のエントロピとして参照されても良い。データのエントロピが増大するにつれ、適切なランダム化レベルに達するために必要な処理の量は減少し得る。
【０１８７】
ノイズ閾の特徴は、基礎データを読み取る又は取得するときに存在するばらつきの量を表し得る。再び指紋の例を用いると、指紋の走査又は読み取りを行うとき、指紋の読み取り値を集めるときに、幾らかのノイズ又は変動が存在し得る。言い換えると、所与の個人について読み取り値が取り込まれる度に、正確に同一のバイオメトリックデータが集められない場合がある。実際に、個人のバイオメトリック特徴は僅かに変化し得るので、完全なシステムにおいてさえ、２つのサンプリングの間には、バイオメトリックデータに幾らかの軽微な変動が存在し得る。これは、ノイズ閾として表されても良い。ノイズ閾が高い場合、システムは、頻繁に偽陽性を生成し、不正なデータが基礎データに一致することを許してしまう。指紋の例を用いると、類似するが同一ではない指紋が多すぎると、本物として認識される場合がある。反対に、ノイズ閾が低い場合には、システムは頻繁に偽陰性を生成し得る。指紋の例を用いると、第２の読み取り値を取り入れる同一人物が認証されない場合がある。ノイズ閾が増大するにつれ、適切なランダム化レベルに達するための処理の量は減少し得る。
【０１８８】
別の特徴は、データのドメイン、又は基礎データが存在する数学的空間を有しても良い。指紋の例を用いると、バイオメトリックデータはビットストリーム又はｐ−ｎａｒｙベクトルに変換される。例えば、所与の指紋は、３２０ビットのビットストリームにより表現できる。ドメインのフォーマット及び長さは、他の因子、例えばノイズレベル及びノイズ閾に関連しても良い。幾つかの実施形態では、基礎データの最小サイズ又はベクトル長しか必要ない。基礎データのサイズ及びドメインの複雑性が増大するにつれ、処理の量は減少し得る。
【０１８９】
適切なランダム化レベルは、データの所望のセキュリティレベルに比例しても良い。所望のセキュリティレベルが増大するにつれ、適切なランダム化レベルは増大し得る。所望のセキュリティレベルは、セキュリティパラメータλが何を表すかを決定し得る。例えば、高いセキュリティレベルが望まれる場合、セキュリティパラメータは、１２８個のセキュリティビットを必要とし得る。
【０１９０】
図１３は、例示的な動作環境のブロック図である。ネットワーク１０７、通信モジュール１１６、設定モジュール１４４、メモリ１２２Ａ、プロセッサ１２４Ａ、通信ユニット１２６Ａ、第１のエンティティ１５０、第２のエンティティ１５２、認証サーバ１４０は、図１に示したものと同じであっても良い。ユーザ装置１３０２は、ユーザ装置１０２と同様であっても良いが、関係暗号化／復号化モジュール１３１０を含むよう変更されても良い。線形性暗号化モジュール１３１２及び近接性暗号化モジュール１３１４は、線形性暗号化／復号化モジュール１１２及び近接性暗号化／復号化モジュール１１４と同様であっても良いが、それらは任意の暗号文を復号化するよう構成されなくても良い。不均一分散データを用いる幾つかの実施形態では、本開示に記載の方法及び処理は、任意の復号化ステップを省略するよう変更されても良い。関係暗号化／復号化モジュール１３１０は、関係暗号化／復号化モジュール１１０と同様であっても良いが、ランダム化モジュール１３２０を含むよう変更されても良い。
【０１９１】
ランダム化モジュール１３２０は、本願明細書に記載の１又は複数の動作を実行するよう構成される１又は複数のルーチンを含むソフトウェアとして実装されても良い。ランダム化モジュール１３２０は、本願明細書に記載の機能を提供するためにプロセッサ１２４により実行可能な命令セットを有しても良い。幾つかの例では、ランダム化モジュール１３２０は、メモリ１２２に格納され又は少なくとも一時的にそれにロードされても良く、プロセッサ１２４のうちの１又は複数によりアクセス可能又は実行可能であっても良い。ランダム化モジュール１３２０は、バスを介してプロセッサ１２４のうちの１又は複数と協働し及び通信するために適応されても良い。
【０１９２】
ランダム化モジュール１３２０は、不均一に分散されたデータであっても良い基礎データを適切なランダム化レベルにまでランダム化するよう構成されても良い。したがって、ランダム化されたデータは、本開示に記載のような関係暗号化方式において使用され得る。幾つかの実施形態では、これは、ランダム化モジュール１３２０が線形抽出器１３２５を利用して不均一分散データから適切にランダム化された平文を抽出するステップを有しても良い。線形抽出器１３２５は、強力な線形抽出器であっても良い。線形抽出器１３２５は、従来知られているような一連の算術的ステップ又は演算として実施されても良い。
【０１９３】
例として、ユーザ装置１３０２は、本開示に従って関係暗号化方式で使用されるべき第１のバイオメトリックデータ１１２０及び第２のバイオメトリックデータ１１３０を受信しても良い。第１のバイオメトリックデータ１１２０及び第２のバイオメトリックデータ１１３０は、不均一に分散していても良い。したがって、基礎データを暗号化する前に、第１及び第２のバイオメトリックデータ１１２０及び１１３０は、平文ベクトルとして適切なランダム化レベルに達するよう、線形抽出器１３２５を用いてランダム化モジュール１３２０において処理されても良い。平文ベクトルは、次に、線形性暗号化モジュール１３１２及び近接性暗号化モジュール１３１４により暗号化されても良い。
【０１９４】
図１４は、関係暗号化方式を用いる不均一分散データを暗号化する例示的な方法１４００のフロー図である。方法１４００は、図２の生体認証システム２００の中で、図１の動作環境１００の中で、又は図１３の動作環境１３００の中で実装され得るような生体認証システムにおいて実行されても良い。幾つかの実施形態では、方法１２００は、図１のユーザ装置１０２又は図１３のユーザ装置１３０２によりプログラム制御可能に実行されても良い。ユーザ装置１０２又はユーザ装置１３０２は、方法１４００を実行する又はその実行を制御するためにプロセッサにより実行可能なプログラムコード又は命令を符号化し格納している非一時的コンピュータ可読媒体（例えば、図１又は図１３のメモリ１２２Ａ）を含み又はそれに通信可能に結合されても良い。追加又は代替で、ユーザ装置１０２又はユーザ装置１３０２は、方法１４００を実行する又はその実行を制御するためにコンピュータ命令を実行するよう構成されるプロセッサ（例えば、図１又は図１３のプロセッサ１２４Ａ）を有しても良い。別個のブロックとして示したが、所望の実装に依存して、種々のブロックは、更なるブロックに分割され、少ないブロックに結合され、又は除去されても良い。
【０１９５】
ブロック１４１０において、ユーザ装置は、バイオメトリックデータ又は他の不均一分散データを受信しても良い。これは、１又は複数のセンサ、検出器、等を用いて受信されても良い。ブロック１４２０において、バイオメトリックデータは、平文ベクトルとして、あるランダム化レベルに処理されても良い。ブロック１４２０は、図１５において更に説明されても良い。ブロック１４３０において、平文ベクトルは、本開示に記載のように関係線形性暗号化方式を用いて暗号化されて、線形性暗号文を生成しても良い。ブロック１４４０において、平文ベクトルは、本開示に記載のように関係近接性暗号化方式を用いて暗号化されて、近接性暗号文を生成しても良い。
【０１９６】
ブロック１４５０で、線形性及び近接性暗号文は、認証サーバに通信されても良い。線形性及び近接性暗号文が認証サーバに通信されると、認証サーバは、暗号文と基準暗号文との間に関係が存在するかどうかを決定するために、本願明細書に記載のように比較及び決定を実行しても良い。関係が存在するとサーバが決定した場合、認証サーバは、ユーザ装置に認証を通信しても良い。幾つかの実施形態では、これは、基礎データが適切にランダム化されている所望のセキュリティレベルに基づいても良い。ブロック１４６０で、ユーザ装置は、認証サーバから、近接性暗号文と登録近接性暗号文との間に近接性が存在するか否かを示す認証を受信しても良い。第１のバイオメトリックテンプレートと第２のバイオメトリックテンプレートとの間に概算類似性が存在すると認証サーバが決定した場合、認証サーバから受信される認証又は認証信号は、近接性暗号文と登録近接性暗号文との間に近接性が存在することを示す。
【０１９７】
図１５は、不均一分散データを処理する例示的な方法１５００のフロー図である。方法１５００は、図１４のブロック１４２０の代用又は拡張であっても良い。例えば、図１４のブロック１４１０の後、方法１５００が実施されても良く、次に図１４のブロック１４４０に戻っても良い。方法１５００は、図２の生体認証システム２００の中で、図１の動作環境１００の中で、又は図１３の動作環境１３００の中で実装され得るような生体認証システムにおいて実行されても良い。幾つかの実施形態では、方法１５００は、図１のユーザ装置１０２又は図１３のユーザ装置１３０２によりプログラム制御可能に実行されても良い。ユーザ装置１０２又はユーザ装置１３０２は、方法１５００を実行する又はその実行を制御するためにプロセッサにより実行可能なプログラムコード又は命令を符号化し格納している非一時的コンピュータ可読媒体（例えば、図１又は図１３のメモリ１２２Ａ）を含み又はそれに通信可能に結合されても良い。追加又は代替で、ユーザ装置１０２又はユーザ装置１３０２は、方法１５００を実行する又はその実行を制御するためにコンピュータ命令を実行するよう構成されるプロセッサ（例えば、図１又は図１３のプロセッサ１２４Ａ）を有しても良い。別個のブロックとして示したが、所望の実装に依存して、種々のブロックは、更なるブロックに分割され、少ないブロックに結合され、又は除去されても良い。例えば、ブロック１５１０及び１５２０は、同時に実行されても良く、又は省略されても良い。
【０１９８】
図１４のブロック１４１０の後に、方法１５００は、ブロック１５１０で開始しても良い。ブロック１５１０で、バイオメトリックデータの特性が決定されても良い。これは、１又は複数のエントロピ、ノイズ閾、及びデータのドメインを決定するステップを有しても良い。幾つかの実施形態では、これは、記憶装置から又は第三機関から読み出されたデータの予め決定された特徴であっても良い。例えば、指紋の分布における多様性は、受信されたバイオメトリックデータが指紋を表すビットストリームである場合、格納され読み出される既知の特徴であっても良い。幾つかの実施形態では、バイオメトリックデータが読み出されると、特徴が決定されても良い。例えば、ノイズ閾は、バイオメトリックデータを集めるために使用されるハードウェア、センサ、又は他のデータキャプチャ技術に部分的に基づいても良い。次に、方法１５００はブロック１５２０に進んでも良い。
【０１９９】
ブロック１５２０において、適切なセキュリティレベルは、セキュリティパラメータλに基づき決定されても良い。適切なセキュリティレベルは、使用されるバイオメトリックデータの感度、認証が要求されるアプリケーション、等に基づいても良い。次に、方法１５００はブロック１５３０に進んでも良い。ブロック１５３０で、バイオメトリックデータについて適切なランダム化レベルが決定されても良い。上述のように、これは、ブロック１５１０において決定された特徴のうちの１又は複数、又はブロック１５２０における決定で用いられたセキュリティパラメータに部分的に基づいても良い。幾つかの実施形態では、適切なランダム化レベルは、セキュリティパラメータに比例しても良い。次に、方法１５００はブロック１５４０に進んでも良い。
【０２００】
ブロック１５４０において、平文ベクトルとして適切なランダム化レベルにバイオメトリックデータを処理するために、強力な線形抽出器が用いられても良い。これは、数学的に演算Ｘ・ｒのように表すことができる。バイオメトリックデータがランダム化されると、方法１５００は、図１４のブロック１４３０へ処理の経路を取ることにより、終了しても良い。
【０２０１】
実施形態と関連して上述したように、近接性検証は、近接性関係秘密キーを用いて、近接性暗号文と登録近接性暗号文との間の近接性関係を検証する。近接性暗号文及び登録近接性暗号文は、この検証のために復号化されない。
【０２０２】
上述の近接性関係を用いる近接性検証によると、ユーザは、データベースの中で特定の情報の近くに情報が登録されているか否かを見出すために、近接性検索を実行しても良い。例えば、近接性検索は、２以上の別個の一致する用語の発生が、特定距離の範囲内にある文書を探しても良い。ここで、距離は、例えば、中間にある語又は文字の数である。しかしながら、検索語（又は単語）、検索文、等であっても良い特定の情報は、暗号化形式で転送され、検索及び近接性検証のために復号化されない。さらに、データベースは、近接性検証のために復号化されない暗号化情報も有する。結果として、ユーザは、ウェブサーバ等に特定の情報それ自体を含む検索（又は閲覧）ログを残さずに、特定の情報の近くにある情報がデータベースに登録されているか否かを見出すことができ、検索の内容は第三者から隠蔽され得る。さらに、ユーザは、特定の情報の近くにある情報がデータベースに登録されているか否かを見出すことができるが、暗号化形式でデータベースに登録された、特定の情報の近くにある情報は、ユーザから隠蔽され得る。
【０２０３】
ユーザが特定の情報の近くにある情報がデータベースに登録されていることを見出す場合、ユーザは、データベースの所有者又は管理者に連絡を取り、例えば所有者又は管理者がユーザとコンテンツを共有することに合意するとき、（例えば連絡により）データベースに登録された特定の情報の近くにある情報、つまり特定の情報に関連するコンテンツを取得するために必要な構成を行っても良い。
【０２０４】
言い換えると、例えばデータベースが一般公衆からアクセス可能にされるときでさえ、検索されるべき情報は暗号化形式で転送され、検索及び近接性検証のために復号化されないので、検索の内容は隠蔽され、検索可能な暗号化を提供できる。さらに、関係暗号化を用いる近接性検証の結果から、検索されている情報の近くにある情報がデ―タベースに登録されているか否かを見出すことが可能である。しかしながら、データベースが近接性検証のために復号化されない暗号化情報を含むので、暗号化形式でデータベースに登録された情報に関連するコンテンツは、隠蔽され、検索可能な暗号化を提供できる。
【０２０５】
したがって、上述の実施形態の１つの適用では、１又は複数の第１のエンティティは、関係暗号化を用いる近接性検証の結果から、検索されている特定の情報の近くにある情報が１又は複数のエンティティの１又は複数のデータベースに登録されているか否かを見出すために、検索を実行しても良い。１又は複数の第１のエンティティは、１又は複数の第２のエンティティが１又は複数の第１のエンティティとコンテンツを共有することに合意するとき、１又は複数のデータベースに登録された、特定の情報の近くにある情報、つまり特定の情報に関連するコンテンツを取得しても良い。結果として、１又は複数の第１のエンティティと情報共有に合意する１又は複数の第２のエンティティとの間で有用な情報が共有され、同時に、データベースに登録された特定の情報に関連するコンテンツの、第三者からの機密性を保証できる。後述するように、第三者は、１又は複数の第２のエンティティにより情報を共有することを許されない１又は複数の第１のエンティティを有しても良い。
【０２０６】
この例では、暗号化は、検索を実行するとき、第１のエンティティの間で相互に異なる第１の（又は検索）キーを用いて実行されても良い。さらに、暗号化は、個々のデータベースに情報を登録するとき、第２のエンティティの間で相互に異なる第２の（又は登録）キーを用いて実行されても良い。ここで、第２のキーは、第１のキーと異なる。
【０２０７】
第１のエンティティは、関係暗号化を用いる近接性検証の結果から、例えばビッグデータ分析のために１又は複数のプロセッサを有するクラウドコンピューティング環境における１又は複数の第２のエンティティの１又は複数のデータベースに、検索されている特定の情報の近くに情報が登録されているか否かを見出すために、検索を実行しても良い。
【０２０８】
上述の実施形態で使用される平文データは、種々の情報に関連しても良く、バイオメトリック情報に限定されない。種々の情報の例は、医療及び生物学的情報、技術情報、金融情報、等を有しても良い。医療及び生物学的情報は、臨床データ、健康データ、遺伝子データ、等を有しても良い。技術情報は、種々の技術分野における分析データ、評価データ、実験データ、等を有しても良い。金融情報は、銀行業務に関連するデータ、証券に関するデータ、等を有しても良い。
【０２０９】
種々の情報は、登録暗号文の形式でデータベースに登録されても良い。一例として、医療及び生物学的情報の暗号化を含む登録暗号文は、病院、研究施設、大学、行政組織、行政機関、等のようなエンティティのデータベースに登録されても良い。
【０２１０】
次に、図１６を参照することにより、上述の実施形態の１つの適用の一例を説明する。図１６は、別の例示的な動作環境１３００−１のブロック図である。図１６では、図１３の対応する部分と同じ部分は、同じ参照符号により示され、その説明は省略される。図１６では、複数のユーザ装置１３０２−１、．．．、１３０２−Ｌ、及びデータベースを形成する複数のメモリ１２２Ｂ−１、．．．、１２２Ｂ−Ｍを含む複数の認証サーバ１４０−１、．．．、１４０−Ｍが設けられる。ここで、Ｌ及びＭは２以上の自然数である。Ｌは、Ｍと等しい又は異なっても良い。Ｎ個のデータベースが設けられても良い。また、２以上の認証サーバに関して共通データベースが設けられても良い。ここで、Ｎは、２以上の自然数であり、Ｍと等しい又は異なっても良い。認証サーバの内部にデータベースを設ける代わりに、データベースは、認証サーバの外部に設けられ、ネットワーク１０７に接続されても良い。便宜のために、ユーザ装置１３０２−１、．．．、１３０２−Ｌは、それぞれエンティティ（以後、「ユーザ」としても言及される）１５０−１、．．．、１５０−Ｌにより用いられると仮定する。さらに、認証サーバ１４０−１、．．．、１４０−Ｍは、それぞれエンティティ（以後、「ユーザ（又はオペレータ）」としても言及される）１５２−１、．．．、１５２−Ｍにより用いられると仮定する。ネットワーク１０７は、１又は複数のネットワークを有しても良く、ネットワーク１０７はインターネットを有しても良い。動作環境１３００−１は、クラウドコンピューティング環境を形成しても良い。
【０２１１】
図１６は、信頼できるエンティティサーバ１１０８を含むとして動作環境１３００−１を示すが、この信頼できるエンティティサーバ１１０８は省略されても良い。信頼できるエンティティサーバ１１０８が設けられる場合、この信頼できるエンティティサーバ１１０８は、プロセッサに基づくコンピューティングシステムを有しても良い。例えば、信頼できるエンティティサーバ１１０８は、ハードウェアサーバ又はサーバとして機能するよう構成される別のプロセッサに基づくコンピューティングシステムを有しても良い。信頼できるエンティティサーバ１１０８は、メモリ及びネットワーク通信能力を有しても良い。動作環境１３００において、信頼できるエンティティサーバ１１０８は、ユーザ装置１３０２−１、．．．、１３０２−Ｌ、認証サーバ１４０−１、．．．、１４０−Ｍ、及びデータベース１２２Ｂとネットワーク１０７を介して通信するよう構成されても良い。
【０２１２】
信頼できるエンティティサーバ１１０８は、信頼できるエンティティに関連付けられても良い。例えば、信頼できるエンティティは、認証機関のような非利害関係第三機関を有しても良い。ユーザ１５０−１、．．．、１５０−Ｌ、及び認証サーバ１４０−１、．．．、１４０−Ｍに関連するエンティティは、信頼できるエンティティを信頼し、選択し、及びそれに合意しても良い。
【０２１３】
信頼できるエンティティサーバ１１０８は、キー生成モジュール１１１８を有しても良い。キー生成モジュール１１１８は、関係暗号化プロトコルで使用されるキーを生成するよう構成されても良い。幾つかの実施形態では、キーは、図２２及び２３と関連して後述する公開キーセット、関係キー、及び第１及び第２の検証キーを有しても良い。キー生成モジュール１１１８により生成されるキーは、ネットワーク１０７を介して、ユーザ装置１３０２−１、．．．、１３０２−Ｌ、認証サーバ１４０−１、．．．、１４０−Ｍに通信され又は利用可能にされても良い。
【０２１４】
動作環境１３００−１において関係暗号化を用いる近接性検証の方法は、ユーザ装置１３０２−１、．．．、１３０２−Ｌの各々から、認証サーバ１４０−１、．．．、１４０−Ｍの各々のデータベースの各々に関して、図１〜１５と関連して上述したように、実行されても良い。
【０２１５】
図１７は、関係暗号化を用いる近接性検証の方法の第１の例を説明する図である。この第１の例では、便宜上、ユーザ１５０−１は、ユーザ装置１３０２−１を操作して、検索を実行し、関係暗号化を用いる近接性検証の結果から、検索されている情報に近い情報が認証サーバ１４０−１、．．．、１４０−Ｍのデータベースに登録されているか否かを発見すると仮定する。また、検索されている情報は、認証サーバ１４０−１のメモリ１２２Ｂ−１により形成されるデータベース（以後、「データベース１２２Ｂ−１」としても参照される）に登録されていると仮定する。さらに、検索されている及びデータベースに登録されている情報は、医療及び生物学的情報の一例である臨床データであると仮定する。
【０２１６】
検索されている情報が、例えば個人に割り当てられた医療ＩＤである場合、ユーザ装置１３０２−１は、行政組織の中に設けられても良く、認証サーバ１４０−１及びデータベース１２２Ｂ−１は病院の中に設けられても良い。図１７に示すように、データベース１２２Ｂ−１は、患者名（ｎ）、患者により訪問された科（ｄｖ）、病歴（ｃｈ）、保険証番号（ｉｃｎ）、保険によりカバーされる費用（ｃｃｂｉ）等のような臨床データを、各々の医療ＩＤについて、暗号化形式で、登録しても良い。したがって、例えば、医療ＩＤ  Ｍ１は暗号化形式Ｅｎｃ１（Ｍ１）で登録され、医療ＩＤ  Ｍ２は暗号化形式Ｅｎｃ１（Ｍ２）で登録される。認証サーバ１４０−１は、暗号化形式でデータベース１２２Ｂ−１に臨床データを登録するために、ユーザ（又はオペレータ）１５２−１により操作されても良い。
【０２１７】
行政組織のユーザ装置１３０２−１のユーザ１５０−１は、例えば病歴ｃｈ１を有する患者を知りたいと望み得る。この場合、病歴ｃｈ１についての検索は、暗号化形式Ｅｎｃ２（ｃｈ１）で行われ、検索及び近接性検証のために復号化されない。ユーザ装置１３０２−１により検索のために使用される暗号化Ｅｎｃ２は、臨床データを暗号化形式でデータベース１２２Ｂ−１に登録するときに使用される暗号化Ｅｎｃ１とは異なる。さらに、データベース１２２Ｂ−１に登録された、暗号化形式の臨床データは、近接性検証のために復号化されない。結果として、ユーザ装置１３０２−１のユーザ１５０−１は、ウェブサーバ等に病歴ｃｈ１自体を含む検索（又は閲覧）ログを残さずに、病歴ｃｈ１の近くにある病歴、つまり病歴ｃｈ１に関連する臨床データがデータベースに登録されているか否かを見出すことができ、検索の内容は第三者から隠蔽され得る。さらに、ユーザ１５０−１は、病歴ｃｈ１の近くにある病歴がデータベース１２２Ｂ−１に登録されていることを見出すことができるが、暗号化形式でデータベース１２２Ｂ−１に登録された、病歴ｃｈ１の近くにある病歴は、ユーザ１５０−１から隠蔽され得る。
【０２１８】
ユーザ１５０−１が、病歴ｃｈ１の近くにある病歴がデータベース１２２Ｂ−１に登録されていることを見出す例では、例えば、ユーザ１５０−１は、データベース１２２Ｂ−１の所有者又は管理者、つまり病院に連絡し、所有者又は管理者がユーザ１５０−１とコンテンツを共有することに合意するとき、データベース１２２Ｂ−１に登録された、病歴ｃｈ１に関連するコンテンツの少なくとも一部を取得するために必要な構成を（例えば、連絡により）生成しても良い。したがって、所有者又は管理者は、行政組織と、病歴ｃｈ１に関連する病歴の一部、つまり、病歴ｃｈ１と類似する病歴を有する患者を共有することに合意しても良い。他方で、例えば、所有者又は管理者は、行政組織と、病歴ｃｈ１に関連する病歴の別の部分、つまり、病歴ｃｈ１と類似する病歴を有する患者の医療ＩＤを共有することに合意しなくても良い。
【０２１９】
その結果、本例では、有用な情報は、行政組織及び行政組織との情報共有に合意する病院の間で効率的に共有され利用され得ると同時に、データベースに登録された、病歴ｃｈ１に関連する病歴の、第三者からの機密性を保証する。また、データベースに登録された、病歴ｃｈ１に関連する病歴の一部の、行政組織からの機密性を保証して、病歴ｃｈ１と類似する病歴を有する患者のプライバシ情報を保護することも可能である。
【０２２０】
図１８は、関係暗号化を用いる近接性検証の方法の第２の例を説明する図である。図１８では、図１７の対応する部分と同じ部分は、同じ参照符号により示され、その説明は省略される。
【０２２１】
図１８に示すように、データベース１２２Ｂ−１は、各々の医療ＩＤについて、暗号化形式で、患者の性別、患者の病気、患者の年齢、等のような臨床データを登録しても良い。本例では、各々の医療ＩＤの複数の臨床データの組合せは、医療ＩＤを有する患者の属性データに対応する。行政組織のユーザ装置１３０２−１のユーザ１５０−１は、医療ＩＤ  Ｍ１を有する患者の属性データがデータベースに登録されているか否かを知りたいと望み得る。この場合、例えば、属性データ（Ｍ１，Ｇ１，Ｉ１，Ａ１）についての検索は、暗号化形式Ｅｎｃ２（Ｍ１，Ｇ１，Ｉ１，Ａ１）で行われ、検索及び近接性検証のために復号化されない。ユーザ装置１３０２−１により検索のために使用される暗号化Ｅｎｃ２は、臨床データを暗号化形式でデータベース１２２Ｂ−１に登録するときに使用される暗号化Ｅｎｃ１とは異なる。さらに、データベース１２２Ｂ−１に登録された、暗号化形式の属性データは、近接性検証のために復号化されない。結果として、ユーザ装置１３０２−１のユーザ１５０−１は、ウェブサーバ等に属性データ（Ｍ１，Ｇ１，Ｉ１，Ａ１）自体を含む検索（又は閲覧）ログを残さずに、属性データ（Ｍ１，Ｇ１，Ｉ１，Ａ１）の近くにある属性データがデータベースに登録されているか否かを見出すことができ、検索の内容は第三者から隠蔽され得る。さらに、ユーザ１５０−１は、属性データ（Ｍ１，Ｇ１，Ｉ１，Ａ１）の近くにある属性データがデータベース１２２Ｂ−１に登録されていることを見出すことができるが、暗号化形式でデータベース１２２Ｂ−１に登録された、属性データ（Ｍ１，Ｇ１，Ｉ１，Ａ１）の近くにある属性データは、ユーザ１５０−１から隠蔽され得る。
【０２２２】
図１９は、関係暗号化を用いる近接性検証の方法の第３の例を説明する図である。図１９では、図１７の対応する部分と同じ部分は、同じ参照符号により示され、その説明は省略される。
【０２２３】
検索されている情報が、医療及び生物学的情報の一例であるＤＮＡパターンである場合、ユーザ装置１３０２−１は、研究施設の中に設けられても良く、認証サーバ１４０−１及びデータベース１２２Ｂ−１は病院の中に設けられても良い。図１８に示すように、データベース１２２Ｂ−１は、ＤＮＡパターン、ＤＮＡパターンに関連する病気、等のような、遺伝子データを、暗号化形式で登録しても良い。したがって、例えば、ＤＮＡパターンＧＴＧ．．．ＴＡＧ及びそれに関連する病気Ｉ１は、暗号化形式Ｅｎｃ１（ＧＴＧ．．．ＴＡＧ）及びＥｎｃ１（Ｉ１）で登録され、ＤＮＡパターンＧＴＣ．．．ＧＡＣ及びそれに関連する病気Ｉ２は、暗号化形式Ｅｎｃ１（ＧＴＣ．．．ＧＡＣ）及びＥｎｃ１（Ｉ２）で登録される。認証サーバ１４０−１は、暗号化形式でデータベース１２２Ｂ−１に遺伝子データを登録するために、ユーザ（又はオペレータ）１５２−１により操作されても良い。
【０２２４】
研究施設のユーザ装置１３０２−１のユーザ１５０−１は、例えば、ＤＮＡパターンＧＴＧ．．．ＴＡＧに関連する病気を知りたいと望み得る。この場合、ＤＮＡパターンＧＴＧ．．．ＴＡＧについての検索は、例えば暗号化形式Ｅｎｃ２（ＧＴＧ．．．ＴＡＧ）で行われ、検索及び近接性検証のために復号化されない。ユーザ装置１３０２−１により検索のために使用される暗号化Ｅｎｃ２は、遺伝子データを暗号化形式でデータベース１２２Ｂ−１に登録するときに使用される暗号化Ｅｎｃ１とは異なる。さらに、データベース１２２Ｂ−１に登録された、暗号化形式の遺伝子データは、近接性検証のために復号化されない。結果として、ユーザ装置１３０２−１のユーザ１５０−１は、ウェブサーバ等にＤＮＡパターンＧＴＧ．．．ＴＡＧ自体を含む検索（又は閲覧）ログを残さずに、ＤＮＡパターンＧＴＧ．．．ＴＡＧの近くにある属性データがデータベースに登録されているか否かを見出すことができ、検索の内容は第三者から隠蔽され得る。さらに、ユーザ１５０−１は、ＤＮＡパターンＧＴＧ．．．ＴＡＧの近くにあるＤＮＡパターンがデータベース１２２Ｂ−１に登録されていることを見出すことができるが、暗号化形式でデータベース１２２Ｂ−１に登録された、ＤＮＡパターンＧＴＧ．．．ＴＡＧの近くにあるＤＮＡパターンは、ユーザ１５０−１から隠蔽され得る。
【０２２５】
ユーザ１５０−１が、ＤＮＡパターンＧＴＧ．．．ＴＡＧの近くにあるＤＮＡパターンがデータベース１２２Ｂ−１に登録されていることを見出す例では、例えば、ユーザ１５０−１は、データベース１２２Ｂ−１の所有者又は管理者、つまり病院に連絡し、所有者又は管理者がユーザ１５０−１とコンテンツを共有することに合意するとき、ＤＮＡパターンＧＴＧ．．．ＴＡＧに関連するコンテンツの少なくとも一部、つまりＤＮＡパターンＧＴＧ．．．ＴＡＧの近くにあるＤＮＡパターンに関してデータベース１２２Ｂ−１に登録された病気、を取得するために必要な構成を（例えば、連絡により）生成しても良い。したがって、本例では、所有者又は管理者は、ＤＮＡパターンＧＴＧ．．．ＴＡＧに関連する遺伝子データの一部、つまりＤＮＡパターンＧＴＧ．．．ＴＡＧの近くにあるＤＮＡパターンに関連する病気を、研究施設と共有することに合意しても良い。他方で、所有者又は管理者は、ＤＮＡパターンＧＴＧ．．．ＴＡＧの近くにあるＤＮＡパターンに関連する遺伝子データの別の部分を、研究施設と共有することに合意しなくても良い。
【０２２６】
その結果、本例では、有用な情報は、研究施設及び研究施設との情報共有に合意する病院の間で効率的に共有され利用され得ると同時に、データベースに登録された、ＤＮＡパターンＧＴＧ．．．ＴＡＧの近くにあるＤＮＡパターンに関連する遺伝子データの、第三者からの機密性を保証する。また、データベースに登録された、ＤＮＡパターンＧＴＧ．．．ＴＡＧの近くにあるＤＮＡパターンに関連する遺伝子データの一部の、研究施設からの機密性を保証して、ＤＮＡパターンＧＴＧ．．．ＴＡＧの近くにあるＤＮＡパターンに関連する機密情報又は秘密情報を保護することも可能である。
【０２２７】
図２０は、関係暗号化を用いる近接性検証の方法の第４の例を説明する図である。図２０では、図１９の対応する部分と同じ部分は、同じ参照符号により示され、その説明は省略される。
【０２２８】
図２０に示すように、データベース１１６−１は、例えば病気等に関連する意味のある単位であるセグメント（つまり、単一データのセグメント）で、ＤＮＡパターンを登録しても良い。本例では、例えば、ＤＮＡセグメントＧＴＧＡ、ＧＡＡＧ、ＴＴＡＴ、ＧＡＴＡ、．．．、それに関連する病気Ｉ１、等は、暗号化形式Ｅｎｃ１（ＧＴＧＡ）、Ｅｎｃ１（ＧＡＡＧ）、Ｅｎｃ１（ＴＴＡＴ）、Ｅｎｃ１（ＧＡＴＡ）、Ｅｎｃ１（Ｉ１）、等で登録される。本例では、例えば、ＤＮＡセグメントＧＴＣＣ、ＴＡＡＧ、ＧＴＧＴ、ＧＡＴＡＡＣ、．．．、それに関連する病気Ｉ２、等は、暗号化形式Ｅｎｃ１（ＧＴＣＣ）、Ｅｎｃ１（ＴＡＡＧ）、Ｅｎｃ１（ＧＴＧＴ）、Ｅｎｃ１（ＧＡＴＡＡＣ）、Ｅｎｃ１（Ｉ２）、等で登録される。この場合、研究施設のユーザ装置１３０２−１のユーザ１５０−１は、例えばＤＮＡセグメントＧＴＧＡに関連する病気のようなＤＮＡセグメントに関連する情報が、データベースに登録されているか否かを見出すことができる。
【０２２９】
上述の第２の例によると、検索される情報及び登録される情報の各々は、複数のデータアイテムの組合せを有する。他方で、第４の例によると、検索される情報及び登録される情報の各々は、単一のデータアイテムの複数のセグメントを有する。
【０２３０】
図２１は、関係暗号化を用いる近接性検証の方法の第５の例を説明する図である。図２１では、図１７の対応する部分と同じ部分は、同じ参照符号により示され、その説明は省略される。
【０２３１】
上述の第１〜第４の例は、医療及び生物学的情報に関連する近接性検証を実行する。しかしながら、上述のように、近接性検証を受ける情報は、医療及び生物学的情報に限定されない。第５の例は、近接性検証が適用される情報種類の一例として、金融情報に関連する近接性検証を実行する。
【０２３２】
検索されている情報が、例えば個人に割り当てられた顧客ＩＤである場合、ユーザ装置１３０２−１は、行政組織の中に設けられても良く、認証サーバ１４０−１及びデータベース１２２Ｂ−１は銀行の中に設けられても良い。図２１に示すように、データベース１２２Ｂ−１は、顧客名（ｃｎ）、顧客により所有される口座の種類（ｔａ）、口座番号（ａｎ）、顧客の口座の残高（ｂａ）、等のような銀行業務に関連するデータ（以後、「銀行業務データ」としても参照される）を、各々の顧客ＩＤについて、暗号化形式で登録しても良い。したがって、例えば、顧客ＩＤ  ＭC１は暗号化形式Ｅｎｃ１（ＭC１）で登録され、顧客ＩＤ  ＭＣ２は暗号化形式Ｅｎｃ１（ＭＣ２）で登録される。認証サーバ１４０−１は、暗号化形式でデータベース１２２Ｂ−１に銀行業務データを登録するために、ユーザ（又はオペレータ）１５２−１により操作されても良い。
【０２３３】
行政組織のユーザ装置１３０２−１のユーザ１５０−１は、例えば、顧客ＩＤ  ＭＣ１の近くにある顧客ＩＤを有する顧客により所有される口座の種類を知りたいと望み得る。この場合、顧客ＩＤ  ＭＣ１についての検索は、例えば暗号化形式Ｅｎｃ２（ＭＣ１）で行われ、検索及び近接性検証のために復号化されない。ユーザ装置１３０２−１により検索のために使用される暗号化Ｅｎｃ２は、銀行業務データを暗号化形式でデータベース１２２Ｂ−１に登録するときに使用される暗号化Ｅｎｃ１とは異なる。さらに、データベース１２２Ｂ−１に登録された、暗号化形式の銀行業務データは、近接性検証のために復号化されない。結果として、ユーザ装置１３０２−１のユーザ１５０−１は、ウェブサーバ等に顧客ＩＤ  ＭＣ１自体を含む検索（又は閲覧）ログを残さずに、顧客ＩＤ  ＭＣ１の近くにある顧客の銀行業務データがデータベースに登録されているか否かを見出すことができ、検索の内容は第三者から隠蔽され得る。さらに、ユーザ１５０−１は、顧客ＩＤ  ＭＣ１の近くにある顧客の銀行業務データがデータベース１２２Ｂ−１に登録されていることを見出すことができるが、暗号化形式でデータベース１２２Ｂ−１に登録された、顧客ＩＤ  ＭＣ１の近くにある顧客の銀行業務データは、ユーザ１５０−１から隠蔽され得る。
【０２３４】
ユーザ１５０−１が、顧客ＩＤ  ＭＣ１の近くにある顧客の銀行業務データがデータベース１２２Ｂ−１に登録されていることを見出す例では、例えば、ユーザ１５０−１は、データベース１２２Ｂ−１の所有者又は管理者、つまり銀行に連絡し、所有者又は管理者がユーザ１５０−１とコンテンツを共有することに合意するとき、データベース１２２Ｂ−１に登録された、顧客ＩＤ  ＭＣ１に関連するコンテンツの少なくとも一部を取得するために必要な構成を（例えば、連絡により）生成しても良い。したがって、所有者又は管理者は、行政組織と、顧客ＩＤ  ＭＣ１に関連する銀行業務データの一部、つまり、顧客ＩＤ  ＭＣ１の近くにある顧客ＩＤを有する顧客により所有される口座の種類を共有することに合意しても良い。他方で、所有者又は管理者は、行政組織と、顧客ＩＤ  ＭＣ１に関連する銀行業務データの別の部分、つまり、顧客ＩＤ  ＭＣ１の近くにある顧客ＩＤを有する顧客の顧客口座の残高を共有することに合意しなくても良い。
【０２３５】
その結果、本例では、有用な情報は、行政組織及び行政組織との情報共有に合意する銀行の間で効率的に共有され利用され得ると同時に、データベースに登録された、顧客ＩＤ  ＭＣ１に関連する銀行業務データの、第三者からの機密性を保証する。また、データベースに登録された、顧客ＩＤ  ＭＣ１に関連する銀行業務データの一部の、行政組織からの機密性を保証して、顧客ＩＤ  ＭＣ１の近くにある顧客ＩＤを有する顧客のプライバシ情報を保護することも可能である。
【０２３６】
次に、図２２及び２３を参照することにより、関係暗号化を用いる近接性検証の方法の第６の例を説明する。図２２は、アクセス制限テーブルの一例を示す。図２３は、関係暗号化を用いる近接性検証の方法の第６の例を説明する図である。図２３では、図１６の対応する部分と同じ部分は、同じ参照符号により示され、その説明は省略される。図２３は、図１６においてＬ＝Ｍ＝３である場合を示す。本例では、各々の認証サーバは、アクセス制限テーブルに基づきデータベースへのアクセスを制限しても良い。さらに、データベースは、認証サーバの外部に設けられ、ネットワーク１０７に接続される。
【０２３７】
図２２は、図２３に示す動作環境１３００−１の中に、３個のユーザ装置１３０２−１〜１３０２−３、３個の認証サーバ１４０−１〜１４０−３、及び３個のデータベース１２２Ｂ−１〜１２２Ｂ−３が設けられる場合の、アクセス制限テーブル１８００を示す。図２２で、Ｋａ、Ｋｂ、及びＫｃは、例えば図１４に示すブロック１４６０に先行する任意のブロックで、信頼できるエンティティサーバ１１０８から通信され、それぞれユーザ装置１３０２−１、１３０２−２、及び１３０２−３により受信されても良い検証キーを示す。さらに、Ｋｘ、Ｋｙ、及びＫｚは、認証サーバ１４０−１、１４０−２、及び１４０−３から認証信号を通信する前の適切なタイミングに、信頼できるエンティティサーバ１１０８から通信され、それぞれ認証サーバ１４０−１、１４０−２、及び１４０−３により受信されても良い検証キーを示す。本例では、検証キーＫａ、Ｋｂ、及びＫｃは、それぞれ、ユーザ装置１３０２−１、１３０２−２、及び１３０２−３のユーザＵａ、Ｕｂ、及びＵｃに割り当てられる。さらに、検証キーＫｘ、Ｋｙ、及びＫｚは、それぞれ、認証サーバ１４０−１、１４０−２、及び１４０−３のユーザ（又はオペレータ）Ｕｘ、Ｕｙ、及びＵｚに割り当てられる。アクセス制限テーブル１８００は、認証サーバ１４０−１、１４０−２、及び１４０−３の各々に格納されても良い。代替で、アクセス制限テーブル１８００は、信頼できるエンティティサーバ１１０８から認証サーバ１４０−１、１４０−２、及び１４０−３へ適切なタイミングに通信されても良い。
【０２３８】
各々のユーザ装置の検証キーは、適切なタイミングに認証サーバに通信されても良い。認証サーバ１４０は、アクセス制限テーブル１８００に基づき、認証信号が近接性暗号文と登録近接性暗号文との間に類似性又は概算類似性が存在することを示すか否かに拘わらず、認証信号が破棄されるべきか否かを決定する。
【０２３９】
アクセス制限テーブル１８００では、一例として、Ｋａ−ｘは、検証キーＫａを割り当てられているユーザ装置１３０２−１が、検証キーＫｘを割り当てられている認証サーバ１４０−１からの近接性検証結果にアクセスできることを示す。同様に、一例として、Ｋａ−ｙは、検証キーＫａを割り当てられているユーザ装置１３０２−１が、検証キーＫｙを割り当てられている認証サーバ１４０−２からの近接性検証結果にアクセスできることを示す。したがって、これらの例では、ユーザ装置１３０２−１は、近接性検証結果にアクセスし、認証サーバ１４０−１及び１４０−２から、近接性暗号文と登録近接性暗号文との間に近接性又は概算近似性が存在するか否かを示す認証信号を受信することを許可される。
【０２４０】
他方で、アクセス制限テーブル１８００では、検証キーＫｂ及びＫｚの組合せにおけるＸは、検証キーＫｂを割り当てられているユーザ装置１３０２−２が、検証キーＫｚを割り当てられている認証サーバ１４０−３からの近接性検証結果にアクセスすることを拒否されることを示す。本例では、ユーザ装置１３０２−２は、認証信号が近接性暗号文と登録近接性暗号文との間に類似性又は概算類似性が存在することを示すか否かに拘わらず、認証サーバ１４０−３から認証信号を受信することを許されない。
【０２４１】
したがって、各々のユーザ装置からの各々の認証サーバのデータベースへのアクセス可能性は、アクセス制限テーブルに基づき制御され得る。
【０２４２】
図２４は、更に別の例示的な動作環境のブロック図である。図２４では、図１６の対応する部分と同じ部分は、同じ参照符号により示され、その説明は省略される。図２４に図示した動作環境１３００−２では、図１６に図示した複数の認証サーバ１４０−１、．．．、１４０−Ｍの機能は、ユーザ（又はオペレータ）１５２により操作され得る単一の認証サーバ１４０に統合される。さらに、複数のデータベース１１２Ｂ−１は、単一のデータベース１１２Ｂに統合される。
【０２４３】
図２５は、更なる例示的な動作環境のブロック図である。図２５では、図１６の対応する部分と同じ部分は、同じ参照符号により示され、その説明は省略される。図２５に図示する動作環境１３００−３では、図１６に図示した信頼できるエンティティサーバ１１０８は省略される。さらに、ユーザ装置１３０２−１、．．．、１３０２−Ｌの各々は、信頼できるエンティティサーバ１１０８のキー生成モジュール１１１８と同様であっても良いキー生成モジュール１１１８Ａを設けられる。さらに、認証サーバ１４０−１、．．．、１４０−Ｍの各々は、関係キーを生成するために、関係キー生成モジュール１１１８Ｂを設けられる。
【０２４４】
本願明細書に記載した実施形態は、以下に更に詳細に議論するように、種々のコンピュータハードウェア又はソフトウェアモジュールを備えた特定用途又は汎用コンピュータの使用を含み得る。
【０２４５】
本願明細書に記載した実施形態は、コンピュータにより実行可能な命令又はデータ構造を伝える又は格納しているコンピュータ可読媒体を用いて実施され得る。このようなコンピュータ可読媒体は、汎用又は特定目的コンピュータによりアクセスできる利用可能な媒体であり得る。例として且つ限定ではなく、このようなコンピュータ可読媒体は、ＲＡＭ（Random  Access  Memory）、ＲＯＭ（Read−Only  Memory）、ＥＥＰＲＯＭ（Electrically  Erasable  Programmable  Read−Only  Memory）、ＣＤ−ＲＯＭ（Compact  Disc  Read−Only  Memory）又は他の光ディスク記憶装置、磁気ディスク記憶装置又は他の磁気記憶装置、フラッシュメモリ装置（例えば、固体メモリ素子）を含む非一時的コンピュータ可読記憶媒体、又はコンピュータにより実行可能な命令若しくはデータ構造の形式で所望のプログラムコード手段を伝える若しくは格納するために用いられ汎用若しくは特定目的コンピュータによりアクセス可能な他の媒体を有し得る。上述の組合せも、コンピュータ可読媒体の範囲に包含され得る。
【０２４６】
コンピュータにより実行可能な命令は、例えば、汎用コンピュータ、特定目的コンピュータ（例えば、１又は複数のプロセッサ）又は特定目的処理装置に特定の機能又は機能グループを実行させる命令及びデータを有する。本発明の主題は構造的特徴及び／又は方法論的動作に特有の言葉で記載されたが、本発明の主題は、特許請求の範囲に定められる上述の特定の特徴又は動作に限定されないことが理解されるべきである。むしろ、上述の特定の特徴及び動作は、特許請求の範囲の実施の例示的形態として開示されたものである。
【０２４７】
本願明細書で用いられるように、用語「モジュール」又は「コンポーネント」は、モジュール若しくはコンポーネントの動作を実行するよう構成される特定ハードウェア実装、及び／又はコンピューティングシステムの汎用ハードウェア（例えばコンピュータ可読媒体、処理装置、等）に格納され及び／又はそれらにより実行され得るソフトウェアオブジェクト若しくはソフトウェアルーチンを表しても良い。幾つかの実施形態では、本願明細書に記載されたのと異なるコンポーネント、モジュール、エンジン及びサービスは、（例えば、別個のスレッドとして）コンピューティングシステムで実行されるオブジェクト又は処理として実施されても良い。本願明細書に記載のシステム及び方法の幾つかは概して（汎用ハードウェアに格納される及び／又はそれにより実行される）ソフトウェアで実装されるように記載されたが、専用ハードウェアの実装又はソフトウェアと専用ハードウェアの組み合わせの実装も可能であり考えられる。本説明では、「コンピュータエンティティ」は、本願明細書で先に定められたようにコンピューティングシステム、又はコンピューティングシステムで実行されるモジュール若しくはモジュールの組合せであっても良い。
【０２４８】
上述の説明は、実施形態を説明するために「決定する」等の用語を用いたが、このような用語は、実行される実際の動作の抽象概念である。したがって、当業者に明らかなように、このような用語に対応する実際の動作は、実装に依存して変化しても良い。
【０２４９】
例は例えば「第１の」、「第２の」、「第３の」、「第４の」、「第５の」、又は「第６の」により番号付けられたが、序数は例の優先度を示さない。多くの他の変形及び変更が当業者に明らかである。
【０２５０】
本願明細書に記載された全ての例及び条件文は、教育上の目的で、読者が本開示の原理及び発明者により考案された概念を理解するのを助け、技術を促進させるためであり、これらの特に記載された例及び条件に限定されないものと考えられるべきである。本開示の実施形態が詳細に記載されたが、種々の変更、置換及び修正が本開示の精神及び範囲から逸脱することなく行われうることが理解されるべきである。
【０２５１】
以上の実施形態に加えて、更に以下の付記を開示する。
（付記１）  関係暗号化を用いる近接性検証の方法であって、
セキュリティパラメータに関連するランダム化レベルに処理され且つ関係線形性暗号化方式を用いて暗号化された情報を表す線形性暗号文を受信するステップと、
線形性関係秘密キーを用いて、前記線形性暗号文と登録線形性暗号文との間の線形性関係を決定するステップと、
前記ランダム化レベルに処理され且つ関係近接性暗号化方式を用いて暗号化された前記情報を表す近接性暗号文を受信するステップと、
近接性関係秘密キーを用いて、前記近接性暗号文と登録近接性暗号文との間の近接性関係を決定するステップと、
前記セキュリティパラメータ、前記線形性関係、及び前記近接性関係に基づき、前記近接性暗号文と前記登録近接性暗号文との間の概算類似性を決定するステップと、
ユーザ装置に割り当てられた第１の検証キーと複数の認証サーバのうちの１つに割り当てられた第２の検証キーとの組合せが、前記概算類似性を決定するステップの結果にアクセスすることを許す場合に、前記複数の認証サーバのうちの前記１つから前記ユーザ装置へ、前記近接性暗号文と前記登録近接性暗号文との間の前記概算類似性が存在するか否かを示す認証信号を通信し、前記第１及び第２の検証キーの前記組合せが前記概算類似性を決定するステップの結果にアクセスすることを許さない場合に、前記認証信号が、前記近接性暗号文と前記登録近接性暗号文との間に前記概算類似性が存在することを示すか否かに拘わらず、前記ユーザ装置に前記認証信号を通信しないステップと、
を有する方法。
（付記２）  第２の線形性暗号文及び第２の近接性暗号文を受信するステップと、
前記第２の線形性暗号文を前記登録線形性暗号文として格納するステップと、
前記第２の近接性暗号文を前記登録近接性暗号文として格納するステップと、
前記線形性関係秘密キー及び前記近接性関係秘密キーを受信するステップと、
を更に有する付記１に記載の方法。
（付記３）  前記ユーザ装置により、信頼できるエンティティサーバから前記第１の検証キーを受信するステップと、
前記信頼できるエンティティサーバから、前記第２の検証キーを受信するステップと、
を更に有する付記１に記載の方法。
（付記４）  前記情報は、複数のデータアイテム又は単一のデータアイテムの複数のセグメントの組合せを有する、付記１に記載の方法。
（付記５）  前記情報は、医療及び生物学的情報、技術情報、金融情報のうちの１つに関連する、付記１に記載の方法。
（付記６）  前記医療及び生物学的情報は、臨床データ、健康データ、及び遺伝子データのうちの１つを含む、付記５に記載の方法。
（付記７）  動作を実行し又は動作の実行を制御するために複数のプロセッサのうちの１つにより実行可能な符号化されたプログラミングコードを有する非一時的コンピュータ可読媒体であって、前記動作は、
セキュリティパラメータに関連するランダム化レベルに処理され且つ関係線形性暗号化方式を用いて暗号化された情報を表す線形性暗号文を受信するステップと、
線形性関係秘密キーを用いて、前記線形性暗号文と登録線形性暗号文との間の線形性関係を決定するステップと、
前記ランダム化レベルに処理され且つ関係近接性暗号化方式を用いて暗号化された前記情報を表す近接性暗号文を受信するステップと、
近接性関係秘密キーを用いて、前記近接性暗号文と登録近接性暗号文との間の近接性関係を決定するステップと、
前記セキュリティパラメータ、前記線形性関係、及び前記近接性関係に基づき、前記近接性暗号文と前記登録近接性暗号文との間の概算類似性を決定するステップと、
ユーザ装置に割り当てられた第１の検証キーと前記複数の認証サーバのうちの１つに割り当てられた第２の検証キーとの組合せが、前記概算類似性を決定するステップの結果にアクセスすることを許す場合に、前記ユーザ装置へ、前記近接性暗号文と前記登録近接性暗号文との間の前記概算類似性が存在するか否かを示す認証信号を通信し、前記第１及び第２の検証キーの前記組合せが前記概算類似性を決定するステップの結果にアクセスすることを許さない場合に、前記認証信号が、前記近接性暗号文と前記登録近接性暗号文との間に前記概算類似性が存在することを示すか否かに拘わらず、前記ユーザ装置に前記認証信号を通信しないステップと、
を有する、非一時的コンピュータ可読媒体。
（付記８）  前記動作は、
第２の線形性暗号文及び第２の近接性暗号文を受信するステップと、
前記第２の線形性暗号文を前記登録線形性暗号文として格納するステップと、
前記第２の近接性暗号文を前記登録近接性暗号文として格納するステップと、
前記線形性関係秘密キー及び前記近接性関係秘密キーを受信するステップと、
を更に有する、付記７に記載の非一時的コンピュータ可読媒体。
（付記９）  前記動作は、
信頼できるエンティティサーバから、前記第１及び第２の検証キーを受信するステップ、
を更に有する、付記７に記載の非一時的コンピュータ可読媒体。
（付記１０）  前記情報は、複数のデータアイテム又は単一のデータアイテムの複数のセグメントの組合せを有する、付記７に記載の非一時的コンピュータ可読媒体。
（付記１１）  前記情報は、医療及び生物学的情報、技術情報、金融情報のうちの１つに関連する、付記７に記載の非一時的コンピュータ可読媒体。
（付記１２）  前記医療及び生物学的情報は、臨床データ、健康データ、及び遺伝子データのうちの１つを含む、付記１１に記載の非一時的コンピュータ可読媒体。
（付記１３）  セキュリティパラメータに関連するランダム化レベルに処理され且つ関係線形性暗号化方式を用いて暗号化された医療及び生物学的データを表す線形性暗号文を受信するステップと、
線形性関係秘密キーを用いて、前記線形性暗号文と医療及び生物学的情報を表す登録線形性暗号文との間の線形性関係を決定するステップと、
前記ランダム化レベルに処理され且つ関係近接性暗号化方式を用いて暗号化された前記医療及び生物学的情報を表す近接性暗号文を受信するステップと、
近接性関係秘密キーを用いて、前記近接性暗号文と医療及び生物学的情報を表す登録近接性暗号文との間の近接性関係を決定するステップと、
前記セキュリティパラメータ、前記線形性関係、及び前記近接性関係に基づき、前記近接性暗号文と前記登録近接性暗号文との間の概算類似性を決定するステップと、
を有する方法。
（付記１４）  前記医療及び生物学的情報は、臨床データ、健康データ、及び遺伝子データのうちの１つを含む、付記１３に記載の方法。
（付記１５）  動作を実行し又は動作の実行を制御するためにプロセッサにより実行可能な符号化されたプログラミングコードを有する非一時的コンピュータ可読媒体であって、前記動作は、
セキュリティパラメータに関連するランダム化レベルに処理され且つ関係線形性暗号化方式を用いて暗号化された医療及びバイオメトリック情報を表す線形性暗号文を受信するステップと、
線形性関係秘密キーを用いて、前記線形性暗号文と医療及びバイオメトリック情報を表す登録線形性暗号文との間の線形性関係を決定するステップと、
前記ランダム化レベルに処理され且つ関係近接性暗号化方式を用いて暗号化された前記医療及びバイオメトリック情報を表す近接性暗号文を受信するステップと、
近接性関係秘密キーを用いて、前記近接性暗号文と医療及びバイオメトリック情報を表す登録近接性暗号文との間の近接性関係を決定するステップと、
前記セキュリティパラメータ、前記線形性関係、及び前記近接性関係に基づき、前記近接性暗号文と前記登録近接性暗号文との間の概算類似性を決定するステップと、
を有する、非一時的コンピュータ可読媒体。
（付記１６）  前記医療及び生物学的情報は、臨床データ、健康データ、及び遺伝子データのうちの１つを含む、付記１５に記載の非一時的コンピュータ可読媒体。
（付記１７）  医療及び生物学的情報を受信するステップと、
平文ベクトルとしてランダム化レベルに前記医療及び生物学的情報を処理するステップであって、前記ランダム化レベルはセキュリティパラメータに関連付けられる、ステップと、
前記平文ベクトルを表す線形性暗号文を生成するために、関係線形性暗号化方式を用いて前記平文ベクトルを暗号化するステップと、
前記平文ベクトルを表す近接性暗号文を生成するために、関係近接性暗号化方式を用いて前記平文ベクトルを暗号化するステップと、
前記線形性暗号文及び前記近接性暗号文を認証サーバに通信するステップと、
前記認証サーバから、関係線形性キーを用いて決定された前記線形性暗号文と登録線形性暗号文との間の線形性関係と、医療及びバイオメトリック情報を表し且つ関係近接性キーを用いて決定された前記近接性暗号文及び登録近接性暗号文の間の近接性と、を示す前記セキュリティパラメータに基づく認証信号を受信するステップと、
を有する方法。
（付記１８）  前記医療及び生物学的情報は、臨床データ、健康データ、及び遺伝子データのうちの１つを含む、付記１７に記載の方法。
【符号の説明】
【０２５２】
１００  動作環境
１０２  ユーザ装置
１０７  ネットワーク
１０８  関係認証モジュール
１１０  関係暗号化／復号化モジュール
１２２  メモリ
１１４  近接性暗号化／復号化モジュール
１１６  通信モジュール
１２４  プロセッサ
１２６  通信ユニット
１２８  近接性認証モジュール
１３０  登録暗号文
１３２  線形性認証モジュール
１３４  サーバ通信モジュール
１４０  認証サーバ
１４２Ａ  第１の平文ベクトル
１４２Ｂ  第２の平文ベクトル
１４４  設定モジュール
１５０  第２のエンティティ
１５２  第１のエンティティ
【図１】
0006805584.tif 000021
【図２】
0006805584.tif 000022
【図３】
0006805584.tif 000023
【図４Ａ】
0006805584.tif 000024
【図４Ｂ】
0006805584.tif 000025
【図５】
0006805584.tif 000026
【図６】
0006805584.tif 000027
【図７】
0006805584.tif 000028
【図８】
0006805584.tif 000029
【図９】
0006805584.tif 000030
【図１０】
0006805584.tif 000031
【図１１】
0006805584.tif 000032
【図１２】
0006805584.tif 000033
【図１３】
0006805584.tif 000034
【図１４】
0006805584.tif 000035
【図１５】
0006805584.tif 000036
【図１６】
0006805584.tif 000037
【図１７】
0006805584.tif 000038
【図１８】
0006805584.tif 000039
【図１９】
0006805584.tif 000040
【図２０】
0006805584.tif 000041
【図２１】
0006805584.tif 000042
【図２２】
0006805584.tif 000043
【図２３】
0006805584.tif 000044
【図２４】
0006805584.tif 000045
【図２５】
0006805584.tif 000046