(57)【要約】  本発明は、あいまいな情報源から抽出される生体特徴量などのデータに関する近さの判定をハミング距離に基づいて行うリニアスケッチシステムを実現可能とする。生成装置は、入力した鍵を誤り訂正符号の符号化関数を用いて符号化鍵に変換する鍵変換部と、入力したファジーデータと前記符号化鍵に対し第一の合成変換を施しスケッチを生成するスケッチ生成部を含み、復元装置は、第一のスケッチおよび第二のスケッチを入力するスケッチ入力部と、前記第一、第二のスケッチに第二の合成変換を施して合成スケッチを求めるスケッチ合成部と、前記合成スケッチに基づき前記第一、第二のスケッチの生成に用いられた二つの鍵の差を算出する鍵の差復元部を含む。
2020174516.tif 000002
【特許請求の範囲】
【請求項１】
生成装置と、復元装置と、を含み、  
前記生成装置は、
鍵を受け取る鍵入力部と、
ファジーデータを受け取るファジーデータ入力部と、
鍵を誤り訂正符号の符号化関数を用いて符号化鍵に変換する鍵変換部と、
前記ファジーデータと前記符号化鍵に対して第一の合成変換を施しスケッチを生成するスケッチ生成部と、
を含み、
前記復元装置は、
第一の鍵と第一のファジーデータに基づき生成された第一のスケッチと、第二の鍵と第二のファジーデータに基づき生成された第二のスケッチを受け取るスケッチ入力部と、
前記第一のスケッチと前記第二のスケッチに対して第二の合成変換を施して合成スケッチを求めるスケッチ合成部と、
前記合成スケッチに基づき、前記第一のスケッチと前記第二のスケッチの生成にそれぞれ用いられた前記第一の鍵と前記第二の鍵の差を算出する鍵の差復元部と、
を含む、ことを特徴とするリニアスケッチシステム。
【請求項２】
前記生成装置は、
乱数を取得する乱数取得部をさらに有し、
前記鍵変換部は、
前記鍵と前記乱数とを誤り訂正符号の符号化関数を用いて符号化鍵に変換し、
前記復元装置は、
前記合成スケッチを誤り訂正符号の復号関数を用いて復号して拡張鍵の差を算出する計算する拡張鍵の差復元部を有し、
前記鍵の差復元部は、前記拡張鍵の差から、前第一のスケッチと前記第二のスケッチの生成にそれぞれ用いられた前記第一の鍵と前記第二の鍵の差を算出する、ことを特徴とする請求項１記載のリニアスケッチシステム。
【請求項３】
前記スケッチ生成部は、前記符号化鍵から少なくとも１ブロックを除いた符号化鍵を生成し、生成した前記符号化鍵と前記ファジーデータに対して前記第一の合成変換を施してスケッチを生成する、ことを特徴とする請求項２記載のリニアスケッチシステム。
【請求項４】
前記生成装置は、前記ファジーデータを拡張する変換を行うファジーデータ変形部をさらに有し、
前記スケッチ生成部は、前記変換後のファジーデータを用いてスケッチを生成する、ことを特徴とする請求項１乃至３のいずれか１項に記載のリニアスケッチシステム。
【請求項５】
鍵を受け取る鍵入力部と、
ファジーデータを受け取るファジーデータ入力部と、
鍵を誤り訂正符号の符号化関数を用いて符号化鍵に変換する鍵変換部と、
前記ファジーデータと前記符号化鍵に対して第一の合成変換を施しスケッチを生成するスケッチ生成部と、
を含む、ことを特徴とする生成装置。
【請求項６】
入力した鍵を誤り訂正符号の符号化関数を用いて符号化鍵に変換し、入力したファジーデータと前記符号化鍵に対し第一の合成変換を施しスケッチを生成する生成装置から、第一の鍵と第一のファジーデータに基づき生成された第一のスケッチと、第二の鍵と第二のファジーデータに基づき生成された第二のスケッチとを受け取るスケッチ入力部と、
前記第一のスケッチと前記第二のスケッチに対して第二の合成変換を施して合成スケッチを求めるスケッチ合成部と、
前記合成スケッチに基づき、前記第一のスケッチおよび前記第二のスケッチの生成にそれぞれ用いられた前記第一の鍵と前記第二の鍵の差を算出する鍵の差復元部と、
を含む、ことを特徴とする復元装置。
【請求項７】
スケッチの生成側では、
入力した鍵を誤り訂正符号の符号化関数を用いて符号化鍵に変換し、  
入力したファジーデータと前記符号化鍵に対し第一の合成変換を施してスケッチを生成し、
復元側では、
第一の鍵と第一のファジーデータに基づき生成された第一のスケッチと、第二の鍵と第二のファジーデータに基づき生成された第二のスケッチを受け取り、
前記第一のスケッチと前記第二のスケッチに対して第二の合成変換を施して合成スケッチを求め、
前記合成スケッチに基づき、前記第一のスケッチと前記第二のスケッチの生成にそれぞれ用いられた前記第一の鍵と前記第二の鍵の差を算出する、ことを特徴とする認証方法。
【請求項８】
鍵を受け取る処理と、
ファジーデータを受け取る処理と、
鍵を誤り訂正符号の符号化関数を用いて符号化鍵に変換する鍵変換部と、
前記ファジーデータと前記符号化鍵に対して第一の合成変換を施しスケッチを生成する処理と、
をコンピュータに実行させるプログラム。
【請求項９】
入力した鍵を誤り訂正符号の符号化関数を用いて符号化鍵に変換し、入力したファジーデータと前記符号化鍵に対し第一の合成変換を施しスケッチを生成する生成装置から第一の鍵と第一のファジーデータに基づき生成された第一のスケッチを受け取る処理と、
前記生成装置から第二の鍵と第二のファジーデータに基づき生成された第二のスケッチを受け取る処理と、
前記第一のスケッチと前記第二のスケッチに対して第二の合成変換を施して合成スケッチを求める処理と、
前記合成スケッチに基づき、前記第一のスケッチおよび前記第二のスケッチの生成にそれぞれ用いられた前記第一の鍵と前記第二の鍵の差を算出する処理と、
をコンピュータに実行させるプログラム。
【請求項１０】
請求項８又は９に記載のプログラムを記録した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はリニアスケッチシステム、装置、認証方法、プログラムと記録媒体に関する。
【背景技術】
【０００２】
個人認証は、被登録者と被認証者の同一性を確認する手段である。事前に保存される被登録者に関する情報と、認証の都度取得される被認証者に関する情報を突き合わせることによって実施される。【０００３】
生体認証では、例えば顔や指紋や虹彩などの身体的特徴などを利用して認証を行う。より具体的には、生体から特徴量と呼ばれるデータを抽出して認証に用いる。生体から抽出される特徴量は抽出の都度少しずつ異なる。そのため、認証時には、被登録者から抽出された特徴量と、被認証者から抽出された特徴量とを比較し、十分近い情報であると認められれば認証成功となる。【０００４】
生体認証は、パスワード等の記憶による認証やＩＣ（Integrated Circuit）カード等の所持による認証と比べ、認証情報を入力するために記憶や所持などのユーザの能動的な準備が不要であることから、利便性が高いというメリットがあるほか、認証情報を他人に使用されにくいことから、安全性が高いというメリットがある。【０００５】
特徴量抽出法などの技術の進展に伴い、近年、個人認証の手段として、生体認証の利用が進んでいる。【０００６】
一方で、生体認証には、生涯不変である生体情報がもし漏洩したとしても変更できないというデメリットもある。【０００７】
そこで、生体情報を秘匿して保存し、秘匿したまま認証結果を判定できる生体認証手法が盛んに研究されている。【０００８】
さらに、生体認証のメリットを活かすため、ユーザによる生体情報以外の記憶や所持が不要である方法が望ましい。【０００９】
そのような生体認証手法の一つとして、非特許文献１などに開示されているファジー署名（Fuzzy Signature）が挙げられる。ファジー署名はクライアントとサーバにより次のように実行される。【００１０】
・登録時：クライアントは、ユーザが入力した生体情報からテンプレートを生成し、サーバに送信する。サーバは、クライアントから受け取ったテンプレートを保存する。【００１１】
・認証時：クライアントは、ユーザが入力した生体情報と、サーバから受け取ったメッセージとから署名を生成し、サーバは、クライアントから受け取った署名と、保存されているテンプレートとから、認証結果を計算する。【００１２】
より詳細には、ファジー署名は、
（１．１）登録時に、クライアントが実行する鍵生成アルゴリズムと、
（１．２）認証時に、クライアントが実行する署名アルゴリズムと、
（１．３）認証時に、サーバが実行する検証アルゴリズムと、
を含む。各アルゴリズムについて以下に概説する。【００１３】
（１．１）鍵生成アルゴリズム：
セキュリティパラメータκとファジーデータｘを鍵生成アルゴリズムＫｅｙＧｅｎｆｓに入力すると、公開鍵（検証鍵）ｖｋを生成して出力する。
ＫｅｙＧｅｎｆｓ（１κ，ｘ）→ｖｋ  
・・・(1)【００１４】
（１．２）署名アルゴリズム：
ファジーデータｘ′とメッセージｍを署名アルゴリズムＳｉｇｎｆｓに入力すると、署名σを出力する。
Ｓｉｇｎｆｓ（ｘ′，ｍ）→σ  
・・・(2)【００１５】
（１．３）検証アルゴリズム：
検証鍵ｖｋ、メッセージｍ、署名σを検証アルゴリズムＶｅｒｉｆｙｆｓに入力すると、署名の検証結果としてＯＫ（good(okay)）又はＮＧ(no good)を出力する。
Ｖｅｒｉｆｙｆｓ（ｖｋ，ｍ，σ）→ＯＫ又はＮＧ 
・・・(3)【００１６】
ファジーデータのドメインＸ、
Ｘ上の距離関数ｄ（ｄ：Ｘ×Ｘ→Ｒ）、
閾値θ、
（ただし、Ｒは実数）
に対し、正しく構成されたファジー署名方式を用いると、ファジーデータｘ∈Ｘから鍵生成アルゴリズムで生成された検証鍵ｖｋを用い、ファジーデータｘと十分近いファジーデータｘ′∈Ｘを用いて、あるメッセージｍに対して生成された署名σを検証すると、ＯＫとなる。【００１７】
すなわち、任意のメッセージｍ、及び、ｄ（ｘ，ｘ′）≦θを満たすファジーデータｘとｘ′に関して、
ＫｅｙＧｅｎｆｓ（１κ，ｘ）→ｖｋ
・・・(4)
に対し、署名アルゴリズムＳｉｇｎｆｓの実行結果を
Ｓｉｇｎｆｓ（ｘ′，ｍ）→σ
・・・(5)
とすると、検証アルゴリズムＶｅｒｉｆｙｆｓの実行結果は、
Ｖｅｒｉｆｙｆｓ（ｖｋ，ｍ，σ）→ＯＫ
・・・(6)
が成り立つ。【００１８】
ファジー署名は、あいまいさを含む情報源から抽出されるファジーデータを用いて署名の付与や署名の検証に用いる鍵の生成を行う署名方式である。ファジーデータの典型例は、生体特徴量であるが、ファジー署名の用途は、生体のみに限らない。例えば、別の例として、タイポ（綴り間違いや誤入力、誤記、誤変換）を許容するパスワード認証がある。また、ＩＣ（Integrated Circuit）カードやパスワードなど、通常は、あいまいさを許容しない認証情報を利用する認証方式であっても、それらの認証情報がノイズを含む通信路を経由して授受される場合にも、ファジー署名が有効である。【００１９】
ファジー署名の実現方法は、例えば特許文献１、特許文献２、非特許文献１、非特許文献２などに開示されている。【００２０】
特に、非特許文献２には、リニアスケッチ（ｌｉｎｅａｒ  ｓｋｅｔｃｈ）と鍵線形性を持つデジタル署名を組み合わせた、一般的な構成法が開示されている。ここで、一般的な構成法を説明する前に、ｌｉｎｅａｒ  ｓｋｅｔｃｈ及び鍵線形性を持つデジタル署名について説明する。【００２１】
ｌｉｎｅａｒ  ｓｋｅｔｃｈは、
（２．１）鍵付きスケッチアルゴリズムと、
（２．２）鍵の差復元アルゴリズムと
からなる。【００２２】
各アルゴリズムについて以下に概説する。
（２．１）鍵付きスケッチアルゴリズム：
鍵ｋとファジーデータｘを鍵付きスケッチアルゴリズムＫｅｙｅｄＳｋｅｔｃｈに入力すると、スケッチｓを出力する。
ＫｅｙｅｄＳｋｅｔｃｈ（ｋ，ｘ）→ｓ
・・・(7)【００２３】
（２．２）鍵の差復元アルゴリズム：
二つのスケッチｓ、ｓ′を鍵の差復元アルゴリズムＤｉｆｆＲｅｃに入力すると、値Δｋを出力する。
ＤｉｆｆＲｅｃ（ｓ，ｓ′）→Δｋ
・・・(8)【００２４】
ファジーデータのドメインＸ、
Ｘ上の距離関数ｄ（ｄ：Ｘ×Ｘ→Ｒ）、
閾値θ、
に対し、正しく構成されたｌｉｎｅａｒ  ｓｋｅｔｃｈ方式は、十分近い２つのファジーデータｘ、ｘ′∈Ｘから生成された２つのスケッチｓ、ｓ′を、鍵の差復元アルゴリズムＤｉｆｆＲｅｃに入力すると、2つのスケッチｓ、ｓ′の生成に用いられた２つの鍵ｋ、ｋ′の差をΔｋとして出力する。【００２５】
すなわち、ｄ（ｘ，ｘ′）≦θ
・・・(9)
を満たすならば、
ＫｅｙｅｄＳｋｅｔｃｈ（ｋ，ｘ）→ｓ
・・・(10)
及び
ＫｅｙｅｄＳｋｅｔｃｈ（ｋ′，ｘ′）→ｓ′
・・・(11)
に対し、
ＤｉｆｆＲｅｃ（ｓ，ｓ′）→Δｋ（＝ｋ−ｋ′）
・・・(12)
となる。【００２６】
デジタル署名は、
（３．１）鍵生成アルゴリズムと、
（３．２）署名アルゴリズムと、
（３．３）検証アルゴリズムと
からなる。【００２７】
各アルゴリズムについて以下に概説する。【００２８】
（３．１）鍵生成アルゴリズム：
セキュリティパラメータκを鍵生成アルゴリズムＫｅｙＧｅｎｄｓに入力すると、秘密鍵（署名鍵）ｓｋ、公開鍵（検証鍵）ｖｋを生成して出力する。
ＫｅｙＧｅｎｄｓ（１κ）→（ｓｋ，ｖｋ）
・・・(13)【００２９】
（３．２）署名アルゴリズム：
署名鍵ｓｋとメッセージｍを署名アルゴリズムＳｉｇｎｄｓに入力すると、署名σを出力する。
Ｓｉｇｎｄｓ（ｓｋ，ｍ）→σ
・・・(14)【００３０】
（３．３）検証アルゴリズム：
検証鍵ｖｋ、メッセージｍ、署名σを検証アルゴリズムＶｅｒｉｆｙｄｓに入力すると、署名の検証結果としてＯＫ又はＮＧを出力する。
Ｖｅｒｉｆｙｄｓ（ｖｋ，ｍ，σ）→ＯＫ又はＮＧ
・・・(15)【００３１】
正しく構成されたデジタル署名方式を用いた場合、鍵生成アルゴリズムＫｅｙＧｅｎｄｓで生成された秘密鍵ｓｋを用いて、あるメッセージｍに対して生成された署名σは、対応する公開鍵ｖｋを用いて検証すると、ＯＫとなる。【００３２】
すなわち、
任意のｍ、及び、ＫｅｙＧｅｎｄｓ（１κ）→（ｓｋ，ｖｋ）
・・・(16)
に対し、署名アルゴリズムの実行結果を
Ｓｉｇｎｄｓ（ｓｋ，ｍ）→σ
・・・(17)
とすると、
Ｖｅｒｉｆｙｄｓ（ｖｋ，ｍ，σ）→ＯＫ
・・・(18)
が成り立つ。【００３３】
さらに、デジタル署名方式が鍵線形性を持つ場合、入力された２つの公開鍵ｖｋ、ｖｋ′にそれぞれ対応する２つの秘密鍵ｓｋ、ｓｋ′の差分Δｓｋが、入力されたもう一つの値に等しいか否かを判定する鍵の差検証アルゴリズムＭＫが存在する。【００３４】
すなわち、
ＫｅｙＧｅｎｄｓ（１κ）→（ｓｋ，ｖｋ）
・・・(19)
及び
ＫｅｙＧｅｎｄｓ（１κ）→（ｓｋ′，ｖｋ′）
・・・(20)
に対し、入力された２つの公開鍵ｖｋ、ｖｋ′にそれぞれ対応する２つの秘密鍵ｓｋ、ｓｋ′の差分を
Δｓｋ＝ｓｋ−ｓｋ′
・・・(21)
とすると、
ＭＫ（ｖｋ，ｖｋ′，Δｓｋ）→ＯＫ
・・・(22)
が成り立つ。【００３５】
鍵線形性を持つ署名アルゴリズムとして、Ｓｃｈｎｏｒｒ署名、Ｅｌｇａｍａｌ署名、ＤＳＡ(Digital Signature Algorithm)、ＥＣＤＳＡ(Elliptic Curve Digital Signature Algorithm)などが知られている。例えばＳｃｈｎｏｒｒ署名、Ｅｌｇａｍａｌ署名、ＤＳＡ署名では、位数が素数ｐである群Ｇｐの生成元ｇに対し、秘密鍵ｓｋとして、ｐより小さい正の整数がランダムに選ばれ、公開鍵は、
ｖｋ＝ｇｓｋ
・・・(23)
と定められる。【００３６】
このとき、２つの鍵ペア（ｓｋ，ｇｓｋ）及び（ｓｋ′，ｇｓｋ′）に対し、
Δｓｋ＝ｓｋ−ｓｋ′
・・・(24)
は、
ｇｓｋ／ｇｓｋ′＝ｇΔｓｋ
・・・(25)
を満たす。【００３７】
すなわち、
ＭＫ（ｖｋ，ｖｋ′，Δｓｋ）は、
ｖｋ／ｖｋ′＝ｇΔｓｋ
・・・(26)
であるときに、ＯＫを出力する。すなわち、公開鍵ｖｋ、ｖｋ′にそれぞれ対応する２つの秘密鍵ｓｋ、ｓｋ′の差分ｌｏｇ（ｖｋ／ｖｋ′）（ｌｏｇはｇを底とする対数関数）が、入力されたもう一つの値Δｓｋに等しい場合に、ＯＫを出力する。【００３８】
上記したｌｉｎｅａｒ  ｓｋｅｔｃｈと鍵線形性を持つデジタル署名を用いると、ファジー署名は、次のように構成できる。【００３９】
（４．１）鍵生成アルゴリズム：  
セキュリティパラメータκとファジーデータｘが鍵生成アルゴリズムＫｅｙＧｅｎｆｓに入力される。
【００４０】
デジタル署名方式の鍵生成アルゴリズムＫｅｙＧｅｎｄｓに、セキュリティパラメータκを入力して、秘密鍵ｓｋｄｓ及び公開鍵ｖｋｄｓを計算する。
ＫｅｙＧｅｎｄｓ（１κ）→（ｓｋｄｓ，ｖｋｄｓ）
・・・(27)【００４１】
次に、ｌｉｎｅａｒ  ｓｋｅｔｃｈ方式の鍵付きスケッチアルゴリズムＫｅｙｅｄＳｋｅｔｃｈに、秘密鍵ｓｋｄｓとファジーデータｘを入力して、スケッチｓを計算する。  
ＫｅｙｅｄＳｋｅｔｃｈ（ｓｋｄｓ，ｘ）→ｓ
・・・(28)【００４２】
次に、公開鍵ｖｋｄｓ及びスケッチｓを合わせた検証鍵ｖｋｆｓを出力する。
ｖｋｆｓ＝（ｓ，ｖｋｄｓ）
・・・(29)
このｖｋｆｓが上式（１）の公開鍵（検証鍵）ｖｋである。【００４３】
（４．２）署名アルゴリズム：
ファジーデータｘ’とメッセージｍが署名アルゴリズムＳｉｇｎｆｓに入力される。【００４４】
デジタル署名方式の鍵生成アルゴリズムＫｅｙＧｅｎｄｓに、セキュリティパラメータκを入力して、秘密鍵ｓｋ′ｄｓ及び公開鍵ｖｋ′ｄｓを計算する。
ＫｅｙＧｅｎｄｓ（１κ）→（ｓｋ′ｄｓ，ｖｋ′ｄｓ）
・・・(30)【００４５】
次に、秘密鍵ｓｋ′ｄｓとファジーデータｘ’をｌｉｎｅａｒ  ｓｋｅｔｃｈ方式の鍵付きスケッチアルゴリズムＫｅｙｅｄＳｋｅｔｃｈに入力して、スケッチｓ′を計算する。
ＫｅｙｅｄＳｋｅｔｃｈ（ｓｋ′ｄｓ，ｘ′）→ｓ′
・・・(31)【００４６】
次に、秘密鍵ｓｋ′ｄｓとメッセージｍをデジタル署名方式の署名アルゴリズムＳｉｇｎｄｓに入力して、署名σｄｓを計算する。
Ｓｉｇｎｄｓ（ｓｋ′ ｄｓ，ｍ）→σｄｓ
・・・(32)【００４７】
次に、公開鍵ｖｋ′ ｄｓとスケッチｓ′と署名σｄｓとを合わせた署名σｆｓを出力する。
σｆｓ＝（ｖｋ′ ｄｓ，ｓ′，σｄｓ）
・・・(33)
このσｆｓが式（２）の署名σである。【００４８】
(４．３）検証アルゴリズム:    
公開鍵ｖｋｄｓとメッセージｍと署名σが検証アルゴリズムＶｅｒｉｆｙｆｓ（式（３）)に入力される。【００４９】
次に、公開鍵ｖｋ′ ｄｓとメッセージｍと署名σｄｓをデジタル署名方式の検証アルゴリズム Ｖｅｒｉｆｙｄｓに入力して、ＯＫが出力されることを確認する。
Ｖｅｒｉｆｙｄｓ（ｖｋ′ ｄｓ，ｍ，σｄｓ）→ＯＫ
・・・(34)【００５０】
次に、スケッチｓとスケッチｓ′をｌｉｎｅａｒ  ｓｋｅｔｃｈ方式の鍵の差復元アルゴリズムＤｉｆｆＲｅｃに入力し、鍵の差Δｓｋｄｓを求める。
ＤｉｆｆＲｅｃ（ｓ，ｓ′）→Δｓｋｄｓ
・・・(35)【００５１】
次に、公開鍵ｖｋｄｓ、ｖｋ′ｄｓ、鍵の差Δｓｋｄｓに対して鍵の差検証アルゴリズムＭＫがＯＫを出力することを確認する。
ＭＫ（ｖｋｄｓ，ｖｋ′ｄｓ，Δｓｋｄｓ）→ＯＫ
・・・(36)【００５２】
上式（３４）及び式（３６）のいずれもＯＫ確認ができれば、ＯＫを出力（式（３）のＯＫに対応）、上式（３４）及び式（３６）のいずれか一方でもＮＧであれば、ＮＧ（式（３）のＮＧに対応）を出力する。【００５３】
さらに、非特許文献１や非特許文献２では、ｌｉｎｅａｒ  ｓｋｅｔｃｈの構成方法が開示されている。開示されたｌｉｎｅａｒ  ｓｋｅｔｃｈと、Ｓｃｈｎｏｒｒ署名などの鍵線形性を持つデジタル署名方式を組み合わせることにより、ファジー署名が構成できることも示されている。いずれの方式も、次のパラメータに対する方式である。【００５４】
・ファジーデータのドメインＸ＝［０，１）ｎ  （各成分が０以上１未満の実数からなるｎ次元ベクトル、［０，１）= {x | 0 =< x < 1} は左閉右開区間）。【００５５】
・Ｘ上の距離関数ｄ：Ｌ∞距離（チェビシェフ距離（Chebyshev distance）:２点の各座標の差の絶対値の最大値を２点間の距離とする）。すなわち、ｎ次元ベクトルｘ′=（ｘ１，…，ｘｎ），ｘ′=（ｘ′１，…，ｘ′ｎ）に関して距離関数ｄは以下で与えられる。
ｄ（（ｘ１，…，ｘｎ），（ｘ′１，…，ｘ′ｎ））＝ｍａｘ｜（ｘi―ｘ′i）｜
（i=1, …，n）
・・・(37)【００５６】
・閾値θ：１／（２θ）が整数となる、０以上１未満の実数。【００５７】
しかし、指紋や虹彩などから抽出される多くの特徴量は、Ｌ∞距離による照合が行えず、例えば次のパラメータを扱う。【００５８】
・ファジーデータのドメインＸ＝｛０，１｝ｎ  （すなわち、各成分が０又は１からなるｎ次元ベクトル）【００５９】
・Ｘ上の距離関数ｄ：ハミング距離（Ｌ１距離）。距離関数ｄは以下で与えられる。
ｄ（（ｘ１，…，ｘｎ），（ｘ′１，…，ｘ′ｎ））＝ｓｕｍ｜（ｘi―ｘ′i）｜  
（i=1, …，n）
・・・(38)【００６０】
・閾値θ：０以上ｎ以下の整数【００６１】
つまり、このようなパラメータに対する特徴量は、そのまま非特許文献１及び非特許文献２のファジー署名方式を利用することはできない。【００６２】
特許文献３には、非特許文献１及び非特許文献２の技術において、２つの生体情報同士が十分類似しているか否かの判定処理が、生体から抽出される特徴量同士の「Ｌ∞距離」に対するしきい値処理で実現されることに相当しており、指紋や静脈、顔、虹彩など多くの生体認証方式では、特徴量同士の距離が、ハミング距離（L1距離）などで定義されるため、上記技術に基づいたファジー署名を実現することができない、という課題が記載されている。特許文献３には、この課題に対して、任意のｐに対するＬｐ距離空間上の特徴量を、Ｌ∞距離空間上のベクトルに変換することで、様々な種類の特徴量を用いたファジー署名を実現する手法（発明）が開示されている。特許文献３に開示されている手法は、例えば、Ｌ１距離に基づいて近さの判定を行う特徴量を、Ｌ∞距離に基づいて近さの判定を行う特徴量に変換するために用いることができる。
【先行技術文献】
【特許文献】
【００６３】
【特許文献１】特許第５７０７３１１号公報
【特許文献２】特許第６０９６８９３号公報
【特許文献３】特許第６２１６５６７号公報
【非特許文献】
【００６４】
【非特許文献１】TAKAHASHI, Kenta, MATSUDA, Takahiro, MURAKAMI, Takao, HANAOKA, Goichiro, NISHIGAKI, Masakatsu. A Signature Scheme with a Fuzzy Private Key. Malkin, Tal and Kolesnikov, Vladimir and Lewko, Allison Bishop and Polychronakis, Michalis. Springer International Publishing, 2015, 105--126. (Lecture Notes in Computer Science). (9092). http://dx.doi.org/10.1007/978-3-319-28166-7_6. ISBN: 978-3-319-28166-7.
【非特許文献２】MATSUDA, Takahiro, TAKAHASHI, Kenta, MURAKAMI, Takao, HANAOKA, Goichiro. Fuzzy Signatures: Relaxing Requirements and a New Construction. Manulis, Mark and Sadeghi, Ahmad-Reza and Schneider, Steve. Springer International Publishing, 2016, 97--116. (Lecture Notes in Computer Science). (9696). http://dx.doi.org/10.1007/978-3-319-39555-5_6. ISBN: 978-3-319-39555-5.
【発明の概要】
【発明が解決しようとする課題】
【００６５】
以下に関連技術の分析を与える。【００６６】
上記したように、例えば指紋や虹彩など特徴量同士の距離が、ハミング距離（L1距離）で定義される生体特徴量などのデータに関して、上記非特許文献１、２等の関連技術の手法をそのまま適用することはできない。  【００６７】
また、特許文献３等に開示された手法を特許文献１、２等の関連技術の手法と組み合わせることは可能であるが、特許文献３に開示された手法は、漸近的な変換であり、ベクトルの次元（ｎ）が大きい場合には、大きな誤差が生じてしまう。すなわち、生体認証の精度が下がってしまう。  【００６８】
そこで、特許文献３等に開示された変換手法に頼らずに、あいまいな情報源から抽出される生体特徴量などのデータに関する近さの判定をハミング距離に基づいて行うｌｉｎｅａｒ  ｓｋｅｔｃｈ方式を構成することが要望される。【００６９】
したがって、本発明は、上述した課題に鑑みて創案されたものであって、その目的は、あいまいな情報源から抽出される生体特徴量などのデータに関する近さの判定をハミング距離に基づいて行うことを実現可能とするリニアスケッチ（ｌｉｎｅａｒ  ｓｋｅｔｃｈ）システム、生成装置、復元装置、認証方法、及び、プログラム、記録媒体を提供することにある。
【課題を解決するための手段】
【００７０】
本発明の一つの形態によれば、リニアスケッチシステムは、生成装置と、復元装置と、を含む。前記生成装置は、鍵を受け取る鍵入力部と、ファジーデータを受け取るファジーデータ入力部と、鍵を誤り訂正符号の符号化関数を用いて符号化鍵に変換する鍵変換部と、前記ファジーデータと前記符号化鍵に対して第一の合成変換を施しスケッチを生成するスケッチ生成部とを含む。前記復元装置は、第一の鍵と第一のファジーデータに基づき生成された第一のスケッチと、第二の鍵と第二のファジーデータに基づき生成された第二のスケッチを受け取るスケッチ入力部と、前記第一のスケッチと前記第二のスケッチに対して第二の合成変換を施して合成スケッチを求めるスケッチ合成部と、前記合成スケッチに基づき、前記第一のスケッチと前記第二のスケッチの生成にそれぞれ用いられた前記第一の鍵と前記第二の鍵の差を算出する鍵の差復元部とを含む。【００７１】
本発明の一つの形態によれば、鍵を受け取る鍵入力部と、ファジーデータを受け取るファジーデータ入力部と、を誤り訂正符号の符号化関数を用いて符号化鍵に変換する鍵変換部と、前記ファジーデータと前記符号化鍵に対して第一の合成変換を施しスケッチを生成するスケッチ生成部と、を備えた生成装置が提供される。【００７２】
本発明の一つの形態によれば、入力した鍵を誤り訂正符号の符号化関数を用いて符号化鍵に変換し、入力したファジーデータと前記符号化鍵に対し第一の合成変換を施しスケッチを生成する生成装置から、第一の鍵と第一のファジーデータに基づき生成された第一のスケッチと、第二の鍵と第二のファジーデータに基づき生成された第二のスケッチとを受け取るスケッチ入力部と、前記第一のスケッチと前記第二のスケッチに対して第二の合成変換を施して合成スケッチを求めるスケッチ合成部と、前記合成スケッチに基づき、前記第一のスケッチおよび前記第二のスケッチの生成にそれぞれ用いられた前記第一の鍵と前記第二の鍵の差を算出する鍵の差復元部と、を含む復元装置が提供される。【００７３】
本発明の一つの形態によれば、
スケッチの生成側では、
入力した鍵を誤り訂正符号の符号化関数を用いて符号化鍵に変換し、  
入力したファジーデータと前記符号化鍵に対し第一の合成変換を施してスケッチを生成し、
復元側では、
第一の鍵と第一のファジーデータに基づき生成された第一のスケッチと、第二の鍵と第二のファジーデータに基づき生成された第二のスケッチを受け取り、
前記第一のスケッチと前記第二のスケッチに対して第二の合成変換を施して合成スケッチを求め、
前記合成スケッチに基づき、前記第一のスケッチと前記第二のスケッチの生成にそれぞれ用いられた前記第一の鍵と前記第二の鍵の差を算出する認証方法が提供される。【００７４】
本発明の一つの形態によれば、鍵を受け取る処理と、ファジーデータを受け取る処理と、鍵を誤り訂正符号の符号化関数を用いて符号化鍵に変換する鍵変換部と、前記ファジーデータと前記符号化鍵に対して第一の合成変換を施しスケッチを生成する処理と、をコンピュータに実行させるプログラムが提供される。【００７５】
本発明の一つの形態によれば、入力した鍵を誤り訂正符号の符号化関数を用いて符号化鍵に変換し、入力したファジーデータと前記符号化鍵に対し第一の合成変換を施しスケッチを生成する生成装置から第一の鍵と第一のファジーデータに基づき生成された第一のスケッチを受け取る処理と、前記生成装置から第二の鍵と第二のファジーデータに基づき生成された第二のスケッチを受け取る処理と、前記第一のスケッチと前記第二のスケッチに対して第二の合成変換を施して合成スケッチを求める処理と、前記合成スケッチに基づき、前記第一のスケッチ及び前記第二のスケッチの生成にそれぞれ用いられた前記第一の鍵と前記第二の鍵の差を算出する処理と、をコンピュータに実行させるプログラムが提供される。【００７６】
本発明によれば、上記プログラムを記憶したコンピュータ読み出し可能な記録媒体（例えばＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、又は、ＥＥＰＲＯＭ（Electrically Erasable and Programmable ROM）等の半導体ストレージや、ＨＤＤ（Hard Disk Drive）、ＣＤ（Compact Disc）、ＤＶＤ（Digital Versatile Disc）等の非一時的なコンピュータ読み出し可能な記録媒体（non-transitory computer readable recording medium））が提供される。
【発明の効果】
【００７７】
本発明によれば、あいまいな情報源から抽出される生体特徴量などのデータに関する近さの判定をハミング距離に基づいて行うｌｉｎｅａｒ  ｓｋｅｔｃｈシステムを実現可能としている。
【図面の簡単な説明】
【００７８】
【図１】本発明の第１の例示的な実施形態のｌｉｎｅａｒ  ｓｋｅｔｃｈシステムの構成例を模式的に示す図である。
【図２Ａ】本発明の第１の例示的な実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステムの生成装置の動作を説明するための流れ図である。
【図２Ｂ】本発明の第１の例示的な実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステムの復元装置の動作を説明するための流れ図である。
【図３】本発明の第２、第３の例示的な実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステムの構成例を模式的に示す図である。
【図４Ａ】本発明の第２、第３の例示的な実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステムの生成装置の動作を説明するための流れ図である。
【図４Ｂ】本発明の第２、第３の例示的な実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステムの復元装置の動作を説明するための流れ図である。
【図５】本発明の第４の例示的な実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステムの構成例を模式的に示す図である。
【図６】本発明の第４の例示的な実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステムの生成装置の動作を説明するための流れ図である。
【図７】本発明の実施形態の構成例を説明する図である。
【図８】（Ａ）乃至（Ｅ）は本発明の第１乃至第５の実施形態の生成装置の演算を説明する図である。
【発明を実施するための形態】
【００７９】
本発明の例示的な実施形態について図面を参照して詳細に説明する。なお、各図面及び明細書記載の各実施形態において、同様の構成要素には同一の符号を付与し、説明を適宜省略する。
【００８０】
本発明の一形態のｌｉｎｅａｒ  ｓｋｅｔｃｈシステムは、誤り訂正符号によって鍵を符号化して得られる符号化鍵と、ファジーデータとを合成することによりスケッチを生成する生成装置と、誤り訂正符号によって合成した二つのスケッチを復号することにより、二つのファジーデータが十分近い場合には、二つの鍵の線形変換結果を出力する復元装置とを有する。 
【００８１】
以下の各実施形態では、特に制限されないが、次のパラメータに対するｌｉｎｅａｒ  ｓｋｅｔｃｈシステムの実現例を説明する。
【００８２】
・ファジーデータのドメインＸ＝各成分が整数であるｎ次元ベクトル
【００８３】
・Ｘ上の距離関数ｄ：Ｌ１距離（ハミング距離）
ｄ（（ｘ１，…，ｘｎ），（ｘ′１，…，ｘ′ｎ））＝  （ｉ＝１,…，ｎのうち、ｘi≠ｘ′iであるインデックスｉの個数）
・・・(39)
【００８４】
・閾値θ：０以上ｎ以下の整数
【００８５】
なお、上記パラメータに対するファジーデータでなくても、上記パラメータに対するファジーデータに変換可能である場合がある。
【００８６】
例えば、各成分が実数であるｎ次元ベクトルは、定数倍することによってこのドメインに含まれるファジーデータに変換可能である。
【００８７】
以下の各実施形態では、構成要素として線形性を持つ誤り訂正符号（以下では、「線形符号」と呼ぶ）を用いる。まず線形符号について説明する。
【００８８】
誤り訂正符号は、
（５．１）符号化アルゴリズムと、
（５．２）復号アルゴリズムと
からなる。
【００８９】
各アルゴリズムについて以下に概説する。
【００９０】
（５．１）符号化アルゴリズム：
メッセージｍを符号化アルゴリズムＥｎｃｏｄｅに入力すると、符号語ｃを生成して出力する。
Ｅｎｃｏｄｅ（ｍ）→ｃ
・・・(40)
【００９１】
（５．２）復号アルゴリズム：
符号語ｃを復号アルゴリズムＤｅｃｏｄｅに入力すると、メッセージｍを出力する。
Ｄｅｃｏｄｅ（ｃ）→ｍ
・・・(41)
【００９２】
メッセージｍがＭブロックからなり、符号語ｃがＣブロック（Ｍ＜Ｃ）からなり、Ｄブロックの誤りを許す誤り訂正符号方式では、正しく構成すると、メッセージｍから符号化アルゴリズムＥｎｃｏｄｅで生成された符号語ｃに関して、Ｃブロックのうち符号語ｃと異なるブロック数がＤ（Ｄ＜Ｃ）ブロック以下である任意の符号語ｃ′を、復号アルゴリズムＤｅｃｏｄｅに入力すると、元のメッセージｍが復元される。
【００９３】
すなわち、任意のＭブロックのメッセージｍに対し、
Ｅｎｃｏｄｅ（ｍ）→ｃ
・・・(42)
とすると、符号語ｃと異なるブロック数がＤブロック以下である任意の符号語ｃ′について、
Ｄｅｃｏｄｅ（ｃ′）→ｍ
・・・(43)
が成り立つ。
【００９４】
さらに、消失訂正も可能な誤り訂正符号の場合、ブロックの誤り及びブロックの消失が合計Ｄブロック以下であれば、正しく復号可能である。  
【００９５】
線形符号を用いると、二つの符号語から、それらのメッセージのブロックごとの線形演算結果に対応する符号語を計算することができる。すなわち、例えば、
Ｅｎｃｏｄｅ（ｍ）→ｃ  及びＥｎｃｏｄｅ（ｍ′）→ｃ′
・・・(44)
に対して、
符号語ｃと符号語ｃ′のブロックごとの和を
Δｃ＝ｃ＋ｃ′
・・・(45)
とすると、メッセージｍとメッセージｍ′のブロックごとの和が、Δｃの復号結果として得られる。
Ｄｅｃｏｄｅ（Δｃ）＝ｍ＋ｍ′
・・・(46)
【００９６】
線形符号は、Ｃブロックからなる符号語の前半部分のＭブロックをメッセージそのものとするように構成することが可能である。このような構成法を、特に、「組織符号」と呼ぶ。
【００９７】
各ブロックがＢビットである線形符号では、メッセージは各要素がＢビット以下のＭ次元ベクトルであり、符号語は各要素がＢビット以下のＣ次元ベクトルであり、前記のｃ＋ｃ′やｍ＋ｍ′の演算は法を２Ｂとして実行される。
【００９８】
また、各ブロックがＢビットである線形符号では、Ｍブロックのメッセージｍから符号化アルゴリズムで生成されたＣブロック符号語ｃと比較し、異なるブロックの個数がＤ個以下であるＣブロックの系列から、復元アルゴリズムによって、メッセージｍが復元される。
【００９９】
したがって、各ブロックが１ビットである線形符号では、前記したｃ＋ｃ′やｍ＋ｍ′の演算が排他的論理和（Exclusive OR: XOR、すなわち、０＋０＝１＋１＝０、０＋１＝１＋０＝１）となる。
【０１００】
また、各ブロックが１ビットである誤り訂正符号では、Ｍビットのメッセージｍから符号化アルゴリズムで生成されたＣビットの符号語ｃと比較し、異なるビットの数がＤビット以下であるｃ′から、復元アルゴリズムによって、メッセージｍが復元される。すなわち、ｃとのハミング距離がＤ以下であるｃ′から、復元アルゴリズムによって、メッセージｍが復元される。
【０１０１】
線形符号として、ＢＣＨ(Bose-Chaudhuri- Hocquenghem code)符号、リードソロモン符号、ＬＤＰＣ（Low-Density Parity-Check code）符号などが知られている。また、リードソロモン符号やＬＤＰＣ符号は消失訂正も可能である。
【０１０２】
本発明の実施形態のｌｉｎｅａｒ  ｓｋｅｔｃｈシステムをファジー署名方式の構成に用いると、ハミング距離に基づいて近さの判定を行う生体特徴量などのデータを扱い、精度を落とさずにファジー署名を実現可能としている。以下、いくつかの実施形態に基づきさらに詳細に説明する。
【０１０３】
［第１の例示的な実施形態］ 
本実施形態では、ファジーデータは、あいまいな情報源から抽出される生体特徴量などのデータであり、各要素の値が０又は１のｎ次元ベクトルとする。
【０１０４】
本実施形態では、次のパラメータに対する線形符号を用いることが望ましい。
【０１０５】
・メッセージに含まれるブロック数：Ｍ＝入力される鍵の長さ、
・符号語に含まれるブロック数：Ｃ＝ｎ、
・許容される誤りブロック数：Ｄ＝θ（生体特徴量の閾値）、
・各ブロックのビット長：Ｂ＝１
【０１０６】
図１は、本実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステム１００の構成の一例を模式的に示す図である。ｌｉｎｅａｒ  ｓｋｅｔｃｈシステム１００は、生成装置１１０と復元装置１２０を含む。
【０１０７】
生成装置１１０は、鍵入力部１１１と、ファジーデータ入力部１１２と、鍵変換部１１３と、スケッチ生成部１１４を備えている。復元装置１２０は、第一スケッチ入力部１２１と、第二スケッチ入力部１２２と、スケッチ合成部１２３と、鍵の差復元部１２４を備えている。生成装置１１０、復元装置１２０は、それぞれ、メモリに保持された命令を実行するプロセッサと、ネットワークインタフェース等の入出力インタフェースを備えたコンピュータで構成し、プロセッサでプログラムを実行することで、各装置の各部の処理を実現するようにしてもよい。生成装置１１０、復元装置１２０は、ネットワーク１３０（有線ＬＡＮ（Local Area Network）又は無線ＬＡＮ、あるいは、ＷＡＮ(Wide Area Network)、又は移動体通信網等）を介して相互に通信接続される。ただし、生成装置１１０、復元装置１２０を同一装置内に実装し通信接続する構成としてもよい。
【０１０８】
図２Ａは、本実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステム１００の生成装置１１０の動作を説明するための流れ図である。
【０１０９】
生成装置１１０は、鍵入力部１１１から入力される鍵ｋ（Ｍビット）を受け取り、ファジーデータ入力部１１２から、入力されるファジーデータｘを受け取る（ステップＡ１）。鍵入力部１１１は、例えば上式（２９）の鍵Ｖｋｆｓを入力する。生成装置１１０は、上記（４．１）の鍵生成アルゴリズムを実行する装置（不図示）から、鍵Ｖｋｆｓを入力するようにしてもよい。ファジーデータ入力部１１２は、不図示のセンサから取得された生体情報等の特徴量を、ファジーデータｘとして入力するようにしてもよい。
【０１１０】
生成装置１１０の鍵変換部１１３は、鍵入力部１１１から受け取った鍵ｋを入力として誤り訂正符号の符号化アルゴリズム（Ｅｎｃｏｄｅ）を実行し、実行結果である符号化鍵ｃ（Ｃビット）を得る（ステップＡ２）。
Ｅｎｃｏｄｅ（ｋ）→ｃ
・・・(47)
【０１１１】
次に、生成装置１１０のスケッチ生成部１１４は、ステップＡ１においてファジーデータ入力部１１２から受け取ったファジーデータｘ（Ｃビット）と、ステップＡ２で得た符号化鍵ｃとのビットごとの排他的論理和（bit-wise xor）を計算し、スケッチｓとして出力する（ステップＡ３）。
ｓ＝ｘ xor ｃ
・・・(48)
【０１１２】
なお、図８（Ａ）は、上記した生成装置１１０におけるスケッチｓの生成のビット演算過程を例示した図である。
【０１１３】
図２Ｂは、本実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステム１００の復元装置１２０の動作を説明するための流れ図である。
【０１１４】
復元装置１２０の第一スケッチ入力部１２１は、入力される第一のスケッチｓを受け取り、第二スケッチ入力部１２２は、入力される第二のスケッチｓ′を受け取る（ステップＢ１）。なお、図１において、第一スケッチ入力部１２１と第二スケッチ入力部１２２とは別々のユニットとして例示されているが、これらを一つのスケッチ入力部１２１１で構成し、スケッチ入力部１２１１で第一のスケッチｓと第二のスケッチｓ′を受け取るようにしてもよい。
【０１１５】
次に、復元装置１２０のスケッチ合成部１２３は、ステップＢ１で受け取った第一のスケッチｓと第二のスケッチｓ′とのビットごとの排他的論理和を計算して、合成スケッチｔを得る（ステップＢ２）。
ｔ＝ｓ xor ｓ′
・・・(49)
【０１１６】
次に、復元装置１２０の鍵の差復元部１２４は、ステップＢ２で計算した合成スケッチｔを誤り訂正符号の復号アルゴリズムＤｅｃｏｄｅに入力して実行し、復号結果Δを出力する（ステップＢ３）。
Ｄｅｃｏｄｅ（ｔ）→Δ
・・・(50)
【０１１７】
本実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステムが正しく動作することを確認する。
【０１１８】
生成装置１１０によって鍵ｋ（第一の鍵）とファジーデータｘ（第一のファジーデータ）とから生成された第一のスケッチをｓとする。
ｓ＝ｘ xor Ｅｎｃｏｄｅ（ｋ）
・・・(51)
【０１１９】
また、生成装置１１０によって鍵ｋ′（第二の鍵）とファジーデータｘ′（第二のファジーデータ）とから生成された第二のスケッチをｓ′とする。
ｓ′＝ｘ′ xor  Ｅｎｃｏｄｅ（ｋ′）
・・・(52)
【０１２０】
生成装置１１０は、生成したこれら第一及び第二のスケッチｓ、ｓ′を、例えばネットワーク１３０等の通信手段を介して、復元装置１２０にそれぞれ第一のスケッチ及び第二のスケッチとして入力する。
【０１２１】
復元装置１２０のスケッチ合成部１２３において（ステップＢ２）、
ｔ＝ｓ xor ｓ′
＝（ｘ xor Ｅｎｃｏｄｅ（ｋ））xor（ｘ′xor Ｅｎｃｏｄｅ（ｋ′））
＝（ｘ xor ｘ′)  xor Ｅｎｃｏｄｅ（ｋ） xor Ｅｎｃｏｄｅ（ｋ′）
・・・(53)
が計算される。
【０１２２】
各ブロックが１ビットである線形符号を用いているため、式（５３）は、
ｔ＝（ｘ xor ｘ′）xor Ｅｎｃｏｄｅ （ｋ xor ｋ′）
・・・(54)
と表せる。
【０１２３】
さらに、ｘとｘ′のハミング距離が線形符号の誤り訂正能力Ｄ以下であるとき、
Ｅｎｃｏｄｅ（ ｋ xor ｋ′）とｔのハミング距離もＤ以下である。
【０１２４】
なぜなら、
Ｅｎｃｏｄｅ （ｋ xor ｋ′） xor  ｔ
＝Ｅｎｃｏｄｅ （ｋ xor ｋ′） xor (（ｘ xor ｘ′）xor Ｅｎｃｏｄｅ （ｋ xor ｋ′）)
＝ｘ xor ｘ′
・・・(55)
であり、Ｅｎｃｏｄｅ（ ｋ xor ｋ′）とｔのハミング距離は、ｘとｘ′のハミング距離に等しいためである。
【０１２５】
したがって、ｋ xor ｋ′の符号語Ｅｎｃｏｄｅ（ ｋ xor ｋ′）とのハミング距離がＤ以下のｔから復元アルゴリズムＤｅｃｏｄｅ（ｔ）の実行によって、ｋ xor ｋ′が復元される。すなわち、Ｄｅｃｏｄｅ（ｔ）の結果Δは、ｋ xor ｋ′である。
Ｄｅｃｏｄｅ（（ｘ xor ｘ′）xor Ｅｎｃｏｄｅ（ｋ xor ｋ′））→ｋ xor ｋ′
・・・(56)
【０１２６】
すなわち、図２ＢのステップＢ３では、第一の鍵ｋと第二の鍵ｋ′の差ｋ-ｋ′が正しく計算されることを確認することができる。
【０１２７】
上述した本実施形態によれば、各々が符号化鍵とファジーデータをビットごとの排他的論理和である第一、第二のスケッチをビットごとの排他的論理和で合成した合成スケッチを誤り訂正復号することで、ビットごとの排他的論理和によって計算された鍵の差を算出できる。
【０１２８】
［第２の例示的な実施形態］ 
本実施形態では、次のパラメータに対する線形符号を用いることが望ましい。
・メッセージに含まれるブロック数：Ｍ、
・符号語に含まれるブロック数：Ｃ＝ｎ（生体特徴量の長さ）、
・許容される誤りブロック数：Ｄ＝θ（生体特徴量の閾値）、
・各ブロックのビット長：Ｂ＝入力される鍵の長さ。
【０１２９】
図３は、第２の例示的な実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステム２００の構成の一例を模式的に示す図である。ｌｉｎｅａｒ  ｓｋｅｔｃｈシステム２００は生成装置２１０と復元装置２２０を含む。
【０１３０】
生成装置２１０は、鍵入力部２１１と、ファジーデータ入力部２１２と、乱数取得部２１５と、鍵変換部２１３と、スケッチ生成部２１４を備えている。復元装置２２０は、第一スケッチ入力部２２１と、第二スケッチ入力部２２２と、スケッチ合成部２２３と、拡張鍵の差復元部２２５と、鍵の差復元部２２４を備えている。生成装置２１０、復元装置２２０は、それぞれ、メモリに保持された命令を実行するプロセッサと、ネットワークインタフェース等の入出力インタフェースを備えたコンピュータで構成し、プロセッサでプログラムを実行することで、各装置の各部の処理を実現するようにしてもよい。生成装置２１０、復元装置２２０は、ネットワーク２３０（有線ＬＡＮ（Local Area Network）又は無線ＬＡＮ、ＷＡＮ(Wide Area Network)、移動体通信網等）を介して相互に通信接続される。ただし、生成装置２１０、復元装置２２０を同一装置内に実装し通信接続する構成としてもよい。
【０１３１】
図４Ａは、本実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステム２００の生成装置２１０の動作を説明するための流れ図である。
【０１３２】
生成装置２１０の鍵入力部２１１は、入力される鍵ｋ（Ｂビット）を受け取り、ファジーデータ入力部２１２は、入力されるファジーデータｘを受け取る（ステップＣ１）。
【０１３３】
次に、生成装置２１０の乱数取得部２１５は、鍵のサイズ以上の長さ（例えばＢビット）の乱数をＭ−１個取得する（ステップＣ２）。本実施形態において、乱数の取得の手法として、任意の手法を用いることができる。例えば、生成装置２１０の内部で生成してもよいし、生成装置２１０の外部で生成したものを生成装置２１０に入力してもよい。
生成した乱数を、
ｒ２，…，ｒＭ
・・・(57)
と表す。
【０１３４】
次に、生成装置２１０の鍵変換部２１３は、ステップＣ１で受け取った鍵ｋと、ステップＣ２で取得したＭ−１個の乱数ｒ2，…，ｒＭを並べ（例えば、ｋ，ｒ２，…，ｒＭ）、鍵ｋとＭ−１個の乱数ｒｉ（i=2, …，M）からなるＭブロックの系列（Ｂ×Ｍビット）としたものを生成する。
【０１３５】
そして、鍵変換部２１３は、Ｍブロックの系列（Ｂ×Ｍビット）に対して、誤り訂正符号の符号化アルゴリズム（Ｅｎｃｏｄｅ）に入力して実行し、結果として、Ｍブロックからなる符号化鍵ｃを得る（ステップＣ３）。
Ｅｎｃｏｄｅ（ｋ，ｒ２，…，ｒＭ）→ｃ＝（ｃ１，…，ｃＣ）
・・・(58)
【０１３６】
ただし、ｋとＭ−１個の乱数の順序は、上記に制限されるものでなく、任意の順序で並べてもよい。
【０１３７】
次に、生成装置２１０のスケッチ生成部２１４は、ステップＣ１で受け取った各成分が０又は１からなるＣビットのファジーデータｘと、ステップＣ３で得た符号化鍵ｃとのブロックごとの加算結果（又は減算結果）：
ｘ＋ｃ＝（ｘ１＋ｃ１，…，ｘＣ＋ｃＣ）
・・・(59)
を計算し、スケッチｓ（Ｃブロック、Ｂ×Ｃビット）として出力する（ステップＣ４）。  
【０１３８】
図８（Ｂ）は上記した生成装置２１０におけるスケッチｓの生成の演算（ブロック毎の演算）を例示した図である。生成装置２１０は、第一のスケッチｓ＝（ｓ１，…，ｓＣ）、第二のスケッチｓ′＝（ｓ′１，…，ｓ′Ｃ）を生成する。
【０１３９】
図４Ｂは、本実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステム２００の復元装置２２０の動作を説明するための流れ図である。
【０１４０】
復元装置２２０の第一スケッチ入力部２２１は、生成装置２１０から入力される第一のスケッチｓ＝（ｓ１，…，ｓＣ）を受け取り、第二スケッチ入力部２２２は、生成装置２１０から入力される第二のスケッチｓ′＝（ｓ′１，…，ｓ′Ｃ）を受け取る（ステップＤ１）。なお、図３において、第一スケッチ入力部２２１と第二スケッチ入力部２２２とは別々のユニットとして例示されているが、これらを一つのスケッチ入力部２２１１で構成し、スケッチ入力部２２１１で第一のスケッチｓと第二のスケッチｓ′を受け取るようにしてもよい。
【０１４１】
次に、復元装置２２０のスケッチ合成部２２３は、ステップＤ１で受け取った
第一のスケッチｓ＝（ｓ１，…，ｓＣ）と、
第二のスケッチｓ′＝（ｓ′１，…，ｓ′Ｃ）
との成分ごとの減算結果（又は加算結果）を計算することにより、合成スケッチｔを得る（ステップＤ２）。
ｔ＝（ｓ１−ｓ′１，…，ｓＣ−ｓ′Ｃ）
・・・(60)
【０１４２】
次に、復元装置２２０の拡張鍵の差復元部２２４は、ステップＤ２で計算した値ｔを、誤り訂正符号の復号アルゴリズム（Ｄｅｃｏｄｅ）に入力して実行し、
Ｄｅｃｏｄｅ（ｔ）→（Δ１，…，ΔＭ）
・・・(61)
を得る（ステップＤ３）。
【０１４３】
次に、復元装置２２０の鍵の差復元部２２４は、ステップＤ３で計算した値の第１成分Δ１を出力する（ステップＤ４）。ただし、ステップＣ３において、鍵ｋをｉブロック目（ｉ＝２，・・・、Ｃのいずれか）に配置した場合、第ｉ成分Δｉを出力する。
【０１４４】
上記のように動作することで、第２の例示的な実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステムが正しく動作することを確認する。
【０１４５】
生成装置２１０によって鍵ｋ及びファジーデータｘから生成されたスケッチをｓとする。すなわち、スケッチｓは次式で表せる。
ｓ＝（ｘ１，…，ｘＣ）＋Ｅｎｃｏｄｅ（ｋ，ｒ２，…，ｒＭ）
・・・(62)
【０１４６】
また、生成装置２１０によって鍵ｋ′及びファジーデータｘ′から生成されたスケッチをｓ′とする。すなわち、ｓ′は次式で表せる。
ｓ′＝（ｘ′１，…，ｘ′Ｃ）＋Ｅｎｃｏｄｅ（ｋ′，ｒ′２，…，ｒ′Ｍ）
・・・(63)
【０１４７】
これらのｓとｓ′を、それぞれ第一のスケッチ及び第二のスケッチとして復元装置２２０に入力すると、ステップＤ２では次式が計算される。
ｔ＝（ｘ１，…，ｘＣ）−（ｘ′１，…，ｘ′Ｃ）
＋Ｅｎｃｏｄｅ（ｋ，ｒ２，…，ｒＭ）
−Ｅｎｃｏｄｅ（ｋ′，ｒ′２，…，ｒ′Ｍ）
＝（ｘ１−ｘ′１，…，ｘＣ−ｘ′Ｃ）
＋Ｅｎｃｏｄｅ（ｋ，ｒ２，…，ｒＭ）
−Ｅｎｃｏｄｅ（ｋ′，ｒ′２，…，ｒ′Ｍ）
・・・(64)
【０１４８】
線形符号を用いているため、式（６４）は
ｔ＝（ｘ１−ｘ′１，…，ｘＣ−ｘ′Ｃ）
＋Ｅｎｃｏｄｅ（ｋ−ｋ′，ｒ２−ｒ′２，…，ｒＭ−ｒ′Ｍ）
・・・(65)
と表せる。
【０１４９】
さらに、ｘとｘ′のハミング距離が線形符号の誤り訂正能力Ｄ以下であるとき、
（ｘ１−ｘ′１，…，ｘＣ−ｘ′Ｃ）
は、Ｃ−Ｄ個以上の０と、Ｄ個以下の１からなるベクトルである。
【０１５０】
このため、Ｅｎｃｏｄｅ（ｋ−ｋ′，ｒ２−ｒ′２，…，ｒＭ−ｒ′Ｍ）とｔの異なるブロックの個数はＤ個以下である。
【０１５１】
したがって、ステップＤ３のＤｅｃｏｄｅ（ｔ）の結果は、
（Δ１，…，ΔＭ）＝（ｋ−ｋ′，ｒ２−ｒ′２，…，ｒＭ−ｒ′Ｍ）
・・・(66)
となる。
【０１５２】
すなわち、ステップＤ４では、２つの鍵ｋとｋ′の差ｋ−ｋ′が正しく計算されることが確認できる。
【０１５３】
本実施形態によれば、符号化鍵とファジーデータをブロックごとの加算や減算によって合成しているため、復元装置では、減算によって計算された鍵の差を正しく算出することができる。
【０１５４】
［第３の例示的な実施形態］
本発明の第３の例示的な実施形態では、次のパラメータに対する消失訂正も可能な線形組織符号を用いることが望ましい。
【０１５５】
・メッセージに含まれるブロック数：Ｍ、
・符号語に含まれるブロック数：Ｃ＝ｎ＋１（生体特徴量の長さ）、
・許容される誤りブロック数：Ｄ＝θ＋１（生体特徴量の閾値）、
・各ブロックのビット長：Ｂ＝入力される鍵の長さ
【０１５６】
第３の例示的な実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステムの構成は、第２の例示的な実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステム２００（図３）の構成と等しいため、説明を省略する。
【０１５７】
次に、本実施形態における各装置の動作について、詳細に説明する。
【０１５８】
本実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステム２００の生成装置２１０の動作は、図４Ａを参照して説明した第２の例示的な実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステムの動作とステップＣ４のみが異なる。ただし、組織符号を用いているため、図４ＡのステップＣ３において、
Ｅｎｃｏｄｅ（ｋ，ｒ２，…，ｒＭ）→ｃ
・・・(67)
によって計算された符号化鍵ｃ＝（ｃ１，…，ｃＣ）の前半Ｍブロックはそれぞれ、
ｃ１＝ｋ，ｃ２＝ｒ２，…，ｃＭ＝ｒＭ
・・・(68)
を満たす。
【０１５９】
本実施形態において、図４ＡのステップＣ４は、次のように動作する。
【０１６０】
生成装置２１０のスケッチ生成部２１４は、ステップＣ１で受け取った各成分が０又は１からなるｎ＝Ｃ−１ビットのファジーデータ
ｘ＝（ｘ１，…，ｘＣ−１）
と、ステップＣ３で得た符号化鍵の第２ブロック以降（ｃ２，…，ｃＣ）とのブロックごとの和
（ｘ１＋ｃ２，…，ｘＣ−１＋ｃＣ）
・・・(69)
を計算し、スケッチｓ（（Ｃ−１）ブロック＝Ｂ×（Ｃ−１）ビット）として出力する（ステップＣ４）。図８（Ｃ）は、上記した生成装置２１０におけるスケッチｓの生成の演算を例示した図である。なお、生成装置２１０は、第一のスケッチｓ＝（ｓ１，…，ｓＣ−１）、第二のスケッチｓ′＝（ｓ′１，…，ｓ′Ｃ−１）を生成する。
【０１６１】
本実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステム２００の復元装置２２０の動作は、図４Ｂを参照して説明した第２の例示的な実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステムの復元装置２２０の動作とステップＤ２のみが異なる。
【０１６２】
本実施形態においてステップＤ２は次のように動作する。
【０１６３】
復元装置２２０のスケッチ合成部２２３は、ステップＤ１で受け取った第一のスケッチｓ＝（ｓ１，…，ｓＣ−１）と、
第二のスケッチｓ′＝（ｓ′１，…，ｓ′Ｃ−１）
との成分ごとの差を計算することにより、合成スケッチ
ｔ＝（ｓ１−ｓ′１，…，ｓＣ−１−ｓ′Ｃ−１）
・・・(70)
を得る（ステップＤ２）。
【０１６４】
この動作によって、本実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステムが正しく動作することは、前記第２の例示的な実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステムが正しく動作することから、明らかである。
【０１６５】
なぜなら、本実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステムにおけるスケッチは、前記第２の例示的な実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステムにおけるスケッチから１ブロックが消失したものと定めているためである。
【０１６６】
さらに、本実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステムが用いる誤り訂正符号は、消失訂正可能であり、許容可能な誤りブロック数は、前記第２の例示的な実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステムが用いる誤り訂正符号における許容可能な誤りブロック数よりも１ブロック多いためである。
【０１６７】
本実施形態によれば、前記第２の例示的な実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステムの効果に加え、スケッチからの鍵の漏洩をより強固に防ぐことが可能であるという効果がある。その理由は、図４ＡのステップＣ４において、符号化鍵のうち鍵そのものを含む部分は、スケッチとして出力しないようにしているためである。
【０１６８】
［第４の例示的な実施形態］
本発明の第４の例示的な実施形態は、前記第２の例示的な実施形態に追加の構成及びそれに伴う動作を加えたものである。
【０１６９】
図５は、本実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステム３００の構成例を模式的に示す図である。本実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステム３００は生成装置３１０及び復元装置２２０を含む。
【０１７０】
生成装置３１０は、 前記第２の例示的な実施形態の構成に、ファジーデータ変形部３１６が追加されている。すなわち、生成装置３１０は、鍵入力部２１１と、ファジーデータ入力部２１２と、鍵変換部２１３と、スケッチ生成部２１４と、乱数取得部２１５と、ファジーデータ変形部３１６を備えている。生成装置３１０において、鍵入力部２１１と、ファジーデータ入力部２１２と、鍵変換部２１３と、スケッチ生成部２１４と、乱数取得部２１５は、それぞれ、前記第２の例示的な実施形態で説明したものと同じである。また、復元装置２２０は、 第一スケッチ入力部２２１と、第二スケッチ入力部２２２と、スケッチ合成部２２３と、拡張鍵の差復元部２２５と、鍵の差復元部２２４を備えている。これらは、前記第２の例示的な実施形態で説明したものと同じである。
【０１７１】
図６は、本実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステム３００の生成装置３１０の動作を説明するための流れ図である。本実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステム３００の生成装置３１０は、第２の例示的な実施形態及び第３の例示的な実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステム２００の動作におけるステップＣ４の前に、次のステップＣ３′を実行する。
【０１７２】
生成装置３１０のファジーデータ変形部３１６は、ステップＣ１で受け取ったファジーデータｘ＝（ｘ１，…，ｘＣ）の各ビットをそれぞれハッシュ関数ｈ等によって変換し、
ｚ＝（ｈ（１，ｘ１），…，ｈ（Ｃ，ｘＣ））
・・・(71)
を得る（ステップＣ３′）。
【０１７３】
ただし、ハッシュ関数等による変換方法はこの方法に限らない。例えば、単に
ｈｘ＝（ｈ（ｘ１），…，ｈ（ｘＣ））
・・・(72)
としてもよい。
【０１７４】
また、例えば、別に保存される鍵ｋｈを用い、
ｈｘ＝（ｈ（ｋｈ，１，ｘ１），…，ｈ（ｋｈ，Ｃ，ｘＣ））
・・・(73)
としてもよい。図８（Ｄ）は、生成装置３１０のスケッチ生成の演算の一例を説明する図である。
【０１７５】
この動作によって、本実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステムが正しく動作することは、第２の例示的な実施形態及び第３の例示的な実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステムが正しく動作することから、明らかである。なぜなら、本実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステムにおけるスケッチは、第２の例示的な実施形態及び第３の例示的な実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステムにおけるスケッチの構成に用いるファジーデータを決定性の関数によって変換している点のみが異なり、２つのファジーデータの異なるビットの数が、２つの変換されたファジーデータの異なるブロックの数と一致するためである。
【０１７６】
上述した本実施形態には、スケッチからの鍵及びファジーデータの漏洩をより強固に防ぐことが可能であるという効果がある。その理由は、図６のステップＣ３′においてファジーデータをハッシュ関数によって拡張し、ステップＣ４において拡張したファジーデータと鍵の符号語とを合成しているためである。
【０１７７】
［第５の例示的な実施形態］
本発明の第５の例示的な実施形態は、前記第４の例示的な実施形態と同様に、前記第３の例示的な実施形態に追加の構成及びそれに伴う動作を加えたものである。本発明の第５の例示的な実施形態では、次のパラメータに対する消失訂正も可能な線形組織符号を用いることが望ましい。
【０１７８】
・メッセージに含まれるブロック数：Ｍ、
・符号語に含まれるブロック数：Ｃ＝ｎ＋１（生体特徴量の長さ）、
・許容される誤りブロック数：Ｄ＝θ＋１（生体特徴量の閾値）、
・各ブロックのビット長：Ｂ＝入力される鍵の長さ
【０１７９】
第５の例示的な実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステムの構成は、前記した第４の例示的な実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステム３００（図５）の構成と等しいため、説明を省略する。
【０１８０】
次に、第５の実施形態における各装置の動作について説明する。
【０１８１】
本実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステム３００の生成装置３１０の動作は、図４Ａを参照して説明した前記第４の例示的な実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステムのステップＣ４と同じである。図４ＡのステップＣ３において、
Ｅｎｃｏｄｅ（ｋ，ｒ２，…，ｒＭ）→ｃ
・・・(74)
によって計算された符号化鍵ｃ＝（ｃ１，…，ｃＣ）の前半Ｍブロックはそれぞれ、
ｃ１＝ｋ，ｃ２＝ｒ２，…，ｃＭ＝ｒＭ
・・・(75)
を満たす。
【０１８２】
生成装置３１０のスケッチ生成部２１４は、図４ＡのステップＣ１で受け取った各成分が０又は１からなるｎ＝Ｃ−１ビットのファジーデータのハッシュ値
ｚ＝（ｈ_１，…，ｈ_Ｃ−１）＝（（ｈ１，ｘ１），…，ｈ（Ｃ−１，ｘＣ−１））
と、ステップＣ３で得た符号化鍵の第２ブロック以降（ｃ２，…，ｃＣ）とのブロックごとの和
（ｈ＿１＋ｃ２，…，ｈ＿Ｃ−１＋ｃＣ−１）
・・・(76)
を計算し、スケッチｓ（（Ｃ−１）ブロック＝Ｂ×（Ｃ−１）ビット）として出力する（ステップＣ４）。生成装置３１０は、第一のスケッチｓ＝（ｓ１，…，ｓＣ−１）、第二のスケッチｓ′＝（ｓ′１，…，ｓ′Ｃ−１）を生成する。図８（Ｅ）は、上記した生成装置３１０におけるスケッチｓの生成の演算を例示した図である。
【０１８３】
本実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステム３００の復元装置２２０の動作は、図５を参照して説明した第４の例示的な実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステムの復元装置２２０の動作とスケッチ合成部２２３の処理が異なる。
【０１８４】
本実施形態において、復元装置２２０のスケッチ合成部２２３は、
第一のスケッチｓ＝（ｓ１，…，ｓＣ−１）と、
第二のスケッチｓ′＝（ｓ′１，…，ｓ′Ｃ−１）
との成分ごとの差を計算することにより、合成スケッチ
ｔ＝（ｓ１−ｓ′１，…，ｓＣ−１−ｓ′Ｃ−１）
・・・(77)
を得る。この動作によって、本実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステムが正しく動作することは、前記第３、第４の例示的な実施形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステムが正しく動作することから、明らかである。
【０１８５】
図７は、本発明の各実施形態の生成装置１１０、２１０、３１０、又は、復元装置１２０、２２０をコンピュータ装置４００に実装した例を説明する図である。コンピュータ装置４００は、プロセッサ４０１と、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ等の半導体ストレージや、ＨＤＤ等からなるストレージ（メモリ）４０２と、表示装置４０３と、通信インタフェース４０４を備えている。通信インタフェース４０４は、図１、図３、図５のネットワーク１３０、２３０に接続する。ストレージ（メモリ）４０２に、プロセッサ４０１で実行可能な命令（instructions）及びデータを含むプログラムを記憶しておき、プロセッサ４０１がストレージ（メモリ）４０２から命令（instructions）をフェッチして実行することで、前記第１乃至第５の実施形態の生成装置１１０、２１０、３１０、復元装置１２０、２２０として動作させることができる。なお、コンピュータ装置４００において、ハイパーバイザ等の仮想化機構を実装することで、生成装置１１０、２１０、３１０、復元装置１２０、２２０を仮想マシン（Virtual Machine）として動作させるようにしてもよい。
【０１８６】
本発明の各形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステムは、ファジー署名の構成要素として用いられる。特に、本発明の各形態に係るｌｉｎｅａｒ  ｓｋｅｔｃｈシステムは、ハミング距離に基づいて照合を行うファジーデータを扱うため、ハミング距離に基づいて照合を行う生体特徴量を利用したファジー署名のために利用可能である。
【０１８７】
なお、上記の特許文献１−３、非特許文献１、２の各開示を、本書に引用をもって繰り込むものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素（各請求項の各要素、各実施例の各要素、各図面の各要素等を含む）の多様な組み合わせ乃至選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【符号の説明】
【０１８８】
１００、２００、３００  ｌｉｎｅａｒ  ｓｋｅｔｃｈ（リニアスケッチ）システム
１１０、２１０、３１０  生成装置
１１１、２１１  鍵入力部
１１２、２１２  ファジーデータ入力部
１１３、２１３  鍵変換部
１１４、２１４  スケッチ生成部
１２０、２２０  復元装置
１２１、２２１  第一スケッチ入力部
１２２、２２２  第二スケッチ入力部
１２３、２２３  スケッチ合成部
１２４、２２４  鍵の差復元部
１３０、２３０  ネットワーク
２１５    乱数取得部
２２５  拡張鍵の差復元部
３１６  ファジーデータ変形部
４００  コンピュータ装置
４０１  プロセッサ
４０２  ストレージ（メモリ）
４０３  表示装置
４０４  通信インタフェース（入出力インタフェース）
１２１１、２２１１  スケッチ入力部
【図１】
2020174516.tif 000003
【図２Ａ】
2020174516.tif 000004
【図２Ｂ】
2020174516.tif 000005
【図３】
2020174516.tif 000006
【図４Ａ】
2020174516.tif 000007
【図４Ｂ】
2020174516.tif 000008
【図５】
2020174516.tif 000009
【図６】
2020174516.tif 000010
【図７】
2020174516.tif 000011
【図８】
2020174516.tif 000012
【手続補正書】
【提出日】令和3年8月24日(2021.8.24)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
生成装置と、復元装置と、を含み、  
前記生成装置は、
鍵を受け取る鍵入力部と、
ファジーデータを受け取るファジーデータ入力部と、
鍵を誤り訂正符号の符号化関数を用いて符号化鍵に変換する鍵変換部と、
前記ファジーデータと前記符号化鍵に対して第一の合成変換を施しスケッチを生成するスケッチ生成部と、
を含み、
前記復元装置は、
第一の鍵と第一のファジーデータに基づき生成された第一のスケッチと、第二の鍵と第二のファジーデータに基づき生成された第二のスケッチを受け取るスケッチ入力部と、
前記第一のスケッチと前記第二のスケッチに対して第二の合成変換を施して合成スケッチを求めるスケッチ合成部と、
前記合成スケッチに基づき、前記第一のスケッチと前記第二のスケッチの生成にそれぞれ用いられた前記第一の鍵と前記第二の鍵の差を算出する鍵の差復元部と、
を含む、ことを特徴とするリニアスケッチシステム。
【請求項２】
前記生成装置は、
乱数を取得する乱数取得部をさらに有し、
前記鍵変換部は、
前記鍵と前記乱数とを誤り訂正符号の符号化関数を用いて符号化鍵に変換し、
前記復元装置は、
前記合成スケッチを誤り訂正符号の復号関数を用いて復号して拡張鍵の差を算出する計算する拡張鍵の差復元部を有し、
前記鍵の差復元部は、前記拡張鍵の差から、前第一のスケッチと前記第二のスケッチの生成にそれぞれ用いられた前記第一の鍵と前記第二の鍵の差を算出する、ことを特徴とする請求項１記載のリニアスケッチシステム。
【請求項３】
前記スケッチ生成部は、前記符号化鍵から少なくとも１ブロックを除いた符号化鍵を生成し、生成した前記符号化鍵と前記ファジーデータに対して前記第一の合成変換を施してスケッチを生成する、ことを特徴とする請求項２記載のリニアスケッチシステム。
【請求項４】
前記生成装置は、前記ファジーデータを拡張する変換を行うファジーデータ変形部をさらに有し、
前記スケッチ生成部は、前記変換後のファジーデータを用いてスケッチを生成する、ことを特徴とする請求項１乃至３のいずれか１項に記載のリニアスケッチシステム。
【請求項５】
前記生成装置において、
前記スケッチ生成部は、前記ファジーデータと、前記符号化鍵に対して前記第一の合成変換としてビット毎の排他的論理和を施して前記スケッチを生成し、
前記復元装置において、
前記スケッチ合成部は、前記第一のスケッチと前記第二のスケッチに対して前記第二の合成変換としてビット毎の排他的論理和を施して前記合成スケッチを求める、請求項１記載のリニアスケッチシステム。
【請求項６】
前記生成装置において、
メッセージに含まれるブロック数をＭ、符号語に含まれるブロック数をＣ、各ブロックのビット長Ｂを前記鍵の長さ、許容されるブロック数を所定値とする線形符号のパラメータを用い、
Ｍ−１個の乱数を取得する乱数取得部を備え、
前記鍵変換部は、前記鍵とＭ−１個の前記乱数とからなるＭブロックの系列を誤り訂正符号の符号化関数を用いてＣブロックからなる符号化鍵に変換し、
前記スケッチ生成部は、Ｃビットの前記ファジーデータとＣブロックからなる前記符号化鍵に対して、前記第一の合成変換として、ブロック毎の加算又は減算を演算してＣブロックの前記スケッチを生成することを特徴とする請求項１記載のリニアスケッチシステム。
【請求項７】
前記復元装置において、
前記スケッチ合成部は、前記第二の合成変換として、前記第一のスケッチと前記第二のスケッチを減算又は加算して前記合成スケッチを求め、
前記合成スケッチを誤り訂正符号の復号関数を用いて復号してＭブロックの拡張鍵の差を算出する拡張鍵の差復元部をさらに備え、
前記鍵の差復元部は、前記拡張鍵の差から、前第一のスケッチと前記第二のスケッチの生成にそれぞれ用いられた前記第一の鍵と前記第二の鍵の差を算出する、ことを特徴とする請求項６記載のリニアスケッチシステム。
【請求項８】
前記生成装置において、
前記許容されるブロック数を前記所定値＋１とした線形符号のパラメータを用い、
前記スケッチ生成部は、Ｃブロックの前記符号化鍵から、少なくとも、前記鍵を含む１ブロックを除いた符号化鍵を生成し、生成したＣ−１ブロックの長さの前記符号化鍵と、Ｃ−１ビットの前記ファジーデータに対して、前記第一の合成変換として、ブロック毎の加算又は減算を演算してＣ−１ブロックの前記スケッチを生成する、ことを特徴とする請求項６又は７記載のリニアスケッチシステム。
【請求項９】
前記生成装置において、
メッセージに含まれるブロック数をＭ、符号語に含まれるブロック数をＣ、各ブロックのビット長Ｂを前記鍵の長さ、許容されるブロック数を所定値とする線形符号のパラメータを用い、
Ｍ−１個の乱数を取得する乱数取得部と、
前記ファジーデータの各ビットをハッシュ関数によって変換することで拡張したファジーデータを生成するファジーデータ変形部と、
を備え、
前記鍵変換部は、前記鍵とＭ−１個の前記乱数とからなるＭブロックの系列を誤り訂正符号の符号化関数を用いてＣブロックからなる符号化鍵に変換し、
前記スケッチ生成部は、Ｃビットの前記拡張したファジーデータと、Ｃブロックの前記符号化鍵に対して、前記第一の合成変換として、ブロック毎の加算又は減算を演算してＣブロックの前記スケッチを生成する、ことを特徴とする請求項１又は６記載のリニアスケッチシステム。
【請求項１０】
前記生成装置において、
前記許容されるブロック数を前記所定値＋１とした線形符号のパラメータを用い、
前記ファジーデータがＣ−１ビットとされ、
前記スケッチ生成部は、前記符号化鍵から、少なくとも、前記鍵を含む１ブロックを除いた符号化鍵を生成し、生成したＣ−１ブロックの長さの前記符号化鍵と、Ｃ−１ビットの前記拡張したファジーデータに対して前記第一の合成変換として、ブロック毎の加算又は減算を演算してＣ−１ブロックの前記スケッチを生成する、ことを特徴とする請求項９記載のリニアスケッチシステム。
【請求項１１】
鍵を受け取る鍵入力部と、
ファジーデータを受け取るファジーデータ入力部と、
鍵を誤り訂正符号の符号化関数を用いて符号化鍵に変換する鍵変換部と、
前記ファジーデータと前記符号化鍵に対して第一の合成変換を施しスケッチを生成するスケッチ生成部と、
を含む、ことを特徴とする生成装置。
【請求項１２】
前記スケッチ生成部は、前記ファジーデータと、前記符号化鍵に対して前記第一の合成変換としてビット毎の排他的論理和を施して前記スケッチを生成する、請求項１１記載の生成装置。
【請求項１３】
メッセージに含まれるブロック数をＭ、符号語に含まれるブロック数をＣ、各ブロックのビット長Ｂを前記鍵の長さ、許容されるブロック数を所定値とする線形符号のパラメータを用い、
Ｍ−１個の乱数を取得する乱数取得部を備え、
前記鍵変換部は、前記鍵とＭ−１個の前記乱数とからなるＭブロックの系列を誤り訂正符号の符号化関数を用いてＣブロックからなる符号化鍵に変換し、
前記スケッチ生成部は、Ｃビットの前記ファジーデータとＣブロックからなる前記符号化鍵に対して、前記第一の合成変換として、ブロック毎の加算又は減算を計算し前記Ｃブロックのスケッチを生成する、ことを特徴とする請求項１２記載の生成装置。
【請求項１４】
前記許容されるブロック数を少なくとも前記所定値＋１とした線形符号符号のパラメータを用い、
前記ファジーデータがＣ−１ビットとされ、
前記スケッチ生成部は、前記符号化鍵から少なくとも前記鍵を含む１ブロックを除いた符号化鍵を生成し、生成したＣ−１ブロックの長さの前記符号化鍵と、Ｃ−１ビットの前記ファジーデータに対して、前記第一の合成変換としてブロック毎の加算又は減算を計算しＣ−１ブロックのスケッチを生成する、ことを特徴とする請求項１３記載の生成装置。
【請求項１５】
メッセージに含まれるブロック数をＭ、符号語に含まれるブロック数をＣ、各ブロックのビット長Ｂを前記鍵の長さ、許容されるブロック数を所定値とする線形符号のパラメータを用い、
Ｍ−１個の乱数を取得する乱数取得部と、
前記ファジーデータの各ビットをハッシュ関数によって変換することで拡張したファジーデータを生成するファジーデータ変形部と、
を備え、
前記鍵変換部は、前記鍵とＭ−１個の前記乱数とからなるＭブロックの系列を誤り訂正符号の符号化関数を用いてＣブロックからなる符号化鍵に変換し、
前記スケッチ生成部は、Ｃビットの前記拡張したファジーデータとＣブロックからなる前記符号化鍵に対して、前記第一の合成変換として、ブロック毎の加算又は減算を計算し前記スケッチとして出力する、ことを特徴とする請求項１２記載の生成装置。
【請求項１６】
前記許容されるブロック数を前記所定値＋１とした線形符号符号のパラメータを用い、
前記ファジーデータがＣ−１ビットとされ、
前記スケッチ生成部は、前記符号化鍵から少なくとも前記鍵を含む１ブロックを除いた符号化鍵を生成し、生成したＣ−１ブロックの長さの前記符号化鍵と、Ｃ−１ビットの前記ファジーデータに対して前記第一の合成変換としてブロック毎の加算又は減算を演算してＣ−１ブロックのスケッチを生成する、ことを特徴とする請求項１５記載の生成装置。
【請求項１７】
入力した鍵を誤り訂正符号の符号化関数を用いて符号化鍵に変換し、入力したファジーデータと前記符号化鍵に対し第一の合成変換を施しスケッチを生成する生成装置から、第一の鍵と第一のファジーデータに基づき生成された第一のスケッチと、第二の鍵と第二のファジーデータに基づき生成された第二のスケッチとを受け取るスケッチ入力部と、
前記第一のスケッチと前記第二のスケッチに対して第二の合成変換を施して合成スケッチを求めるスケッチ合成部と、
前記合成スケッチに基づき、前記第一のスケッチおよび前記第二のスケッチの生成にそれぞれ用いられた前記第一の鍵と前記第二の鍵の差を算出する鍵の差復元部と、
を含む、ことを特徴とする復元装置。
【請求項１８】
前記スケッチ入力部は、前記鍵と乱数とを誤り訂正符号の符号化関数を用いて符号化鍵に変換し前記ファジーデータと前記符号化鍵に対し前記第一の合成変換を施し前記スケッチを生成する前記生成装置から前記第一のスケッチと前記第二のスケッチを受け取り、
前記スケッチ合成部で求めた前記合成スケッチを誤り訂正符号の復号関数を用いて復号して拡張鍵の差を算出する計算する拡張鍵の差復元部を有し、
前記鍵の差復元部は、前記拡張鍵の差から、前第一のスケッチと前記第二のスケッチの生成にそれぞれ用いられた前記第一の鍵と前記第二の鍵の差を算出する、ことを特徴とする請求項１７記載の復元装置。
【請求項１９】
スケッチの生成側では、
入力した鍵を誤り訂正符号の符号化関数を用いて符号化鍵に変換し、  
入力したファジーデータと前記符号化鍵に対し第一の合成変換を施してスケッチを生成し、
復元側では、
第一の鍵と第一のファジーデータに基づき生成された第一のスケッチと、第二の鍵と第二のファジーデータに基づき生成された第二のスケッチを受け取り、
前記第一のスケッチと前記第二のスケッチに対して第二の合成変換を施して合成スケッチを求め、
前記合成スケッチに基づき、前記第一のスケッチと前記第二のスケッチの生成にそれぞれ用いられた前記第一の鍵と前記第二の鍵の差を算出する、ことを特徴とする認証方法。
【請求項２０】
鍵を受け取る処理と、
ファジーデータを受け取る処理と、
鍵を誤り訂正符号の符号化関数を用いて符号化鍵に変換する鍵変換部と、
前記ファジーデータと前記符号化鍵に対して第一の合成変換を施しスケッチを生成する処理と、
をコンピュータに実行させるプログラム。
【請求項２１】
入力した鍵を誤り訂正符号の符号化関数を用いて符号化鍵に変換し、入力したファジーデータと前記符号化鍵に対し第一の合成変換を施しスケッチを生成する生成装置から第一の鍵と第一のファジーデータに基づき生成された第一のスケッチを受け取る処理と、
前記生成装置から第二の鍵と第二のファジーデータに基づき生成された第二のスケッチを受け取る処理と、
前記第一のスケッチと前記第二のスケッチに対して第二の合成変換を施して合成スケッチを求める処理と、
前記合成スケッチに基づき、前記第一のスケッチおよび前記第二のスケッチの生成にそれぞれ用いられた前記第一の鍵と前記第二の鍵の差を算出する処理と、
をコンピュータに実行させるプログラム。
【国際調査報告】
2020174516.tif 000013
2020174516.tif 000014
2020174516.tif 000015
2020174516.tif 000016
2020174516.tif 000017
2020174516.tif 000018