(57)【特許請求の範囲】
【請求項１】
被認証デバイスと認証デバイスを備えた認証システムにおいて、
前記被認証デバイスは、
秘密鍵を含む共通情報を格納する記憶部と、
強度制限の厳しい第１雑音、強度制限が緩い第２雑音を、それぞれ生成する雑音生成部と、
レスポンス生成部と、
を備え、
前記第１雑音は、「1」の数がΔ個以下となるように生成されたＮビット列のバイナリベクトルであり、
前記第２雑音は、ランダムに生成されたバイナリベクトルであり、
前記認証デバイスは、
秘密鍵を含む共通情報を格納する記憶部と、
強度制限の厳しい第１雑音の候補を網羅的に生成する雑音候補生成部と、
チャレンジ生成部と、
ローカルレスポンス生成部と、
認証判定部と、
を備え、
前記第１雑音候補は、「1」の数がΔ個となるように網羅的に生成されたＮビット列群であり、
前記被認証デバイスの前記レスポンス生成部は、当該被認証デバイスが生成した第１雑音及び第２雑音と、前記認証デバイスから受信したチャレンジと、前記共通情報と、を用いてレスポンスを生成し、
前記認証デバイスの前記ローカルレスポンス生成部は、当該認証デバイスが網羅的に生成した第１雑音候補と、当該認証デバイスが生成したチャレンジと、前記共通情報と、を用いてローカルレスポンスを生成し、
前記認証デバイスの前記認証判定部は、前記雑音候補を網羅的に用いて生成された前記ローカルレスポンスと、前記被認証デバイスから受信した前記レスポンスと、を比較して、認証を判定する、
認証システム。
【請求項２】
前記雑音生成部は、
Ｎビット列からなるバイナリベクトルをランダムに生成するバイナリベクトル生成部と、
前記バイナリベクトル生成部により生成されたバイナリベクトルの「1」の数を重みとして抽出し、共通情報に含まれるパラメータΔと比較する判定部と、
を備え、
前記バイナリベクトル生成部により生成されたバイナリベクトルの重みがΔ個より多い場合には、バイナリベクトルの重みがΔ個以下になるまでバイナリベクトルの生成を繰り返し、バイナリベクトルの重みがΔ個以下となった時のバイナリベクトルを第１雑音とし、
前記バイナリベクトル生成部により生成された任意のバイナリベクトルを第２雑音とし、
前記雑音候補生成部は、重みΔの全てのＮビット列のバイナリベクトルを生成して第１雑音候補とする、
請求項１に記載の認証システム。
【請求項３】
前記被認証デバイスは、コミットメントを生成して、前記認証デバイスに送信し、
前記共通情報は、ｍ×ｎバイナリベクトルである秘密鍵Ｓを含み、
前記第１雑音は、
0006602210.tif 000115
にしたがって、ｍビットのｅ＊の各ビットをパラメータτ＊のベルヌーイ分布にしたがって生起させてｅ＊をランダムに生成し、その重みが条件
0006602210.tif 000116
を満たすまで、新しいｅ＊を生成することで得られ、
前記第２雑音は、
0006602210.tif 000117
にしたがって、ｍビットのｅの各ビットをパラメータτのベルヌーイ分布にしたがって生起させてｅをランダムに生成することで得られ、
前記第１雑音候補は、
0006602210.tif 000118
個の重みΔのｍ次元バイナリベクトルを、第１雑音ｅ＊の候補
0006602210.tif 000119
として生成することで得られ、
前記レスポンス生成部は、演算子Ｏを用いて、
0006602210.tif 000120
秘密データＳ、第１雑音ｅ＊、チャレンジｃ、を入力として、ランダム化された秘密データＳ＊、ランダム化されたチャレンジｓ＊、を出力するものであり、
ランダム化された秘密データＳ＊、ランダム化されたチャレンジｓ＊、第２雑音ｅ、コミットメントｒ、から、レスポンス
0006602210.tif 000121
を生成し、
前記ローカルレスポンス生成部は、前記演算子Ｏを用いて、
秘密データＳ、各第１雑音候補
0006602210.tif 000122
、チャレンジｃ、を入力として、ランダム化された秘密データＳ＊、ランダム化されたチャレンジｓ＊、を出力するものであり、
ランダム化された秘密データＳ＊、ランダム化されたチャレンジｓ＊、コミットメントｒから、ローカルレスポンス
0006602210.tif 000123
を生成し、
前記認証判定部は、
0006602210.tif 000124
にしたがって、すべての第１雑音候補
0006602210.tif 000125
について
0006602210.tif 000126
を満たす場合には、前記レスポンスを許可して認証を受け入る、
請求項１、２いずれか１項に記載の認証システム。
【請求項４】
前記共通情報は、ｎ次元バイナリベクトルである秘密鍵ｓと、
ｎ次元のバイナリベクトルを暗号化する暗号アルゴリズム
0006602210.tif 000127
と、
を含み、
前記第１雑音は、
0006602210.tif 000128
にしたがって、ｎビットのｅ＊の各ビットをパラメータτ＊のベルヌーイ分布にしたがって生起させてｅ＊をランダムに生成し、その重みが条件
0006602210.tif 000129
を満たすまで、新しいｅ＊を生成することで得られ、
前記第２雑音は、
0006602210.tif 000130
にしたがって、ｎビットのｅの各ビットをパラメータτのベルヌーイ分布にしたがって生起させてｅをランダムに生成することで得られ、
前記第１雑音候補は、
0006602210.tif 000131
個の重みΔのｎ次元バイナリベクトルを、第１雑音ｅ＊の候補
0006602210.tif 000132
として生成することで得られ、
前記レスポンス生成部は、第１雑音ｅ＊、チャレンジｍを用いて、ノイジーチャレンジｖ
0006602210.tif 000133
を生成し、ノイジーチャレンジｖを用いて、秘密データｓのマッピングを実行して、マッピングされた秘密データ
0006602210.tif 000134
を生成し、マッピングされた秘密データs(v)を用いてチャレンジｍの暗号化を実行し、第２雑音ｅを付加することで、レスポンス
0006602210.tif 000135
を生成し、  
前記ローカルレスポンス生成部は、各第１雑音候補
0006602210.tif 000136
と、チャレンジｍを用いて、ノイジーチャレンジ
0006602210.tif 000137
を生成し、ノイジーチャレンジを用いて、秘密データｓのマッピングを実行して、マッピングされた秘密データ
0006602210.tif 000138
を生成し、マッピングされた秘密データを用いてチャレンジｍの暗号化を実行して、ローカルレスポンス
0006602210.tif 000139
を生成し、
前記認証判定部は、
0006602210.tif 000140
にしたがって、すべての第１雑音候補
0006602210.tif 000141
について
0006602210.tif 000142
を満たす場合には、前記レスポンスを許可して認証を受け入る、
請求項１、２いずれか１項に記載の認証システム。
【請求項５】
被認証デバイスと認証デバイスとの間の認証方法において、
前記被認証デバイスと前記認証デバイスは秘密鍵を含む共通情報を共有し、
前記認証デバイスはチャレンジを生成して前記被認証デバイスに送信し、
前記被認証デバイスは、強度制限の厳しい第１雑音として、「1」の数がΔ個以下となるようにＮビット列のバイナリベクトルを生成し、強度制限が緩い第２雑音として、バイナリベクトルをランダムに生成し、生成した第１雑音及び第２雑音と、前記認証デバイスから受信したチャレンジと、前記共通情報と、を用いてレスポンスを生成して、前記認証デバイスに送信し、
前記認証デバイスは、強度制限の厳しい第１雑音の候補として、「1」の数がΔ個となるように網羅的に生成されたＮビット列群を生成し、生成した第１雑音候補と、当該認証デバイスが生成したチャレンジと、前記共通情報と、を用いてローカルレスポンスを生成し、生成したローカルレスポンスと、前記被認証デバイスから受信した前記レスポンスと、を比較して、認証を判定する、
認証方法。
【請求項６】
前記第１雑音の生成は、ランダムに生成されたＮビット列からなるバイナリベクトルの「1」の数を重みとして抽出し、生成されたバイナリベクトルの重みがΔ個より多い場合には、バイナリベクトルの重みがΔ個以下になるまでバイナリベクトルの生成を繰り返し、バイナリベクトルの重みがΔ個以下となった時のバイナリベクトルを第１雑音とするものであり、
前記第２雑音は、ランダムに生成された任意のバイナリベクトルであり、
前記第１雑音候補は、重みΔの全てのＮビット列のバイナリベクトルを生成することで得られる、
請求項５に記載の認証方法。
【請求項７】
前記被認証デバイスは、コミットメントを生成して、前記認証デバイスに送信し、
前記共通情報は、ｍ×ｎバイナリベクトルである秘密鍵Ｓを含み、
前記第１雑音は、
0006602210.tif 000143
にしたがって、ｍビットのｅ＊の各ビットをパラメータτ＊のベルヌーイ分布にしたがって生起させてｅ＊をランダムに生成し、その重みが条件
0006602210.tif 000144
を満たすまで、新しいｅ＊を生成することで得られ、
前記第２雑音は、
0006602210.tif 000145
にしたがって、ｍビットのｅの各ビットをパラメータτのベルヌーイ分布にしたがって生起させてｅをランダムに生成することで得られ、
前記第１雑音候補は、
0006602210.tif 000146
個の重みΔのｍ次元バイナリベクトルを、第１雑音ｅ＊の候補
0006602210.tif 000147
として生成することで得られ、
前記レスポンスは、演算子Ｏを用いて、
0006602210.tif 000148
秘密データＳ、第１雑音ｅ＊、チャレンジｃ、を入力として、ランダム化された秘密データＳ＊、ランダム化されたチャレンジｓ＊、を出力するものであり、
ランダム化された秘密データＳ＊、ランダム化されたチャレンジｓ＊、第２雑音ｅ、コミットメントｒ、から、レスポンス
0006602210.tif 000149
を生成し、
前記ローカルレスポンス生成部は、前記演算子Ｏを用いて、
秘密データＳ、各第１雑音候補
0006602210.tif 000150
、チャレンジｃ、を入力として、ランダム化された秘密データＳ＊、ランダム化されたチャレンジｓ＊、を出力するものであり、
ランダム化された秘密データＳ＊、ランダム化されたチャレンジｓ＊、コミットメントｒから、ローカルレスポンス
0006602210.tif 000151
を生成し、
前記認証デバイスは、
0006602210.tif 000152
にしたがって、すべての第１雑音候補
0006602210.tif 000153
について
0006602210.tif 000154
を満たす場合には、前記レスポンスを許可して認証を受け入る、
請求項５、６いずれか１項に記載の認証方法。
【請求項８】
前記共通情報は、ｎ次元バイナリベクトルである秘密鍵ｓと、
ｎ次元のバイナリベクトルを暗号化する暗号アルゴリズム
0006602210.tif 000155
と、
を含み、
前記第１雑音は、
0006602210.tif 000156
にしたがって、ｎビットのｅ＊の各ビットをパラメータτ＊のベルヌーイ分布にしたがって生起させてｅ＊をランダムに生成し、その重みが条件
0006602210.tif 000157
を満たすまで、新しいｅ＊を生成することで得られ、
前記第２雑音は、
0006602210.tif 000158
にしたがって、ｎビットのｅの各ビットをパラメータτのベルヌーイ分布にしたがって生起させてｅをランダムに生成することで得られ、
前記第１雑音候補は、
0006602210.tif 000159
個の重みΔのｎ次元バイナリベクトルを、第１雑音ｅ＊の候補
0006602210.tif 000160
として生成することで得られ、
前記レスポンスは、第１雑音ｅ＊、チャレンジｍを用いて、ノイジーチャレンジｖ
0006602210.tif 000161
を生成し、ノイジーチャレンジｖを用いて、秘密データｓのマッピングを実行して、マッピングされた秘密データ
0006602210.tif 000162
を生成し、マッピングされた秘密データs(v)を用いてチャレンジｍの暗号化を実行し、第２雑音ｅを付加することで、レスポンス
0006602210.tif 000163
を生成し、  
前記ローカルレスポンス生成部は、各第１雑音候補
0006602210.tif 000164
と、チャレンジｍを用いて、ノイジーチャレンジ
0006602210.tif 000165
を生成し、ノイジーチャレンジを用いて、秘密データｓのマッピングを実行して、マッピングされた秘密データ
0006602210.tif 000166
を生成し、マッピングされた秘密データを用いてチャレンジｍの暗号化を実行して、ローカルレスポンス
0006602210.tif 000167
を生成し、
前記認証デバイスは、
0006602210.tif 000168
にしたがって、すべての第１雑音候補
0006602210.tif 000169
について
0006602210.tif 000170
を満たす場合には、前記レスポンスを許可して認証を受け入る、
請求項５、６いずれか１項に記載の認証方法。
【請求項９】
被認証デバイスと認証デバイスとの間の認証方法において、
前記被認証デバイスと前記認証デバイスは秘密鍵を含む共通情報を共有し、
前記認証デバイスはチャレンジを生成して前記被認証デバイスに送信し、
前記被認証デバイスは、強度制限の厳しい第１雑音、強度制限が緩い第２雑音を、それぞれ生成し、生成した第１雑音及び第２雑音と、前記認証デバイスから受信したチャレンジと、前記共通情報と、を用いてレスポンスを生成して、前記認証デバイスに送信し、
前記認証デバイスは、強度制限の厳しい第１雑音の候補を網羅的に生成し、生成した第１雑音候補と、当該認証デバイスが生成したチャレンジと、前記共通情報と、を用いてローカルレスポンスを生成し、生成したローカルレスポンスと、前記被認証デバイスから受信した前記レスポンスと、を比較して、認証を判定するものであり、
前記被認証デバイスは、コミットメントを生成して、前記認証デバイスに送信し、
前記共通情報は、ｍ×ｎバイナリベクトルである秘密鍵Ｓを含み、
前記第１雑音は、
0006602210.tif 000171
にしたがって、ｍビットのｅ＊の各ビットをパラメータτ＊のベルヌーイ分布にしたがって生起させてｅ＊をランダムに生成し、その重みが条件
0006602210.tif 000172
を満たすまで、新しいｅ＊を生成することで得られ、
前記第２雑音は、
0006602210.tif 000173
にしたがって、ｍビットのｅの各ビットをパラメータτのベルヌーイ分布にしたがって生起させてｅをランダムに生成することで得られ、
前記第１雑音候補は、
0006602210.tif 000174
個の重みΔのｍ次元バイナリベクトルを、第１雑音ｅ＊の候補
0006602210.tif 000175
として生成することで得られ、
前記レスポンスは、演算子Ｏを用いて、
0006602210.tif 000176
秘密データＳ、第１雑音ｅ＊、チャレンジｃ、を入力として、ランダム化された秘密データＳ＊、ランダム化されたチャレンジｓ＊、を出力するものであり、
ランダム化された秘密データＳ＊、ランダム化されたチャレンジｓ＊、第２雑音ｅ、コミットメントｒ、から、レスポンス
0006602210.tif 000177
を生成し、
前記ローカルレスポンス生成部は、前記演算子Ｏを用いて、
秘密データＳ、各第１雑音候補
0006602210.tif 000178
、チャレンジｃ、を入力として、ランダム化された秘密データＳ＊、ランダム化されたチャレンジｓ＊、を出力するものであり、
ランダム化された秘密データＳ＊、ランダム化されたチャレンジｓ＊、コミットメントｒから、ローカルレスポンス
0006602210.tif 000179
を生成し、
前記認証デバイスは、
0006602210.tif 000180
にしたがって、すべての第１雑音候補
0006602210.tif 000181
について
0006602210.tif 000182
を満たす場合には、前記レスポンスを許可して認証を受け入る、
認証方法。
【請求項１０】
被認証デバイスと認証デバイスとの間の認証方法において、
前記被認証デバイスと前記認証デバイスは秘密鍵を含む共通情報を共有し、
前記認証デバイスはチャレンジを生成して前記被認証デバイスに送信し、
前記被認証デバイスは、強度制限の厳しい第１雑音、強度制限が緩い第２雑音を、それぞれ生成し、生成した第１雑音及び第２雑音と、前記認証デバイスから受信したチャレンジと、前記共通情報と、を用いてレスポンスを生成して、前記認証デバイスに送信し、
前記認証デバイスは、強度制限の厳しい第１雑音の候補を網羅的に生成し、生成した第１雑音候補と、当該認証デバイスが生成したチャレンジと、前記共通情報と、を用いてローカルレスポンスを生成し、生成したローカルレスポンスと、前記被認証デバイスから受信した前記レスポンスと、を比較して、認証を判定するものであり、
前記共通情報は、ｎ次元バイナリベクトルである秘密鍵ｓと、
ｎ次元のバイナリベクトルを暗号化する暗号アルゴリズム
0006602210.tif 000183
と、
を含み、
前記第１雑音は、
0006602210.tif 000184
にしたがって、ｎビットのｅ＊の各ビットをパラメータτ＊のベルヌーイ分布にしたがって生起させてｅ＊をランダムに生成し、その重みが条件
0006602210.tif 000185
を満たすまで、新しいｅ＊を生成することで得られ、
前記第２雑音は、
0006602210.tif 000186
にしたがって、ｎビットのｅの各ビットをパラメータτのベルヌーイ分布にしたがって生起させてｅをランダムに生成することで得られ、
前記第１雑音候補は、
0006602210.tif 000187
個の重みΔのｎ次元バイナリベクトルを、第１雑音ｅ＊の候補
0006602210.tif 000188
として生成することで得られ、
前記レスポンスは、第１雑音ｅ＊、チャレンジｍを用いて、ノイジーチャレンジｖ
0006602210.tif 000189
を生成し、ノイジーチャレンジｖを用いて、秘密データｓのマッピングを実行して、マッピングされた秘密データ
0006602210.tif 000190
を生成し、マッピングされた秘密データs(v)を用いてチャレンジｍの暗号化を実行し、第２雑音ｅを付加することで、レスポンス
0006602210.tif 000191
を生成し、  
前記ローカルレスポンス生成部は、各第１雑音候補
0006602210.tif 000192
と、チャレンジｍを用いて、ノイジーチャレンジ
0006602210.tif 000193
を生成し、ノイジーチャレンジを用いて、秘密データｓのマッピングを実行して、マッピングされた秘密データ
0006602210.tif 000194
を生成し、マッピングされた秘密データを用いてチャレンジｍの暗号化を実行して、ローカルレスポンス
0006602210.tif 000195
を生成し、
前記認証デバイスは、
0006602210.tif 000196
にしたがって、すべての第１雑音候補
0006602210.tif 000197
について
0006602210.tif 000198
を満たす場合には、前記レスポンスを許可して認証を受け入る、
認証方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、認証システム及び方法に係り、典型的な態様例では、非対称計算機資源環境における認証システム及び方法に関する。
【背景技術】
【０００２】
認証プロトコルは、証明者Ｐが自身を検証者Ｖに対して認証するためのプロトコルである。例えばＲＦＩＤ実装においては、証明者Ｐはタグ、検証者Ｖはリーダである。図１は、認証プトコルの概要を示し、典型的な認証プロトコルは、タグとリーダが共通鍵を共有するための疑似乱数関数(PRF)f(AES等)を用いることで構築される。認証プロトコルは、リーダがチャレンジｃをタグに送信し、タグはこれに対してf(c)を返し、リーダは、タグから受信したｃの評価が正しいかについて検証する。
【０００３】
この手法の主な問題は、疑似乱数関数が、数学的仮説あるいはＡＥＳのようなアドホックのブロック暗号に基づいて証明可能安全性を備えていたとしても、制限された計算機資源を備えた軽量デバイスにおいて手順を実行するにはコストが高いということである。
【０００４】
軽量の認証手法としては、以下の２つの手法が提案されている。
(i)ＬＰＮ問題に基づく認証（非特許文献３、５）
(ii)ランダム選択に基づく認証（非特許文献１、２、４）
【０００５】
LPN問題に基づく認証
LPN問題（Learning parity with Noise）の困難性を仮定して、それに基づく幾つかの認証プロトコルが提案されている。LPN問題自体については、当業者に知られているので、本明細書での詳細な説明は省略する。非特許文献３には、以下の３つの認証プロトコルが提案されている。
(1)Authentication Protocol Secure Against Active Attacks (Protocol A1)
(2)The First MAC based Construction of Authentication Protocol Secure against MIM (Protocol MAC1)
(3)The Second MAC based Construction of Authentication Protocol Secure against MIM (Protocol MAC2)
プロトコルA１は、アクティブ攻撃シナリオ下において安全であり、プロトコルMAC1、MAC2は、中間者(MIM)攻撃シナリオ下において安全である。
非特許文献５には、MIM攻撃シナリオ下において安全である別の認証プロトコルが提案されている。
【０００６】
ランダム選択（Random Selection）に基づく認証
認証プロトコルにおけるランダム選択の原理は以下の通りである。
検証者アリスと証明者ボブが、プロック長ｎの軽量の対称暗号演算
0006602210.tif 000002
を用いるチャレンジ・レスポンス認証プロトコルを実行するとする。
ここで、
0006602210.tif 000003
は、適切な鍵空間である。
さらに、Ｅは、パッシブな攻撃者によって効率的に秘密鍵
0006602210.tif 000004
を関数
0006602210.tif 000005
のサンプルから計算できるものとする。これは、Ｅが線形の場合は自明である。
【０００７】
ランダム選択は、Ｅの無力さを以下の実行モードによって補償することである。
単一の
0006602210.tif 000006
を保有することに代えて、アリスとボブは、共通の秘密情報として、
0006602210.tif 000007
からの複数の鍵から成る集合（L＞1は小さな定数である）
0006602210.tif 000008
を共有する。
【０００８】
アリスからチャレンジ
0006602210.tif 000009
を受信すると、ボブは、選択インデックス
0006602210.tif 000010
を選択し、レスポンス
0006602210.tif 000011
を出力する。
チャレンジuに関するレスポンスｙの検証は、全ての
0006602210.tif 000012
について、
0006602210.tif 000013
を計算することによって効率的に実行される。
【０００９】
ここで、軽量の認証プロトコルの開発においては、ワイヤレス・センサーネットワーク（WSN）やIoT(Internet of Things)において適用し得る軽量の認証プロトコルの開発が課題である。すなわち、タグやセンサー等の計算機資源の乏しいデバイスが、ＰＣのような計算機資源豊かなデバイスと通信を行う環境（非対称計算機資源環境）に適用し得る軽量の認証プロトコルの開発が重要である。非対称計算機資源環境とは、「自分は確かに自分である」と証明する側（証明者）と、それを検証して確認する側（検証者）との間に、証明者としてセンサーやタグなどの計算機資源が乏しいデバイスを想定し、検証者としてサーバなどの計算機資源が豊かな装置を想定するがゆえに、計算機資源の大きな格差が存在する環境をいう（図２）。
【００１０】
しかしながら、(1)非特許文献３、５に記載された認証プロトコルは、幾つかの興味深い要素を提供しているが、幾つかのM2M認証シナリオにとって十分に軽量ではなく、また、非対称計算機資源環境下の制約を考慮していない。(2)非特許文献１、２、４に記載された認証プロトコルは、ランダムセレクションという興味深いパラダイムを採用しているが、所望の暗号セキュリティを備えていない。すなわち、非特許文献１〜５に開示されたプロトコルは、非対称計算機資源環境を考慮していない点、あるいは／および、所望の暗号セキュリティを提供しない点において、適切ではない。
【非特許文献１】J. Cichon, M. Klonowski and M. Kutyowski, ”Privacy protection for RFID with  hidden subset identifiers”, PERVASIVE 2008, Lecture Notes in Computer Science, vol. 5013, pp. 298-314, 2008.
【非特許文献２】Z. Golebiewski, K. Majcher and F. Zagrski, ”Attacks on CKK family of RFID authentication protocols”, In: Coudert, D., Simplot-Ryl, D., Stojmenovic, I. (eds.) ADHOC-NOW 2008. Lecture Notes in Computer Science, vol. 5198, pp. 241-250, 2008
【非特許文献３】E. Kiltz, K. Pietrzak, D. Cash, A. Jain, and D. Venturi, ”Efficient Authentication from Hard Learning Problems”, EUROCRYPT 2011, Lecture Notes in Computer Science, vol. 6632, pp. 7-26, 2011.
【非特許文献４】M. Krause and M. Hamann, ”The Cryptographic Power of Random Selection”, SAC 2011, Lecture Notes in Computer Science, vol. 7118, pp. 134-150, 2012.
【非特許文献５】V. Lyubashevsky and D. Masny, ”Man-in-the-Middle Secure Authentication Schemes from LPN and Weak PRFs”, CRYPTO 2013, Lecture Notes in Computer Science, vol. 8043, pp. 308-325, 2013.
【発明の開示】
【発明が解決しようとする課題】
【００１１】
本発明は、認証のための通信手順（プロトコル）において、証明者の計算機資源が検証者のそれよりも圧倒的に乏しい場合に、(i)その非対称性を考慮し、(ii)証明者がタグやセンサーであっても問題にならないほど十分に軽量で、しかも(iii)暗号理論的に十分な安全性を達成すること、を目的とするものである。
【課題を解決するための手段】
【００１２】
本発明が採用した認証システムは、被認証デバイスと認証デバイスを備え、
前記被認証デバイスは、
秘密鍵を含む共通情報を格納する記憶部と、
強度制限の厳しい第１雑音、強度制限が緩い第２雑音を、それぞれ生成する雑音生成部と、
レスポンス生成部と、
を備え、
前記認証デバイスは、
秘密鍵を含む共通情報を格納する記憶部と、
強度制限の厳しい第１雑音の候補を網羅的に生成する雑音候補生成部と、
チャレンジ生成部と、
ローカルレスポンス生成部と、
認証判定部と、
を備え、
前記被認証デバイスの前記レスポンス生成部は、当該被認証デバイスが生成した第１雑音及び第２雑音と、前記認証デバイスから受信したチャレンジと、前記共通情報と、を用いてレスポンスを生成し、
前記認証デバイスの前記ローカルレスポンス生成部は、当該認証デバイスが網羅的に生成した第１雑音候補と、当該認証デバイスが生成したチャレンジと、前記共通情報と、を用いてローカルレスポンスを生成し、
前記認証デバイスの前記認証判定部は、前記雑音候補を網羅的に用いて生成された前記ローカルレスポンスと、前記被認証デバイスから受信した前記レスポンスと、を比較して、認証を判定する。
【００１３】
本発明が採用した認証方法は、
被認証デバイスと認証デバイスが秘密鍵を含む共通情報を共有し、
前記認証デバイスはチャレンジを生成して前記被認証デバイスに送信し、
前記被認証デバイスは、強度制限の厳しい第１雑音、強度制限が緩い第２雑音を、それぞれ生成し、生成した第１雑音及び第２雑音と、前記認証デバイスから受信したチャレンジと、前記共通情報と、を用いてレスポンスを生成して、前記認証デバイスに送信し、
前記認証デバイスは、強度制限の厳しい第１雑音の候補を網羅的に生成し、生成した第１雑音候補と、当該認証デバイスが生成したチャレンジと、前記共通情報と、を用いてローカルレスポンスを生成し、生成したローカルレスポンスと、前記被認証デバイスから受信した前記レスポンスと、を比較して、認証を判定する。
【００１４】
本発明において、証明者である被認証デバイスによってレスポンスを生成するための処理の計算量は、検証者である認証デバイスによってローカルレスポンスを生成して認証を判定する計算量よりも計量である。
【００１５】
１つの態様では、前記第１雑音は、「1」の数がΔ個以下となるように生成されたＮビット列のバイナリベクトルであり、
前記第２雑音は、ランダムに生成されたバイナリベクトルであり、
前記第１雑音候補は、「1」の数がΔ個となるように網羅的に生成されたＮビット列群（NCΔ個のＮビット列からなる群）である。
１つの態様では、前記雑音生成部は、
Ｎビット列からなるバイナリベクトルをランダムに生成するバイナリベクトル生成部と、前記バイナリベクトル生成部により生成されたバイナリベクトルの「1」の数を重みとして抽出し、共通情報に含まれるパラメータΔと比較する判定部と、を備え、
前記バイナリベクトル生成部により生成されたバイナリベクトルの重みがΔ個より多い場合には、バイナリベクトルの重みがΔ個以下になるまでバイナリベクトルの生成を繰り返し、バイナリベクトルの重みがΔ個以下となった時のバイナリベクトルを第１雑音とし、
前記バイナリベクトル生成部により生成された任意のバイナリベクトルを第２雑音とし、
前記雑音候補生成部は、重みΔの全てのＮビット列のバイナリベクトルを生成して第１雑音候補とする。
【００１６】
１つの態様（後述する認証プロトコルI）では、  前記被認証デバイスは、コミットメントを生成して、前記認証デバイスに送信し、
前記共通情報は、ｍ×ｎバイナリベクトルである秘密鍵Ｓを含み、
前記第１雑音は、
0006602210.tif 000014
にしたがって、ｍビットのｅ＊の各ビットをパラメータτ＊のベルヌーイ分布にしたがって生起させてｅ＊をランダムに生成し、その重みが条件
0006602210.tif 000015
を満たすまで、新しいｅ＊を生成することで得られ、
前記第２雑音は、
0006602210.tif 000016
にしたがって、ｍビットのｅの各ビットをパラメータτのベルヌーイ分布にしたがって生起させてｅをランダムに生成することで得られ、
前記第１雑音候補は、
0006602210.tif 000017
個の重みΔのｍ次元バイナリベクトルを、第１雑音ｅ＊の候補
0006602210.tif 000018
として生成することで得られ、
前記レスポンス生成部は、演算子Ｏを用いて、
0006602210.tif 000019
秘密データＳ、第１雑音ｅ＊、チャレンジｃ、を入力として、ランダム化された秘密データＳ＊、ランダム化されたチャレンジｓ＊、を出力するものであり、
ランダム化された秘密データＳ＊、ランダム化されたチャレンジｓ＊、第２雑音ｅ、コミットメントｒ、から、レスポンス
0006602210.tif 000020
を生成し、
前記ローカルレスポンス生成部は、前記演算子Ｏを用いて、
秘密データＳ、各第１雑音候補
0006602210.tif 000021
、チャレンジｃ、を入力として、ランダム化された秘密データＳ＊、ランダム化されたチャレンジｓ＊、を出力するものであり、
ランダム化された秘密データＳ＊、ランダム化されたチャレンジｓ＊、コミットメントｒから、ローカルレスポンス
0006602210.tif 000022
を生成し、
前記認証判定部は、
0006602210.tif 000023
にしたがって、すべての第１雑音候補
0006602210.tif 000024
について
0006602210.tif 000025
を満たす場合には、前記レスポンスを許可して認証を受け入る。
【００１７】
１つの態様（後述する認証プロトコルII）では、前記共通情報は、ｎ次元バイナリベクトルである秘密鍵ｓと、
ｎ次元のバイナリベクトルを暗号化する暗号アルゴリズム
0006602210.tif 000026
と、
を含み、
前記第１雑音は、
0006602210.tif 000027
にしたがって、ｎビットのｅ＊の各ビットをパラメータτ＊のベルヌーイ分布にしたがって生起させてｅ＊をランダムに生成し、その重みが条件
0006602210.tif 000028
を満たすまで、新しいｅ＊を生成することで得られ、
前記第２雑音は、
0006602210.tif 000029
にしたがって、ｎビットのｅの各ビットをパラメータτのベルヌーイ分布にしたがって生起させてｅをランダムに生成することで得られ、
前記第１雑音候補は、
0006602210.tif 000030
個の重みΔのｎ次元バイナリベクトルを、第１雑音ｅ＊の候補
0006602210.tif 000031
として生成することで得られ、
前記レスポンス生成部は、第１雑音ｅ＊、チャレンジｍを用いて、ノイジーチャレンジｖ
0006602210.tif 000032
を生成し、ノイジーチャレンジｖを用いて、秘密データｓのマッピングを実行して、マッピングされた秘密データ
0006602210.tif 000033
を生成し、マッピングされた秘密データs(v)を用いてチャレンジｍの暗号化を実行し、第２雑音ｅを付加することで、レスポンス
0006602210.tif 000034
を生成し、  
前記ローカルレスポンス生成部は、各第１雑音候補
0006602210.tif 000035
と、チャレンジｍを用いて、ノイジーチャレンジ
0006602210.tif 000036
を生成し、ノイジーチャレンジを用いて、秘密データｓのマッピングを実行して、マッピングされた秘密データ
0006602210.tif 000037
を生成し、マッピングされた秘密データを用いてチャレンジｍの暗号化を実行して、ローカルレスポンス
0006602210.tif 000038
を生成し、
前記認証判定部は、
0006602210.tif 000039
にしたがって、すべての第１雑音候補
0006602210.tif 000040
について
0006602210.tif 000041
を満たす場合には、前記レスポンスを許可して認証を受け入る。
【発明の効果】
【００１８】
本発明では、計算機資源が乏しいデバイスである証明者は、軽量な行列計算を行い、計算機資源が豊かなデバイスである検証者は、軽量ではないベクトル評価を含む検証演算を行うことで、計算資源に応じた非対称的な方式とし、安全性を確保しつつ、負荷の高い処理を計算機資源が豊かなデバイス側へ偏らせることによって、計算機資源の乏しいデバイス側の動作コストを低くした。したがって、証明者の計算機資源が検証者のそれよりも圧倒的に乏しい場合、例えば、証明者がタグやセンサーであっても問題にならないほど十分に軽量で、かつ、暗号理論的に十分な安全性を備えた認証プロトコルを提供することができる。
【図面の簡単な説明】
【００１９】
【図１】チャレンジ・レスポンス認証プロトコルの概要を示す。
【図２】非対称計算機資源環境下（計算能力の低い証明者と計算能力の高い検証者）における認証シナリオを示す。
【図３】本実施形態に認証システムの概略図である。
【図４】本実施形態に係る認証フレームワークを示す。
【図５】本実施形態に係る認証プロトコルIにおける証明者における処理を示すブロック図である。
【図６】本実施形態に係る認証プロトコルIにおける検証者における処理を示すブロック図である。
【図７】本実施形態に係る認証プロトコルIIにおける証明者における処理を示すブロック図である。
【図８】本実施形態に係る認証プロトコルIIにおける検証者における処理を示すブロック図である。
【発明を実施するための形態】
【００２０】
［Ａ］非対称計算機資源環境
本実施形態は、非対称計算機資源環境における認証方法及びシステムに関する。非対称計算機資源環境とは、タグやセンサー等の計算機資源の乏しいデバイスが、ＰＣのような計算機資源豊かなデバイスと暗号通信を行う環境である。図２に示すように、本実施形態に係る認証は、検証者としての第１デバイス（認証デバイス）と証明者としての第２デバイス（被認証デバイス）との間で行われる。第１デバイス、第２デバイスは共にコンピュータを含んでいると共に、通信機能（典型的には無線通信機能）を備えている。コンピュータは、ハードウェアとして、入力部、記憶部、処理部（演算部ないしＣＰＵ）、出力部等を備えており、ソフトウェア（コンピュータプログラム）によって所定の処理を実行する。
【００２１】
本実施形態では、第１デバイスは計算機資源（ＣＰＵ、メモリ等）が豊かであり、第２デバイスは計算機資源が乏しい。第１デバイスは第２デバイスよりも処理能力（計算能力）が高く、また、第２デバイスはより小さい消費電力で動作可能である。第１デバイスとしては、ＰＣ（デスクトップ、ラップトップ、ノートブック等）、サーバ、モバイルコンピュータ（スマートフォン、携帯電話、ＰＤＡ、タブレット、所定の計算機資源を備えたウェラブルコンピュータ等）、タグリーダ等が例示される。第２デバイスとしては、センサー（ＩＣ内蔵）、ＲＦＩＤタグ、ＩＣタグ、ＩＣカード、ウェアラブルコンピュータが例示される。
【００２２】
［Ｂ］認証システム
図３、図４に示すように、認証システムは、証明者である被認証デバイスと、検証者である認証デバイスと、を備えたチャレンジ・レスポンス認証システムである。被認証デバイスと認証デバイスが秘密データを含む共通情報を共有し、認証デバイスはチャレンジを生成して当該チャレンジを被認証デバイスに送信し、チャレンジを受信した被認証デバイスは、受信したチャレンジ及び秘密データを用いて、所定の処理を実行してレスポンスを生成して当該レスポンスを認証デバイスに送信し、レスポンスを受信した認証デバイスは、チャレンジ及び秘密データを用いて、所定の処理を事項してローカルレスポンスを生成し、被認証デバイスから受信したレスポンスと認証デバイスで生成したローカルレスポンスとを比較して、受信したレスポンスを評価し、当該レスポンスを受け入れるか否かを判定する。
【００２３】
認証デバイスは、秘密データを含む共通情報を格納する共通情報記憶部と、雑音生成部と、チャレンジ生成部と、ローカルレスポンス生成部と、認証判定部と、を備えている。被認証デバイスは、秘密データを含む共通情報を格納する共通情報記憶部と、雑音生成部と、レスポンス生成部と、を備えている。後述する認証プロトコルIでは、さらに、コミットメント生成部を備えている。認証デバイス及び被認証デバイスは、共に、データの送受信部を備えている。
【００２４】
被認証デバイスの雑音生成部は、強度制限の厳しい第１雑音、強度制限が緩い第２雑音を、それぞれ生成する。認証デバイスの雑音生成部は、強度制限の厳しい雑音の候補を網羅的に生成する雑音候補生成部である。後述する実施形態では、雑音生成部は、バイナリベクトルを生成するバイナリベクトル生成部であり、
【００２５】
被認証デバイスのレスポンス生成部は、当該被認証デバイスが生成した第１雑音及び第２雑音と、認証デバイスから受信したチャレンジと、共通情報と、を用いてレスポンスを生成する。レスポンスの生成アルゴリズムは、軽量な計算で実行できる処理である。
【００２６】
被認証デバイスにおけるレスポンス生成処理は、「認証デバイスが生成して被認証デバイスに送信したチャレンジ」と、「被認証デバイスが生成し、認証デバイスには送信しない、２つの雑音（強度制限の厳しい雑音と厳しくない雑音）」と、を用いて（プロトコルIでは「被認証デバイスが生成して認証デバイスに送信したコミットメント」も用いて）、認証デバイスが現実的な負荷（図４のmoderate complexity processing）で検証可能な範囲で、かつ、攻撃者が十分な情報を得られない強度で、秘密情報から部分情報を抽出してスクランブルを施したレスポンスを生成するものである。
【００２７】
認証デバイスのローカルレスポンス生成部は、当該認証デバイスが網羅的に生成した雑音候補と、当該認証デバイスが生成したチャレンジと、共通情報と、を用いてローカルレスポンスを生成する。認証デバイスの認証判定部は、雑音候補を網羅的に用いて生成されたローカルレスポンスと、前記被認証デバイスから受信したレスポンスと、を比較して、認証を判定する。認証デバイスにおける処理は、強度制限の厳しい雑音の候補を網羅的にテストするだけで、強度制限の厳しくない雑音の候補を考えることなく、実行できる処理である。
【００２８】
図４に本実施形態に係る認証フレームワークを示す。認証フレームワークは、図４に示す複数のボックスから構成されており、これらのボックスは、「共通秘密データ(shared secret data)」、「コミットメント(commitment)」、「チャレンジ(challenge)」、「証明者における軽量な処理(lightweight processing P)」、「レスポンス(response)」、「検証者における無理の無い程度の複雑な処理(moderate complexity processing V)」、「認証結果(authentication result)」からなり、後述する本実施形態に係るそれぞれの認証プロトコルでは、所定のボックスにおいて異なる設計や構成が採用される。
【００２９】
本実施形態は、「共通秘密データ」、「証明者における処理」、「レスポンス」、「検証者における処理」において新規の設計/構成を備えている。本実施形態は、特に、「証明者（被認証デバイス）における処理Ｐ（図５、図６参照）」、「検証者（認証デバイス）における処理Ｖ（図７、図８参照）」に特徴を有している。それによって、本実施形態に係る認証プロトコルは、以下の要求に対応することができる。
(a)図２に示す非対称計算機資源環境下での認証シナリオに適合するものであること、
(b)証明者と検証者との間に実装の複雑性（implementation complexities）のトレードオフを解決するものであること、
(c)以下の２つの概念に基づく認証の高い安全性を提供するものであること、
- LPN問題とランダムセレクション問題の組み合わせ、
- 適切な暗号、ランダムセレクション、暗号文のランダム化の組み合わせ。
【００３０】
［Ｃ］認証プロトコル
本実施形態に係る認証プロトコルは、認証プロトコルIと、認証プロトコルIIからなる。認証プロトコルIは、(i) LPN問題と、(ii)ランダムセレクション問題 の２つの問題の組み合わせに基づいた認証セキュリティを提供するものであり、認証プロトコルIIは、(i)適切な暗号アルゴリズム（ストリーム暗号）、(ii) ランダムセレクションパラダイム、(iii)暗号文のランダム化、の組み合わせに基づいた認証セキュリティを提供するものである。
【００３１】
［Ｃ−１］表記法
0006602210.tif 000042
ベルヌーイ分布にしたがってｍ次元バイナリベクトルを引き出す演算であって、ベルヌーイ分布は、確率τで「1」を生成し、確率１−τで「0」を生成し、τ＜1/2である。
【００３２】
0006602210.tif 000043
バイナリベクトルｅの重みであり、バイナリベクトルｅにおける「1」の数に等しい。パラメータΔは重みの上限を規定する。
【００３３】
0006602210.tif 000044
それぞれ、バイナリ引数のmodulo2加算（排他的論理和）、modulo2加算による総和を示す。
【００３４】
0006602210.tif 000045
それぞれ、l次元バイナリベクトルのドメイン、ｍ×ｎ次元バイナリ行列のドメイン、である。
【００３５】
0006602210.tif 000046
演算子
0006602210.tif 000047
は、
●与えられたｍｘｎのバイナリ行列（各要素は0または1）
0006602210.tif 000048
ここで、
0006602210.tif 000049
は行列Ｓのi番目の行、
●ｍ次元のバイナリベクトルｅ＊、
●ｎ次元のバイナリベクトルｃ、
について、以下の手順で、ｍｘｎバイナリ行列Ｓ＊、ｍ次元バイナリベクトルｓ＊を返すものである。
【００３６】
与えられたベクトル
0006602210.tif 000050
について、ｍｘｎバイナリ行列Ｅ＊を以下ように評価する。
行列Ｅ＊のj番目の列は、j-1番目の列におけるｅ＊の要素のサイクリックシフトによって得られたベクトルと等しい。
【００３７】
演算子
0006602210.tif 000051
、行列Ｓ*、ベクトルｓ*を以下ように定義する。
0006602210.tif 000052
ここで、
0006602210.tif 000053
である。
ここで、「1」は、全ての要素が1のｍｘｎバイナリ行列であり、すなわち、
0006602210.tif 000054
は、行列Ｅ＊の各要素をビット反転させた行列となる。
【００３８】
すなわち、一般的に表現すると、演算子
0006602210.tif 000055
は、「秘密データＳ」、「バイナリベクトルｅ＊ （本実施形態では、ベクトルｅ＊によって規定されるランダム行列Ｅ＊が生成されるが、ランダム化の具体的な計算は本実施形態に限定されない）」、「チャレンジｃ」、を入力として、「ランダム化された秘密データＳ＊」、「ランダム化されたチャレンジｓ＊」、を出力する。
【００３９】
［Ｃ−２］認証プロトコルＩ
［共有情報］
証明者と検証者との間で共有されるデータは、
●行列形式（ｍ×ｎ次元バイナリ行列）の秘密鍵Ｓ、
0006602210.tif 000056
●パラメータ
0006602210.tif 000057
ｍ，ｎ：次元数、
Δ：バイナリベクトル生成時の重み（「1」の数）の上限、
τ，τ＊：ベルヌーイ分布において「1」を生成する確率、
thr：認証の合否を決定する閾値、
である。
【００４０】
［ステップ１］
証明者は、ランダムに生成されたｎ次元バイナリベクトルであるコミットメントメッセージｒを生成し、検証者に送信する。
【００４１】
［ステップ２］
検証者は、ランダムに生成されたｎ次元バイナリベクトルであり、重みがΔよりも大きいチャレンジメッセージｃを生成し、証明者に送信する。
【００４２】
［ステップ３］
証明者は、検証者からチャレンジメッセージｃを受信すると、以下の手順でレスポンスを生成する（図４における処理Ｐ）。
【００４３】
［セレクト（選択）］
●ｅ＊の生成
0006602210.tif 000058
証明者は、ｍビットのｅ＊の各ビットをパラメータτ＊のベルヌーイ分布にしたがって生起させてｅ＊をランダムに生成する。
0006602210.tif 000059
の場合（ｅ＊のうち1の立っているビットがΔ個より多ければ）には、新しいｅ＊を生成し、その重みが条件
0006602210.tif 000060
を満たすまで、新しいｅ＊を生成して再チェックする（Δ個以下になるまで繰り返す）。
●ｅの生成
0006602210.tif 000061
証明者は、ｍビットのｅの各ビットをパラメータτのベルヌーイ分布にしたがって生起させてｅをランダムに生成する。
【００４４】
認証プロトコルIで採用されるバイナリベクトルｅ＊ 、ｅにおいて、ｅ＊は、データのランダム化のための第１系列（ベクトル）、すなわち、第１雑音であり、ｅは、データのランダム化のための第２系列（ベクトル）、すなわち、第２雑音である。第１雑音（ｅ＊）は、強度制限のより厳しい雑音であり、第２雑音（ｅ）は、強度制限がより厳しくない雑音、である。
【００４５】
［評価］
証明者は、演算子Ｏを用いて、ｍ×ｎバイナリ行列Ｓ*、及び、ｍ次元バイナリベクトルｓ*を計算し、そして、レスポンスｚを計算する。
0006602210.tif 000062
0006602210.tif 000063
0006602210.tif 000064
【００４６】
図５を参照しつつ、証明者（被認証デバイス）における処理Ｐをより具体的に説明する。ブロック「ランダムセレクション(Random selection)」において第１雑音ｅ＊が生成される。ブロック「秘密データのマッピング(Mapping of secret data)」において、生成された第１雑音ｅ＊を用いて、秘密データ（秘密鍵）Ｓのマッピング
0006602210.tif 000065
が実行され、ランダム化された秘密データＳ＊を得る。ここで、Ｅ＊は、ベクトルｅ＊によって規定されるランダム行列である。
【００４７】
ブロック「LPN処理(LPN Processing)」において、マッピング（ランダム化）された秘密データＳ＊と、コミットメントｒと、生成された第２雑音ｅと、を用いて、
0006602210.tif 000066
が生成される。
【００４８】
ブロック「レスポンスの評価(Evaluation of response)」において、生成された第１雑音ｅ＊により規定されるランダム行列Ｅ＊を用いて、チャレンジｃのランダム化
0006602210.tif 000067
が実行され、ランダム化されたチャレンジｓ＊を得る。
【００４９】
ブロック「LPN処理」で生成された
0006602210.tif 000068
と、ランダム化されたチャレンジｓ＊と、からレスポンスｚ
0006602210.tif 000069
が生成される。
【００５０】
［送信］
証明者は、レスポンスｚを検証者に送信する。
【００５１】
［ステップ４］
検証者は、レスポンスｚを受信すると、以下の手順で認証の成否を決定する（図４における処理Ｖ）。
【００５２】
検証者は、ｅ＊について、ｍ次元から「1」である要素をΔ個選んで得られる組合せ、すなわち、
0006602210.tif 000070
個のｍ次元バイナリベクトル（重みΔ）を、ｅ＊の候補
0006602210.tif 000071
として生成し、演算子Ｏを用いて行列Ｓ＊及びベクトルｓ＊を以下のように評価する。
0006602210.tif 000072
であり、
0006602210.tif 000073
である。
【００５３】
検証者は、候補として検討されたすべての
0006602210.tif 000074
について
0006602210.tif 000075
を満たす場合には、レスポンスｚを許可して認証を受け入れ（合格）、そうでない場合には、レスポンスｚは拒否され、認証を棄却（不合格）とする。
ここで、thrは事前に設定された閾値であり、thr＜＜ｍ/2である。
【００５４】
図６を参照しつつ、検証者（認証デバイス）における処理Ｖをより具体的に説明する。ブロック「ランダムセレクションにおける仮定の設定(Setting a hypothesis on random selection)」において第１雑音の候補
0006602210.tif 000076
が生成される。
【００５５】
ブロック「秘密データのマッピング(Mapping of secret data)」において、生成された第１雑音の候補
0006602210.tif 000077
用いて、秘密データ（秘密鍵）Ｓのマッピング
0006602210.tif 000078
が実行され、ランダム化された秘密データＳ＊を得る。ここで、Ｅ＊は、ベクトル
0006602210.tif 000079
によって規定されるランダム行列である。
【００５６】
ブロック「マッピングされた秘密データを用いた評価(Evaluation employing mapped secret data)」において、マッピング（ランダム化）された秘密データＳ＊と、コミットメントｒと、を用いて、
0006602210.tif 000080
が生成される。
【００５７】
ブロック「ローカルで生成されたレスポンス推定の評価(Evaluation of locally generated response estimation)」において、生成された第１雑音の候補
0006602210.tif 000081
により規定されるランダム行列Ｅ＊を用いて、チャレンジｃのランダム化
0006602210.tif 000082
が実行され、ｓ＊を得る。ブロック「マッピングされた秘密データを用いた評価」で生成された
0006602210.tif 000083
と、ランダム化されたチャレンジｓ＊と、からローカルレスポンス
0006602210.tif 000084
が生成される。
【００５８】
受信したレスポンスｚと、認証デバイスにおいてローカルに生成されたレスポンス
0006602210.tif 000085
と、を判定関数
0006602210.tif 000086
によって出力される重みを用いて比較して、認証の認否を決定する。
【００５９】
［Ｃ−３］認証プロトコルＩＩ
［共有情報］
証明者と検証者との間で共有される情報は、
●秘密ベクトル
0006602210.tif 000087
●ｎ次元のバイナリベクトルを暗号化する暗号（ストリーム暗号）アルゴリズム
0006602210.tif 000088
●パラメータ
0006602210.tif 000089
ｌ，ｎ：次元数、
Δ：バイナリベクトル生成時の重み（「1」の数）の上限、
τ，τ＊：ベルヌーイ分布において「1」を生成する確率、
thr：認証の合否を決定する閾値、
である。
【００６０】
［ステップ１］
検証者は、ｎ次元バイナリベクトルであるメッセージｍを証明者に送信する。
【００６１】
［ステップ２］
証明者は、検証者からメッセージｍを取得すると、以下の手順でレスポンスを生成する（図４における処理Ｐ）。
【００６２】
［セレクト（選択）］
●ｅ＊の生成
0006602210.tif 000090
証明者は、ｎビットのｅ＊の各ビットをパラメータτ＊のベルヌーイ分布にしたがって生起させてｅ＊をランダムに生成する。
0006602210.tif 000091
の場合（ｅ＊のうち1の立っているビットがΔ個より多ければ）には、新しいｅ＊を生成し、その重みが条件
0006602210.tif 000092
を満たすまで、新しいｅ＊を生成して再チェックする（Δ個以下になるまで繰り返す）。
●ｅの生成
0006602210.tif 000093
証明者は、ｎビットのｅの各ビットをパラメータτのベルヌーイ分布にしたがって生起させてｅをランダムに生成する。
【００６３】
認証プロトコルIIで採用されるバイナリベクトルｅ＊ 、ｅにおいて、ｅ＊は、ランダム化のための第１系列（ベクトル）、すなわち、第１雑音であり、ｅは、ランダム化のための第２系列（ベクトル）、すなわち、第２雑音である。第１雑音（ｅ＊）は、強度制限のより厳しい雑音であり、第２雑音（ｅ）は、強度制限がより厳しくない雑音、である。
【００６４】
［評価］
証明者は、メッセージｍに生成されたｅ＊（第１雑音）を加えることでvを生成し、s0に「vの第i成分が1であるようなsi（i=1, 2, …, ｎ）」をビット毎の排他的論理和で足し合わせていき、その結果をs(v)とする。s(v)を暗号アルゴリズムによるスクランブルで鍵として利用してレスポンスｚを得る。
0006602210.tif 000094
0006602210.tif 000095
【００６５】
図７を参照しつつ、証明者（被認証デバイス）における処理Ｐをより具体的に説明する。ブロック「ランダムセレクション(Random selection)」において第１雑音ｅ＊が生成される。ブロック「秘密データのマッピング(Mapping of secret data)」において、生成された第１雑音ｅ＊、認証デバイスから受信したチャレンジｍを用いて、ノイジーチャレンジｖ
0006602210.tif 000096
が生成され、ノイジーチャレンジｖを用いて、秘密データ（秘密鍵）ｓのマッピングが実行され、マッピングされた秘密データｓ（ｖ）
0006602210.tif 000097
を得る。
【００６６】
ブロック「軽量暗号化及び加法性雑音(Lightweight Encryption & Additive noise)」において、マッピングされた秘密データs(v)を用いてチャレンジｍの暗号化が実行され、暗号化（スクランブル）チャレンジEs(v)(m)が生成され、生成された第２雑音ｅを用いて、レスポンスｚ
0006602210.tif 000098
が生成される。
【００６７】
［送信］
証明者は、レスポンスｚを送信する。
【００６８】
[ステップ３]
検証者は、レスポンスｚを受信すると、以下の手順で認証の成否を決定する（図４における処理Ｖ）。
【００６９】
検証者は、ｅ＊について、ｎ次元から「1」である要素をΔ個選んで得られる組合せ、すなわち、
0006602210.tif 000099
個のｎ次元バイナリベクトル（重みΔ）を、ｅ＊の候補
0006602210.tif 000100
として生成し、各候補について、
0006602210.tif 000101
を計算し、その結果にしたがって各候補を評価する。
【００７０】
検証者は、候補として検討されたすべての
0006602210.tif 000102
について
0006602210.tif 000103
を満たす場合には、レスポンスｚを許可して認証受け入れ（合格）、そうでない場合には、レスポンスｚは拒否され、認証を棄却（不合格）とする。
ここで、thrは予め設定された閾値であり、thr＜＜ｎ/2である。
【００７１】
図８を参照しつつ、検証者（認証デバイス）における処理Ｖをより具体的に説明する。ブロック「ランダムセレクションにおける仮定の設定(Setting a hypothesis on random selection)」において雑音ｅ＊の候補
0006602210.tif 000104
が生成される。
【００７２】
ブロック「秘密データのマッピング(Dedicated secret data mapping)」において、生成された雑音ｅ＊の候補
0006602210.tif 000105
と、チャレンジｍを用いて、ノイジーチャレンジ
0006602210.tif 000106
が生成され、ノイジーチャレンジを用いて、秘密データ（秘密鍵）ｓのマッピングが実行され、マッピングされた秘密データ
0006602210.tif 000107
を得る。
【００７３】
ブロック「軽量暗号化及び加法性雑音(Lightweight Encryption & Additive noise)」において、マッピングされた秘密データを用いてチャレンジｍの暗号化が実行され、暗号化（スクランブル）チャレンジ
0006602210.tif 000108
が生成される。
【００７４】
受信したレスポンスｚと、認証デバイスにおいてローカルに生成されたレスポンス
0006602210.tif 000109
と、を判定関数
0006602210.tif 000110
によって出力される重みを用いて比較して、認証の認否を決定する。
【００７５】
［Ｄ］本実施形態に係る認証プロトコルと非特許文献に係るプロトコルとの対比
本実施形態に係る認証プロトコルは、非特許文献３、５及び１、２、４に開示された認証プロトコルの結果を考慮し、これらの開示事項の非自明な組み合わせに基づくものである。
本実施形態に係る認証プロトコルは、非特許文献３、５に開示されている幾つかの要素を採用するものであるが、非特許文献３、５に開示されている要素において、計算能力の乏しい当事者（通常は、証明者）のおける認証の軽量性をサポートできない要素、特に、
(i)非特許文献３における主要要素である長いバイナリベクト転置(permutation)、
(ii)非特許文献５における主要要素である非バイナリ有限体(non-binary finite field)における演算を含まない。
プロトコルの暗号セキュリティとより計算能力の高い当事者（通常は、検証者）における複雑性の実装とのトレードオフとして、ランダムセレクション手法を採用して計算能力の乏しい当事者におけるプロトコルの暗号セキュリティを確保する。
本実施形態の認証プロトコルの主要な技術的特徴を非特許文献３〜５に開示された認証プロトコルにおける対応する要素と対比して示す。
【００７６】
表１は、ｎが支配的パラメータであると仮定して、秘密鍵及び通信の次元を対比したものである。
【表１】
0006602210.tif 000111
【００７７】
表２は、証明者側における支配的な演算を対比して示すものである。本実施形態に係る認証プロトコルは、非特許文献３における主要要素である長いバイナリベクト転置(permutation)、非特許文献５における主要要素である非バイナリ有限体における演算を含まない。
【表２】
0006602210.tif 000112
【００７８】
表３は、レスポンスを対比して示す。
【表３】
0006602210.tif 000113
【００７９】
表４は、検証者側における支配的な演算を対比して示す。
【表４】
0006602210.tif 000114
【産業上の利用可能性】
【００８０】
高性能な計算機だけでなく情報処理能力の低いウェラブルデバイスやセンサーなどのデバイスを含む複雑なネットワークシステムを構築し、ＩＴが新たなサービスと市場を創出する期待が高まっている。本発明に係る認証プロトコルは、そのようなシステムのためのセキュリティ技術として利用可能である。
【００８１】
本発明に係る認証プロトコルでは、計算機資源の乏しいデバイス側の消費電力を大幅に抑えることができるため、応用範囲が格段に広まる。例えば、電力など重要インフラのセキュリティ、人への埋め込みもしくは携帯デバイスを活用したヘルスケアや高齢者向けサービス、様々なセンサーを活用した農業、漁業支援や災害対策システム、計算機を持ち歩かずとも利用可能な外出先での次世代クレジットカード決済など、市場の大きな応用しかもグローバルな市場への応用が期待できる。ウェアラブルデバイスを着用した作業員がロボットやセンサーと協調して働く制御システムなど、一見異なる応用に見えるものの融合もあり得る。それらの基盤技術として利用価値が高い。
【図１】
0006602210.tif 000199
【図２】
0006602210.tif 000200
【図３】
0006602210.tif 000201
【図４】
0006602210.tif 000202
【図５】
0006602210.tif 000203
【図６】
0006602210.tif 000204
【図７】
0006602210.tif 000205
【図８】
0006602210.tif 000206