図面 (/)

この項目の情報は公開日時点(2015年12月14日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (14)

課題

プライバシィを保護した生体認証システムを提供する。

解決手段

リレーショナル線形暗号により暗号化した第1生体テンプレートを表す第1線形暗号テキストを受信し302、リレーショナル線形暗号により暗号化した第2生体テンプレートを表す第2線形暗号テキストを受信し310、線形リレーショナル秘密キーを使用して、第1線形暗号テキストと第2線形暗号テキスト間の線形関係発見する314。更に、リレーショナル近似暗号により暗号化した第1生体テンプレートを表す第1近似暗号テキストを受信し304、リレーショナル近似暗号化スキームにより暗号化した第2生体テンプレートを表す第2近似暗号テキストを受信し312、近似リレーショナル秘密キーを使用して、ハミング距離に関して第1近似暗号テキストと第2近似暗号テキスト間の近似を検出し316、近似および線形関係に基づいてユーザの特定を認証する318。

概要

背景

ユーザ認証(user authentication)の形式は、生体(biometric)認証を含む。生体認証は、一般にユーザに固有のユーザの生体特性の測定を有する。測定された生体特性またはその表現は、次いでユーザの特定を認証する基礎として使用される。生体特性は、ユーザの指紋虹彩静脈デオキシリボ核酸(deoxyribonucleic acid)(DNA)等を有する。生体特性は、パスワードを思い出すこと無しにユーザが認証されるのを可能にするという利点を有する。生体特性は変更不能であるため、生体認証システムでは、プライバシィが重要である。

ここで請求する主題は、上記のような欠点を解決またはそのような環境においてのみ動作する実施形態に限定されない。むしろ、この背景は、ここで説明するいくつかの実施形態が実行される技術分野の一例を説明するためにのみ提供される。

概要

プライバシィを保護した生体認証システムを提供する。リレーショナル線形暗号により暗号化した第1生体テンプレートを表す第1線形暗号テキストを受信し302、リレーショナル線形暗号により暗号化した第2生体テンプレートを表す第2線形暗号テキストを受信し310、線形リレーショナル秘密キーを使用して、第1線形暗号テキストと第2線形暗号テキスト間の線形関係発見する314。更に、リレーショナル近似暗号により暗号化した第1生体テンプレートを表す第1近似暗号テキストを受信し304、リレーショナル近似暗号化スキームにより暗号化した第2生体テンプレートを表す第2近似暗号テキストを受信し312、近似リレーショナル秘密キーを使用して、ハミング距離に関して第1近似暗号テキストと第2近似暗号テキスト間の近似を検出し316、近似および線形関係に基づいてユーザの特定を認証する318。

目的

いくつかの生体認証システムにおいて、安全な生体認証システムを提供する

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

リレーショナル線形暗号化スキームを使用して暗号化した第1生体テンプレートを表す第1線形暗号テキストを受信し、前記リレーショナル線形暗号化スキームを使用して暗号化した第2生体テンプレートを表す第2線形暗号テキストを受信し、線形リレーショナル秘密キーを使用して、前記第1線形暗号テキストと前記第2線形暗号テキスト間の線形関係発見し、リレーショナル近似暗号化スキームを使用して暗号化した前記第1生体テンプレートを表す第1近似暗号テキストを受信し、前記リレーショナル近似暗号化スキームを使用して暗号化した前記第2生体テンプレートを表す第2近似暗号テキストを受信し、近似リレーショナル秘密キーを使用して、ハミング距離に関する前記第1近似暗号テキストと前記第2近似暗号テキスト間の近似を検出し、そして前記近似および前記線形関係に基づいてユーザの特定を認証する、方法。

請求項2

さらに、前記第1線形暗号テキストおよび前記第1近似暗号テキストを登録暗号テキストとして記憶し、そして前記線形リレーショナル秘密キーおよび前記近似リレーショナル秘密キーを受信する、請求項1に記載の方法。

請求項3

前記第1生体テンプレートおよび前記第2生体テンプレートは、ビットベクトルを有し、前記発見は、特別なベクトルを、ゼロと1の要素、および線形秘密キーの長さである特別な数のディメンジョンを有する第1フィールドメンバとして定義し、前記線形リレーショナル秘密キーの累乗まで累乗された前記第1線形暗号テキストの第1要素および前記第2線形暗号テキストの第1要素の対関数として第1の値を計算し、前記特別なベクトルの対応する要素の累乗まで累乗された数の負数の累乗まで累乗された前記第1線形暗号テキストの各要素および前記第2線形暗号テキストの対応する要素の対関数の積として第2の値を計算し、前記第1の値が前記第2の値に等しいか決定し、そして前記第1の値が前記第2の値に等しいことに応答して、前記第1線形暗号テキストが前記第2線形暗号テキストに対して線形であると結論付ける、請求項1に記載の方法。

請求項4

前記第1生体テンプレートおよび前記第2生体テンプレートは、p-aryベクトルを有し、前記発見は、特別なベクトルを、ゼロからベース数(p)より小さい値までの要素、および線形秘密キーの長さである特別な数のディメンジョンを有する第2フィールドのメンバとして定義し、前記線形リレーショナル秘密キーの累乗まで累乗された前記第1線形暗号テキストの第1要素および前記第2線形暗号テキストの第1要素の対関数として第1の値を計算し、負の1および前記特別なベクトルの対応する要素の積の累乗まで累乗され、ゼロがのぞかれた整数セットのサブグループから選択された任意の生成器の累乗まで累乗された前記第1線形暗号テキストの各要素および前記第2線形暗号テキストの対応する要素の対関数の積として第2の値を計算し、前記第1の値が前記第2の値に等しいか決定し、そして前記第1の値が前記第2の値に等しいことに応答して、前記第1線形暗号テキストが前記第2線形暗号テキストに対して線形であると結論付ける、請求項1に記載の方法。

請求項5

公開キー情報ら線エラー補正コードデコードオペレータ(DECODE)にアクセスし、前記第1近似暗号テキストについてのランダム性の和を復元し、前記DECODEがエラーを返すのに応答して拒絶を出力し、そしてそれ以外で、線形確認アルゴリズムを出力し、前記第1近似暗号テキストについての前記ランダム性の和は、前記DECODEとして定義され、前記DECODEは、入力としてさらにCPA復号アルゴリズムを受信し、前記CPA復号アルゴリズムは、前記CPA秘密キー、および前記第1近似暗号テキストの第1部分と、入力として前記CPA秘密キーおよび前記第2近似暗号テキストの前記第1部分を受信する前記CPA復号アルゴリズムの和を、入力として受信し、前記線形確認アルゴリズムは、前記線形リレーショナル秘密キー、前記第2近似暗号テキストの前記第1部分、前記第2近似暗号テキストの前記第2部分、そしてランダム性の和を、入力として受信する、請求項1に記載の方法。

請求項6

プロセッサが、リレーショナル線形暗号化スキームを使用して暗号化した第1生体テンプレートを表す第1線形暗号テキストを受信し、前記リレーショナル線形暗号化スキームを使用して暗号化した第2生体テンプレートを表す第2線形暗号テキストを受信し、線形リレーショナル秘密キーを使用して、前記第1線形暗号テキストと前記第2線形暗号テキスト間の線形関係を発見し、リレーショナル近似暗号化スキームを使用して暗号化した前記第1生体テンプレートを表す第1近似暗号テキストを受信し、前記リレーショナル近似暗号化スキームを使用して暗号化した前記第2生体テンプレートを表す第2近似暗号テキストを受信し、近似リレーショナル秘密キーを使用して、ハミング距離に関する前記第1近似暗号テキストと前記第2近似暗号テキスト間の近似を検出し、そして前記近似および前記線形関係に基づいてユーザの特定を認証する、動作の実行または実行を制御するように、前記プロセッサにより実行可能なコード化されたプログラミングコードを有する非一時的なコンピュータ読取可能な媒体

請求項7

前記動作は、さらに、前記第1線形暗号テキストおよび前記第1近似暗号テキストを登録暗号テキストとして記憶し、前記線形リレーショナル秘密キーおよび前記近似リレーショナル秘密キーを受信する、請求項6に記載の非一時的なコンピュータ読取可能な媒体。

請求項8

前記第1生体テンプレートおよび前記第2生体テンプレートは、ビットベクトルを有し、前記発見は、特別なベクトルを、ゼロと1の要素、および線形秘密キーの長さである特別な数のディメンジョンを有する第1フィールドのメンバとして定義し、前記線形リレーショナル秘密キーの累乗まで累乗された前記第1線形暗号テキストの第1要素および前記第2線形暗号テキストの第1要素の対関数として第1の値を計算し、前記特別なベクトルの対応する要素の累乗まで累乗された数の負数の累乗まで累乗された前記第1線形暗号テキストの各要素および前記第2線形暗号テキストの対応する要素の対関数の積として第2の値を計算し、前記第1の値が前記第2の値に等しいか決定し、そして前記第1の値が前記第2の値に等しいことに応答して、前記第1線形暗号テキストが前記第2線形暗号テキストに対して線形であると結論付ける、請求項6に記載の非一時的なコンピュータ読取可能な媒体。

請求項9

前記第1生体テンプレートおよび前記第2生体テンプレートは、p-aryベクトルを有し、前記発見は、特別なベクトルを、ゼロからベース数(p)より小さい値までの要素、および線形秘密キーの長さである特別な数のディメンジョンを有する第2フィールドのメンバとして定義し、前記線形リレーショナル秘密キーの累乗まで累乗された前記第1線形暗号テキストの第1要素および前記第2線形暗号テキストの第1要素の対関数として第1の値を計算し、負の1および前記特別なベクトルの対応する要素の積の累乗まで累乗され、ゼロがのぞかれた整数セットのサブグループから選択された任意の生成器の累乗まで累乗された前記第1線形暗号テキストの各要素および前記第2線形暗号テキストの対応する要素の対関数の積として第2の値を計算し、前記第1の値が前記第2の値に等しいか決定し、そして前記第1の値が前記第2の値に等しいことに応答して、前記第1線形暗号テキストが前記第2線形暗号テキストに対して線形であると結論付ける、請求項6に記載の非一時的なコンピュータ読取可能な媒体。

請求項10

前記検出は、公開キー情報から線形エラー補正コードのデコードオペレータ(DECODE)にアクセスし、前記第1近似暗号テキストについてのランダム性の和を復元し、前記DECODEがエラーを返すのに応答して拒絶を出力し、そしてそれ以外で、線形確認アルゴリズムを出力し、前記第1近似暗号テキストについての前記ランダム性の和は、前記DECODEとして定義され、前記DECODEは、入力としてさらにCPA復号アルゴリズムを受信し、前記CPA復号アルゴリズムは、前記CPA秘密キー、および前記第1近似暗号テキストの第1部分と、入力として前記CPA秘密キーおよび前記第2近似暗号テキストの前記第1部分を受信する前記CPA復号アルゴリズムの和を、入力として受信し、前記線形確認アルゴリズムは、前記線形リレーショナル秘密キー、前記第2近似暗号テキストの前記第1部分、前記第2近似暗号テキストの前記第2部分、そしてランダム性の和を、入力として受信する、請求項6に記載の非一時的なコンピュータ読取可能な媒体。

請求項11

リレーショナル線形暗号化スキームを使用して第1平文テキストベクトルを暗号化して、前記第1平文テキストベクトルを表す第1線形暗号テキストを生成し、リレーショナル近似暗号化スキームを使用して前記第1平文テキストベクトルを暗号化して、前記第1平文テキストベクトルを表す第1近似暗号テキストを生成し、前記第1線形暗号テキストおよび前記第1近似暗号テキストを認証サーバ通信し、前記リレーショナル線形暗号化スキームを使用して第2平文テキストベクトルを暗号化して、前記第2平文テキストベクトルを表す第2線形暗号テキストを生成し、前記リレーショナル近似暗号化スキームを使用して前記第2平文テキストベクトルを暗号化して、前記第2平文テキストベクトルを表す第2近似暗号テキストを生成し、前記第2線形暗号テキストおよび前記第2近似暗号テキストを前記認証サーバに通信し、前記リレーショナル線形暗号化スキームのリレーショナル線形キーおよび前記リレーショナル近似暗号化スキームのリレーショナル近似キーを前記認証サーバに通信し、前記認証サーバから、前記リレーショナル線形キーを使用した前記第1線形暗号テキストと前記第2線形暗号テキストの間の線形関係、および前記リレーショナル近似キーを使用した前記第1近似暗号テキストと前記第2近似暗号テキストの間の近似を示す認証信号を受信する、方法。

請求項12

前記第1平文テキストベクトルは、ユーザからの登録入力として受信された第1生体テンプレートを有し、前記第2平文テキストベクトルは、ユーザから挑戦入力として受信された第2生体テンプレートを有し、前記認証信号は、前記第2生体テンプレートが前記ユーザを起源とすることを示す、請求項11に記載の方法。

請求項13

さらに、前記リレーショナル線形暗号化スキームのキーを生成することを有し、前記生成は、前記安全パラメータ中の指数関数である素数位数の3つの双一次グループを生成し、前記3つの双一次グループの第1双一次グループの第1生成器をサンプリングし、前記3つの双一次グループの第2双一次グループの第2生成器をサンプリングし、ゼロから前記素数の位数より小さい整数までを含む整数セットから、特別な要素数ランダムにサンプリングすることにより、第1線形秘密キーを生成し、前記整数セットから、前記特別な要素数をランダムにサンプリングすることにより、第2線形秘密キーを生成し、前記第1生成器である要素、および前記第1線形秘密キーの対応する要素の累乗まで累乗された前記第1生成器である1つ以上の他の要素を有する第1線形公開キーを定義する、請求項11に記載の方法。

請求項14

前記第1平文テキストベクトルは、p-aryベクトルを有し、ゼロから前記ベース数より小さい数までの要素および前記特別な数のディメンジョンを有する第2フィールドのメンバであり、前記3つの双一次グループは、前記安全パラメータ内の前記素数の位数の指数関数で、ベース数(p)の1つのモジュールに等しいように生成され、前記第1公開キーは、ゼロを除去した前記整数セットのサブグループの任意の生成器である他の要素を有し、前記第2線形公開キーは、前記任意の生成器である他の要素を有し、前記リレーショナル線形暗号化スキームを使用した前記第1平文テキストベクトルの暗号化は、前記整数セットからのランダム数のサンプリング、および前記第1線形暗号テキストの作成を、有し、前記第1線形暗号テキストは、前記ランダム数の累乗まで累乗された前記第1生成器である第1要素、および線形暗号化の累乗まで累乗された前記第1線形公開キーの対応する要素を有する1つ以上の他の要素を有し、前記線形暗号化の累乗は、前記ランダム数と前記第1平文テキストベクトルの対応する要素の累乗まで累乗された前記任意の生成器の積を有する、請求項13に記載の方法。

請求項15

前記第1平文テキストベクトルは、ビットベクトルを有し、ゼロおよび1の要素および前記特別な数のディメンジョンを有する第1フィールドのメンバであり、前記リレーショナル線形暗号化スキームを使用した前記暗号化は、前記整数セットからのランダム数のサンプリング、および前記第1線形暗号テキストの作成を有し、前記第1線形暗号テキストは、前記ランダム数の累乗まで累乗された前記第生成器である第1要素、および線形暗号化累乗まで累乗された前記第1線形公開キーの対応する要素である1つ以上の他の要素を有し、前記線形暗号化累乗は、前記ランダム数と前記第1平文テキストベクトルの対応する要素の累乗までの累乗された数の負数の積を有する、請求項13に記載の方法。

請求項16

さらに、安全パラメータのための前記リレーショナル近似暗号化スキームのキーを生成することを、有し、前記生成は、長さ、前記安全パラメータの同じ順番におけるランク、および選択された最小距離を有する線形エラー補正コード(ECC)を選択し、CPA(chosen-plaintext attack)公開キーおよびCPA秘密キーを出力するCPA安全暗号化スキームのキー生成アルゴリズムを動作させ、第1線形公開キー、第2線形公開キー、第1線形秘密キー、第2線形秘密キー、およびリレーショナル線形秘密キーを出力するリレーショナル線形キー生成アルゴリズムを動作させ、ECCエンコードオペレータ、ECCデコードオペレータ、前記CPA公開キー、および前記第1線形公開キーとして、第1近似公開キーを定義し、前記ECCエンコードオペレータ、前記ECCデコードオペレータ、前記CPA公開キー、および前記第2線形公開キーとして、第2近似公開キーを定義し、前記CPA秘密キーおよび前記第1線形秘密キーとして、第1近似秘密キーを定義し、前記CPA秘密キーおよび前記第2線形秘密キーとして、第2近似秘密キーを定義し、そして前記CPA秘密キーおよび前記リレーショナル線形秘密キーとして、近似リレーショナル秘密キーを定義する請求項11に記載の方法。

請求項17

前記リレーショナル近似暗号化スキームを使用した前記暗号化は、ベース数および前記ECCのランクであるディメンジョンを有する第3フィールドから近似ランダム数をサンプリングし、前記CPA公開キーおよび前記第1平文テキストベクトルの和を入力として受信するCPA暗号化アルゴリズム、および入力として前記近似ランダム数を受信する前記ECCエンコードオペレータとして、第1近似暗号テキストの第1部分を定義し、前記第1線形公開キーおよび前記近似ランダム数を入力として受信する第1線形暗号化アルゴリズムとして、前記第1近似暗号テキストの第2部分を定義する請求項16に記載の方法。

請求項18

さらに、前記リレーショナル線形暗号化スキームを使用した前記第1線形暗号テキストの復号化を有し、前記復号化は、前記第1平文テキストベクトルの各要素について、前記第1線形暗号テキスト内の対応する要素が、第1線形秘密キーの対応する要素までの累乗された前記第1線形暗号テキストの第1要素に等しいか決定し、前記第1線形暗号テキスト内の対応する前記要素が、前記第1線形秘密キーの前記対応する要素だけ乗じられた負の数までの累乗された前記第1線形暗号テキストの前記第1要素に等しいか決定し、前記第1線形暗号テキスト内の前記対応する要素が他の値に等しいか決定し、前記第1線形暗号テキスト内の前記対応する要素が、前記第1線形秘密キーの前記対応する要素までの累乗された前記第1線形暗号テキストの第1要素に等しいことに応答して、前記第1平文テキストベクトルをゼロに設定し、前記第1線形暗号テキスト内の前記対応する要素が、前記第1線形秘密キーの前記対応する要素だけ乗じられた負の数までの累乗された前記第1線形暗号テキストの前記第1要素に等しいことに応答して、前記第1平文テキストベクトルを1に設定し、前記第1線形暗号テキスト内の前記対応する要素が、他の値に等しいことに応答して、エラーを返信する、請求項11に記載の方法。

請求項19

さらに、前記リレーショナル線形暗号化スキームを使用した前記第1線形暗号テキストの復号化を有し、前記復号化は、前記第1平文テキストベクトルの各要素について、前記第1線形暗号テキスト内の対応する要素が、前記特別な要素値までの累乗された前記任意の生成器と前記第1線形秘密キーの対応する要素の積までの累乗された前記第1線形暗号テキストの第1要素に等しいか決定し、前記特別な値の存在に応答して、前記要素を前記特別な値に設定し、そして前記特別な値が存在しないのに応答して、エラーを出力し、前記特別な要素値は、前記リレーショナル線形暗号化スキームおよび第2フィールドのメンバの安全パラメータにおける多項式により、範囲が制限される、請求項11に記載の方法。

請求項20

さらに、前記リレーショナル近似暗号化スキームを使用した前記第1線形暗号テキストの復号化を有し、前記復号化は、CPA秘密キーおよび前記第1近似暗号テキストの第1部分を入力として受信する選択された平文テキスト攻撃(CPA)復号アルゴリズム、および第1線形秘密キーおよび前記第1近似暗号テキストの第2部分を入力として受信する第1線形復号アルゴリズムの和をとして、前記第1平文テキストベクトルを作成することを有する、請求項11に記載の方法。

技術分野

0001

ここで説明する実施形態は、リレーショナル(関係)(relational)暗号化(encryption)に関する。

背景技術

0002

ユーザ認証(user authentication)の形式は、生体(biometric)認証を含む。生体認証は、一般にユーザに固有のユーザの生体特性の測定を有する。測定された生体特性またはその表現は、次いでユーザの特定を認証する基礎として使用される。生体特性は、ユーザの指紋虹彩静脈デオキシリボ核酸(deoxyribonucleic acid)(DNA)等を有する。生体特性は、パスワードを思い出すこと無しにユーザが認証されるのを可能にするという利点を有する。生体特性は変更不能であるため、生体認証システムでは、プライバシィが重要である。

0003

ここで請求する主題は、上記のような欠点を解決またはそのような環境においてのみ動作する実施形態に限定されない。むしろ、この背景は、ここで説明するいくつかの実施形態が実行される技術分野の一例を説明するためにのみ提供される。

0004

実施形態の1つの態様によれば、方法は、リレーショナル線形暗号化スキームを使用して暗号化した第1生体テンプレートを表す第1線形暗号テキストを受信することを有する。方法は、リレーショナル線形暗号化スキームを使用して暗号化した第2生体テンプレートを表す第2線形暗号テキストを受信することを有する。方法は、線形リレーショナル秘密キーを使用して、第1線形暗号テキストと第2線形暗号テキスト間の線形関係発見することを有する。方法は、リレーショナル近似暗号化スキームを使用して暗号化した第1生体テンプレートを表す第1近似暗号テキストを受信することを有する。方法は、リレーショナル近似暗号化スキームを使用して暗号化した第2生体テンプレートを表す第2近似暗号テキストを受信することを有する。方法は、近似リレーショナル秘密キーを使用して、ハミング距離に関する第1近似暗号テキストと第2近似暗号テキスト間の近似を検出することを有する。方法は、近似および線形関係に基づいてユーザの特定を認証することを有する。

0005

実施形態の目的および利点は、少なくとも請求範囲で特に指摘された要素、特徴および組合せにより、実現および達成される。

0006

上記の一般的な説明および以下の詳細な説明の両方は、例示および説明のためであり、請求された本発明を限定されるものでないことが理解されるべきである。

0007

例示の実施形態は、付属の図面を使用して、本発明の実施形態の詳細な説明は、付加的な特別な例および詳細により、記述および説明される。

図面の簡単な説明

0008

図1は、例示の動作環境ブロック図である。
図2は、例示の生体認証環境のブロック図である。
図3は、生体認証の例示の方法のフロー図である。
図4Aは、リレーショナル暗号化の例示の方法のフロー図である。
図4Bは、リレーショナル暗号化の例示の方法のフロー図である。
図5は、リレーショナル暗号化スキームにおいて線形関係を発見する例示の方法のフロー図である。
図6は、リレーショナル暗号化スキームにおいて近似を検出する例示の方法のフロー図である。
図7は、リレーショナル線形暗号化スキームのキー生成の例示の方法のフロー図である。
図8は、リレーショナル線形暗号化スキームを使用して第1平文テキストベクトルを暗号化する例示の方法のフロー図である。
図9は、リレーショナル近似暗号化スキームのキー生成の例示の方法のフロー図である。
図10は、リレーショナル近似暗号化スキームを使用して第1平文テキストベクトルを暗号化する例示の方法のフロー図である。
図11は、第1線形暗号テキストを復号する例示の方法のフロー図である。
図12は、第1線形暗号テキストを復号する他の例示の方法のフロー図である。

実施例

0009

生体認証の挑戦(challenge)は、ユーザが認証の基礎として使用される生体特性を変更しないということである。例えば、ユーザの指紋またはユーザの虹彩のようなユーザの固有の特徴の1つ以上を記載した生体データを含む生体テンプレート(template)を登録する。もし生体テンプレートが損傷されたら、ユーザは生体テンプレートにより記載された固有の特徴を変更できない。したがって、一旦損傷すると、他の生体テンプレートが登録されるか、または他の生体特性の生体テンプレートが登録される。少なくともこの理由で、生体認証システムは、強力なプライバシィ保証に役立つ。

0010

いくつかの生体認証システムにおいて、安全な生体認証システムを提供するための各種のアプローチが試みられてきた。例えば、いくつかの生体認証システムは、「特徴変換(feature transformation)アプローチ」、「生体暗号システム(biometric cryptosystem)アプローチ」および/または「異体同形(homomorphic)暗号化アプローチ」を実現する。しかし、これらのアプローチのそれぞれは、生体テンプレート、クライアント特定キー公開キーなどのようなそれぞれ損傷するかもしれない情報の通信に少なくとも部分的に起因する制限されたプライバシィおよび安全性を提供する。

0011

したがって、ここで議論するいくつかの実施形態は、プライバシィ保護の生体認証に関係する。プライバシィ保護の生体認証は、リレーショナル(関係)暗号化に基づく。リレーショナル暗号化は、認証者が平文テキスト復元することまたは純粋な暗号テキストと特別な関係を有する不正な暗号テキストを生成することを可能にすること無しに、暗号テキスト間の関係を、認証者が発見するのを可能にする。例えば、例示の実施形態は、生体認証の1つの方法を有する。この方法は、登録入力を受信することを有する。登録入力は、ユーザの第1生体テンプレートを有する。第1生体テンプレートは、ユーザの生体特性の固有の特徴を表す。この方法は、リレーショナル暗号化スキーム(scheme)にしたがって第1線形暗号テキストおよび第1近似暗号テキストを生成することを有する。この方法は、第1線形暗号テキストおよび第1近似暗号テキストを認証サーバに通信することを有する。この方法は、挑戦(challenge)入力を受信することを有する。挑戦入力は、第2生体テンプレートを有する。第2生体テンプレートは、ユーザの生体特性の1つ以上の固有の特徴を表す。この方法は、リレーショナル暗号化スキームにしたがって第2線形暗号テキストおよび第2近似暗号テキストを生成することを有する。この方法は、第2線形暗号テキストおよび第2近似暗号テキストを認証サーバに通信することを有する。認証サーバは、第1と第2線形暗号テキスト間の線形関係性を発見し、第1と第2近似暗号テキスト間の近似を検出する。この方法は、認証サーバから、認証決定を示す信号を受け取ることを有する。認証決定は、線形関係性および/または近似が存在するか否かに基づく。本発明の実施形態は、付属の図面を参照して説明される。

0012

図1は、ここで説明する少なくとも1つの実施形態にしたがって配置された例示の動作環境100のブロック図である。動作環境100では、リレーショナル暗号化が実行される。リレーショナル暗号化は、第1エンティティ(entity)152が第2エンティティ150により提供された2つ以上の暗号化テキスト中で1つ以上の関係性を決定するのを可能にする暗号プリミティブを有する。特に、リレーショナル暗号化は、第1エンティティ152が、2つ以上の暗号テキスト間の線形関係性を発見し、1つ以上の暗号テキスト間の近似を検出するのを可能にする。さらに、リレーショナル暗号化は、第1エンティティ152が、暗号テキストから平文テキストを復元し、特別な純粋の暗号テキストと特別な関係を有する不正な暗号テキストを生成することを許可しない。

0013

リレーショナル暗号化は、各種の環境で実現される。例えば、リレーショナル暗号化は、個人がその居場所秘密にすることを望むが、半信頼サービス(semi-trusted service)が居場所間の近似を検出可能である社会環境で実現される。さらに、リレーショナル暗号化は、画像比較環境で実現される。近似が、データベースからの画像間で検出され、画像間の類似性を決定する。画像のプライバシィは維持される。ユーザは、データベース上に画像を公開すること無しに、リレーショナル暗号化を使用して画像をサーチする。さらに、リレーショナル暗号化は、私的データ記憶環境でも実現される。ユーザは、そのデータを暗号化し、暗号化データをデータベースに通信する。解析(例えば、記憶、分類等)は、暗号データが復号されるリスク(危険)無しに、暗号データ上で実行される。

0014

例えば、第2エンティティ150は、第1平文テキストベクトル142Aおよび第2平文テキストベクトル142B(一般には、平文ベクトル142または複数の平文ベクトル142)を受信する。平文ベクトル142は、生体テンプレート、位置情報などのようなデータセットを有する。第2エンティティ150は、第1平文テキストベクトル142Aの暗号化バージョンを有する第1暗号テキストを、第1エンティティ152に通信する。その後で、第2エンティティ150は、第2平文テキストベクトル142Bの暗号化バージョンを有する第2暗号テキストを、第1エンティティ152に通信する。第1エンティティ152は、第1暗号テキストと第2暗号テキストの間に線形関係があるか否か見つけ出し、第1暗号テキストと第2暗号テキストの間の近似を検出する。近似は、いくつかの実施形態では、ハミング距離(Hamming distance)についてである。

0015

しかし、リレーショナル暗号化は、第1エンティティ152が、第1および第2暗号テキストから平文テキストベクトルを作成することを許可しない。さらに、リレーショナル暗号化は、第1エンティティ152が、特定の線形関係を有するおよび/または第1暗号テキストおよび/または第2暗号テキストと特別な近似を有する第3暗号テキストベクトルを作成することを許可しない。図1は、2つの平文テキストベクトル142、およびしたがって2つの暗号テキストを有する実施形態を示す。いくつかの実施形態では、2つ以上の平文テキストベクトル142およびしたがって2つ以上の暗号テキストは、動作環境100に含まれる。

0016

リレーショナル暗号化は、1つ以上のリレーショナルキー(鍵)を有する。リレーショナルキーは、公開および/またはサインキーに類似しており、第1エンティティ152により提供または発生される。リレーショナルキーは、暗号テキスト間の関係性の決定を可能にするが、暗号テキストの解読または平文テキストベクトル142の復元を許可しない。さらに、リレーショナルキーは、特別な暗号テキストと特別な関係を有する暗号テキストの作成を許可しない。

0017

いくつかの実施形態では、リレーショナル暗号は、アルゴリズムの組(tuple)を有する関係(リレーション)についてのリレーションナル暗号化スキームにしたがって定義される。アルゴリズムは、キー生成アルゴリズム、第1暗号アルゴリズム、第1復号アルゴリズム、第2暗号アルゴリズム、第2復号アルゴリズム、および確認アルゴリズムを有する。リレーションは、3組のサブセットとして定義される。さらに、リレーションおよびアルゴリズムは、1つ以上の正解条件を満たす。例えば、リレーションは、次の例示の正解条件を満たす。

0018

0019

リレーションナル暗号化スキームは、リレーションナルキーが特別な暗号テキストに特別なリレーションを有する暗号テキストの作成を許可せず、特別な暗号テキストから平文テキストベクトル142の復元を許可しないという意味で、安全である。例えば、リレーションナル暗号化スキームは、もし以下の式を維持するならば安全である。

0020

1.Kx(lλ)が、KeyGen(lλ)を動作させ、次に出力(pkx,skx,pky,sky,skR)および出力(pkx,skx)を取るアルゴリズムである。そして、(Kx,EncX,DecX)はIND-CPAの安全(secure)である。
2.Ky(lλ)が、KeyGen(lλ)を動作させ、次に出力(pkx,skx,pky,sky,skR)および出力(pky,sky)を取るアルゴリズムである。そして、(Ky,EncY,DecY)はIND-CPAの安全(secure)である。
3.KR(lλ)が、KeyGen(lλ)を動作させ、次に出力(pkx,skx,pky,sky,skR)および出力(pkx,skxy,skR)を取るアルゴリズムである。そして、EncX(pkx,・)およびEncY(pky,・)はskRの知識で与えられる一方向の関数である。
上記の式で、pkx,skx,psy,sky,KeyGen,EncX(),λ,およびEncY()は上記と同じである。DecXは第1復号アルゴリズムを表す。DecYは第2復号アルゴリズムを表す。Kx(),Ky(),およびKR()式の通りである。シンボル・はいずれかの値を示す。用語"IND-CPA"は選択平文テキスト攻撃下での識別性の速記法を表す。いくつかの他の実施形態では、(Ky,EncY,DecY)および/または(Kx,EncX,DecX)は、選択暗号テキスト攻撃(例えば、IND-CCA1またはIND-CCA2)または他のいかなる適切な安全計算(metric)の下での識別性のような他の演算安全計算にしたがって安全である。

0021

さらに、いくつかの実施形態では、リレーションナル暗号化スキームは、リレーションナル線形暗号化スキームを有する。リレーションナル線形暗号化スキームは、次に示す例示の線形関係式にしたがってリレーションを定義する。

0022

0023

さらに、いくつかの実施形態では、リレーションナル暗号化スキームは、次の例示の近似式にしたがってリレーションを定義するリレーションナル近似暗号化スキームを有する。

0024

0025

ここで議論するリレーションナル暗号化スキームは、図1の動作環境100で実現される。リレーションナル暗号化スキームは、第2エンティティ150が第1エンティティ152に暗号化した情報を通信するのを可能にし、第1エンティティ152が暗号化された情報中で線形リレーションを発見および/または暗号化された情報間近似度を決定するのを可能にする。

0026

動作環境100は、第2エンティティ150に関係するユーザ装置102および第1エンティティ152に関係する認証サーバ140を有する。ユーザ装置102および認証サーバ140は、動作環境100内で実現され、リレーションナル暗号化を実行する。

0027

ユーザ装置102および認証サーバ140は、ネットワーク107を介してリレーションナル暗号化に関係する情報および/またはデータ(例えば、暗号テキスト、キー、平文ベクトル142等)の生成および通信を可能にする演算装置を有する。ユーザ装置102のいくつかの例は、携帯電話スキャン装置スマートフォンタブレット型コンピュータラップトップコンピュータデスクトップコンピュータ、セット・トップボックスまたは接続装置(例えば、スマートウオッチ、スマートメガネ、スマートペドメータ、または他の接続装置)を有する。認証サーバ140のいくつかの例は、ハードウェアサーバ、またはサーバとして機能するように構成された他のプロセッサベースの演算装置を有する。

0028

ネットワーク107は、有線または無線である。ネットワーク107は、スター構成トークンリング構成、または他の構成を含む多数の構成を有する。さらに、ネットワーク107は、ローカルエリアネットワーク(LAN)、ワイドエリアネットワークWAN)(例えば、インターネット)、および/または複数の装置が通信する他の相互接続データパスを有する。いくつかの例では、ネットワーク107は、ピアツゥ−ピア(peer-to-peer)ネットワークを有する。ネットワーク107は、各種の異なる通信プロトコルでデータを送信する電話通信ネットワークに結合されてもまたはその一部を有してもよい。いくつかの例では、ネットワーク107は、BLUETOOTH(登録商標通信ネットワークまたはショートメッセージサービスSMS)、マルチメディアメッセージサービスMMS)、ハイパーテキスト送信プロトコルHTTP),直接データ接続無線アプリケーションプロトコル(WAP)、e-mail等を介してデータの送受信を行うセルラー通信ネットワークを有する。

0029

ユーザ装置102は、リレーショナル暗号/復号モジュール(enc/dec module)110、プロセッサ124A、メモリ122A、および通信ユニット126Aを有する。enc/decモジュール110、プロセッサ124A、メモリ122A、および通信ユニット126Aは、バス120Aを介して接続されている。認証サーバ140は、リレーショナル認証モジュール108、プロセッサ124B、メモリ122B、および通信ユニット126Bを有する。リレーショナル認証モジュール108、プロセッサ124B、メモリ122B、および通信ユニット126Bは、バス120Bを介して接続されている。

0030

プロセッサ124Aおよび124Bは、ここでは一般に、プロセッサ124またはプロセッサ群124として言及され、メモリ122Aおよび122Bは、ここでは一般に、メモリ122として言及され、通信ユニット126Aおよび126Bは、ここでは一般に、通信ユニット126または通信ユニット群126として言及され、バス120Aおよび120Bは、ここでは一般に、バス120またはバス群120として言及される。

0031

プロセッサ124は、アリスティック論理ユニット(ALU)、マイクロプロセッサ汎用コントローラ、または演算およびプライバシィ保護を実行する他のプロセッサアレイを有する。プロセッサ124は、バス120に接続され、他の要素(例えば、108、110、122、および126)と通信する。プロセッサ124は、一般にデータ信号を処理し、コンプレックス命令セットコンピュータ(complex instruction set computer:CISC)アーキテクチャリデュース命令セットコンピュータ(reduced instruction set computer:RISC)アーキテクチャ、または命令セットの組み合わせを組み込んだアーキテクチャを含む各種のコンピューティングアーキテクチャを有する。図1において、ユーザ装置102および認証サーバ140は、単一プロセッサ124を有する。しかし、ユーザ装置102および/または認証サーバ140は、多重プロセッサを有してもよい。他のプロセッサ、オペレーティングシステム、および物理的な構成も可能である。

0032

メモリ122は、1つ以上のプロセッサ124により実行される命令および/またはデータを記憶する。メモリ122は、他の要素との通信のため、バス120に接続される。命令および/またはデータは、ここで説明する技術または方法を実行するためのコードを有する。メモリ122は、DRAMメモリ装置、SRAMメモリ装置、フラッシュメモリ、またはいくつかのの他のメモリ装置を有する。いくつかの実施形態では、メモリ122は、不揮発性メモリまたは類似の永久記憶装置、およびハードディスクドライブフロッピー(登録商標)ディスクドライブCD−ROM装置、DVD−ROM装置、DVD−RAM装置、DVD−RW装置フラッシュメモリ装置、またはより永久的な基礎技術で情報を記憶する他の大容量装置を含む媒体を有する。

0033

通信ユニット126は、ユーザ装置102および/または認証サーバ140の1つ以上にデータを送信するかまたはそれからデータを受信するように構成される。通信ユニット126は、バス120に接続される。いくつかの実施形態では、通信ユニット126は、ネットワーク107への直接の物理的な接続用ポートまたは他の通信チャネルを有する。例えば、通信ユニット126は、図1オペレーティング環境100の要素との有線通信のためのUSB、SD、CAT−5、または類似のポートを有する。いくつかの実施形態では、通信ユニット126は、IEEE 802.11,IEEE 802.16,BLUETOOTH(登録商標)、または他の適当な無線通信方法を含む1つ以上の無線通信方法を使用する通信チャネルを介してデータを交換するための無線トランシーバを有する。

0034

いくつかの実施形態では、通信ユニット126は、SMS、MMS、HTTP、直接データ接続、WAP、e-mail、または他の適切な型式電子通信を介することを含むセルラー通信ネットワーク上で、データの送信および受信のためのセルラー通信トランシーバを有する。いくつかの実施形態では、通信ユニット126は、有線ポートおよび無線トランシーバを有する。通信ユニット126は、送信制御プロトコル/インターネットプロトコル(TCP/IP)、HTTP、HTTPセキュア(HTTPS)、および単純なメール送信プロトコル(SMTP)等を含む標準ネットワークプロトコルを使用して、ファイルおよび/または媒体対象物を分配するためのネットワーク107への他の接続を提供もする。

0035

enc/decモジュール110は、上記で定義したリレーショナル暗号化スキームまたは上記で議論した特徴の1つ以上を有するようなリレーショナル暗号化スキームをセットアップするように構成される。enc/decモジュール110は、平文テキストベクトル142を受信し、平文テキストベクトル142を暗号化し、暗号テキストをネットワーク107を介して認証サーバ140に通信する。さらに、enc/decモジュール110は、暗号テキストを復号して1つ以上の平文テキストベクトル142を作成するように構成されている。enc/decモジュール110が暗号化および/または復号化処理を実行するように構成された実施形態では、enc/decモジュール110は、暗号化および/または復号化アルゴリズムおよび/またはここで議論した暗号化および/または復号化キーを使用して、暗号化および/または復号化処理を実行する。

0036

enc/decモジュール110がリレーショナル暗号化スキームをセットアップするように構成されるいくつかの実施形態では、enc/decモジュール110は、1つ以上のリレーショナル秘密キーおよび/または確認アルゴリズムを、認証サーバ140のリレーショナル認証モジュール108に通信するように構成されている。いくつかの実施形態では、リレーショナル認証モジュール108は、リレーショナル秘密キーおよび/または確認アルゴリズムをローカルに生成する、および/またはリレーショナル秘密キーおよび/または確認アルゴリズムを他のソースから取得する。

0037

リレーショナル認証モジュール108は、暗号テキスト、リレーショナル秘密キー、確認アルゴリズム、またはそれらの組み合わせを、enc/decモジュール110または他のソースから受信するように構成されている。次に、リレーショナル認証モジュール108は、暗号テキスト間に線形関係を発見するか、および/または暗号テキスト間に近似を検出する。リレーショナル認証モジュール108は、リレーショナル秘密キーおよび/または確認アルゴリズムを使用して、暗号テキスト間に線形関係を発見すると共に近似を検出する。

0038

図1の動作環境100において、enc/decモジュール110は、線形暗号化/復号化モジュール112、近似暗号化/復号化モジュール114、通信モジュール116、およびセットアップモジュール144を有する。さらに、リレーショナル認証モジュール108は、サーバ通信モジュール134、線形認証モジュール132、および近似認証モジュール128を有する。いくつかの実施形態では、セットアップモジュール144またはセットアップモジュール144に属する1つ以上の動作を実行するように構成されたモジュールは、リレーショナル認証モジュール108内に含まれる。

0039

enc/decモジュール110、線形暗号化/復号化モジュール112、近似暗号化/復号化モジュール114、通信モジュール116、セットアップモジュール144、リレーショナル認証モジュール108、サーバ通信モジュール134、線形認証モジュール132、および近似認証モジュール128は、まとめてリレーショナルモジュールとして言及される。リレーショナルモジュールの1つ以上は、ここで説明した1つ以上の動作を実行するように構成された1つ以上のルーチンを含むソフトウェアとして実現される。リレーショナルモジュールは、ここで説明した機能を提供するようにプロセッサ124により実行可能な命令セットを有する。いくつかの例では、リレーショナルモジュールは、メモリ122に記憶されるか、少なくとも一時的にメモリ122にロードされ、プロセッサ124の1つ以上によりアクセス可能で実行可能である。リレーショナルモジュールの1つ以上は、バス120の1つ以上を介して、プロセッサ124の1つ以上を協働および通信するように適応されている。

0040

一般的にリレーショナルモジュールを参照すると、通信モジュール116および/またはサーバ通信モジュール134は、enc/decモジュール110またはリレーショナル認証モジュール108と、ユーザ装置102または認証サーバ140(例えば、122、124、および126)の他の要素との間の通信を取り扱うように構成されている。通信モジュール116および/またはサーバ通信モジュール134は、通信ユニット126を介して、ユーザ装置102または認証サーバ140にデータを送信するかまたはそれからデータを受信するように構成されている。いくつかの例では、通信モジュール116および/または通信モジュール134は、他のリレーショナルモジュールと協働し、通信ユニット126を介して、ユーザ装置102または認証サーバ140からデータを受信するおよび/またはそれにデータを送信するように構成されている。

0041

線形暗号化/復号化モジュール112は、平文テキストベクトル142を暗号化して線形暗号テキストを生成することに関係するおよび/または線形暗号テキストの復号化に関係する1つ以上の動作を実行するように構成されている。線形認証モジュール132は、線形暗号テキストに関係する1つ以上の動作を実行するように構成されている。例えば、線形認証モジュール132は、2つ以上の線形暗号テキストの線形関係を発見するように構成されている。

0042

近似暗号化/復号化モジュール114は、平文テキストベクトル142を暗号化して近似暗号テキストを生成することに関係するおよび/または近似暗号テキストの復号化に関係する1つ以上の動作を実行するように構成されている。近似認証モジュール128は、近似暗号テキストに関係する1つ以上の動作を実行するように構成されている。例えば、近似認証モジュール128は、2つ以上の近似暗号テキスト間の近似関係を検出するように構成されている。

0043

セットアップモジュール144は、1つ以上のキー(例えば、公開キー、秘密キー、リレーショナル秘密キー)および/または1つ以上のアルゴリズム(例えば、暗号化アルゴリズム、復号化アルゴリズム、および確認アルゴリズム)を生成するように構成されている。セットアップモジュール144は、次にキーおよびアルゴリズムの1つ以上を、通信モジュール116およびサーバ通信モジュール134を介してリレーショナル認証モジュール108に、または線形暗号化/復号化モジュール112および近似暗号化/復号化モジュール114に通信するように構成されている。

0044

以下のセクションでは、リレーショナル線形暗号化スキームが説明され、それに続いてリレーショナル近似暗号化スキームが説明される。リレーショナル線形暗号化スキームは、ビットベクトルを参照して、次いでp−aryベクトルを参照して説明される。記載のそれぞれにおいて、セットアップモジュール144はキーを生成し、そのキーについてまず説明される。キーを使用して、線形暗号化/復号化モジュール112または近似暗号化/復号化モジュール114は暗号化を実行し、それについてはその次に説明される。暗号テキスト(例えば、線系暗号テキストまたは近似暗号テキスト)は、次に線形認証モジュール132および近似認証モジュール128の1つに通信され、そこで線形関係が発見されるかまたは近似が検出される。最後に、線形暗号化/復号化モジュール112または近似暗号化/復号化モジュール114により実行される暗号テキストの復号が説明される。

0045

リレーショナル線形暗号化スキーム
暗号テキスト間に線形関係を発見するのに含まれる1つ以上の動作では、セットアップモジュール144は、平文テキストベクトル142および/または暗号テキストの要素のベース数に少なくとも部分的に基づく。例えば、要素のベース数は、2つ(例えば、2値またはビットベクトル)を有する。したがって、平文テキストベクトル142および暗号テキストは、ゼロまたは1を含む要素を有する。または、要素のベース数は、3つ(例えば、3次aryベクトル)を有する。したがって、平文テキストベクトル142および暗号テキストは、ゼロ、1または2を含む要素を有する。一般に、ベース数は、変数"p"(例えば、p-aryベクトル)により表される。p-aryベクトルは、ゼロ、1、…p-2、およびp-1を含む要素を有する。リレーショナル線形暗号化スキームは、平文テキストベクトル142および/または暗号テキストがビットベクトルまたはp-aryベクトルであるかに基づいて少し異なる。ビットベクトルのリレーショナル線形暗号化スキームをまず説明し、その次にp-aryベクトルのリレーショナル線形暗号化スキームを説明する。

0046

ビットベクトルまたはp-aryベクトルのリレーショナル線形暗号化スキームにおいて、セットアップモジュール144は、リレーショナル線形暗号化スキームのキーを生成するように構成されている。図示の実施形態では、セットアップモジュール144は、第1線形秘密キー、第2線形秘密キー、第1線形公開キー、第2線形公開キー、および線形リレーショナル秘密キー(合わせて「線形キー」)を生成する。線形キーは、線形暗号テキストを生成し、および線形暗号テキスト間の線形関係を発見するために、平文テキストベクトル142を暗号化するのを使用される。

0047

例えば、第1線形公開キーは、第1線形暗号テキストを生成するために第1平文テキストベクトル142Aを暗号化するのに、線形暗号化/復号化モジュール112により使用される。第1線形暗号テキストは、通信モジュール116により認証サーバ140に通信され、そこで登録暗号テキスト130として記憶される。第2線形公開キーは、第2線形暗号テキストを生成するために第2平文テキストベクトル142Bを暗号化するのに、線形暗号化/復号化モジュール112により使用される。第2線形暗号テキストは、通信モジュール116により認証サーバ140に通信される。線形リレーショナル秘密キーは、第2線形暗号テキストと第1線形暗号テキスト間の線形関係を発見するために、認証サーバ140で、特に線形認証モジュールにより使用され、線形関係は登録暗号テキスト130として記憶される。

0048

第1および第2線形秘密キーは、1つ以上の線形暗号テキストを復号するために、線形暗号化/復号化モジュール112により使用される。例えば、第1線形暗号テキストは、第1秘密キーを使用して復号される。さらに、第1および第2線形秘密キーは、リレーショナル線形キーを生成するために、セットアップモジュール144により使用される。線形キーおよび上記の動作のいくつかの付加的な詳細は、ビットベクトルおよびp-aryベクトル用が以下に提供される。

0049

ビットベクトルリレーショナル線形暗号化スキーム
ビットベクトルが使用される実施形態では、線形キーが安全パラメータ用に生成される。一般に、ここで使用される安全パラメータは、キーの長さに関係する。キーを生成するため、セットアップモジュール144は、素数位数の3つの双一次グループを生成する。素数の位数は、安全パラメータ中の指数関数である。セットアップモジュール144は、3つの双一次グループの第1双一次グループの第1生成器サンプルし、3つの双一次グループの第2双一次グループの第2生成器をサンプルする。

0050

セットアップモジュール144は、整数の組(整数セット)から要素の特別な数をランダムにサンプルすることにより、第1線形秘密キーを生成する。整数セットは、ゼロから、素数の位数の値から1を減算した数までの数を有する。セットアップモジュール144は、整数セットから特別な数の要素をランダムにサンプルすることにより、第2線形秘密キーを生成する。

0051

セットアップモジュール144は、第1線形公開キーを定義する。第1線形公開キーは、第1生成器である要素を有する。第1線形公開キーは、第1線形秘密キーの対応する要素の累乗までの累乗された第1生成器を有する1つ以上の他の要素をさらに有する。いくつかの実施形態では、第1生成器である要素は、第1線形公開キーの第1要素であり、第1線形公開キーは、第1線形公開キーと第1線形秘密キーの間の対応性については計算されない。例えば、これらおよび他の実施形態では、第1線形公開キーの(例えば、第1要素を計算するための)「6番目」の要素は、第1線形秘密キーの5番目の要素の累乗までの累乗である第1生成器を有する。この出願を通して、同様の規定は、要素間の対応性について使用される。

0052

セットアップモジュール144は、第2線形公開キーを定義する。第2線形公開キーは、第2生成器である要素を有する。第2線形公開キーは、第2線形秘密キーの対応する要素の累乗まで累乗された第2生成器を有する1つ以上の他の要素をさらに有する。いくつかの実施形態では、第2生成器である要素は、第2線形公開キーの第1要素であり、それは第2線形公開キーと第2線形秘密キーの要素間の対応性については計算されない。

0053

セットアップモジュール144は、線形リレーショナル秘密キーを定義する。線形リレーショナル秘密キーの各要素は、第2線形秘密キーの対応する要素と第1線形秘密キーの対応する要素の和を有する。例えば、線系リレーショナル秘密キーの5番目の要素は、第1線形秘密キーの5番目の要素と第2線形秘密キーの5番目の要素の和を有する。

0054

いくつかの実施形態では、線形キーの生成は、次の例示の線形ビットベクトルキー方程式に従う。

0055

0056

線形暗号化/復号化モジュール112は、平文テキストベクトル142を暗号化する。線形暗号化/復号化モジュール112は、平文テキストベクトル142を受信する。さらにまたは別に、通信モジュール116は、平文テキストベクトル142を受信し、平文テキストベクトル142を線形暗号化/復号化モジュール112に通信する。

0057

平文テキストベクトル142は、第1フィールドメンバを有する。第1フィールドは、ゼロと、1と、特別な数のディメンジョンと、を有する。フィールドの要素は、要素のベース数により決定される。例えば、ビットベクトルでは、第1フィールドはゼロと1の要素を有し、p-aryベクトルでは、フィールドはゼロ、1、…p-1の要素を有する。

0058

線形暗号化/復号化モジュール112は、整数セットからランダム数をサンプルする。線形暗号化/復号化モジュール112は、次に第1線形暗号テキストおよび第2線形暗号テキストを作成する。第1線形暗号テキストは、ランダム数の累乗まで累乗された第1生成器である第1要素を有する。第1線形暗号テキストは、さらに、線形暗号化累乗まで累乗された第1線形公開キーの対応する要素を有する1つ以上の要素を有する。第1線形暗号テキスト用の線形暗号累乗は、第1平文テキストベクトル142Aの対応する要素の累乗まで累乗された数の負数を乗じたランダム数を有する。いくつかの実施形態では、第1線形暗号テキストの第1要素は、対応性について計算されない。

0059

第2線形暗号テキストは、ランダム数の累乗まで累乗された第2生成器である第1要素を有する。第2線形暗号テキストは、さらに、線形暗号化累乗まで累乗された第2線形公開キーの対応する要素を有する1つ以上の要素を有する。第2線形暗号テキスト用の線形暗号累乗は、第2平文テキストベクトル142Bの対応する要素の累乗まで累乗された数の負数を乗じたランダム数を有する。いくつかの実施形態では、第2線形暗号テキストの第1要素は、対応性について計算されない。

0060

いくつかの実施形態では、線形暗号化/復号化モジュール112は、次の例示の線形ビットベクトル暗号化方程式にしたがって、平文テキストベクトル142を暗号化する。

0061

0062

線形ビットベクトル暗号化方程式において、<>,cx,cy,g0,h0,gi,hi,i,およびnは上記の通りである。さらに、線形ビットベクトル暗号化方程式において、パラメータcxは第1線形暗号テキストを表し、パラメータcyは第2線形暗号テキストを表す。パラメータmIは第1平文テキストベクトル142Aを表す。パラメータmIiは第1平文テキストベクトル142Aの要素を表す。パラメータm2は第2平文テキストベクトル142Bを表す。パラメータm2iは第2平文テキストベクトル142Bの要素を表す。パラメータFは第1フィールドを表す。フィールドの次の添え字は第1フィールドのベース数を表す。第1フィールドの次の添え字nは第1フィールドのディメンジョンを表す。

0063

線形ビットベクトル暗号化方程式は、上記で議論した第1暗号化アルゴリズム(EncX)および第2暗号化アルゴリズム(EncY)を定義する。例えば、第1暗号化アルゴリズムは、第1平文テキストベクトル142Aおよび第1線形公開キーを与えると、第1暗号化アルゴリズムがランダム数をサンプルし、次の式で表されるcxとして第1線形暗号テキストを作成する。

0064

0065

同様に、第2暗号化アルゴリズムは、第1平文テキストベクトル142Aおよび第2線形公開キーを与えると、第2暗号化アルゴリズムがランダム数をサンプルし、次の式で表されるcyとして第2線形暗号テキストを作成する。

0066

0067

第1線形暗号テキストおよび第2線形暗号テキストは、線形認証モジュール132に通信される。さらにまたは別に、第1線形暗号テキストおよび第2線形暗号テキストは、ネットワーク107を介して認証サーバに通信される。認証サーバモジュール134は、第1線形暗号テキストおよび第2線形暗号テキストを受信し、第1線形暗号テキストおよび第2線形暗号テキストを線形認証モジュール132に通信する。

0068

いくつかの実施形態では、第1線形暗号テキストは、第2線形暗号テキストの通信の前に線形認証モジュール132に通信される。線形認証モジュール132は、第1線形暗号テキストをメモリ122Bに登録暗号テキスト130として記憶する。第1線形暗号テキストの通信後、第2線形暗号テキストが線形認証モジュール132に通信される。さらに、セットアップモジュール144は、リレーショナル線形キーを線形認証モジュール132に通信する。

0069

リレーショナル暗号化が認証に使用されるいくつかの実施形態では、第1線形暗号テキストは、登録暗号テキスト130として記憶される。登録暗号テキスト130は、第2線形暗号テキストとのまたは他のそれに続く線形暗号テキストとの比較の基礎として使用される。他のリレーショナル暗号化を行う実施形態では、第1線形暗号テキストは、登録暗号テキスト130として記憶されない。例えば、第1線形暗号テキストおよび第2線形暗号テキストは、それらをまたは両方を記憶すること無しに解析される。

0070

線形認証モジュール132は、第1線形暗号テキストと第2線形暗号テキスト間の線形関係を発見するように構成されている。線形関係を発見するため、線形認証モジュール132は、特別なベクトルを定義する。特別なベクトルは、第1フィールドのメンバである。線形認証モジュール132により決定される認証の問題は、特別なベクトルが第1平文テキストベクトル142Aおよび第2平文テキストベクトル142Bの和であるか決定することである。

0071

線形認証モジュール132は、線形リレーショナル秘密キーの累乗まで累乗された第1平文テキストの第1要素(例えば、ランダム数の累乗まで累乗された第1生成器)および第2平文テキストの第1要素(例えば、ランダム数の累乗まで累乗された第2生成器)の対関数として、第1の値を計算する。

0072

線形認証モジュール132は、特別なベクトルの対応する要素の累乗まで累乗された数の負数の累乗まで累乗された第1平文テキストの各要素および第2平文テキスト内の対応する要素の対関数の積として、第2の値を計算する。

0073

線形認証モジュール132は、第1の値が第2の値に等しいか決定する。第1の値が第2の値に等しいことに応答して、線形認証モジュール132は、第1線形暗号テキストが第2線形暗号テキストおよび定義したベクトルに線形に関係すると結論付ける。

0074

いくつかの実施形態では、線形認証モジュール132は、次の例示の線形ビットベクトル確認方程式にしたがって、第1線形暗号テキストと第2線形暗号テキストの間の線形関係を発見する。

0075

0076

さらに、いくつかの実施形態では、線形暗号化/復号化モジュール112は、第1および/または第2線形暗号テキストを復号する。線形暗号化/復号化モジュール112は、線形暗号テキストの値に基づいて、結果である平文テキストベクトル142の各要素を決定する。例えば、値は、第1線形暗号テキストを復号することにより作成される第1平文テキストベクトルの各要素(例えば、第1平文テキストベクトル142A)について決定される。

0077

各要素について、線形暗号化/復号化モジュール112は、(1)第1線形暗号テキスト内の対応する要素は、第1線形秘密キーの対応する要素まで累乗された第1線形暗号テキストの第1要素に等しいか、(2)第1線形暗号テキスト内の対応する要素は、第1線形秘密キーの対応する要素が乗じられた数の負数まで累乗された第1線形暗号テキストの第1要素に等しいか、(3)第1線形暗号テキスト内の対応する要素は、他の値に等しいかを決定する。

0078

第1線形暗号テキスト内の対応する要素が、第1線形秘密キーの対応する要素まで累乗された第1線形暗号テキストの第1要素に等しいこと(例えば、直前の段落の(1))に応答して、線形暗号化/復号化モジュール112は、第1平文テキストベクトル142Aの要素をゼロに設定する。第1線形暗号テキスト内の対応する要素が、第1線形秘密キーの対応する要素が乗じられた数の負数まで累乗された第1線形暗号テキストの第1要素に等しいこと(例えば、直前の段落の(2))に応答して、線形暗号化/復号化モジュール112は、第1平文テキストベクトル142Aの要素を1に設定する。第1線形暗号テキスト内の対応する要素は、他の値に等しいこと(例えば、直前の段落の(3))に応答して、線形暗号化/復号化モジュール112は、エラー返信する。第2線形暗号テキストは、第2線形秘密キーおよび第2線形暗号テキストを使用して、同様に復号される。

0079

いくつかの実施形態では、線形暗号化/復号化モジュール112は、次の例示の線形ビットベクトル復号方程式にしたがって線形暗号テキストを復号する。

0080

0081

線形ビットベクトル復号方程式は、上記で議論した第1復号アルゴリズム(DecX)および第2復号アルゴリズム(DecY)を定義する。例えば、第1復号アルゴリズムは、第1線形暗号テキストおよび第1線形秘密キーが与えられると、第1復号アルゴリズムは、次の方程式にしたがって、ビットごとに第1平文テキストベクトル142を作成する。

0082

0083

同様に、第2復号アルゴリズムは、第2線形暗号テキストおよび第2線形秘密キーが与えられると、第2復号アルゴリズムは、次の方程式にしたがって、ビットごとに第2平文テキストベクトル142Bを作成する。

0084

0085

P−ARYベクトルリレーショナル線形暗号化スキーム
p-aryベクトル(例えば、平文テキスト142および/または暗号テキストがp-aryベクトルである)が使用される実施形態では、線形キーは安全パラメータ用に生成される。キーを生成するため、セットアップモジュール144は、素数の位数の3つの双一次グループを生成する。素数の位数は、安全パラメータ中の指数関数で、ベース数(p)を法(modulo)とする1に等しい。したがって、これらの実施形態では、サブグループは、ゼロを除去した整数セット内に存在する。サブグループは、ベース数の位数を有する。セットアップモジュール144は、サブグループの任意の生成器を選択する。

0086

セットアップモジュール144は、第1生成器および第2生成器をサンプルする。第1生成器は第1双一次グループからサンプルされ、第2生成器は第2双一次グループからサンプルされる。第1線形秘密キーおよび第2線形秘密キーは、ビットベクトルを使用する実施形態を参照して上記のように生成される。

0087

セットアップモジュール144は、第1生成器である要素を有する第1線形公開キーを定義する。第1線形公開キーは、第1線形秘密キーの対応する要素の累乗まで累乗された第1生成器を有する1つ以上の他の要素をさらに有する。さらに、第1線形公開キーの要素は、任意の生成器を有する。いくつかの実施形態では、第1線形公開キーの第1要素は任意の生成器であり、第1線形公開キーの第2要素は、第1生成器である。第2線形公開キーの第1および第2要素は、対応性について計算されない。

0088

セットアップモジュール144は、第2線形公開キーを定義する。第2線形公開キーは、第2生成器である要素を有する。第2線形公開キーは、第2線形秘密キーの対応する要素の累乗まで累乗された第2生成器を有する1つ以上の他の要素をさらに有する。いくつかの実施形態では、第2線形公開キーの第1要素は、任意の生成器であり、第2線形公開キーの第2要素は第2生成器である。第2線形公開キーの第1および第2要素は、対応性については計算されない。

0089

セットアップモジュール144は、線形リレーショナル秘密キーを定義する。線形リレーショナル秘密キーの各要素は、第2線形秘密キーの対応する要素と第1線形秘密キーの対応する要素の和を有する。

0090

いくつかの実施形態では、線形キーの生成は、次の例示の線形p-aryベクトルキー方程式に従う。

0091

0092

線形p-aryベクトルキー方程式において、<>,g0,h0,gi,hi,ai,bi,i,n,Z,F,skR,r,G1,G2,GT,q,pkxlin,skxlin,pkylin,skylin,skRlin,←およびλは一般的に上記の通りである。さらに、pkxlin,skxlin,pkylin,skylin,およびskRlinは、少なくとも上記で議論したキー生成アルゴリズムの線形部分出力を表す。

0093

パラメータpはベース数を表す。パラメータJpは次数pのサブグループを表す。パラメータωは任意の生成器を表す。オペレータmodはモジュロ関数(modulo function)を表す。Zの次の上添え字"*"は整数セットからゼロが除去されたことを表す。

0094

線形暗号化/復号化モジュール112は、平文テキストベクトル142を受信する。さらにまたは別に、通信モジュール116は、平文テキストベクトル142を受信し、平文テキストベクトル142を線形暗号化/復号化モジュール112に通信する。平文テキストベクトル142は、第2フィールドのメンバを有する。第2フィールドは、ゼロの値からベース数から変じた1値(例えば、0,1,...,p-1)を有する要素を有する。

0095

線形暗号化/復号化モジュール112は、整数セットからランダム数をサンプルする。線形暗号化/復号化モジュール112は、次に第1線形暗号テキストおよび第2線形暗号テキストを作成する。第1線形暗号テキストは、ランダム数の累乗まで累乗された第1生成器である第1要素を有する。さらに、第1線形暗号テキストは、線形暗号化累乗まで累乗された第1線形公開キーの対応する要素を有する1つ以上の他の要素を有する。第1線形暗号テキスト用の線形暗号累乗は、第1平文テキストベクトル142Aの対応する要素の累乗まで累乗され、任意の生成器により乗じたランダム数を有する。いくつかの実施形態では、第1線形暗号テキストの第1要素は、対応性について計算されない。

0096

第2線形暗号テキストは、ランダム数の累乗まで累乗された第2生成器である第1要素を有する。さらに、第2線形暗号テキストは、線形暗号化累乗まで累乗された第2線形公開キーの対応する要素を有する1つ以上の他の要素を有する。第2線形暗号テキスト用の線形暗号累乗は、第2平文テキストベクトル142Bの対応する要素の累乗まで累乗された任意の生成器により乗じたランダム数を有する。いくつかの実施形態では、第2線形暗号テキストの第1要素は、対応性について計算されない。

0097

いくつかの実施形態では、線形暗号化/復号化モジュール112は、次の例示の線形p-aryベクトル暗号化方程式にしたがって、平文テキストベクトル142を暗号化する。

0098

0099

線形p-aryベクトル暗号化方程式において、<>,m1,m1i,m2,m2i,cx,cy,g0,h0,gi,hi,i,およびnは上記の通りである。パラメータFは第2フィールドを表す。第2フィールドの次の添え字pは第2フィールドのベース数を表す。第2フィールドの次の添え字nは第2フィールドのディメンジョンを表す。第2フィールドのディメンジョンは特別な数である。

0100

線形p-aryベクトル暗号化方程式は、上記で議論した第1暗号化アルゴリズム(EncX)および第2暗号化アルゴリズム(EncY)を定義する。例えば、第1暗号化アルゴリズムは、第1平文テキストベクトル142Aおよび第1線形公開キーを与えると、第1暗号化アルゴリズムがランダム数をサンプルし、次の式で表されるcxとして第1線形暗号テキストを作成する。

0101

0102

同様に、第2暗号化アルゴリズムは、第1平文テキストベクトル142Aおよび第2線形公開キーを与えると、第2暗号化アルゴリズムがランダム数をサンプルし、次の式で表されるcyとして第2線形暗号テキストを作成する。

0103

0104

第1線形暗号テキストおよび第2線形暗号テキストは、線形認証モジュール132に通信される。さらにまたは別に、第1線形暗号テキストおよび第2線形暗号テキストは、ネットワーク107を介して認証サーバに通信される。認証サーバモジュール134は、第1線形暗号テキストおよび第2線形暗号テキストを受信し、第1線形暗号テキストおよび第2線形暗号テキストを線形認証モジュール132に通信する。

0105

線形関係を発見するため、線形認証モジュール132は、特別なベクトルを定義する。特別なベクトルは、第2フィールドのメンバである。特別なベクトルは、第1平文テキストベクトル142Aおよび第2平文テキストベクトル142Bの和として定義される。線形認証モジュール132は、線形リレーショナル秘密キーの累乗まで累乗された第1平文テキストの第1要素(例えば、ランダム数の累乗まで累乗された第1生成器)および第2平文テキストの第1要素(例えば、ランダム数の累乗まで累乗された第2生成器)の対関数として、第1の値を計算する。

0106

線形認証モジュール132は、負数1と特別なベクトルの対応する要素の積の累乗まで累乗された任意の生成器の累乗まで累乗された第1平文テキストの各要素および第2平文テキスト内の対応する要素の対関数の積として、第2の値を計算する。

0107

線形認証モジュール132は、第1の値が第2の値に等しいか決定する。第1の値が第2の値に等しいことに応答して、線形認証モジュール132は、第1線形暗号テキストが第2線形暗号テキストに線形に関係すると結論付ける。

0108

いくつかの実施形態では、線形認証モジュール132は、次の例示の線形p-aryベクトル確認方程式にしたがって、第1線形暗号テキストと第2線形暗号テキストの間の線形関係を発見する。

0109

0110

線形p-aryベクトル確認方程式は、上記で議論した確認アルゴリズム(Verify)を定義する。例えば、確認アルゴリズムは、暗号テキスト、特別なベクトル、およびリレーショナル線形キーが与えられ、次の等価性式をチェックすることとして定義される。

0111

0112

さらに、いくつかの実施形態では、線形暗号化/復号化モジュール112は、第1および/または第2線形暗号テキストを復号する。線形暗号化/復号化モジュール112は、線形暗号テキストの値に基づいて、結果である平文テキストベクトル142の各要素を決定する。例えば、値は、第1線形暗号テキストを復号することにより作成される第1平文テキストベクトルの各要素(例えば、第1平文テキストベクトル142A)について決定される。

0113

暗号テキストを復号するため、特別な要素値が決定される。特別な要素値は、安全パラメータにおける多項式により範囲が決められる。さらに、特別な要素値は、ベース数を有する要素を含むフィールドのメンバである。第1平文テキストベクトル142Aの各要素について、線形暗号化/復号化モジュール112は、第1線形暗号テキスト内の対応する要素が、特別な要素値まで累乗された任意の生成器と第1線形秘密キーの対応する要素の積まで累乗された第1線形暗号テキストの第1要素に等しくなるような特別な要素値が存在するか決定する。

0114

第1線形暗号テキスト内の対応する要素が、特別な要素値まで累乗された任意の生成器と第1線形秘密キーの対応する要素の積まで累乗された第1線形暗号テキストの第1要素に等しくなるような特別な要素値が存在することに応答して、線形暗号化/復号化モジュール112は、要素を特別な要素値に設定する。

0115

そのような特別な要素値が存在しないことに応答して、線形暗号化/復号化モジュール112は、エラーを返信する。第2線形暗号テキストは、第2線形秘密キーおよび第2線形暗号テキストを使用して、同様に復号される。

0116

いくつかの実施形態では、線形暗号化/復号化モジュール112は、次の例示の線形p-aryベクトル復号方程式にしたがって線形暗号テキストを復号する。

0117

0118

線形p-aryベクトル復号方程式は、上記で議論した第1復号アルゴリズム(DecX)および第2復号アルゴリズム(DecY)を定義する。例えば、第1復号アルゴリズムは、第1線形暗号テキストおよび第1線形秘密キーが与えられると、第1復号アルゴリズムは、次の方程式にしたがって、ビットごとに第1平文テキストベクトル142を作成する。

0119

0120

同様に、第2復号アルゴリズムは、第2線形暗号テキストおよび第2線形秘密キーが与えられると、第2復号アルゴリズムは、次の方程式にしたがって、ビットごとに第2平文テキストベクトル142Bを作成する。

0121

0122

リレーショナル近似暗号化スキーム
リレーショナル近似暗号化スキームは、近似暗号テキスト間の近似を決定するのに使用される。いくつかの実施形態では、近似は、ハミング距離に関して提供される。リレーショナル近似暗号化スキームにおいて、セットアップモジュール144は、キーを生成する。キーを使用して、近似暗号化/復号化モジュール114は、平文テキストベクトル142の暗号化および/または復号化を実行する。近似暗号テキストは、近似認証モジュール128に通信され、そこで近似暗号テキスト間の近似が検出される。

0123

例えば、セットアップモジュール144は、選択平文テキスト攻撃(chosen-plaintext attack:CPA)キー生成アルゴリズムおよび線形キー生成アルゴリズムの出力を生成する。例えば、セットアップモジュール144は、他のところで説明したように、線形キーを動作させる。CPAキー生成アルゴリズムは、CPA公開キーおよびCPA秘密キーを出力する。線形キー生成アルゴリズムは、上記のように、pkxlin,skxlin,pkylin,skylin,およびskRlinを出力する。

0124

さらに、セットアップモジュール144は、エラー補正コード(ECC)を選択する。ECCは、線形エラー補正コードスキームである。ECCは、長さ、ランク、および距離を有する。さらに、ECCは、ECCコード化オペレータ(ENCODE)およびECCデコード化オペレータ(DECODE)を有する。セットアップモジュール144は、第1近似秘密キー、第2近似秘密キー、第1近似公開キー、第2近似公開キー、および近似リレーショナル秘密キー(合わせて「近似キー」)を有する。近似キーは、リレーショナル暗号化において、平文テキストベクトル142を暗号化して近似暗号テキストを生成し、近似暗号テキストを復号し、そして近似暗号テキスト間の近似を検出するのに使用される。

0125

第1近似秘密キーは、CPA秘密キーおよび第1線形秘密キーに基づいて定義される。第2近似秘密キーは、CPA秘密キーおよび第2線形秘密キーに基づいて定義される。第1近似公開キーは、ENCODE、DECODE、CPA公開キー、および第1線形公開キーに基づいて定義される。第2近似公開キーは、ENCODE、DECODE、CPA公開キー、および第2線形公開キーに基づいて定義される。近似リレーショナル秘密キーは、CPA秘密キー、および線形リレーショナル秘密キーに基づいて定義される。

0126

いくつかの実施形態において、セットアップモジュール144は、次の例示の近似キー生成方程式にしたがって近似キーを生成する。

0127

0128

近似キー生成方程式において、pkxlin,pkylin,skxlin,skylin,skRlin,および←は、上記の通りである。パラメータpkCPAはCPA公開キーを表す。パラメータskCPAはCPA秘密キーを表す。パラメータKeyGenCPAはCPAキー生成アルゴリズムを表す。パラメータpkxproxは第1近似公開キーを表す。パラメータpkyproxは第2近似公開キーを表す。パラメータskxproxは第1近似秘密キーを表す。パラメータskyproxは第2近似秘密キーを表す。パラメータskRproxは近似リレーショナル秘密キーを表す。さらに、パラメータpkxprox,skxprox,pkyprox,skyprox,およびskRproxは、上記で議論したキー生成アルゴリズム(KeyGen)の出力の少なくとも近似部分を表す。

0129

第1近似公開キーは、近似暗号化/復号化モジュール114により、第1平文テキストベクトル142Aを暗号化して、第1近似暗号テキストを生成するのに使用される。近似暗号化/復号化モジュール114は、平文テキストベクトル142を受信する。さらにまたは別に、通信モジュール116は、平文テキストベクトル142を受信し、平文テキストベクトル142を近似暗号化/復号化モジュール114に通信する。平文テキストベクトル142は、第1または第2フィールドのメンバを有する。

0130

近似暗号化/復号化モジュール114は、第3フィールドから近似ランダム数をサンプルする。第3フィールドは、ベース数およびECCのランクであるディメンジョンを有する。近似暗号化/復号化モジュール114は、第1近似暗号テキストおよび第2近似暗号テキストを作成する。第1近似暗号テキストおよび第2近似暗号テキストのそれぞれは、2つの部分を有する。第1近似暗号テキストの第1の部分は、CPA公開キーおよび第1平文テキストベクトル142Aと入力として近似ランダム数を受信するENCODEの和を入力として受信するCPA暗号化アルゴリズムを有する。第1近似暗号テキストの第2の部分は、第1線形公開キーおよび近似ランダム数を受信する第1線形暗号化アルゴリズムを有する。

0131

第2近似暗号テキストの第1の部分は、CPA公開キーおよび第2平文テキストベクトル142Bと入力として近似ランダム数を受信するENCODEの和を入力として受信するCPA暗号化アルゴリズムを有する。第2近似暗号テキストの第2の部分は、第2線形公開キーおよび近似ランダム数を入力として受信する第2線形暗号化アルゴリズムを有する。

0132

いくつかの実施形態において、近似暗号テキストは、次の例示の近似暗号化方程式にしたがって近似キーを生成される。

0133

0134

近似暗号化方程式において、ENCODE,m1,m2,pkcpa,pkxlin,およびpkylinは、上記の通りである。EncCPAはCPA暗号化アルゴリズムを表す。パラメータcxp1は、第1近似暗号テキストの第1部分を表す。パラメータcxp2は、第1近似暗号テキストの第2部分を表す。パラメータcxpは、第1近似暗号テキストを表す。パラメータcyp1は、第2近似暗号テキストの第1部分を表す。パラメータcyp2は、第2近似暗号テキストの第2部分を表す。パラメータcypは、第2近似暗号テキストを表す。パラメータEncXLinearは、第1線形暗号化アルゴリズムを表す。パラメータEncYLinearは、第2線形暗号化アルゴリズムを表す。

0135

第1近似暗号テキストは、通信モジュール116により認証サーバ140に通信され、そこで登録暗号テキスト130として記憶される。第2近似公開キーは、近似暗号化/復号化モジュール114により、第2平文テキストベクトル142Bを暗号化して第2近似暗号テキストを生成するのに使用される。第2近似暗号テキストは、通信モジュール116により認証サーバ140に通信される。近似リレーショナル秘密キーは、認証サーバ140において、特に近似認証モジュール128により、第2近似暗号テキストおよび第1近似暗号テキスト間の近似を検出するのに使用され、それは登録暗号テキスト130として記憶される。

0136

近似認証モジュール128は、第1近似暗号テキストと第2近似暗号テキスト間の近似を検出するように構成される。近似を検出するため、近似認証モジュール128は、公開キー情報内で利用可能なDECODEにアクセスする。近似認証モジュール128は、第1近似暗号テキストについてのランダム性の和を復元する。第1近似暗号テキストについてのランダム性の和は、入力としてCPA復号アルゴリズムを受信し、さらに入力としてCPA秘密キーおよび第1近似暗号テキストの第1部分の和を受信するDECODEとして定義され、CPA復号アルゴリズムは入力としてCPA秘密キーおよび第2近似暗号テキストの第1部分を受信する。

0137

もしDECODEがエラーを返信すると、近似認証モジュール128は、拒絶を返信する。さらに、近似認証モジュール128は、入力として線形リレーショナル秘密キー、第2近似暗号テキストの第1部分、第2近似暗号テキストの第2部分、およびランダム性の和を受信する線形確認アルゴリズムを出力する。

0138

このように、近似確認アルゴリズムは、第1近似暗号テキスト、第2近似暗号テキスト、および近似秘密キーを受信するように定義されている。近似確認アルゴリズムは、ランダム性の和を復元し、拒絶を出力するか、入力として線形リレーショナル秘密キー、第2近似暗号テキストの第1部分、第2近似暗号テキストの第2部分、およびランダム性の和を入力として受信する線形確認アルゴリズムを出力する。例えば、近似認証モジュール128は、次の例示の近似確認アルゴリズムにしたがって1つ以上の動作を実行する。

0139

0140

近似確認アルゴリズムにおいて、skcpa,cx1,cx2,cy2,⊥,skRlin,およびDECODEは上記の通りである。パラメータOutputは、近似認証モジュール128の出力を示す。パラメータZrsはランダム性の和を表す。パラメータDecCPAは、CPA復号アルゴリズムを表す。VerifyLinearは線形確認アルゴリズムを表す。

0141

さらに、いくつかの実施形態では、近似暗号化/復号化モジュール114は、第1および/または第2近似暗号テキストを復号する。近似暗号化/復号化モジュール114は、第1近似暗号テキストおよび第1近似秘密キー、または第2近似暗号テキストおよび第2近似秘密キーを使用して、平文テキストベクトル142を作成する。いくつかの実施形態では、近似暗号化/復号化モジュール114は、次の例示の近似復号方程式に従う。

0142

0143

近似復号方程式において、DecCPA,skcpa,cx1,cx2,cy1,cy2,skxlin,およびskylinは上記の通りである。パラメータDecXlinearは第1線形復号アルゴリズムを表す。

0144

ここまで説明したリレーショナル近似暗号化スキームは、次の条件が真であれば安全である。

0145

0146

この条件で、KeyGenCPA,EncCPA,DecCPA,KeyGenLinear,EncXlinear,DecXlinear,EncYLinear,DecYlinear,VerifyLinear,およびFは、上記の通りである。ECCはECCを表す。パラメータnは長さを表し、kはランクを表し、そして2σは距離を表す。

0147

図2は、ここで説明した少なくとも1つの実施形態にしたがって配置された生体認証システム(生体システム)200のブロック図である。生体システム200は、図1の動作環境100の例に含まれるかまたはそれを含み、そこでは認証サービスが提供される。生体システム200では、ユーザ206の認証は、認証サーバ140により実行される。生体システム200では、図1を参照して議論したリレーショナル暗号化が、ユーザ206の特定を認証するのに使用される。

0148

認証サービスは、登録プロセスおよび認証プロセスを有する。登録プロセスは、認証プロセスで使用されるユーザ206から情報およびデータを取得することを有する。認証プロセスは、時間的に後で(登録プロセスに続いて)生じる。認証プロセスでは、ユーザ206の特定は、図1を参照して議論したリレーショナル暗号化動作の1つ以上を使用して認証される。一般に、ユーザ206の特定は、説明したように、第1線形暗号テキストと第2線形暗号テキスト間の線形関係を発見し、第1近似暗号テキストと第2近似暗号テキスト間の近似を検出することにより認証される。第1線形暗号テキストおよび第1近似暗号テキストは、第1生体テンプレートの形で、ユーザ206により提供される。第1生体テンプレートは、図1の第1平文テキストベクトル142Aまたは図2の登録入力232に含まれる。

0149

ユーザ206および/または(以下で議論する)作為者(imposter)222は、1つ以上の生体特性を有する個人を有する。生体特性は、1つ以上の特有の特徴を有する。例えば、生体特性は、背および/または深いしわパターンを有するユーザ206の指紋を有する。ユーザ206は、いくつかの実施形態ではユーザ装置102に関係している。例えば、ユーザ206は、ユーザ装置102を所有するかまたは普通に動作させる。いくつかの実施形態では、ユーザ206は、特にユーザ装置102に関係している。例えば、ユーザ装置102は、ユーザ206を有する複数のユーザに公開でアクセス可能である。いくつかの実施形態では、作為者222は、生体特性を表す入力を提供するエンティティを有する。

0150

いくつかの実施形態では、ユーザ装置102は、センサ298を有する。センサ298は、例えば、ユーザ206を認証するのに使用される生体特性を測定するかまたは捕捉するように構成されたハードウェア装置を有する。ユーザ206の生体特性が測定されるかまたは捕捉された時、ユーザ装置102は生体テンプレートを生成する。生体テンプレートは、生体特性を表し、ユーザ206の生体特性の特有な特徴の少なくともいくつかを有している。生体テンプレートは、例えば、生体特性のグラフィックな表現および/またはアルゴリズム的表現を有する。

0151

センサ298のいくつかの例は、指紋スキャナ虹彩画像を捕えるように構成されたカメラ、DNAを測定するように構成された装置、心臓レートを捕えるように構成された心臓レートモニタ骨格筋肉により生成される電気的な活動を捕えるように構成された装着可能な電子筋収縮センサ、または生体特性を測定するかまたは捕えるように構成された他のセンサ298を有する。

0152

図示の生体システム200では、センサ298は、ユーザ装置102に含まれる。他の実施形態では、センサ298は、ユーザ装置102またはそこに含まれるプロセッサに通信可能に接続される。例えば、線さ298は、図1のネットワーク107のようなネットワークを介して、ユーザ装置102に信号を通信するように構成されている。図2では1つのセンサ298のみが示されているが、いくつかの実施形態では、ユーザ装置102は1つ以上のセンサ298を有する。

0153

enc/decモジュール110は、登録入力232から第1暗号テキストおよび近似暗号テキストを生成する。次に、enc/decモジュール110は、第1暗号テキストおよび近似暗号テキストを、登録データ234として認証サーバ140に通信する。

0154

リレーショナル認証モジュール108は、第1線形暗号テキストおよび第1近似暗号テキストを登録暗号テキスト130として記憶する。登録暗号テキスト130は、ユーザ206に関係する。例えば、ユーザ206は、ユーザ特定器に関係する。登録暗号テキスト130は、いくつかの実施形態では、メモリ122Bに記憶される。

0155

次に、enc/decモジュール110は、第1挑戦入力236Aまたは第2挑戦入力236B(一般に、挑戦入力236)を受信する。第1挑戦入力236Aおよび第2挑戦入力236Bは、ユーザ206またはその特定を認証される作為者222による試みである。第1挑戦入力236Aおよび第2挑戦入力236Bは、例えば、センサ298により読み取られた第2生体テンプレートを有する。第2生体テンプレートは、ユーザ206または作為者222の生体特性の特有の特徴を表す。

0156

enc/decモジュール110は、挑戦入力236から第2線形暗号テキストおよび第2近似暗号テキストを生成する。enc/decモジュール110は、第2線形暗号テキストおよび第2近似暗号テキストを、挑戦データ238として認証サーバ140に通信する。

0157

リレーショナル認証モジュール108は、挑戦データ238を受信する。リレーショナル認証モジュール108は、次にユーザ206用の登録暗号テキスト130を抽出する。

0158

リレーショナル認証モジュール108は、登録暗号テキスト130として記憶された第1線形暗号テキストとユーザ装置102から受信した第2線形暗号テキストの間の線形関係を決定する。さらに、リレーショナル認証モジュール108は、登録暗号テキスト130として記憶された第1近似暗号テキストとユーザ装置102から受信した第2近似暗号テキストの間の近似関係を決定する。

0159

第1線形暗号テキストが第2線形暗号テキストに対して線形関係を有することおよび第1近似暗号テキストと第2近似暗号テキストの間に特別な近似があることに応答して、認証サーバ140は、第1生体テンプレートと第2生体テンプレート間に近似的な類似性が存在すると決定する。

0160

このように、ユーザ206により提供された第1挑戦入力236Aが第2線形暗号テキストおよび第2近似暗号テキストに基づくならば、第1線形暗号テキストと第2線形暗号テキスト間に線形関係があり、第1近似暗号テキストと第2近似暗号テキスト間に近似がある。

0161

しかし、もし作為者222により提供された第2挑戦入力236Bが第2線形暗号テキストおよび第2近似暗号テキストに基づくならば、第1線形暗号テキストと第2線形暗号テキスト間に線形関係が無く、第1近似暗号テキストと第2近似暗号テキスト間に近似が無い。

0162

線形関係および/または近似に基づき、リレーショナル認証モジュール108は、認証決定を行う。例えば、リレーショナル認証モジュール108は、挑戦データ238がユーザ206または作為者222で発生したかを決定する。リレーショナル認証モジュール108は、線形関係の発見および/または近似の検出に基づいて、認証信号242を通信する。enc/decモジュール110は、認証信号242を受信する。

0163

本開示の範囲を逸脱すること無しに、生体システム200について、変形例、付加、または除去が行える。特に、図2に示した実施形態は、ひとりのユーザ206、1つのユーザ装置102、および1つの認証サーバ140を有する。しかし、本開示は、ひとり以上のユーザ206、1つ以上のユーザ装置102、1つ以上の認証サーバ140、またはそれらの組み合わせを有してもよい。

0164

さらに、ここで説明した実施形態における各種の要素の分離は、すべての実施形態で分離が発生することを示しているわけではない。記載の要素が単一の要素にまとめられるか、または複数の要素に分離されることは、ここでの開示の利点であると理解される。例えば、いくつかの実施形態では、enc/decモジュール110および/またはそれに付随する1つ以上の機能性は、認証サーバ140におけるモジュールにより実行されてもよい。

0165

リレーショナル認証モジュール108および/またはenc/decモジュール110は、生体認証用のコードおよびルーチンを有する。いくつかの実施形態では、リレーショナル認証モジュール108および/またはenc/decモジュール110は、例えば、ユーザ装置102に記憶された薄いクライアントアプリケーション(thin-client application)または他の演算装置として部分的に、そして認証サーバ140に記憶された要素として部分的に、動作する。いくつかの実施形態では、リレーショナル認証モジュール108および/またはenc/decモジュール110は、フィールドプログラマブルゲートアレイ(FPGA)またはアプリケーションスペフィック集積回路(ASIC)を有するハードウェアを使用して、実現される。いくつかの他の例では、リレーショナル認証モジュール108および/またはenc/decモジュール110は、ハードウェアおよびソフトウェアの組み合わせを使用して実現される。

0166

図3は、ここで説明した少なくとも1つの実施形態にしたがって配置した生体認証の例示の方法300のフロー図である。方法300は、図2の生体システム200または図1の動作環境100におけるような生体認証システムで実行される。方法300は、ここで説明した認証サーバ140により、いくつかの実施形態でプログラムにより実行される。認証サーバ140は、非一時的コンピュータ読取可能な媒体(例えば図1のメモリ122B)を有するかまたはそれに通信可能に接続され、媒体は方法300の実行または実行制御を行うようにプロセッサにより実行可能なプログラミングコードまたは命令がそこに記憶されるかコード化される。さらにまたは別に、認証サーバ140は方法300の実行または実行制御を行うようにコンピュータ命令を実行するように構成されたプロセッサ(例えば、図1のプロセッサ124B)を有する。個別のブロックとして示されているが、各種ブロックは、所望の実現方法に応じて、付加的なブロックに分割されるか、少ないブロックに組み合わせるか、または除去するかできる。

0167

方法300は、ブロック302で開始する。ブロック302で、第1線形暗号テキストが受信される。第1線形暗号テキストは、リレーショナル線形暗号化スキームを使用して暗号化された第1生体テンプレートを表す。ブロック304で、第1近似暗号テキストが受信される。第1近似暗号テキストは、リレーショナル近似暗号化スキームを使用して暗号化された第1生体テンプレートを表す。

0168

ブロック306で、第1線形暗号テキストおよび第1近似暗号テキストは、登録暗号テキストとして記憶される。ブロック308で、線形リレーショナル秘密キーおよび近似リレーショナル秘密キーが受信される。ブロック310で、第2近似暗号テキストが受信される。第2近似暗号テキストは、リレーショナル近似暗号化スキームを使用して暗号化した第2生体テンプレートを表す。ブロック312で、第2線形暗号テキストが受信される。第2線形暗号テキストは、リレーショナル線形暗号化スキームを使用して暗号化した第2生体テンプレートを表す。

0169

ブロック314で、第1線形暗号テキストと第2線形暗号テキスト間の線形関係が、線形リレーショナル秘密キーを使用して発見される。ブロック316で、第1近似暗号テキストと第2近似暗号テキスト間の近似が、近似リレーショナル秘密キーを使用して検出される。近似は、ハミング距離の多項式で決定される。ブロック318で、ユーザの特定が、近似および線形関係に基づいて決定される。

0170

業者であれば、このおよび他の手法および方法について、プロセスおよび方法で実行される機能が異なる順番でも行えることが理解される。さらに、概略のステップおよび動作は、例示の目的でのみ提示され、ステップおよび動作のいくつかは任意であり、開示の実施形態から逸脱すること無しに、より少ないステップおよび動作に組み合わせることも、付加的なステップおよび動作に拡張することもできる。

0171

図4Aおよび図4Bは、ここで説明した少なくとも1つの実施形態にしたがって配置されたリレーショナル暗号化の例示の方法400のフロー図である。方法400は、図2の生体システム200または図1の動作環境100のような生体認証システムで実行される。方法400は、ここで説明したユーザ装置102によりいくつかの実施形態でプログラムにより実行される。ユーザ装置102は、方法400の実行または実行の制御をプロセッサにより行えるプログラミングコードまたは命令を記憶またはその上にコード化した非一時的コンピュータ読取可能な媒体(例えば、図1のメモリ122A)に通信可能に接続される。さらにまたは別に、ユーザ装置102は、方法400の実行または実行の制御を行うコンピュータ命令を実行するように構成されたプロセッサ(例えば、図1のプロセッサ124A)を有する。図では個別のブロックとして示されているが、各種のブロックは、所望の実現方法に応じて、付加的なブロックに分割することも、より少ないブロックに結合することもできる。

0172

図4Aを参照すると、方法400は、ブロック402で開始する。ブロック402で、リレーショナル線形暗号化スキームのキーが生成される。リレーショナル線形暗号化スキームのキーは、安全パラメータ用に生成される。ブロック404で、第1平文テキストベクトルはリレーショナル線形暗号化スキームを使用して暗号化される。第1平文テキストベクトルの暗号化は、第1平文テキストベクトルを表す第1線形暗号テキストを生成する。ブロック406で、リレーショナル近似暗号化スキームが生成される。リレーショナル線形暗号化スキームのキーは、安全パラメータ用に生成される。ブロック408で、第1平文テキストベクトルはリレーショナル近似暗号化スキームを使用して暗号化される。リレーショナル近似暗号化スキームを使用した第1平文テキストベクトルの暗号化は、第1平文テキストベクトルを表す第1近似暗号テキストを生成する。ブロック410で、第1線形暗号テキストおよび第1近似暗号テキストは、認証サーバに通信される。

0173

ブロック412で、第2平文テキストベクトルは、リレーショナル線形暗号化スキームを使用して暗号化される。第2平文テキストベクトルの暗号化は、第2平文テキストベクトルを表す第2線形暗号テキストを生成する。図4Bを参照すると、ブロック414で、第2平文テキストベクトルは、リレーショナル近似暗号化スキームを使用して暗号化される。リレーショナル近似暗号化スキームを使用した第2平文テキストベクトルの暗号化は、第2近似暗号テキストを生成する。ブロック416で、第2線形暗号テキストおよび第2近似暗号テキストは、認証サーバに通信される。ブロック418で、ブロック402で生成されたリレーショナル形暗号化スキームのキーは、認証サーバに通信される。キーは、リレーショナル線形キーおよびリレーショナル近似キーを有する。

0174

ブロック420で、認証信号が、認証サーバから受信される。認証信号は、リレーショナル線形キーを使用して発見した第1線形暗号テキストと第2線形暗号テキスト間の線形関係、およびリレーショナル近似キーを使用して検出した第1近似暗号テキストと第2近似暗号テキスト間の近似を示す。いくつかの実施形態では、第1平文テキストベクトルは、ユーザから登録入力として受信した第1生体テンプレートを有する。さらに、第2平文テキストベクトルは、挑戦入力として受信した第2生体テンプレートを有する。これらおよび他の実施形態では、認証信号は、第2生体テンプレートがユーザで発生したかを示す。

0175

ブロック422で、第1線形暗号テキストは、リレーショナル線形暗号化スキームを使用して復号される。ブロック424で、第1近似暗号テキストは、リレーショナル近似暗号化スキームを使用して復号される。例えば、リレーショナル近似暗号化スキームを使用した第1近似暗号テキストの復号は、第1平文テキストベクトルの作成を有する。第1平文テキストベクトルは、入力としてCPA暗号キーおよび第1近似暗号テキストの第1部分を受信するCPA復号アルゴリズムおよび入力として第1線形秘密キーおよび第1近似暗号テキストの第2部分を受信する第1線形復号アルゴリズムの和として作成される。

0176

図5は、ここで説明した実施形態の少なくとも1つにしたがって配置されたリレーショナル暗号化スキームにおける線形関係を発見する例示の方法500のフロー図である。方法500は、図2の生体システム200または図1の動作環境100のような生体認証システムで実行される。方法500は、ここで説明した認証サーバ140によりいくつかの実施形態でプログラムにより実行される。認証サーバ140は、方法500の実行または実行の制御をプロセッサにより行えるプログラミングコードまたは命令を記憶またはその上にコード化した非一時的コンピュータ読取可能な媒体(例えば、図1のメモリ122B)に通信可能に接続される。さらにまたは別に、認証サーバ140は、方法500の実行または実行の制御を行うコンピュータ命令を実行するように構成されたプロセッサ(例えば、図1のプロセッサ124B)を有する。図では個別のブロックとして示されているが、各種のブロックは、所望の実現方法に応じて、付加的なブロックに分割することも、より少ないブロックに結合することもできる。

0177

方法500は、ブロック502で開始する。ブロック502で、特別なベクトルが定義される。特別なベクトルは、第1フィールドのメンバである。特別なベクトルは、ゼロと1と線形秘密キーの長さである特別な数のディメンジョンの要素を有する。さらにまたは別に、特別なベクトルは、第2フィールドのメンバを有する。第2フィールドのメンバは、ゼロから、ベース数および特別な数のディメンジョンより小さな数までを有する。

0178

ブロック504で、第1の値が計算される。第1の値は、線形リレーショナル秘密キーの累乗まで累乗された第1線形暗号テキストの第1要素および第2線形暗号テキストの第1要素の対関数として計算される。ブロック506で、第2の値が計算される。いくつかの実施形態では、第2の値は、特別なベクトルの対応する要素の累乗まで累乗された数の負数の累乗まで累乗された第1線形暗号テキストの各要素および第2線形暗号テキストの対応する要素の対関数の積である。いくつかの実施形態では、第2の値は、負の1と特別なベクトルの対応する要素の積の累乗まで累乗された任意の生成器の累乗まで累乗された第1線形暗号テキストの各要素および第2線形暗号テキストの対応する要素の対関数の積である。任意の生成器は、ゼロを除去した整数セットのサブグループから選択される。

0179

ブロック508で、第1の値が第2の値に等しいか決定される。第1の値が第2の値に等しいことに応答して(ブロック508で、"Yes")、方法500は、ブロック510に進む。ブロック510で、第1暗号テキストは第2暗号テキストに線形であると結論付けられる。第1の値が第2の値に等しくないことに応答して(ブロック508で、"No")、方法500は、ブロック512に進む。ブロック512で、エラーが出力され、それは第1線形暗号テキストが第2線形暗号テキストに線形でないことを示す。

0180

図6は、ここで説明した少なくとも1つの実施形態にしたがって配置した近似を検出する例示の方法600のフロー図である。方法600は、図2の生体システム200または図1の動作環境100のような生体認証システムで実行される。方法600は、ここで説明した認証サーバ140によりいくつかの実施形態でプログラムにより実行される。認証サーバ140は、方法600の実行または実行の制御をプロセッサにより行えるプログラミングコードまたは命令を記憶またはその上にコード化した非一時的コンピュータ読取可能な媒体(例えば、図1のメモリ122B)に通信可能に接続される。さらにまたは別に、認証サーバ140は、方法600の実行または実行の制御を行うコンピュータ命令を実行するように構成されたプロセッサ(例えば、図1のプロセッサ124B)を有する。図では個別のブロックとして示されているが、各種のブロックは、所望の実現方法に応じて、付加的なブロックに分割することも、より少ないブロックに結合することもできる。

0181

方法600は、ブロック602で開始する。ブロック602で、DECODEが公開キー情報からアクセスされる。ブロック604で、ランダム性の和が復元される。ランダム性の和は、第1近似暗号テキストについて受信される。第1近似暗号テキストについてのランダム性の和はDECODEとして定義され、DECODEは、入力として(a)CPA秘密キーおよび(b)第1近似暗号テキストの第1部分の和をさらに受信するCPA復号アルゴリズム、および入力としてCPA秘密キーおよび第2近似暗号テキストの第1部分を受信するCPA復号アルゴリズムを、入力として受信する。

0182

ブロック606で、DECODEがエラーを返信するのに応答して、拒絶が出力される。ブロック608で、そうでなければ線形確認アルゴリズムが出力される。線形確認アルゴリズムは、線形リレーショナル秘密キー、第2近似暗号テキストの第1部分、第2近似暗号テキストの第2部分、およびランダム性の和を入力として受信する。

0183

図7は、ここで説明した少なくとも1つの実施形態にしたがって配置したリレーショナル線形暗号化スキームのキー生成の例示の方法700のフロー図である。方法700は、図2の生体システム200または図1の動作環境100のような生体認証システムで実行される。方法700は、ここで説明したユーザ装置102によりいくつかの実施形態でプログラムにより実行される。ユーザ装置102は、方法700の実行または実行の制御をプロセッサにより行えるプログラミングコードまたは命令を記憶またはその上にコード化した非一時的コンピュータ読取可能な媒体(例えば、図1のメモリ122A)に通信可能に接続される。さらにまたは別に、ユーザ装置102は、方法700の実行または実行の制御を行うコンピュータ命令を実行するように構成されたプロセッサ(例えば、図1のプロセッサ124A)を有する。図では個別のブロックとして示されているが、各種のブロックは、所望の実現方法に応じて、付加的なブロックに分割することも、より少ないブロックに結合することもできる。

0184

方法700は、ブロック702で開始する。ブロック702で、双一次グループが生成される。いくつかの実施形態では、双一次グループは、素数の位数である。素数の位数は、安全パラメータにおける指数関数である。さらにまたは別に、素数の位数は、安全パラメータにおける指数関数で且つベース数(p)の1基本単位(module)に等しい。例えば、平文テキストベクトルがビットベクトルを有する実施形態では、素数の位数は安全パラメータにおける指数関数である。平文テキストベクトルがp-aryベクトルを有する実施形態では、素数の位数は、安全パラメータにおける指数関数で且つベース数(p)の1基本単位に等しい。

0185

ブロック704で、生成器がサンプルされる。例えば、第1生成器は、第1双一次グループからサンプルされ、第2生成器は第2双一次グループからサンプルされる。ブロック706で、線形秘密キーが生成される。例えば、第1線形秘密キーおよび第2線形秘密キーは、整数セットから特定の番号の要素をランダムにサンプルすることにより生成される。整数セットは、ゼロから素数の位数より小さい数を有する。

0186

ブロック708で、線形公開キーが定義される。例えば、第1線形公開キーは、第1生成器である1つの要素と、第1線形秘密キーの対応する要素の累乗まで累乗された第1生成器である他の要素の1つ以上と、を有する。いくつかの実施形態では、第1線形公開キーは、任意の生成器をさらに有する。任意の生成器は、ゼロを除去した整数セットのサブグループから選択される。さらに、第2線形公開キーが定義される。第2線形公開キーは、第2生成器である1つの要素と、第2線形秘密キーの対応する要素の累乗まで累乗された第2生成器である他の要素の1つ以上と、を有する。いくつかの実施形態では、第2線形公開キーは、任意の生成器である要素をさらに有する。

0187

ブロック710で、線形リレーショナル秘密キーが定義される。線形リレーショナル秘密キーの各要素は、第2線形秘密キーの対応する要素および第1線形秘密キーの対応する要素の和を有する。

0188

図8は、ここで説明した少なくとも1つの実施形態にしたがって配置したリレーショナル線形暗号化スキームを使用した第1平文テキストの暗号化の例示の方法800のフロー図である。方法800は、図2の生体システム200または図1の動作環境100のような生体認証システムで実行される。方法800は、ここで説明したユーザ装置102によりいくつかの実施形態でプログラムにより実行される。ユーザ装置102は、方法800の実行または実行の制御をプロセッサにより行えるプログラミングコードまたは命令を記憶またはその上にコード化した非一時的コンピュータ読取可能な媒体(例えば、図1のメモリ122A)に通信可能に接続される。さらにまたは別に、ユーザ装置102は、方法800の実行または実行の制御を行うコンピュータ命令を実行するように構成されたプロセッサ(例えば、図1のプロセッサ124A)を有する。図では個別のブロックとして示されているが、各種のブロックは、所望の実現方法に応じて、付加的なブロックに分割することも、より少ないブロックに結合することもできる。

0189

方法800は、ブロック80で開始する。ブロック802で、ランダム数がサンプルされる。ランダム数は整数セットからサンプルされる。ブロック804で、第1線形暗号テキストが作成される。第1線形暗号テキストの第1要素は、ランダム数の累乗まで累乗された第1生成器である。さらに、第1線形暗号テキストの他の1つ以上の要素は、線形暗号化累乗まで累乗された第1線形公開キーの対応する要素を有する。いくつかの実施形態では、線形暗号化累乗は、ランダム数および第1平文テキストベクトルの対応する要素の累乗まで累乗された数の負数の積を有する。いくつかの実施形態では、線形暗号化累乗は、ランダム数および第1平文テキストベクトルの対応する要素の累乗まで累乗された数の任意の生成器の積を有する。

0190

図9は、ここで説明した少なくとも1つの実施形態にしたがって配置したリレーショナル線形暗号化スキームのキー生成の例示の方法900のフロー図である。方法900は、図2の生体システム200または図1の動作環境100のような生体認証システムで実行される。方法900は、ここで説明したユーザ装置102によりいくつかの実施形態でプログラムにより実行される。ユーザ装置102は、方法900の実行または実行の制御をプロセッサにより行えるプログラミングコードまたは命令を記憶またはその上にコード化した非一時的コンピュータ読取可能な媒体(例えば、図1のメモリ122A)に通信可能に接続される。さらにまたは別に、ユーザ装置102は、方法900の実行または実行の制御を行うコンピュータ命令を実行するように構成されたプロセッサ(例えば、図1のプロセッサ124A)を有する。図では個別のブロックとして示されているが、各種のブロックは、所望の実現方法に応じて、付加的なブロックに分割することも、より少ないブロックに結合することもできる。

0191

方法900は、ブロック902で開始する。ブロック902で、ECCが選択される。ECCは、長さ、安全パラメータの同じ次数におけるランク、および選択された最小距離を有する。ブロック904で、CPA安全暗号化スキームのキー生成アルゴリズムが動作される。CPA安全暗号化スキームは、CPA公開キーおよびCPA秘密キーを出力する。ブロック906で、リレーショナルキー生成アルゴリズムが動作される。リレーショナルキー生成アルゴリズムは、第1線形公開キー、第2線形公開キー、第1線形秘密キー、第2線形秘密キー、およびリレーショナル線形秘密キーを出力する。

0192

ブロック907で、近似公開キーが定義される。例えば、第1近似公開キーは、ENCODE、DECODE、CPA公開キー、および第1線形公開キーに基づいて定義される。さらに、第2近似公開キーは、ENCODE、DECODE、CPA公開キー、および第2線形公開キーに基づいて定義される。ブロック908で、近似秘密キーが定義される。例えば、第1近似秘密キーは、CPA秘密キーおよび第1線形秘密キーに基づいて定義される。さらに、第2近似秘密キーは、CPA秘密キーおよび第2線形秘密キーに基づいて定義される。ブロック910で、近似リレーショナル秘密キーが定義される。例えば、近似リレーショナル秘密キーは、CPA秘密キーおよびリレーショナル線形秘密キーに基づいて定義される。

0193

図10は、ここで説明した少なくとも1つの実施形態にしたがって配置した、リレーショナル近似暗号化スキームを使用して第1平文テキストを暗号化する例示の方法1000のフロー図である。方法1000は、図2の生体システム200または図1の動作環境100のような生体認証システムで実行される。方法1000は、ここで説明したユーザ装置102によりいくつかの実施形態でプログラムにより実行される。ユーザ装置102は、方法1000の実行または実行の制御をプロセッサにより行えるプログラミングコードまたは命令を記憶またはその上にコード化した非一時的コンピュータ読取可能な媒体(例えば、図1のメモリ122A)に通信可能に接続される。さらにまたは別に、ユーザ装置102は、方法1000の実行または実行の制御を行うコンピュータ命令を実行するように構成されたプロセッサ(例えば、図1のプロセッサ124A)を有する。図では個別のブロックとして示されているが、各種のブロックは、所望の実現方法に応じて、付加的なブロックに分割することも、より少ないブロックに結合することも、除去することもできる。

0194

方法1000は、ブロック1002で開始する。ブロック1002で、近似ランダム数がサンプルされる。近似ランダム数は、第3フィールドからサンプルされる。第3フィールドは、ベース数およびECCのランクであるディメンジョンを有する。ブロック1004で、第1近似暗号テキストの第1部分が定義される。第1部分は、CPA公開キー、および第1平文テキストおよび入力として近似ランダム数を受信するENCODEの和を、入力として受信するCPA暗号化アルゴリズムとして定義される。

0195

ブロック1006で、第1近似暗号テキストの第2部分が定義される。第2部分は、入力として第1線形公開キーおよび近似ランダム数を受信する第1線形暗号化アルゴリズムとして定義される。

0196

図11は、ここで説明した少なくとも1つの実施形態にしたがって配置した、第1線形暗号テキストを復号する例示の方法1100のフロー図である。方法1100は、図2の生体システム200または図1の動作環境100のような生体認証システムで実行される。方法1100は、ここで説明したユーザ装置102によりいくつかの実施形態でプログラムにより実行される。ユーザ装置102は、方法1100の実行または実行の制御をプロセッサにより行えるプログラミングコードまたは命令を記憶またはその上にコード化した非一時的コンピュータ読取可能な媒体(例えば、図1のメモリ122A)に通信可能に接続される。さらにまたは別に、ユーザ装置102は、方法1100の実行または実行の制御を行うコンピュータ命令を実行するように構成されたプロセッサ(例えば、図1のプロセッサ124A)を有する。図では個別のブロックとして示されているが、各種のブロックは、所望の実現方法に応じて、付加的なブロックに分割することも、より少ないブロックに結合することも、除去することもできる。

0197

方法1100は、ブロック1102で開始する。ブロック1102で、第1線形暗号テキストにおける対応する要素が、特別な要素値まで累乗された任意の生成器と第1線形秘密キーの対応する要素の累乗まで累乗された第1線形暗号テキストの第1要素に等しいような特別な要素値が存在するか決定される。特別な要素値の存在(ブロック1102における"Yes")に応じて、要素は特別な要素値に設定される。特別な要素値が存在しないこと(ブロック1102における"No")に応じて、エラーが出力される。

0198

図12は、ここで説明した少なくとも1つの実施形態にしたがって配置した、第1線形暗号テキストを復号する例示の他の方法1200のフロー図である。方法1200は、図2の生体システム200または図1の動作環境100のような生体認証システムで実行される。方法1200は、ここで説明したユーザ装置102によりいくつかの実施形態でプログラムにより実行される。ユーザ装置102は、方法1200の実行または実行の制御をプロセッサにより行えるプログラミングコードまたは命令を記憶またはその上にコード化した非一時的コンピュータ読取可能な媒体(例えば、図1のメモリ122A)に通信可能に接続される。さらにまたは別に、ユーザ装置102は、方法1100の実行または実行の制御を行うコンピュータ命令を実行するように構成されたプロセッサ(例えば、図1のプロセッサ124A)を有する。図では個別のブロックとして示されているが、各種のブロックは、所望の実現方法に応じて、付加的なブロックに分割することも、より少ないブロックに結合することも、除去することもできる。

0199

方法1200は、ブロック1202で開始する。ブロック1202で、第1線形暗号テキストにおける対応する要素が、第1線形秘密キーの対応する要素まで累乗された第1線形暗号テキストの第1要素に等しいか決定される。第1線形暗号テキストにおける対応する要素が、第1線形秘密キーの対応する要素まで累乗された第1線形暗号テキストの第1要素等しいこと(ブロック1202における"Yes")に応じて、方法1200はブロック1208に進む。ブロック1208で、第1平文テキストベクトルの要素はゼロに設定される。

0200

第1線形暗号テキストにおける対応する要素が、第1線形秘密キーの対応する要素まで累乗された第1線形暗号テキストの第1要素等しくないこと(ブロック1202における"No")に応じて、方法1200はブロック1204に進む。ブロック1204で、第1線形暗号テキストにおける対応する要素が、第1線形秘密キーの対応する要素を乗じた数の負数まで累乗された第1線形暗号テキストの第1要素等しくか決定される。第1線形暗号テキストにおける対応する要素が、第1線形秘密キーの対応する要素を乗じた数の負数まで累乗された第1線形暗号テキストの第1要素等しいこと(ブロック1204における"Yes")に応じて、方法1200はブロック1210に進む。ブロック1210で、第1平文テキストベクトルの要素は、1に設定される。第1線形暗号テキストにおける対応する要素が、第1線形秘密キーの対応する要素を乗じた数の負数まで累乗された第1線形暗号テキストの第1要素等しくないこと(ブロック1204における"No")に応じて、方法1200はブロック1206に進む。ブロック1206で、第1線形暗号テキストにおける対応する要素が他の値に等しいか決定される。第1線形暗号テキストにおける対応する要素が他の値に等しいこと(ブロック1206における"Yes")に応答して、方法1200はブロック1212に進む。ブロック1212で、エラーが返信される。

0201

ここで説明した実施形態は、これまで詳細に議論したように、各種のコンピュータハードウェアまたはソフトウェアモジュールを含む専用のまたは汎用のコンピュータの使用を有する。

0202

ここで説明した実施形態は、コンピュータ読取可能な媒体を使用して実現され、媒体は記憶されたコンピュータ実行可能な命令またはデータ構造担持または有する。このようなコンピュータ読取可能な媒体は、汎用または引用のコンピュータによりアクセスされる利用可能な媒体である。それにより制限されない例として、このようなコンピュータ読取可能な媒体は、RAM、ROM、EEPROM、CD−ROM、または他の光学ディスク記憶装置磁気ディスク記憶装置、または他の磁気記憶装置、フラッシュメモリ装置(例えば、固体メモリデバイス)、またはコンピュータ実行可能な命令またはデータ構造の形で所望のプログラムコードを担持または記憶するのに使用され、汎用のまたは専用のコンピュータによりアクセスされる他の記憶媒体を含む非一時的および/または確実なコンピュータ読取可能な記憶媒体を有する。上記の組み合わせは、コンピュータ読取可能な媒体の範囲に含まれる。

0203

コンピュータ実行可能な命令は、例えば、汎用コンピュータ、専用コンピュータまたは特別な専用処理装置に、あるファンクションまたはファンクションのグループを実行させる命令およびデータを有する。主題は構造的な特徴および/または方法論的動きを特定する言語で記載されているが、特許請求の範囲に定義した主題はかならずしも上記の特別な特徴または動きに限定されないと理解される。むしろ、上記の特別な特徴および動きは、特許請求の範囲を実現する例示の形式として開示される。

0204

ここで使用した用語「モジュール」または「要素」は、コンピューティングシステムで実行するソフトウェアのオブジェクトまたはルーチンを示す。ここで説明した異なる要素、モジュール、エンジン、およびサービスは、コンピューティングシステムで実行するオブジェクトまたはプロセスとして実現される(例えば、分離したスレッド)。いくつかの実施形態では、ここで説明したモジュール、エンジン、およびサービスは、コンピューティングシステムで実行するオブジェクトまたはプロセス(例えば、分離したスレッド)で実現される。ここで説明したシステムおよび方法は、(記憶されるかおよび/または汎用のハードウェアにより実行される)ソフトウェアで実現するように一般的に述べたが、特別なハードウェア構成またはソフトウェアと特別なハードウェア構成の組み合わせも可能であり、企画してもよい。この記載で、「コンピューティングエンティティ」は、ここであらかじめ定義したようないかなるコンピューティングシステムでも、コンピューティングシステム上で動作するいかなるモジュールまたはモジュールの組み合わせでもよい。

0205

ここで引用したすべての例および条件付き言語は、発明者により従来の技術を更に推し進めるために提供された発明と概念読者が理解するのを支援する教育的目的のためであり、そのように特定的に引用した例と条件に制限されるものではないと解釈されるべきである。本開示の実施形態を詳細に記述したが、種々の変更、置換、および改造が、本開示の精神と範囲を逸脱することなく実施形態に対して行えるということは理解されたい。

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ