(57)【特許請求の範囲】
【請求項１】
サーバによって実施される少なくとも２つの索引付きデータ項目（Ａｊ）の集合を暗号化する方法であって、データ（Ａｊ）は、要素
【数１】
0005714785.tif 000026
のリストの形式であり、各要素は、アルファベットと呼ばれる索引付き符号（ｘｉ）の有限集合（ε）に属し、
方法は、データ（Ａｊ）が暗号化されて保護集合（ＬＯＣＫ（Ａ１，…，ＡＮ））を形成し、暗号化および保護集合の生成のステップは、
−サーバが、ベース内の各データ項目（Ａｊ）に対して、対応する符号化関数（Ｆｊ）をランダムに生成し
−アルファベット（ε）の各符号（ｘｉ）に対して
○各データ項目（Ａｊ）に対して
データ項目を構成するリストの少なくとも１つの要素
【数２】
0005714785.tif 000027
がアルファベットの符号（ｘｉ）である場合、サーバは、データ項目（Ａｊ）に対応する符号化関数（Ｆｊ）を介してアルファベットの前記符号（ｘｉ）の画像を決定し、データ項目およびアルファベットの符号の関数であるコードワード座標Ｆｊ（ｘｉ）を取得し
サーバは、それにより得られたコードワード座標Ｆｊ（ｘｉ）を、アルファベット（ｘｉ）の要素に対応する索引付き集合（Ｓｉ）に追加し、集合は、所定の基数（ｌ）を有し
○次いで、サーバは、アルファベット（ε）の符号（ｘｉ）に対応する索引付き集合（Ｓｉ）の要素にランダムに再索引付けをし
○サーバは、アルファベットの符号（ｘｉ）に対応する索引付き集合（Ｓｉ）を、保護集合（ＬＯＣＫ（Ａ１，…，ＡＮ））に追加し
−アルファベット（ε）での各符号（ｘｉ）に対して、再索引付けステップの前に、サーバは、エラー誘導ポイントを有するアルファベット要素（ｘｉ）に対応する索引付き集合（Ｓｉ）を完成することを特徴とする、方法。
【請求項２】
ベース内のデータのいずれの要素にも対応しないアルファベットの符号（ｘｉ）に対して、
−サーバは、前記要素（ｘｉ）の幾つかをランダムに選択し
−選択された各要素（ｘｉｅ）に対して、要素（ｘｉｅ）のものに対応する索引を有する所定の基数集合（Ｓｉｅ）を生成し、要素の基数と同じ数のエラー誘導ポイントをこの要素（ｘｉｅ）に追加する、請求項１に記載の方法。
【請求項３】
アルファベット（ε）の選択されなかった符号（ｘｉ）が、空集合と関連づけられる、請求項２に記載の方法。
【請求項４】
エラー誘導ポイントが、符号化関数の目的地集合（Ｙ）間でランダムに生成され、データ（Ａｊ）に対応する符号化関数（Ｆｊ）によってアルファベット（ε）の符号（ｘｉ）の画像Ｆｊ（ｘｉ）を除去したポイントである、請求項２から３のいずれか一項に記載の方法。
【請求項５】
データ（Ｆｊ）に対応する符号化関数が、少なくとも１つのリスト回復アルゴリズムが存在する評価コードと関連づけられる、請求項１から４のいずれか一項に記載の方法。
【請求項６】
評価コードが、畳込みリードソロモン符号、リードマラー符号、または代数的符号である、請求項５に記載の方法。
【請求項７】
サーバが、パブリックハッシュ関数（Ｈａｓｈ）によりデータ項目（Ａｊ）に対応する各符号化関数（Ｆｊ）の画像（Ｈａｓｈ（Ｆｊ））を算出し、前記画像を保護集合に追加する、請求項１から６のいずれか一項に記載の方法。
【請求項８】
データ（Ａｊ）が生体情報データである、請求項１から７のいずれか一項に記載の暗号化方法。
【請求項９】
生体情報データ（Ａｊ）が、個人の指紋に関する情報を備え、前記データは、個人の指紋の詳細についての座標のトリプレット（ｘ，ｙ，θ）のリストの形式である、請求項８に記載の暗号化方法。
【請求項１０】
トリプレット（ｘ，ｙ，θ）の各座標が、１バイトでコード化され、アルファベットは、各座標が１バイトでコード化されたトリプレットの、起こり得る構成のすべてを含む、請求項１から９のいずれか一項に記載の暗号化方法。
【請求項１１】
個人（Ｉ）を識別する方法であって、識別対象である個人（Ｉ）の生体情報データ項目（Ｂ）を取得するのに適切な制御サーバ（ＳＣ）、およびリスト化された個人の生体情報データを含むベース（ＤＢ）を管理するサーバ（ＳＧ）を備えるシステムにおいて、
個人（Ｉ）を識別するために、対象のデータ項目（Ｂ）は、ベース内（ＤＢ）のＮ個のデータ（Ａｊ）と比較され、ある程度の類似性を有するベース内の１つまたは複数のデータ項目（Ａｊ）と、所定の閾値を超過する個人のデータ項目とを識別し、
方法は、個人のデータ項目をベース内のデータと比較するステップの前に、請求項１から１０のいずれか一項に記載の方法を使用して、管理サーバ（ＳＧ）によって暗号化されることを特徴とする、方法。
【請求項１２】
識別対象の個人の生体情報データ項目（Ｂ）が、要素（ｂｉ）のリストの形式であり、その各要素（ｂｉ）は、アルファベット（ε）の符号（ｘｉ）であり、管理サーバが保護集合（ＬＯＣＫ（Ａ１，…，ＡＮ））を制御サーバ（ＳＣ）に通信し、識別対象の個人の生体情報データ項目（Ｂ）から、制御サーバ（ＳＣ）は、保護集合（ＬＯＣＫ（Ａ１，…，ＡＮ））を復号化するステップを実施し、復号化ステップは、
−個人（Ｉ）のデータ項目（Ｂ）を構成する要素（ｂｉ）のリスト内にあるアルファベット（ε）の符号（ｘｉ）に対応する索引付き集合（Ｓｉ）のすべてを備える保護集合（ＬＯＣＫ（Ａ１，…，ＡＮ））の部分集合を選択すること
−個人のデータ項目（Ｂ）がベース内のデータ項目（Ａｊ）に対応する場合、符号化関数の集合が、前記データ項目（Ａｊ）に対応する符号化関数（Ｆｊ）を含むように、引数が前記選択された部分集合であり、結果が符号化関数の集合であるリスト回復アルゴリズムを使用すること
から成るステップを備える、請求項１１に記載の方法。
【請求項１３】
取得された１つまたは複数の符号化関数から、制御サーバが、所定の閾値より大きい、ある程度の類似性を有する個人のデータ項目（Ｂ）に対応するベース（ＤＢ）内の１つまたは複数のデータ項目（Ａｊ）を決定する、請求項１２に記載の方法。
【請求項１４】
制御サーバ（ＳＣ）が、パブリックハッシュ関数（Ｈａｓｈ）によりリスト回復アルゴリズムからもたらされる集合の符号化関数の画像を決定し、この画像を、保護集合（ＬＯＣＫ（Ａ１，…，ＡＮ））内に含まれたベース内のデータに対応する符号化関数の画像と比較する、請求項１２または１３のいずれか一項に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データの暗号化の分野、および暗号化データを候補データ項目と比較して、暗号化データ項目の１つと候補データ項目との間の類似性を評価することに関する。
【０００２】
本発明は、特に、生物測定の分野に適用可能であり、個々の生体情報データを暗号化し、生体情報データの１つを暗号化データと比較することによって、候補となる個人を識別する。
【背景技術】
【０００３】
“ｆｕｚｚｙ  ｖａｕｌｔ”方式という名で知られる、データ項目を暗号化する方法が知られている。この方法については、以下の文献で説明されている。
【０００４】
−Ａｒｉ  Ｊｕｅｌｓ  ａｎｄ  Ｍａｇｈｕ  Ｓｕｄａｎ，Ａ  ｆｕｚｚｙ  ｖａｕｌｔ  ｓｃｈｅｍｅ．Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，ＩＳＩＴ，Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，ｐａｇｅ  ４０８，  ２００２，および
−Ａｒｉ  Ｊｕｅｌｓ  ａｎｄ  Ｍａｇｈｕ  Ｓｕｄａｎ，Ａ  ｆｕｚｚｙ  ｖａｕｌｔ  ｓｃｈｅｍｅ．Ｄｅｓ．Ｃｏｄｅｓ  Ｃｒｙｐｔｏｇｒａｐｈｙ，３８（２）：２３７−２５７，２００６
【０００５】
“ｆｕｚｚｙ  ｖａｕｌｔ”方式は、“ｆｕｚｚｙ  ｖａｕｌｔ”と呼ばれる数学的集合（以下、「保護集合」と称する）において、データ項目Ａに関する情報と、ランダムに生成され、データ項目Ａとは独立した補足寄生情報とを統合することから成る。この寄生情報は、Ａに関連した情報をマスクすることを可能にする。
【０００６】
より正確には、この暗号化は、有限フィールドＦの索引付き要素ａｉのリストの形式でのデータ項目Ａに適用する。
【０００７】
この方法の間、本明細書で説明しない、ある種の数学的特性を有する多項式ｐがランダムに生成され、Ａの各要素ａｉに対して、要素ａｉのｐによる画像が算出される。
【０００８】
次いで、データ項目Ａの要素ａｉとｐによる画像とから成るペアが、保護集合に加えられる。
【０００９】
最後に、エラー誘導ポイントが保護集合に加えられる。このポイントは、ランダムに生成されたペア（ｘｉ、ｘｉ’）であり、ｘｉはＡの要素ではなく、ｘｉ’はｘｉのｐによる画像ではない。数学的に、
【００１０】
【数１】
0005714785.tif 000002
である。
【００１１】
したがって、ペア
【００１２】
【数２】
0005714785.tif 000003
の集合は、横座標
【００１３】
【数３】
0005714785.tif 000004
がＡに属し、
【００１４】
【数４】
0005714785.tif 000005
であるか、またはそれらがＦ＼Ａに属する場合に取得され、この場合、
【００１５】
【数５】
0005714785.tif 000006
が、Ｆ＼ｐ（Ａ）において選択される。
【００１６】
多数のエラー誘導ポイントを加えることで、データ項目Ａおよび多項式ｐに関するポイントをマスクすることが可能になる。
【００１７】
次に、保護集合を使用して、前記データ項目Ａについての情報を取得することなく、第２のデータ項目Ｂをデータ項目Ａと比較する。
【００１８】
これを行うために、復号化アルゴリズムが開発されており、保護集合を用いて、索引付き要素ｂｉのリストの形式でのデータ項目Ｂを比較することを可能にし、ある程度の類似点が所定の閾値を超過する場合に、データ項目Ｂがデータ項目Ａに対応するかどうかを判断する。
【００１９】
特に、多数の要素ｂｉが、Ａの要素ａｉに対応する場合に、ＢはＡに対応する。後者の要素は、保護集合における定義により位置決めされる。
【００２０】
これらの復号化アルゴリズムの引数は、保護集合の横座標ｘｉに対応するデータ項目Ｂの要素ｂｉであり、その結果は、多項式ｐ’である。ＢがＡに十分対応する場合、多項式ｐ’は、データ項目Ａを暗号化するために使用された多項式ｐである。
【００２１】
次いで、この多項式ｐを、保護集合の横座標ｘｉに対応するＢのすべての要素ｂｉに適用し、どの要素ｂｉが、Ａの要素ａｉであるかを判断することが可能である。というのも、構造により、ある要素と、ｐによるこの要素の画像を備えるペアのみがＡの要素であるためである。
【００２２】
適切な復号化アルゴリズムの例の１つには、リードソロモン符号を復号化するためのものがある。
【００２３】
したがって、ｆｕｚｚｙ  ｖａｕｌｔ方式により、データの一方についての情報を取得することなく、２つのデータ項目を比較することが可能となる。
【００２４】
しかしながら、２つのデータ項目の比較に限定され、データバンク内に複数のデータの集合を有するデータ項目の比較に適用することはできない。しかしながら、この種類の比較は、特に、個人の生体認証において、ますます頻繁に使用される。
【００２５】
したがって、ｆｕｚｚｙ  ｖａｕｌｔ方式の原理を、データバンク内の複数のデータ向けに拡張し、バンク内のデータを所与のサードパーティと、それらについての情報を取得することなく比較することを可能にすることに対する必要性がある。
【先行技術文献】
【非特許文献】
【００２６】
【非特許文献１】Ａｒｉ  Ｊｕｅｌｓ  ａｎｄ  Ｍａｇｈｕ  Ｓｕｄａｎ，Ａ  ｆｕｚｚｙ  ｖａｕｌｔ  ｓｃｈｅｍｅ．Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，ＩＳＩＴ，Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，ｐａｇｅ  ４０８，２００２
【非特許文献２】Ａｒｉ  Ｊｕｅｌｓ  ａｎｄ  Ｍａｇｈｕ  Ｓｕｄａｎ，Ａ  ｆｕｚｚｙ  ｖａｕｌｔ  ｓｃｈｅｍｅ．Ｄｅｓ．Ｃｏｄｅｓ  Ｃｒｙｐｔｏｇｒａｐｈｙ，３８（２）：２３７−２５７，２００６
【発明の概要】
【発明が解決しようとする課題】
【００２７】
本発明の目的の１つは、上記した問題を克服することである。
【課題を解決するための手段】
【００２８】
この目的は、本発明において、サーバによって実施される少なくとも２つの索引付きデータの集合を暗号化する方法によって実現される。そのデータは、要素のリストの形式であり、その各要素は、アルファベットと呼ばれる索引付き符号の有限集合に属する。
【００２９】
本方法は、データが暗号化されて保護集合を形成することを特徴とし、暗号化および保護集合の生成のステップは、以下のステップを備える：
−サーバは、ベース内の各データ項目に対して、対応する符号化関数をランダムに生成する。
−アルファベットの各符号に対して
○各データ項目に対して
データ項目を構成するリストの少なくとも１つの要素がアルファベットの符号である場合、サーバは、データ項目に対応する符号化関数を介してアルファベットの前記符号の画像を決定し、データ項目およびアルファベットの符号の関数であるコードワード座標を取得する。
サーバは、それにより得られたコードワード座標を、アルファベットの要素に対応する索引付き集合に追加する。その集合は、所定の基数を有する。
○次いで、サーバは、アルファベットの符号に対応する索引付き集合の要素にランダムに再索引付けをする。
○サーバは、アルファベットの符号に対応する索引付き集合を、保護集合に追加する。
【００３０】
有利には、だが任意選択的に、本発明は、さらに、以下の機能の少なくとも１つを備えることができる：
−アルファベットでの各符号に対して、再索引付けステップの前に、サーバは、エラー誘導ポイントを有するアルファベット要素に対応する索引付き集合を完成する。
−ベース内のデータのいずれの要素にも対応しないアルファベットの符号に対して、
○サーバは、前記要素の幾つかをランダムに選択する。
○選択された各要素に対して、その要素のものに対応する索引を有する所定の基数集合を生成し、要素の基数と同じ数のエラー誘導ポイントをこの要素に追加する。
−アルファベットの選択されなかった符号は、空集合と関連する。
−エラー誘導ポイントは、符号化関数の目的地集合間でランダムに生成され、データに対応する符号化関数によってアルファベットの符号の画像を除去したポイントである。
−データに対応する符号化関数は、少なくとも１つのリスト回復アルゴリズムが存在する評価コードと関連づけられる。
−評価コードは、畳込みリードソロモン符号、リードマラー符号、または代数的符号である。
−サーバは、パブリックハッシュ関数によりデータ項目に対応する各符号化関数の画像を算出し、前記画像を保護集合に追加する。
−そのデータは、生体情報データである。
−生体情報データは、個人の指紋に関する情報を備え、前記データは、個人の指紋の詳細についての座標のトリプレット（ｘ，ｙ，θ）のリストの形式である。
−トリプレット（ｘ，ｙ，θ）の各座標は、１バイトでコード化され、アルファベットは、各座標が１バイトでコード化されたトリプレットの、起こり得る構成のすべてを含む。
【００３１】
本発明はさらに、識別対象である個人の生体情報データ項目を取得するのに適切な制御サーバ、およびリスト化された個人の個々の生体情報データを含むベースを管理するサーバを備えるシステムにおいて、個人を識別する方法に関する。
【００３２】
個人を識別するために、対象のデータ項目は、ベース内のＮ個のデータと比較され、ある程度の類似性を有するベース内の１つまたは複数のデータ項目と、所定の閾値を超過する個人のデータ項目とを識別する。
本方法は、個人のデータ項目をベース内のデータと比較するステップの前に、上記項目の１つによる方法を使用して、管理サーバによって暗号化されることを特徴とする。
【００３３】
有利には、だが任意選択的に、本識別法はまた、以下の特徴の少なくとも１つを備えてもよい：
−識別対象の個人の生体情報データ項目は、要素のリストの形式であり、その各要素は、アルファベットの符号であり、管理サーバが保護集合を制御サーバに通信し、識別対象の個人の生体情報データ項目から、制御サーバは、保護集合を復号化するステップを実施し、復号化ステップは、以下から成るステップを備える：
○個人のデータ項目を構成する要素のリスト内にあるアルファベットの符号に対応する索引付き集合のすべてを備える保護集合の部分集合を選択するステップ。
○個人のデータ項目がベース内のデータ項目に対応する場合、符号化関数の集合が、前記データ項目に対応する符号化関数を含むように、引数が前記選択された部分集合であり、結果が符号化関数の集合であるリスト回復アルゴリズムを使用するステップ。
−取得された１つまたは複数の符号化関数から、制御サーバは、所定の閾値より大きい、ある程度の類似性を有する個人のデータ項目に対応するベース内の１つまたは複数のデータ項目を決定する。
−制御サーバは、パブリックハッシュ関数によりリスト回復アルゴリズムからもたらされる集合の符号化関数の画像を決定し、この画像を、保護集合内に格納されたベース内のデータに対応する符号化関数の画像と比較する。
【００３４】
本発明の他の特徴、目的、および利点は、純粋に例示的で、非限定的であり、添付図面を参照して読み取られる必要のある、以下の説明から明らかになるであろう。
【図面の簡単な説明】
【００３５】
【図１ａ】本発明により提案される、暗号化方法のステップを示す図である。
【図１ｂ】本方法の第１のステップを実施するアルゴリズムを示す図である。
【図２】復号化方法のステップを示す図である。
【図３】本発明による識別方法の模式的な実施態様を示す図である。
【図４ａ】個人の指紋をコーディングするために使用される規則を示す図である。
【図４ｂ】個人の指紋をコーディングするために使用される規則を示す図である。
【図４ｃ】個人の指紋をコーディングするために使用される規則を示す図である。
【発明を実施するための形態】
【００３６】
少なくとも１つの例示的実施形態の詳細な説明
データベースＤＢ内の複数のデータＡｊを暗号化する方法の主要ステップを、図１を参照して説明する。
【００３７】
記号および語彙
データベースＤＢは、ｎ個の秘密データＡｊ（ｊ＝１．．ｎ）を含む。各データ項目Ａｊは、例えば、ｔ個の索引付き要素
【００３８】
【数６】
0005714785.tif 000007
ｉ＝１．．ｔの要素のリストの形式であり、したがって、Ａｊは、
【００３９】
【数７】
0005714785.tif 000008
と書き表される。
【００４０】
あるいは、データＡｊは、互いに異なるサイズとしてもよい。
【００４１】
各Ａｊの要素
【００４２】
【数８】
0005714785.tif 000009
は、２進要素またはベクトルであることが好ましく、その各座標は、２進要素である。
【００４３】
本発明は、符号理論に適合し、ある種の数学的対象を使用し、その定義は、ここで再び提供される。
【００４４】
εはアルファベットであり、すなわちＮ個の符号ｘ１．．．ｘＮを含有する集合であり、データ項目Ａｊの各要素は、アルファベットεの符号である。このアルファベットは、データＡｊをコード化する方法に従って定義される。
【００４５】
したがって、例えば、データＡｊの要素が、ある数のビットでコード化された値である場合、アルファベットεは、すべてこの数のビットでコード化された２進符号を備える。１バイトでコード化されたデータＡｊの場合、アルファベットεは、２５６バイトを備えることが可能である。
【００４６】
評価関数はまた、次の通りに定義される：
−Ｄを有限集合とする。
−Ｐ１．．．ＰＮを、Ｄ内の座標のＮ個の別個のポイントとする。
−Ｐを、集合Ｙ内の値を有するカルテシアン積Ｄ＊．．．＊Ｄの関数の集合の部分集合とし、Ｙは、例えば、集合Ｄとすることができる。
−評価関数ｅｖは、以下によって定義することができる。
【００４７】
【数９】
0005714785.tif 000010
【００４８】
さらに、Ｌｋが、次元ｋのＰの部分集合である場合、Ｃ＝ｅｖ（Ｌｋ）が、Ｌｋによって定義される評価コードである。Ｃが、長さＮおよび次元ｋのＹについての評価コードであると言える。
【００４９】
最後に、コードワードは、コードＣの要素を意味し、すなわち、評価関数ｅｖ（ｆ）による関数ｆの評価である。
【００５０】
ベース内のデータの暗号化
ベース内のデータＡｊの暗号化１００は、図１に示されるステップの実装態様によって、コンピュータサーバにより実行される。
【００５１】
符号化関数の生成
ステップ１１０の間、サーバは、ベース内の各データ項目Ａｊに対して、対応する符号化関数Ｆｊをランダムに生成する。
【００５２】
符号化関数は、コードワードの座標を要素と関連づける関数を意味する。
【００５３】
この場合では、リスト回復アルゴリズムが存在する評価コードと関連づけられた符号化関数Ｆｊが選択される。
【００５４】
例えば、リードマラー符号が知られ、ゴッパ符号などの代数的符号、または「畳込みリードソロモン符号」という用語で知られるコードがある。
【００５５】
本発明では、畳込みリードソロモン符号の使用が都合良く、次の通りに定義される：
−Ｆを、基数ｑの有限体とし（Ｆ＝ＧＦ（ｑ））、γをＦのジェネレータとする。
−リードソロモン符号Ｃ［ｕ，ｋ］をｍ回畳み込んだバージョンは、ＦＲＳＦ，γ，ｍ，Ｎ，ｋで表され、Ｆｍについてのブロックサイズ
【００５６】
【数１０】
0005714785.tif 000011
のコードであり、ｕ＝ｑ−１は、ｍで割り切れる。
−最大ｋ−１次のメッセージｐ∈Ｆ［Ｘ］のコーディングが、評価関数ｅｖ（ｆ）＝ｆ（Ｐ１，．．．，ＰＮ）の適用によりもたらされ、ここで、Ｐｉ＝γｍ（ｉ−１）であり、
【００５７】
【数１１】
0005714785.tif 000012
である。
【００５８】
畳込みリードソロモン符号型の評価コードの場合、データＡｊに対応する符号化関数Ｆｊは、この場合、次の通りに定義される：
−ｆｊを、Ｆ［Ｘ］においてランダムに選択された関数とし、例えば、次数ｋ−１の多項式とすることができる。
−Ｆｊ（ｘｉ）＝ｆｊ（Ｐｉ）であり、ここで、Ｐｉ＝γｍ（ｉ−１）である。Ｆｊ（ｘｉ）は、コードワードｅｖ（ｆｊ）のｉ番目の座標である。
【００５９】
保護集合内のデータの符号化
再び図１を参照すると、符号化ステップ１２０の間に、符号化関数から、ベース内のデータを暗号化する保護集合ＬＯＣＫ（Ａｊ）をサーバが生成する。
【００６０】
このために、サーバは、ステップ１２１の間、アルファベットεにある符号と同数の集合Ｓｉを生成する。各集合Ｓｉは、アルファベットε内の要素ｘｉに対応する。
【００６１】
サーバはまた、２つのセキュリティパラメータｌおよびｒを定義する。
【００６２】
第１のセキュリティパラメータｌは、索引付き集合Ｓｉと関連づけられた整数である。この整数は、１つの集合Ｓｉから別のものまで様々であるか、またはすべての集合Ｓｉに対して同じとすることができる。
【００６３】
第２のセキュリティパラメータｒもまた、整数である。その役割は、以下により詳細に説明される。
【００６４】
アルゴリズムが初期化されると、集合Ｓｉは、要素を含まなくなる。
【００６５】
その場合、アルファベットε内の各符号ｘｉに対して、
−ベース内の各データ項目Ａｊに対し、
○ｘｉ∈Ａｊの場合、サーバは、ステップ１２２の間、データ項目Ａｊに対応する符号化関数Ｆｊ、すなわち、Ｆｊ（ｘｉ）により符号ｘｉの画像を算出する。上記のように、この画像は、コードワードの座標、およびデータ項目Ａｊならびにアルファベットεの符号ｘｉの関数である。サーバは、この値を、符号ｘｉに対応する集合Ｓｉに追加する。
−次いで、サーバは、ステップ１２３の間、索引付き集合Ｓｉの基数が事前に決定した整数ｌに達するまで、索引付き集合Ｓｉに寄生またはエラー誘導ポイントを追加する。
【００６６】
エラー誘導ポイントは、データＡｊに対応する符号化関数Ｆｊによりアルファベットεの符号の画像を除去された集合Ｙにおいて、ランダムに選択される。したがって、これらのエラー誘導ポイントは、符号化関数から独立している。
【００６７】
これらのエラー誘導ポイントは、確実なコードワードの識別を妨げる。したがって、これらのエラー誘導ポイントは、アルファベットεの符号およびコードワードからデータＡｊの符号化関数Ｆｊを決定することを妨げる。
【００６８】
整数ｌは、暗号化方法のセキュリティパラメータである。その値は、後に使用したい復号化アルゴリズムと、許容可能な算出時間とに左右される。畳込みリードソロモン符号の使用が選択された場合、整数ｌは、典型的に、ｍ未満であり、ｍは、畳込みリードソロモン符号のパラメータの１つであり、さらに、ベース内のデータＡｊの個数ｎ未満である。
【００６９】
さらに、サーバは、空ではない索引付き集合Ｓｉの数のカウンタを保持し、このカウンタは、アルファベットεの符号ｘｉがデータＡｊの少なくとも１つの中にある場合に、１ずつインクリメントされる。カウンタ値は、ｃｐｔと呼ばれる。
【００７０】
これらの第１のステップ１２２、１２３の最後では、対応するアルファベットｘｉの符号が、ベース内のいずれのデータＡｊ内にない場合、空の索引付き集合Ｓｉが残っている可能性がある。
【００７１】
次いで、サーバは、ステップ１２４の間、索引ｉｅ，ｉｅ＝｛ｉｃｐｔ＋１，…，ｉｒ｝をランダムに選択する。索引付き集合
【００７２】
【数１２】
0005714785.tif 000013
は空であり、各索引付き集合
【００７３】
【数１３】
0005714785.tif 000014
の基数が値ｌに達するまで、寄生もしくはエラー誘導ポイントをこれらの集合に追加する。
【００７４】
ここで再び、エラー誘導ポイントは、データ
【００７５】
【数１４】
0005714785.tif 000015
に対応する符号化関数Ｆｊによりアルファベットの符号の画像を除去されたＹにおいて選択される。
【００７６】
ステップ１２３の最後では、Ｎ−ｒ個の空集合Ｓｉが残る。
【００７７】
したがって、セキュリティパラメータｒは、暗号化ステップ１２０の最後で、空ではない索引付き集合Ｓｉの数を表す。
【００７８】
ｒは正の整数であり、Ｎ未満であり、アルファベットε内の符号の数であり、ベース内のデータＡｊの数に従って選択される。ｒがアルファベット内の符号の数であるＮと同じ桁を有するようにｒが選択されることが好ましい。ｒ＝Ｎとすることも可能であり、その結果、暗号化ステップ１２０の間に空集合は残らない。
【００７９】
非限定の例として、Ｎは、１０４の桁を有してもよく、その場合、ｒは、数千からＮの値の間であり、Ｎの値は、数十万程度であるあることが好ましい。
【００８０】
いかなるコードワードも備えていない集合
【００８１】
【数１５】
0005714785.tif 000016
にエラー誘導ポイントを追加するこのステップ１２４は、これらの集合
【００８２】
【数１６】
0005714785.tif 000017
が、アルファベットのどの符号がベース内のデータＡｊ内にあるかについての判断を妨げるため、暗号化アルゴリズムでのさらなるセキュリティをもたらす。
【００８３】
ステップ１２１から１２４の数学的アルゴリズムが、図１ｂで添付される。
【００８４】
最後に、ステップ１２５の間、サーバは、各索引付き集合Ｓｉの要素にスクランブルをかける。このスクランブルは、各集合Ｓｉ内の要素のランダムな再索引付けによって実施される。
【００８５】
実際に、最初に集合Ｓｉに追加されたコードワードは、これらの集合内のその位置により、それらを識別することが可能となる。したがって、スクランブルすることで、コードワードが、集合Ｓｉ内でランダムな位置を有することが可能となる。
【００８６】
最後に、ステップ１２６の間、アルファベットの符号と、対応する索引付き集合とから成るペアが、アルファベット内の各符号に対して、保護集合ＬＯＣＫに追加される。
【００８７】
以下で詳述するように、サーバはまた、ステップ１２７の間、コードワードを生成するために使用された各符号化関数Ｆｊのパブリックハッシュ関数Ｈａｓｈにより、画像を算出し、集合ＬＯＣＫ内の画像Ｈａｓｈ（Ｆｊ）を統合することができ、ＬＯＣＫ（Ａｊ，Ｈａｓｈ（Ｆｊ））と書き表される。
【００８８】
復号化
データＡｊが集合ＬＯＣＫ内で暗号化された場合、この集合を使用して、データ項目Ｂから、データＡｊについて、何らの情報をもたらすことなく、データ項目Ｂと最も類似するデータ項目Ａｊを決定する。このステップ２００は復号化と呼ばれ、そのステップは、図２に示される。
【００８９】
データ項目Ｂは、ｔ個の要素｛ｂ１，…，ｂｔ｝のリストであり、その各要素ｂｉは、アルファベットε内の符号ｘｉである。
【００９０】
復号化を続ける必要があるサーバは、ステップ２１０の間、集合ＬＯＣＫに格納された索引付き集合Ｓｉの中から選択する。それらの
【００９１】
【数１７】
0005714785.tif 000018
は、Ｂに含まれる要素
【００９２】
【数１８】
0005714785.tif 000019
に対応する。すなわち、集合
【００９３】
【数１９】
0005714785.tif 000020
において、その索引ｉｅは、
【００９４】
【数２０】
0005714785.tif 000021
であり、ｅ＝１，．．，ｔである。
【００９５】
次に、サーバは、ステップ２２０の間、すべてのペア
【００９６】
【数２１】
0005714785.tif 000022
を入力として有するリスト回復アルゴリズムを使用する。
【００９７】
このリスト回復アルゴリズムは、データＡｊを暗号化するために選ばれたコードに依存する。コードが畳込みリードソロモン符号である場合、適切なリスト回復アルゴリズムは、Ｖｅｎｋａｔｅｓａｎ  Ｇｕｒｕｓｗａｍｉによる文献、Ｌｉｎｅａｒ−ａｌｇｅｂｒａｉｃ  ｌｉｓｔ  ｄｅｃｏｄｉｎｇ  ｏｆ  ｆｏｌｄｅｄ  Ｒｅｅｄ  Ｓｏｌｏｍｏｎ  Ｃｏｄｅｓ，ｉｎ  ＩＥＥＥ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ｃｏｍｐｌｅｘｉｔｙ，ｐａｇｅｓ  ７７−８５．ＩＥＥＥ  Ｃｏｍｐｕｔｅｒ  Ｓｏｃｉｅｔｙ，２０１１で説明されるＧｕｒｕｓｗａｍｉリスト符号化アルゴリズムである。
【００９８】
リスト回復アルゴリズムは、所定の閾値を超える索引付き集合Ｓｉとある程度の類似性を有するコードワードのリストを結果として供給する。これらのコードワードでは、所定の閾値を超えてデータ項目Ｂとある程度の類似性を有するデータＡｊの１つまたは複数の符号化関数Ｆｊに対応する、１つまたは複数の符号化関数が推定される。
【００９９】
特に、データ項目Ｂが、データＡｊの１つに対応する場合、このデータ項目Ａｊに対応する符号化関数Ｆｊが、リスト回復アルゴリズムの結果から取得される。
【０１００】
このアルゴリズムに起因する関数は、
【０１０１】
【数２２】
0005714785.tif 000023
のような
【０１０２】
【数２３】
0005714785.tif 000024
の比率に対して、前記比率がデータＡｊおよびデータ項目Ｂとの間の類似性閾値から決定され、これにより、ＡｊがＢと同様である場合のみ該当する、
【０１０３】
【数２４】
0005714785.tif 000025
が得られる。
【０１０４】
このアルゴリズムの結果である関数が、実際に、対応するデータ項目Ａｊの評価関数であるという証拠を取得したい場合、サーバは、検証ステップ２３０の間、上記したパブリックハッシュ関数Ｈａｓｈによるこの結果の関数の画像を算出し、この結果を、保護アセンブリＬＯＣＫに格納されたデータＡｊのそれぞれのハッシュと比較することができる。
【０１０５】
最後に、符号化関数Ｆｊから、サーバは、データ項目Ａｊを発見することができる。こうするために、すべての符号ｘｉの画像が、符号化関数Ｆｊにより算出され、Ｆｊ（ｘｉ）が索引付き集合Ｓｉに属するかどうかが判断される。その場合、ｘｉはデータ項目Ａｊに属する。次いで、データ項目Ａｊを再構築することが可能である。
【０１０６】
生体情報識別への応用
この暗号化アルゴリズムおよび対応する復号化アルゴリズムの優先的用途は、生体情報識別である。
【０１０７】
生体情報識別は、図１ｂに模式的に示す。
【０１０８】
個人の識別は、特に、個人に対するデータ項目を、基準となる個人の類似データと比較し、識別対象の個人が、所定の閾値を超えるある程度の類似性を有する基準となる個人の１人に対応するかどうかを判断することから成る。
【０１０９】
基準となる個人は、例えば、その場所へのアクセスが承認された個人か、あるいは警察が捜索している個人とすることができる。
【０１１０】
例えば、図３において、データ項目Ｂは、制御サーバＳＣによって、識別したい個人Ｉの生体情報特性ｂの、２進数でコード化されて収集したものである。
【０１１１】
例えば、この生体情報特性は、虹彩または指紋とすることができる。
【０１１２】
図４を参照して、指紋をコード化する方法を示す。図４ａに示す指紋１０は、それらを形作る線１２についての細部１１と称される不規則性によって特徴づけられる。例えば、細部１１には、線の終端または二叉分岐がある可能性がある。
【０１１３】
指紋１０における細部の数、形、および位置により、この指紋が一意のものとなり、それを有する個人に特有とする。したがって、細部を用いて指紋をコード化する。
【０１１４】
指紋１０のコーディングは、トリプレット（ｘ，ｙ，θ）の集合であり、Ｘおよびｙは、図４ａ、図４ｂおよび図４ｃで識別される直交座標系での細部の横座標および縦座標を示し、θは、Ｘ軸に対する線１２の向きによって形成される角度である。より正確には、図４ｂにおいて、示した細部は線の終端であり、θは、途切れる前の線の向きとＸ軸との角度である。図４ｃにおいて、細部は、二叉分岐を表し、θは、二叉分岐前の線の向きとＸ軸との角度である。
【０１１５】
ｘ、ｙ、およびθは、それぞれ、１バイトでコード化される。暗号化方法に対して対応するアルファベットεは、すべての可能なトリプレットから成り、その各座標は、１バイトで配位される。２５６（２８）バイトが可能であるため、アルファベットεは、Ｎ＝２５６３の要素を含む。
【０１１６】
再び図３を参照すると、基準となる個人の生体情報データＡｊは、管理サーバＳＧによって管理されるデータベースＤＢ内に格納される。
【０１１７】
管理サーバＳＧは、データＡｊについて、上記した暗号化方法を使用して、保護集合ＬＯＣＫ（Ａ１，．．．，ＡＮ）を生成する。
【０１１８】
ある個人が識別対象の人物である場合、制御サーバＳＣは、指紋センサにより、または識別情報ドキュメントに格納されたチップを読み取ることにより、生体情報データ項目Ｂを取得する。
【０１１９】
次いで、制御サーバＳＣは、上記した復号化アルゴリズムを使用して、どのデータ項目Ａｊが、それが存在する場合は、所定の閾値を超えるある程度の類似性を有する個人のデータ項目Ｂに対応するかを判断する。
【０１２０】
したがって、暗号化アルゴリズムが開発され、複数のデータＡｊが、保護集合内で符号化されることを可能にする。このアルゴリズムは、ｆｕｚｚｙ  ｖａｕｌｔ方式の拡張版であり、後者は複数のデータをコーディングすることができず、これらのデータが共通の要素を有する場合でもそうである。
【０１２１】
このアルゴリズムはまた、エラー誘導ポイントがすべてのデータに追加されるため、データを符号化するための保管場所を最小にすることもできる。
さらに、このアルゴリズムは、すべてのデータに対して、ただ１度の復号化で実現することができ、使用するリスト回復アルゴリズムにより、計算時間を節約することができる。
【図１ａ】
0005714785.tif 000028
【図１ｂ】
0005714785.tif 000029
【図２】
0005714785.tif 000030
【図３】
0005714785.tif 000031
【図４ａ】
0005714785.tif 000032
【図４ｂ】
0005714785.tif 000033
【図４ｃ】
0005714785.tif 000034