(57)【特許請求の範囲】
【請求項１】
ＳＫＩＤ←ＫＧ（ＭＳＫ，ＩＤ）がマスタ秘密鍵ＭＳＫと識別子ＩＤから秘密鍵ＳＫＩＤを得る写像であり、（Ａ，ＳＴ）←Σｉｂｉ−ｃｏｍ（ＭＰＫ，ＩＤ，ＳＫＩＤ）がマスタ公開鍵ＭＰＫと前記識別子ＩＤと前記秘密鍵ＳＫＩＤからコミットメントＡと内部状態情報ＳＴを得る写像であり、Ｃ←Σｉｂｉ−ｃｈ（ＭＰＫ，ＩＤ）が前記マスタ公開鍵ＭＰＫと前記識別子ＩＤからチャレンジＣを得る写像であり、Ｕ←Σｉｂｉ−ｒｅｓ（ＭＰＫ，ＩＤ，ＳＫＩＤ，Ａ，Ｃ，ＳＴ）が前記マスタ公開鍵ＭＰＫと前記識別子ＩＤと前記秘密鍵ＳＫＩＤと前記コミットメントＡと前記チャレンジＣと前記内部状態情報ＳＴからレスポンスＵを得る写像であり、ＤＥＣ←Σｉｂｉ−ｖｒｆｙ（ＭＰＫ，ＩＤ，Ａ，Ｃ，Ｕ）が前記マスタ公開鍵ＭＰＫと前記識別子ＩＤと前記コミットメントＡと前記チャレンジＣと前記レスポンスＵから検証結果ＤＥＣを得る写像であり、Ｃ’←Σ+ｉｂｉ−ｃｈ（ＭＰＫ）が前記マスタ公開鍵ＭＰＫからチャレンジＣ’を得る写像であり、（Ａ’，Ｕ’）←Σｉｂｉ−ｓｉｍ（ＭＰＫ，ＩＤ，Ｃ）が前記マスタ公開鍵ＭＰＫと前記識別子ＩＤと前記チャレンジＣから前記チャレンジＣに対して前記検証結果ＤＥＣが受理となるコミットメントＡ’とレスポンスＵ’を得る写像であり、
前記マスタ公開鍵ＭＰＫがｍｐｋであり、前記マスタ秘密鍵ＭＳＫがｍｓｋであり、ｉｄが利用者識別子であり、Ｍ（α，β）がαとβに対応する値であり、ｓｋ（ｉｄ，ｂ（ｉｄ））が何れかのｂ（ｉｄ）∈｛０，１｝に対応するｓｋ（ｉｄ，ｂ（ｉｄ））←ＫＧ（ｍｓｋ，Ｍ（ｉｄ，ｂ（ｉｄ）））によって得られる値であり、
証明装置と検証装置とを有し、
前記証明装置は、
（ａｂ（ｉｄ），ｓｔ）←Σｉｂｉ−ｃｏｍ（ｍｐｋ，Ｍ（ｉｄ，ｂ（ｉｄ）），ｓｋ（ｉｄ，ｂ（ｉｄ）））によってａｂ（ｉｄ）とｓｔを得る第１演算部と、
ｒｂ（ｉｄ）＝１−ｂ（ｉｄ）であり、ｃｒｂ（ｉｄ）←Σ+ｉｂｉ−ｃｈ（ｍｐｋ）によってｃｒｂ（ｉｄ）を得る第２演算部と、
（ａｒｂ（ｉｄ），ｕｒｂ（ｉｄ））←Σｉｂｉ−ｓｉｍ（ｍｐｋ，Ｍ（ｉｄ，ｒｂ（ｉｄ）），ｃｒｂ（ｉｄ））によってａｒｂ（ｉｄ）とｕｒｂ（ｉｄ）を得る第３演算部と、
コミットメント（ａ０，ａ１）を出力する第１出力部と、
入力されたチャレンジｃからｃｂ（ｉｄ）＝ｃ−ｃｒｂ（ｉｄ）を得る第４演算部と、
ｕｂ（ｉｄ）←Σｉｂｉ−ｒｅｓ（ｍｐｋ，Ｍ（ｉｄ，ｂ（ｉｄ）），ｓｋ（ｉｄ，ｂ（ｉｄ）），ａｂ（ｉｄ），ｃｂ（ｉｄ），ｓｔ）によってｕｂ（ｉｄ）を得る第５演算部と、
レスポンス（ｃ０，ｕ０，ｕ１）を出力する第２出力部と、
を有し、
前記検証装置は、
前記コミットメント（ａ０，ａ１）の入力を受け付ける第１入力部と、
ｃ←Σ+ｉｂｉ−ｃｈ（ｍｐｋ）によってチャレンジｃを得る第６演算部と、
前記チャレンジｃを出力する第３出力部と、
前記レスポンス（ｃ０，ｕ０，ｕ１）の入力を受け付ける第２入力部と、
ｃ１＝ｃ−ｃ０を得る第７演算部と、
ｄｅｃ←Σｉｂｉ−ｖｒｆｙ（ｍｐｋ，Ｍ（ｉｄ，０），ａ０，ｃ０，ｕ０）によって得られる検証結果ｄｅｃと、ｄｅｃ’←Σｉｂｉ−ｖｒｆｙ（ｍｐｋ，Ｍ（ｉｄ，１），ａ１，ｃ１，ｕ１）によって得られる検証結果ｄｅｃ’とがともに受理となるかを判定する判定部と、
を有する、認証システム。
【請求項２】
ＳＫＩＤ←ＫＧ（ＭＳＫ，ＩＤ）がマスタ秘密鍵ＭＳＫと識別子ＩＤから秘密鍵ＳＫＩＤを得る写像であり、（Ａ，ＳＴ）←Σｉｂｉ−ｃｏｍ（ＭＰＫ，ＩＤ，ＳＫＩＤ）がマスタ公開鍵ＭＰＫと前記識別子ＩＤと前記秘密鍵ＳＫＩＤからコミットメントＡと内部状態情報ＳＴを得る写像であり、Ｃ←Σｉｂｉ−ｃｈ（ＭＰＫ，ＩＤ）が前記マスタ公開鍵ＭＰＫと前記識別子ＩＤからチャレンジＣを得る写像であり、Ｕ←Σｉｂｉ−ｒｅｓ（ＭＰＫ，ＩＤ，ＳＫＩＤ，Ａ，Ｃ，ＳＴ）が前記マスタ公開鍵ＭＰＫと前記識別子ＩＤと前記秘密鍵ＳＫＩＤと前記コミットメントＡと前記チャレンジＣと前記内部状態情報ＳＴからレスポンスＵを得る写像であり、ＤＥＣ←Σｉｂｉ−ｖｒｆｙ（ＭＰＫ，ＩＤ，Ａ，Ｃ，Ｕ）が前記マスタ公開鍵ＭＰＫと前記識別子ＩＤと前記コミットメントＡと前記チャレンジＣと前記レスポンスＵから検証結果ＤＥＣを得る写像であり、Ｃ’←Σ+ｉｂｉ−ｃｈ（ＭＰＫ）が前記マスタ公開鍵ＭＰＫからチャレンジＣ’を得る写像であり、（Ａ’，Ｕ’）←Σｉｂｉ−ｓｉｍ（ＭＰＫ，ＩＤ，Ｃ）が前記マスタ公開鍵ＭＰＫと前記識別子ＩＤと前記チャレンジＣから前記チャレンジＣに対して前記検証結果ＤＥＣが受理となるコミットメントＡ’とレスポンスＵ’を得る写像であり、
前記マスタ公開鍵ＭＰＫがｍｐｋであり、前記マスタ秘密鍵ＭＳＫがｍｓｋであり、ｉｄが利用者識別子であり、Ｍ（α，β）がαとβに対応する値であり、ｂ（ｉｄ）∈｛０，１｝であり、ｓｋ（ｉｄ，ｂ（ｉｄ））がｓｋ（ｉｄ，ｂ（ｉｄ））←ＫＧ（ｍｓｋ，Ｍ（ｉｄ，ｂ（ｉｄ）））によって得られる値であり、
証明装置と検証装置とを有し、
前記証明装置は、
何れかのｂ（ｉｄ）∈｛０，１｝に対応する（ａｂ（ｉｄ），ｓｔ）←Σｉｂｉ−ｃｏｍ（ｍｐｋ，Ｍ（ｉｄ，ｂ（ｉｄ）），ｓｋ（ｉｄ，ｂ（ｉｄ）））によってａｂ（ｉｄ）とｓｔを得る第１演算部と、
ｒｂ（ｉｄ）＝１−ｂ（ｉｄ）であり、ｃｒｂ（ｉｄ）←Σ+ｉｂｉ−ｃｈ（ｍｐｋ）によってｃｒｂ（ｉｄ）を得る第２演算部と、
（ａｒｂ（ｉｄ），ｕｒｂ（ｉｄ））←Σｉｂｉ−ｓｉｍ（ｍｐｋ，Ｍ（ｉｄ，ｒｂ（ｉｄ）），ｃｒｂ（ｉｄ））によってａｒｂ（ｉｄ）とｕｒｂ（ｉｄ）を得る第３演算部と、
コミットメント（ａ０，ａ１）を出力する第１出力部と、
入力されたチャレンジｃからｃｂ（ｉｄ）＝ｃ−ｃｒｂ（ｉｄ）を得る第４演算部と、
ｕｂ（ｉｄ）←Σｉｂｉ−ｒｅｓ（ｍｐｋ，Ｍ（ｉｄ，ｂ（ｉｄ）），ｓｋ（ｉｄ，ｂ（ｉｄ）），ａｂ（ｉｄ），ｃｂ（ｉｄ），ｓｔ）によってｕｂ（ｉｄ）を得る第５演算部と、
レスポンス（ｃ０，ｕ０，ｕ１）を出力する第２出力部と、
を有し、
前記検証装置は、
前記コミットメント（ａ０，ａ１）の入力を受け付ける第１入力部と、
ｃ←Σ+ｉｂｉ−ｃｈ（ｍｐｋ）によって前記チャレンジｃを得る第６演算部と、
前記チャレンジｃを出力する第３出力部と、
前記レスポンス（ｃ０，ｕ０，ｕ１）の入力を受け付ける第２入力部と、
ｃ１＝ｃ−ｃ０を得る第７演算部と、
ｄｅｃ←Σｉｂｉ−ｖｒｆｙ（ｍｐｋ，Ｍ（ｉｄ，０），ａ０，ｃ０，ｕ０）によって得られる検証結果ｄｅｃと、ｄｅｃ’←Σｉｂｉ−ｖｒｆｙ（ｍｐｋ，Ｍ（ｉｄ，１），ａ１，ｃ１，ｕ１）によって得られる検証結果ｄｅｃ’とがともに受理となるかを判定する判定部と、
を有する、認証システム。
【請求項３】
ＳＫＩＤ←ＫＧ（ＭＳＫ，ＩＤ）がマスタ秘密鍵ＭＳＫと識別子ＩＤから秘密鍵ＳＫＩＤを得る写像であり、（Ａ，ＳＴ）←Σｉｂｉ−ｃｏｍ（ＭＰＫ，ＩＤ，ＳＫＩＤ）がマスタ公開鍵ＭＰＫと前記識別子ＩＤと前記秘密鍵ＳＫＩＤからコミットメントＡと内部状態情報ＳＴを得る写像であり、Ｃ←Σｉｂｉ−ｃｈ（ＭＰＫ，ＩＤ）が前記マスタ公開鍵ＭＰＫと前記識別子ＩＤからチャレンジＣを得る写像であり、Ｕ←Σｉｂｉ−ｒｅｓ（ＭＰＫ，ＩＤ，ＳＫＩＤ，Ａ，Ｃ，ＳＴ）が前記マスタ公開鍵ＭＰＫと前記識別子ＩＤと前記秘密鍵ＳＫＩＤと前記コミットメントＡと前記チャレンジＣと前記内部状態情報ＳＴからレスポンスＵを得る写像であり、ＤＥＣ←Σｉｂｉ−ｖｒｆｙ（ＭＰＫ，ＩＤ，Ａ，Ｃ，Ｕ）が前記マスタ公開鍵ＭＰＫと前記識別子ＩＤと前記コミットメントＡと前記チャレンジＣと前記レスポンスＵから検証結果ＤＥＣを得る写像であり、Ｃ’←Σ+ｉｂｉ−ｃｈ（ＭＰＫ）が前記マスタ公開鍵ＭＰＫからチャレンジＣ’を得る写像であり、（Ａ’，Ｕ’）←Σｉｂｉ−ｓｉｍ（ＭＰＫ，ＩＤ，Ｃ）が前記マスタ公開鍵ＭＰＫと前記識別子ＩＤと前記チャレンジＣから前記チャレンジＣに対して前記検証結果ＤＥＣが受理となるコミットメントＡ’とレスポンスＵ’を得る写像であり、
前記マスタ公開鍵ＭＰＫがｍｐｋであり、前記マスタ秘密鍵ＭＳＫがｍｓｋであり、ｉｄが利用者識別子であり、ｉｄｍａｓｔｅｒがマスタ識別子であり、ｉｄ≠ｉｄｍａｓｔｅｒであり、ｓｋｉｄがｓｋｉｄ←ＫＧ（ｍｓｋ，ｉｄ）によって得られる値であり、
証明装置と検証装置とを有し、
前記証明装置は、
（ａ０，ｓｔ）←Σｉｂｉ−ｃｏｍ（ｍｐｋ，ｉｄ，ｓｋｉｄ）によってａ０とｓｔを得る第１演算部と、
ｃ１←Σ+ｉｂｉ−ｃｈ（ｍｐｋ）によってｃ１を得る第２演算部と、
（ａ１，ｕ１）←Σｉｂｉ−ｓｉｍ（ｍｐｋ，ｉｄｍａｓｔｅｒ，ｃ１）によってａ１とｕ１を得る第３演算部と、
コミットメント（ａ０，ａ１）を出力する第１出力部と、
入力されたチャレンジｃからｃ０＝ｃ−ｃ１を得る第４演算部と、
ｕ０←Σｉｂｉ−ｒｅｓ（ｍｐｋ，ｉｄ，ｓｋｉｄ，ａ０，ｃ０，ｓｔ）によってｕ０を得る第５演算部と、
レスポンス（ｃ０，ｕ０，ｕ１）を出力する第２出力部と、
を有し、
前記検証装置は、
前記コミットメント（ａ０，ａ１）の入力を受け付ける第１入力部と、
ｃ←Σ+ｉｂｉ−ｃｈ（ｍｐｋ）によって前記チャレンジｃを得る第６演算部と、
前記チャレンジｃを出力する第３出力部と、
前記レスポンス（ｃ０，ｕ０，ｕ１）の入力を受け付ける第２入力部と、
ｃ１＝ｃ−ｃ０を得る第７演算部と、
ｄｅｃ←Σｉｂｉ−ｖｒｆｙ（ｍｐｋ，ｉｄ，ａ０，ｃ０，ｕ０）によって得られる検証結果ｄｅｃと、ｄｅｃ’←Σｉｂｉ−ｖｒｆｙ（ｍｐｋ，ｉｄｍａｓｔｅｒ，ａ１，ｃ１，ｕ１）によって得られる検証結果ｄｅｃ’とがともに受理となるかを判定する判定部と、
を有する、認証システム。
【請求項４】
ＳＫＩＤ←ＫＧ（ＭＳＫ，ＩＤ）がマスタ秘密鍵ＭＳＫと識別子ＩＤから秘密鍵ＳＫＩＤを得る写像であり、（Ａ，ＳＴ）←Σｉｂｉ−ｃｏｍ（ＭＰＫ，ＩＤ，ＳＫＩＤ）がマスタ公開鍵ＭＰＫと前記識別子ＩＤと前記秘密鍵ＳＫＩＤからコミットメントＡと内部状態情報ＳＴを得る写像であり、Ｃ←Σｉｂｉ−ｃｈ（ＭＰＫ，ＩＤ）が前記マスタ公開鍵ＭＰＫと前記識別子ＩＤからチャレンジＣを得る写像であり、Ｕ←Σｉｂｉ−ｒｅｓ（ＭＰＫ，ＩＤ，ＳＫＩＤ，Ａ，Ｃ，ＳＴ）が前記マスタ公開鍵ＭＰＫと前記識別子ＩＤと前記秘密鍵ＳＫＩＤと前記コミットメントＡと前記チャレンジＣと前記内部状態情報ＳＴからレスポンスＵを得る写像であり、ＤＥＣ←Σｉｂｉ−ｖｒｆｙ（ＭＰＫ，ＩＤ，Ａ，Ｃ，Ｕ）が前記マスタ公開鍵ＭＰＫと前記識別子ＩＤと前記コミットメントＡと前記チャレンジＣと前記レスポンスＵから検証結果ＤＥＣを得る写像であり、Ｃ’←Σ*ｉｂｉ−ｃｈ（１κ）がセキュリティパラメータ１κからチャレンジＣ’を得る写像であり、（Ａ’，Ｕ’）←Σｉｂｉ−ｓｉｍ（ＭＰＫ，ＩＤ，Ｃ）が前記マスタ公開鍵ＭＰＫと前記識別子ＩＤと前記チャレンジＣから前記チャレンジＣに対して前記検証結果ＤＥＣが受理となるコミットメントＡ’とレスポンスＵ’を得る写像であり、
（ｍｐｋ０，ｍｓｋ０）および（ｍｐｋ１，ｍｓｋ１）のそれぞれがマスタ公開鍵とマスタ秘密鍵との鍵ペア（ＭＰＫ，ＭＳＫ）であり、ｉｄが利用者識別子であり、ｓｋ（ｉｄ，ｂ（ｉｄ））が何れかのｂ（ｉｄ）∈｛０，１｝に対応するｓｋ（ｉｄ，ｂ（ｉｄ））←ＫＧ（ｍｓｋｂ（ｉｄ），ｉｄ）によって得られる値であり、
証明装置と検証装置とを有し、
前記証明装置は、
（ａｂ（ｉｄ），ｓｔ）←Σｉｂｉ−ｃｏｍ（ｍｐｋｂ（ｉｄ），ｉｄ，ｓｋ（ｉｄ，ｂ（ｉｄ）））によってａｂ（ｉｄ）とｓｔを得る第１演算部と、
ｒｂ（ｉｄ）＝１−ｂ（ｉｄ）であり、ｃｒｂ（ｉｄ）←Σ*ｉｂｉ−ｃｈ（１κ）によってｃｒｂ（ｉｄ）を得る第２演算部と、
（ａｒｂ（ｉｄ），ｕｒｂ（ｉｄ））←Σｉｂｉ−ｓｉｍ（ｍｐｋｒｂ（ｉｄ），ｉｄ，ｃｒｂ（ｉｄ））によってａｒｂ（ｉｄ）とｕｒｂ（ｉｄ）を得る第３演算部と、
コミットメント（ａ０，ａ１）を出力する第１出力部と、
入力されたチャレンジｃからｃｂ（ｉｄ）＝ｃ−ｃｒｂ（ｉｄ）を得る第４演算部と、
ｕｂ（ｉｄ）←Σｉｂｉ−ｒｅｓ（ｍｐｋｂ（ｉｄ），ｉｄ，ｓｋ（ｉｄ，ｂ（ｉｄ）），ａｂ（ｉｄ），ｃｂ（ｉｄ），ｓｔ）によってｕｂ（ｉｄ）を得る第５演算部と、
レスポンス（ｃ０，ｕ０，ｕ１）を出力する第２出力部と、
を有し、
前記検証装置は、
前記コミットメント（ａ０，ａ１）の入力を受け付ける第１入力部と、
ｃ←Σ*ｉｂｉ−ｃｈ（１κ）によって前記チャレンジｃを得る第６演算部と、
前記チャレンジｃを出力する第３出力部と、
レスポンス（ｃ０，ｕ０，ｕ１）の入力を受け付ける第２入力部と、
ｃ１＝ｃ−ｃ０を得る第７演算部と、
ｄｅｃ←Σｉｂｉ−ｖｒｆｙ（ｍｐｋ０，ｉｄ，ａ０，ｃ０，ｕ０）によって得られる検証結果ｄｅｃと、ｄｅｃ’←Σｉｂｉ−ｖｒｆｙ（ｍｐｋ１，ｉｄ，ａ１，ｃ１，ｕ１）によって得られる検証結果ｄｅｃ’とがともに受理となるかを判定する判定部と、
を有する、認証システム。
【請求項５】
請求項１から４の何れかの認証システムが有する証明装置。
【請求項６】
請求項１から４の何れかの認証システムが有する検証装置。
【請求項７】
請求項５の証明装置としてコンピュータを機能させるためのプログラム。
【請求項８】
請求項６の検証装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は情報セキュリティ技術における相手認証に関し、特に、認証相手の識別子（ＩＤ）を公開鍵に用いる相手認証方式（ＩＤベース認証方式）における安全性の強化方式に関する。
【背景技術】
【０００２】
通信相手の正当性を確認する技術として相手認証の技術がある。相手認証を実現する方式としては、パスワードを用いる方式や、デジタル署名を用いたプロトコル（ＳＩプロトコル）のほかに、利用者の名前やメールアドレスなどの識別子を公開鍵に用いるＩＤベース認証プロトコル(以下ＩＢＩプロトコル)がある。一般的に、ＩＢＩプロトコルは、鍵発行局・証明者・検証者の三者で実行される。鍵発行局は証明者の識別子ｉｄに対応する秘密鍵ｓｋｉｄを証明者に発行し、証明者と検証者が通信することで、検証者が「証明者が識別子ｉｄ対応した秘密鍵ｓｋｉｄを持っていること」を検証することができる技術である。
【０００３】
ＩＢＩプロトコルにおける安全性は攻撃の強さにより定義され、最も強い安全性は、並列攻撃に対してなりすましができないこと（secure against impersonation under concurrent attacks，以下「ｉｍｐ−ｃａ安全」）である。また、弱い安全性の定義としては，受動的攻撃に対してなりすましができないこと（secure against impersonation under passive attacks，以下「ｉｍｐ−ｐａ安全」）がある。ｉｍｐ−ｃａ安全とｉｍｐ−ｐａ安全の違いは、大まかに言えば、ｉｍｐ−ｃａ安全で想定している攻撃者がＩＢＩプロトコルを利用している全ての利用者にいつでも並列的にアクセスし、操作することが許されているのに対し、ｉｍｐ−ｐａ安全で想定している攻撃者はＩＢＩプロトコルの利用者間の通信履歴の盗聴のみが許されている点にある（例えば、非特許文献１参照）。
【０００４】
現実の利用を想定した場合、より高い安全性を持ったｉｍｐ−ｃａ安全なＩＢＩプロトコルであることが望ましい。この問題を解決するために、非特許文献２では、ｉｍｐ−ｐａ安全なＩＢＩプロトコルをもとにｉｍｐ−ｃａ安全なＩＢＩプロトコルを構成する手法が提案されている。非特許文献３の構成は、ｉｍｐ−ｐａ安全な方式におけるパラメータを２つ用意して、１つの識別子に対して各パラメータを用いて発行された秘密鍵を利用して認証を行うものである。ただし、この構成は特定の１方式（Boneh-Boyenのデジタル署名方式（例えば、非特許文献３参照）をＩＢＩプロトコルに拡張した方式）に基づく構成であり、汎用的な構成方法は示されていない。
【０００５】
よく知られた事実として、ｉｍｐ−ｐａ安全なＳＩプロトコルからｉｍｐ−ｃａ安全性をもつＳＩプロトコルを構成する方法にＯＲ−ｐｒｏｏｆと呼ばれる技法がある。一般にＯＲ−ｐｒｏｏｆとは、「２つの秘密情報(秘密鍵)のうち、どちらかを持っていることを証明する」方法である（例えば、非特許文献４参照）。ただし、ＯＲ−ｐｒｏｏｆの技法は上記に示した概念レベルの話であり、非特許文献４の方式を除いて、ＩＤベース認証で安全性の強化が証明できるＯＲ−ｐｒｏｏｆの構成はよくわかっていなかった。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Mihir Bellare, Chanathip Namprempre, and Gregory Neven, “Security proofs for identity-based identication and signature schemes,” In Christian Cachin and Jan Camenisch, editors, EUROCRYPT 2004, volume 3027 of Lecture Notes in Computer Science, pages 268-286, Springer-Verlag, 2004.
【非特許文献２】Kaoru Kurosawa and Swee-Huay Heng, “Identity-based identi cation without random oracles,” In Osvaldo Gervasi, Marina L. Gavrilova, Vipin Kumar, Antonio Lagana, Heow Pueh Lee, Youngsong Mun, David Taniar, and Chih Jeng Kenneth Tan, editors, ICCSA 2005, Part II, volume 3481 of Lecture Notes in Computer Science, pages 603-613, Springer-Verlag, 2005.
【非特許文献３】Dan Boneh and Xavier Boyen, “Short signatures without random oracles,”In Christian Cachin and Jan Camenisch, editors, EUROCRYPT, volume 3027 of Lecture Notes in Computer Science, pages 56-73, Springer, 2004.
【非特許文献４】Uriel Feige and Adi Shamir, “Witness indistinguishable and witness hiding protocols,” In STOC'90, pages 416-426, ACM, 1990.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
本発明の課題は、Σ＋型および／またはΣ＊型のあらゆるＩＢＩプロトコルに汎用的に適用可能であり、ＩＢＩプロトコルの安全性を容易に強化することができる技術を提供することである。
【課題を解決するための手段】
【０００８】
前提として、ＳＫＩＤ←ＫＧ（ＭＳＫ，ＩＤ）がマスタ秘密鍵ＭＳＫと識別子ＩＤから秘密鍵ＳＫＩＤを得る写像であり、（Ａ，ＳＴ）←Σｉｂｉ−ｃｏｍ（ＭＰＫ，ＩＤ，ＳＫＩＤ）がマスタ公開鍵ＭＰＫと識別子ＩＤと秘密鍵ＳＫＩＤからコミットメントＡと内部状態情報ＳＴを得る写像であり、Ｃ←Σｉｂｉ−ｃｈ（ＭＰＫ，ＩＤ）がマスタ公開鍵ＭＰＫと識別子ＩＤからチャレンジＣを得る写像であり、Ｕ←Σｉｂｉ−ｒｅｓ（ＭＰＫ，ＩＤ，ＳＫＩＤ，Ａ，Ｃ，ＳＴ）がマスタ公開鍵ＭＰＫと識別子ＩＤと秘密鍵ＳＫＩＤとコミットメントＡとチャレンジＣと内部状態情報ＳＴからレスポンスＵを得る写像であり、ＤＥＣ←Σｉｂｉ−ｖｒｆｙ（ＭＰＫ，ＩＤ，Ａ，Ｃ，Ｕ）がマスタ公開鍵ＭＰＫと識別子ＩＤとコミットメントＡとチャレンジＣとレスポンスＵから検証結果ＤＥＣを得る写像であり、Ｃ’←Σ+ｉｂｉ−ｃｈ（ＭＰＫ）がマスタ公開鍵ＭＰＫからチャレンジＣ’を得る写像であり、Ｃ’←Σ*ｉｂｉ−ｃｈ（１κ）がセキュリティパラメータ１κからチャレンジＣ’を得る写像であり、（Ａ’，Ｕ’）←Σｉｂｉ−ｓｉｍ（ＭＰＫ，ＩＤ，Ｃ）がマスタ公開鍵ＭＰＫと識別子ＩＤとチャレンジＣからチャレンジＣに対して検証結果ＤＥＣが受理となるコミットメントＡ’とレスポンスＵ’を得る写像である。
【０００９】
［第１態様］
第１態様では、マスタ公開鍵ＭＰＫがｍｐｋであり、マスタ秘密鍵ＭＳＫがｍｓｋであり、ｉｄが利用者識別子であり、Ｍ（α，β）がαとβに対応する値であり、ｓｋ（ｉｄ，ｂ（ｉｄ））が何れかのｂ（ｉｄ）∈｛０，１｝に対応するｓｋ（ｉｄ，ｂ（ｉｄ））←ＫＧ（ｍｓｋ，Ｍ（ｉｄ，ｂ（ｉｄ）））によって得られる値であり、ｒｂ（ｉｄ）＝１−ｂ（ｉｄ）である。第１態様では、これらを前提として以下の処理を実行する。
証明装置が、（ａｂ（ｉｄ），ｓｔ）←Σｉｂｉ−ｃｏｍ（ｍｐｋ，Ｍ（ｉｄ，ｂ（ｉｄ）），ｓｋ（ｉｄ，ｂ（ｉｄ）））によってａｂ（ｉｄ）とｓｔを得、ｃｒｂ（ｉｄ）←Σ+ｉｂｉ−ｃｈ（ｍｐｋ）によってｃｒｂ（ｉｄ）を得、（ａｒｂ（ｉｄ），ｕｒｂ（ｉｄ））←Σｉｂｉ−ｓｉｍ（ｍｐｋ，Ｍ（ｉｄ，ｒｂ（ｉｄ）），ｃｒｂ（ｉｄ））によってａｒｂ（ｉｄ）とｕｒｂ（ｉｄ）を得、コミットメント（ａ０，ａ１）を出力する。
検証装置が、コミットメント（ａ０，ａ１）の入力を受け付け、ｃ←Σ+ｉｂｉ−ｃｈ（ｍｐｋ）によってチャレンジｃを得、チャレンジｃを出力する。
証明装置が、入力されたチャレンジｃからｃｂ（ｉｄ）＝ｃ−ｃｒｂ（ｉｄ）を得、ｕｂ（ｉｄ）←Σｉｂｉ−ｒｅｓ（ｍｐｋ，Ｍ（ｉｄ，ｂ（ｉｄ）），ｓｋ（ｉｄ，ｂ（ｉｄ）），ａｂ（ｉｄ），ｃｂ（ｉｄ），ｓｔ）によってｕｂ（ｉｄ）を得、レスポンス（ｃ０，ｕ０，ｕ１）を出力する。
検証装置が、レスポンス（ｃ０，ｕ０，ｕ１）の入力を受け付け、ｃ１＝ｃ−ｃ０を得、ｄｅｃ←Σｉｂｉ−ｖｒｆｙ（ｍｐｋ，Ｍ（ｉｄ，０），ａ０，ｃ０，ｕ０）によって得られる検証結果ｄｅｃと、ｄｅｃ’←Σｉｂｉ−ｖｒｆｙ（ｍｐｋ，Ｍ（ｉｄ，１），ａ１，ｃ１，ｕ１）によって得られる検証結果ｄｅｃ’とがともに受理となるかを判定する。
【００１０】
［第２態様］
第２態様では、マスタ公開鍵ＭＰＫがｍｐｋであり、マスタ秘密鍵ＭＳＫがｍｓｋであり、ｉｄが利用者識別子であり、Ｍ（α，β）がαとβに対応する値であり、ｂ（ｉｄ）∈｛０，１｝であり、ｓｋ（ｉｄ，ｂ（ｉｄ））がｓｋ（ｉｄ，ｂ（ｉｄ））←ＫＧ（ｍｓｋ，Ｍ（ｉｄ，ｂ（ｉｄ）））によって得られる値であり、ｒｂ（ｉｄ）＝１−ｂ（ｉｄ）である。第２態様では、これらを前提として以下の処理を実行する。
証明装置が、何れかのｂ（ｉｄ）∈｛０，１｝に対応する（ａｂ（ｉｄ），ｓｔ）←Σｉｂｉ−ｃｏｍ（ｍｐｋ，Ｍ（ｉｄ，ｂ（ｉｄ）），ｓｋ（ｉｄ，ｂ（ｉｄ）））によってａｂ（ｉｄ）とｓｔを得、ｃｒｂ（ｉｄ）←Σ+ｉｂｉ−ｃｈ（ｍｐｋ）によってｃｒｂ（ｉｄ）を得、（ａｒｂ（ｉｄ），ｕｒｂ（ｉｄ））←Σｉｂｉ−ｓｉｍ（ｍｐｋ，Ｍ（ｉｄ，ｒｂ（ｉｄ）），ｃｒｂ（ｉｄ））によってａｒｂ（ｉｄ）とｕｒｂ（ｉｄ）を得、コミットメント（ａ０，ａ１）を出力する。
検証装置が、コミットメント（ａ０，ａ１）の入力を受け付け、ｃ←Σ+ｉｂｉ−ｃｈ（ｍｐｋ）によってチャレンジｃを得、チャレンジｃを出力する。
証明装置が、入力されたチャレンジｃからｃｂ（ｉｄ）＝ｃ−ｃｒｂ（ｉｄ）を得、ｕｂ（ｉｄ）←Σｉｂｉ−ｒｅｓ（ｍｐｋ，Ｍ（ｉｄ，ｂ（ｉｄ）），ｓｋ（ｉｄ，ｂ（ｉｄ）），ａｂ（ｉｄ），ｃｂ（ｉｄ），ｓｔ）によってｕｂ（ｉｄ）を得、レスポンス（ｃ０，ｕ０，ｕ１）を出力する。
検証装置が、レスポンス（ｃ０，ｕ０，ｕ１）の入力を受け付け、ｃ１＝ｃ−ｃ０を得、ｄｅｃ←Σｉｂｉ−ｖｒｆｙ（ｍｐｋ，Ｍ（ｉｄ，０），ａ０，ｃ０，ｕ０）によって得られる検証結果ｄｅｃと、ｄｅｃ’←Σｉｂｉ−ｖｒｆｙ（ｍｐｋ，Ｍ（ｉｄ，１），ａ１，ｃ１，ｕ１）によって得られる検証結果ｄｅｃ’とがともに受理となるかを判定する。
【００１１】
［第３態様］
第３態様では、マスタ公開鍵ＭＰＫがｍｐｋであり、マスタ秘密鍵ＭＳＫがｍｓｋであり、ｉｄが利用者識別子であり、ｉｄｍａｓｔｅｒがマスタ識別子であり、ｉｄ≠ｉｄｍａｓｔｅｒであり、ｓｋｉｄがｓｋｉｄ←ＫＧ（ｍｓｋ，ｉｄ）によって得られる値である。第３態様では、これらを前提として以下の処理を実行する。
証明装置が、（ａ０，ｓｔ）←Σｉｂｉ−ｃｏｍ（ｍｐｋ，ｉｄ，ｓｋｉｄ）によってａ０とｓｔを得、ｃ１←Σ+ｉｂｉ−ｃｈ（ｍｐｋ）によってｃ１を得、（ａ１，ｕ１）←Σｉｂｉ−ｓｉｍ（ｍｐｋ，ｉｄｍａｓｔｅｒ，ｃ１）によってａ１とｕ１を得、コミットメント（ａ０，ａ１）を出力する。
検証装置が、コミットメント（ａ０，ａ１）の入力を受け付け、ｃ←Σ+ｉｂｉ−ｃｈ（ｍｐｋ）によってチャレンジｃを得、チャレンジｃを出力する。
証明装置が、入力されたチャレンジｃからｃ０＝ｃ−ｃ１を得、ｕ０←Σｉｂｉ−ｒｅｓ（ｍｐｋ，ｉｄ，ｓｋｉｄ，ａ０，ｃ０，ｓｔ）によってｕ０を得、レスポンス（ｃ０，ｕ０，ｕ１）を出力する。
検証装置が、レスポンス（ｃ０，ｕ０，ｕ１）の入力を受け付け、ｃ１＝ｃ−ｃ０を得、ｄｅｃ←Σｉｂｉ−ｖｒｆｙ（ｍｐｋ，ｉｄ，ａ０，ｃ０，ｕ０）によって得られる検証結果ｄｅｃと、ｄｅｃ’←Σｉｂｉ−ｖｒｆｙ（ｍｐｋ，ｉｄｍａｓｔｅｒ，ａ１，ｃ１，ｕ１）によって得られる検証結果ｄｅｃ’とがともに受理となるかを判定する。
【００１２】
［第４態様］
第４態様では、（ｍｐｋ０，ｍｓｋ０）および（ｍｐｋ１，ｍｓｋ１）のそれぞれがマスタ公開鍵とマスタ秘密鍵との鍵ペア（ＭＰＫ，ＭＳＫ）であり、ｉｄが利用者識別子であり、ｓｋ（ｉｄ，ｂ（ｉｄ））が何れかのｂ（ｉｄ）∈｛０，１｝に対応するｓｋ（ｉｄ，ｂ（ｉｄ））←ＫＧ（ｍｓｋｂ（ｉｄ），ｉｄ）によって得られる値であり、ｒｂ（ｉｄ）＝１−ｂ（ｉｄ）である。第４態様では、これらを前提として以下の処理を実行する。
証明装置が、（ａｂ（ｉｄ），ｓｔ）←Σｉｂｉ−ｃｏｍ（ｍｐｋｂ（ｉｄ），ｉｄ，ｓｋ（ｉｄ，ｂ（ｉｄ）））によってａｂ（ｉｄ）とｓｔを得、ｃｒｂ（ｉｄ）←Σ*ｉｂｉ−ｃｈ（１κ）によってｃｒｂ（ｉｄ）を得、（ａｒｂ（ｉｄ），ｕｒｂ（ｉｄ））←Σｉｂｉ−ｓｉｍ（ｍｐｋｒｂ（ｉｄ），ｉｄ，ｃｒｂ（ｉｄ））によってａｒｂ（ｉｄ）とｕｒｂ（ｉｄ）を得、コミットメント（ａ０，ａ１）を出力する。
検証装置が、コミットメント（ａ０，ａ１）の入力を受け付け、ｃ←Σ*ｉｂｉ−ｃｈ（１κ）によってチャレンジｃを得、チャレンジｃを出力する。
証明装置が、入力されたチャレンジｃからｃｂ（ｉｄ）＝ｃ−ｃｒｂ（ｉｄ）を得、ｕｂ（ｉｄ）←Σｉｂｉ−ｒｅｓ（ｍｐｋｂ（ｉｄ），ｉｄ，ｓｋ（ｉｄ，ｂ（ｉｄ）），ａｂ（ｉｄ），ｃｂ（ｉｄ），ｓｔ）によってｕｂ（ｉｄ）を得、レスポンス（ｃ０，ｕ０，ｕ１）を出力する。
検証装置が、レスポンス（ｃ０，ｕ０，ｕ１）の入力を受け付け、ｃ１＝ｃ−ｃ０を得、ｄｅｃ←Σｉｂｉ−ｖｒｆｙ（ｍｐｋ０，ｉｄ，ａ０，ｃ０，ｕ０）によって得られる検証結果ｄｅｃと、ｄｅｃ’←Σｉｂｉ−ｖｒｆｙ（ｍｐｋ１，ｉｄ，ａ１，ｃ１，ｕ１）によって得られる検証結果ｄｅｃ’とがともに受理となるかを判定する。
【発明の効果】
【００１３】
本発明は、Σ＋型、およびΣ＊型のあらゆるＩＢＩプロトコルに汎用的に適用可能であり、ＩＢＩプロトコルの安全性を容易に強化することができる。
【図面の簡単な説明】
【００１４】
【図１】実施形態の認証システムの構成を例示したブロック図である。
【図２】第１実施形態の認証方法を例示したフロー図である。
【図３】第１，２実施形態の認証方法を例示したフロー図である。
【図４】第２実施形態の認証方法を例示したフロー図である。
【図５】第３実施形態の認証方法を例示したフロー図である。
【図６】第３実施形態の認証方法を例示したフロー図である。
【図７】第４実施形態の認証方法を例示したフロー図である。
【図８】第５実施形態の認証方法を例示したフロー図である。
【発明を実施するための形態】
【００１５】
本発明の実施形態を説明する。
＜定義＞
まず、本形態で用いる用語を定義する。
【００１６】
≪ＩＤベース認証プロトコル≫
ＩＤベース認証プロトコル（Identity-based identification protocol: IBI protocol）とは、利用者の識別子を公開鍵に用いることのできる相手認証方式である。一般的に、ＩＤベース認証プロトコルは、鍵発行局・証明者・検証者の三者によって実行される。ＩＤベース認証プロトコルでは、鍵発行局は証明者の識別子ＩＤに対応する秘密鍵ＳＫＩＤを証明者に発行し、証明者と検証者が通信することで、検証者が「証明者が識別子ＩＤに対応したＳＫＩＤを持っていること」を検証できる。より形式的には、ＩＤベース認証は次の４つの確率的多項式時間アルゴリズムＩＢＩ＝（ＳｅｔＵｐ，ＫＧ，Ｐ，Ｖ）から構成される。
・ＳｅｔＵｐ（マスタ鍵生成アルゴリズム）：鍵発行局で実行されるＳｅｔＵｐは、セキュリティパラメータ１κを入力として、ＩＤベース暗号方式のマスタ秘密鍵ＭＳＫおよびマスタ公開鍵ＭＰＫを出力する（（ＭＰＫ，ＭＳＫ）←ＳｅｔＵｐ（１κ））。マスタ秘密鍵ＭＳＫは秘匿され、マスタ公開鍵ＭＰＫは公開される。なお、κは正整数であり、１κは１が並んだ長さκのビット列である。
・ＫＧ（ユーザ鍵生成アルゴリズム）：ＫＧは、ＭＳＫと識別子ＩＤを入力として、ＩＤに対応する秘密鍵ＳＫＩＤを出力する（ＳＫＩＤ←ＫＧ（ＭＳＫ，ＩＤ））。
・Ｐ（証明者アルゴリズム）：Ｐは、（ＭＰＫ，ＩＤ，ＳＫＩＤ）を入力とし、Ｖと通信する。
・Ｖ（検証者アルゴリズム）：（ＭＰＫ，ＩＤ）を入力として、Ｐと通信し、最終的に証明者がＳＫＩＤを持っていることが検証できれば「受理（ａｃｃｅｐｔ）」、そうでなければ「拒否（ｒｅｊｅｃｔ）」を出力する。
上記のうち、鍵発行局はＳｅｔＵｐ、ＫＧを、証明者はＰを、検証者はＶをそれぞれ実行する。
【００１７】
≪Σ＋型およびΣ＊型ＩＢＩプロトコル≫
ここでは、ＩＢＩプロトコルＩＢＩ＝（ＳｅｔＵｐ，ＫＧ，Ｐ，Ｖ）として、ＰとＶの通信が３回で完了し、ＰとＶは、以下の確率的多項式時間アルゴリズム（ Σｉｂｉ−ｃｏｍ，Σｉｂｉ−ｃｈ，Σｉｂｉ−ｒｅｓ，Σｉｂｉ−ｖｒｆｙ）を利用するプロトコル（「標準的ＩＢＩプロトコル」）を対象とする。
・Ｐ→Ｖ：Ｐは（Ａ，ＳＴ）←Σｉｂｉ−ｃｏｍ（ＭＰＫ，ＩＤ，ＳＫＩＤ）を計算し、コミットメントＡをＶに送信する。ただし、ＳＴはＰの内部状態情報である。また、（Ａ，ＳＴ）←Σｉｂｉ−ｃｏｍ（ＭＰＫ，ＩＤ，ＳＫＩＤ）は、マスタ公開鍵ＭＰＫと識別子ＩＤと秘密鍵ＳＫＩＤからコミットメントＡと内部状態情報ＳＴを得るアルゴリズムである。
・Ｖ→Ｐ：ＶはチャレンジＣ← Σｉｂｉ−ｃｈ（ＭＰＫ，ＩＤ）を計算し、ＣをＰに送信する。ただし、Ｃ←Σｉｂｉ−ｃｈ（ＭＰＫ，ＩＤ）は、マスタ公開鍵ＭＰＫと識別子ＩＤからチャレンジＣを得るアルゴリズムである。
・Ｐ→Ｖ：ＰはレスポンスＵ←Σｉｂｉ−ｒｅｓ（ＭＰＫ，ＩＤ，ＳＫＩＤ，Ａ，Ｃ，ＳＴ）を計算し、ＵをＶに送信する。ただし、Ｕ←Σｉｂｉ−ｒｅｓ（ＭＰＫ，ＩＤ，ＳＫＩＤ，Ａ，Ｃ，ＳＴ）は、マスタ公開鍵ＭＰＫと識別子ＩＤと秘密鍵ＳＫＩＤとコミットメントＡとチャレンジＣと内部状態情報ＳＴからレスポンスＵを得るアルゴリズムである。
・Ｖ：Ｖは検証結果ＤＥＣ←Σｉｂｉ−ｖｒｆｙ（ＭＰＫ，ＩＤ，Ａ，Ｃ，Ｕ）を計算し、ＤＥＣ∈｛ａｃｃｅｐｔ，ｒｅｊｅｃｔ｝を出力する。ただし、ＤＥＣ←Σｉｂｉ−ｖｒｆｙ（ＭＰＫ，ＩＤ，Ａ，Ｃ，Ｕ）は、マスタ公開鍵ＭＰＫと識別子ＩＤとコミットメントＡとチャレンジＣとレスポンスＵから検証結果ＤＥＣを得るアルゴリズムである。
【００１８】
標準的ＩＢＩプロトコルのうち、以下の３つの性質（special zero-knowledge, special soundness, special challenge）を同時に満たすＩＢＩプロトコルをΣ＋型ＩＢＩプロトコルと呼ぶ。
【００１９】
Special zero-knowledge：チャレンジＣ、マスタ公開鍵ＭＰＫおよび識別子ＩＤから、受理可能な通信履歴を計算できる。つまり、ＭＰＫ，ＩＤおよびＣ←Σｉｂｉ−ｃｈ（ＭＰＫ，ＩＤ）を満たすＣを入力として、ａｃｃｅｐｔ＝Σｉｂｉ−ｖｒｆｙ（ＭＰＫ，ＩＤ，Ａ，Ｃ，Ｕ）を満たす（検証結果ＤＥＣが受理となる）コミットメントとレスポンス（Ａ’，Ｕ’）を出力する確率的多項式時間アルゴリズム Σｉｂｉ−ｓｉｍ（ＭＰＫ，ＩＤ，Ｃ）を構成できる。ただし、（Ａ’，Ｕ’）←Σｉｂｉ−ｓｉｍ（ＭＰＫ，ＩＤ，Ｃ）を、マスタ公開鍵ＭＰＫと識別子ＩＤとチャレンジＣからチャレンジＣに対して検証結果ＤＥＣが受理となるコミットメントＡ’とレスポンスＵ’を得るアルゴリズムとする。ここで、Σｉｂｉ−ｃｈとΣｉｂｉ−ｓｉｍの出力の確率分布は、実際のプロトコルの出力の分布と識別不可能である。
【００２０】
Special soundness：マスタ公開鍵ＭＰＫと識別子ＩＤと２つの通信履歴（Ａ，Ｃ，Ｕ）（Ａ，Ｃ’’，Ｕ’’）（ただし、Ｃ≠Ｃ’’）から、識別子ＩＤに対応する秘密鍵ＳＫＩＤを計算できる。つまり、ＭＰＫとＩＤとａｃｃｅｐｔ＝Σｉｂｉ−ｖｒｆｙ（ＭＰＫ，ＩＤ，Ａ，Ｃ，Ｕ）＝Σｉｂｉ−ｖｒｆｙ（ＭＰＫ，ＩＤ，Ａ，Ｃ’’，Ｕ’’）を満たす２つの通信履歴（Ａ，Ｃ，Ｕ），（Ａ，Ｃ’’，Ｕ’’）を入力とし、ＳＫＩＤを出力する確率的多項式時間アルゴリズムＳＫＩＤ←Σｉｂｉ−ｅｘｔ（ＭＰＫ，（Ａ，Ｃ，Ｕ），（Ａ，Ｃ’’，Ｕ’’））を構成することができる。
【００２１】
Special challenge：Σｉｂｉ−ｃｈはマスタ公開鍵ＭＰＫのみに依存し（つまりＩＤには非依存）、その出力であるチャレンジＣ’はある集合Ｇ（例えば、可換群）の要素であって、出力の分布はＧ上の一様分布である。さらに、Ｇでの演算＋は多項式時間で実行できる。つまり、ＭＰＫのみを入力とし、Ｃ’を出力する確率的多項式時間アルゴリズムＣ’←Σ＋ｉｂｉ−ｃｈ（ＭＰＫ）があって、その出力はＧ上の一様分布である。
【００２２】
また、上記の Σ＋型の性質において、special challengeを以下のStrongly special challengeに置き換えたＩＢＩプロトコルをΣ＊型ＩＢＩプロトコルと呼ぶ。
Strongly special challenge：Σ＊ｉｂｉ−ｃｈはセキュリティパラメータ１κのみに依存し（つまりＭＰＫとＩＤには非依存）、その出力であるチャレンジＣ’はある集合Ｇ（例えば、可換群）の要素であって、出力の分布はＧ上の一様分布である。さらに、Ｇでの演算＋は多項式時間で実行できる。つまり、セキュリティパラメータ１κのみを入力とし、チャレンジＣ’を出力する確率的多項式時間アルゴリズムＣ’←Σ＊ｉｂｉ−ｃｈ（１κ）があって、その出力はＧ上の一様分布である。
【００２３】
≪Σ＋型およびΣ＊型ＩＢＩプロトコルの具体例≫
上述のΣ＋型およびΣ＊型ＩＢＩプロトコルには多くの具体的な方式が存在し、それらの構成方法はよく知られている。
【００２４】
例えば、Σ＋型ＩＢＩプロトコルの具体例として、参考文献１「Kaoru Kurosawa and Swee-Huay Heng, “Identity-based identification without random oracles,” In Osvaldo Gervasi, Marina L. Gavrilova, Vipin Kumar, Antonio Lagana, Heow Pueh Lee, Youngsong Mun, David Taniar, and Chih Jeng Kenneth Tan, editors, ICCSA 2005, Part II, volume 3481 of Lecture Notes in Computer Science, pages 603-613, Springer-Verlag, 2005.」に記載された方式がある。この方式では、Boneh-Boyenの方式（参考文献２「Dan Boneh and Xavier Boyen, “Short signatures without random oracles,” In Christian Cachin and Jan Camenisch, editors, EUROCRYPT, volume 3027 of Lecture Notes in Computer Science, pages 56-73, Springer, 2004.」参照）が、適応的選択文書攻撃に対して潜在的に偽造不可であれば、ｉｍｐ−ｃａ安全であることが示されている。
【００２５】
Σ＊型ＩＢＩプロトコルの具体例として、参考文献３「Mihir Bellare, Chanathip Namprempre, and Gregory Neven, “Security proofs for identity-based identification and signature schemes,” Journal of Cryptology, 22(1):1-61, January 2009, Preliminary version in EURO-CRYPT 2004, 2004.」に記載された方式がある。参考文献３に記載された方式は、ShamirのＩＤベース署名（参考文献４「Adi Shamir, “Identity-based cryptosystems and signature schemes,” In George Robert Blakley and David Chaum, editors, CRYPTO '84, volume 196 of Lecture Notes in Computer Science, pages 47-53, Springer-Verlag, 1985.」等参照）をＩＤベース認証に変形したものである。
【００２６】
以下にΣ＋型およびΣ＊型ＩＢＩプロトコルの具体例を示す。ただし、これらは本発明を限定するものではなく、本発明は様々なΣ＋型および／またはΣ＊型ＩＢＩプロトコルに汎用的に適用できる。
【００２７】
［参考文献１のΣ＋型ＩＢＩプロトコル］
参考文献１のΣ＋型ＩＢＩプロトコルを例示する。この例では（Ｇ１，Ｇ２）が素数位数ｐの双線形群であり、ｇ１が群Ｇ１の生成元であり、ｇ２が群Ｇ２の生成元である。ｅは双線形群（Ｇ１，Ｇ２）で定義された双線形写像である。
【００２８】
・ＳｅｔＵｐ：（ＭＰＫ，ＭＳＫ）←ＳｅｔＵｐ（１κ）の構成は以下の通りである。
１．セキュリティパラメータ１κを入力として、ランダムにｘ，ｙ∈Ｚｐ*を選択する。
２．ｗ＝ｇ１ｘおよびｖ＝ｇ２ｙを計算する。
３．衝突困難なハッシュ関数Ｈ：｛０，１｝*→Ｚｐ*を選択する。
４．マスタ公開鍵ＭＰＫ＝（ｇ１，ｇ２，ｗ，ｖ，Ｈ）およびマスタ秘密鍵ＭＳＫ＝（ｘ，ｙ）とする。
【００２９】
・ＫＧ：ＳＫＩＤ←ＫＧ（ＭＳＫ，ＩＤ）の構成は以下の通りである。
１．ＭＳＫ＝（ｘ，ｙ）と識別子ＩＤを入力として、ランダムにｒ∈Ｚｐ*を選択する。
２．σ＝ｇ１１／（ｘ＋Ｈ（ＩＤ）＋ｙｒ）∈Ｇ１を計算する。ただし、（ｘ＋Ｈ（ＩＤ）＋ｙｒ）はｐを法とした剰余演算（ｘ＋Ｈ（ＩＤ）＋ｙｒ）  ｍｏｄ  ｐとして得られる。（ｘ＋Ｈ（ＩＤ）＋ｙｒ）ｍｏｄ  ｐが０  ｍｏｄ  ｐとなる場合、ＫＧは乱数ｒを選びなおして新たにσを得る。
３．秘密鍵をＳＫＩＤ＝（σ，ｒ）とする。
【００３０】
・Ｐ→Ｖ：（Ａ，ＳＴ）←Σｉｂｉ−ｃｏｍ（ＭＰＫ，ＩＤ，ＳＫＩＤ）の構成は以下の通りである。
１．ＭＰＫ＝（ｇ１，ｇ２，ｗ，ｖ，Ｈ）、ＩＤ、およびＳＫＩＤ＝（σ，ｒ）を入力とし、ランダムにＲ∈Ｇ１を選択する。
２．Ｘ＝ｅ（Ｒ，ｗ・ｇ２Ｈ（ＩＤ）・ｖｒ）を計算する。
３．ＳＴ＝Ｒとし、コミットメントＡ＝（ｒ，Ｘ）とする。コミットメントＡをＶに送信する。
【００３１】
・Ｖ→Ｐ：Ｃ← Σｉｂｉ−ｃｈ（ＭＰＫ，ＩＤ）の構成は以下の通りである。
１．ＭＰＫおよびＩＤを入力とし、ランダムにチャレンジＣ∈Ｚｐを選択する。
２．ＣをＰに送信する。
【００３２】
・Ｐ→Ｖ：Ｕ←Σｉｂｉ−ｒｅｓ（ＭＰＫ，ＩＤ，ＳＫＩＤ，Ａ，Ｃ，ＳＴ）の構成は以下の通りである。
１．ＭＰＫ＝（ｇ１，ｇ２，ｗ，ｖ，Ｈ），ＩＤ，ＳＫＩＤ＝（σ，ｒ），Ａ，ＣおよびＳＴ＝Ｒを入力とし、Ｓ＝Ｒ・σＣを計算する。
２．ＳをレスポンスＵとしてＶに送信する。
【００３３】
・Ｖ：ＤＥＣ←Σｉｂｉ−ｖｒｆｙ（ＭＰＫ，ＩＤ，Ａ，Ｃ，Ｕ）の構成は以下の通りである。
ＭＰＫ＝（ｇ１，ｇ２，ｗ，ｖ，Ｈ），ＩＤ，Ａ，Ｃ，Ｕを入力とし、ｅ（Ｕ，ｗ・ｇ２Ｈ（ＩＤ）・ｖｒ）＝Ｘ・ｅ（ｇ１，ｇ２）Ｃを満たす場合にＤＥＣ＝ａｃｃｅｐｔを出力し、それ以外の場合にＤＥＣ＝ｒｅｊｅｃｔを出力する。
【００３４】
・Special zero-knowledge：（Ａ’，Ｕ’）←Σｉｂｉ−ｓｉｍ（ＭＰＫ，ＩＤ，Ｃ）の構成は以下の通りである。
１．ＭＰＫ，ＩＤ，Ｃを入力とし、Ｓ’∈Ｇ１をランダムに選択する。
２．Ｘ’＝ｅ（Ｓ’，ｗ・ｇ２Ｈ（ＩＤ）・ｖｒ）／ｅ（ｇ１，ｇ２）Ｃを計算する。
３．Ａ’＝（ｒ，Ｘ’）およびＵ’＝Ｓを出力する。
【００３５】
・Special soundness：ＳＫＩＤ←Σｉｂｉ−ｅｘｔ（ＭＰＫ，（Ａ，Ｃ，Ｕ），（Ａ，Ｃ’’，Ｕ’’）の構成は以下の通りである。
１．Ｕ＝Ｒ・σＣおよびＵ’’＝Ｒ・σＣ’’であることから、Ｕ／Ｕ’’＝σＣ−Ｃ’’であり、ゆえにσ＝（Ｕ／Ｕ’’）１／（Ｃ−Ｃ’’）を得ることができる。
２．Ａ＝（ｒ，Ｘ）であることから、秘密鍵ＳＫＩＤ＝（σ，ｒ）を得ることができる。
【００３６】
Special challenge： この例のＣ← Σｉｂｉ−ｃｈ（ＭＰＫ，ＩＤ）は、マスタ公開鍵ＭＰＫのみに依存し、その出力であるチャレンジＣはある可換群Ｇ＝Ｚｐの要素であって，出力の分布はＧ上の一様分布である。さらに、Ｇの群演算＋は多項式時間で実行できることは明らかである。したがって、Σｉｂｉ−ｃｈ（ＭＰＫ，ＩＤ）をΣ＋ｉｂｉ−ｃｈ（ＭＰＫ）とできる。
【００３７】
［参考文献３のΣ＊型ＩＢＩプロトコル］
参考文献３のΣ＊型ＩＢＩプロトコルを例示する。
・ＳｅｔＵｐ：（ＭＰＫ，ＭＳＫ）←ＳｅｔＵｐ（１κ）の構成は以下の通りである。
１．（Ｎ，Ｅ，Ｄ）←Ｋｒｓａ（１κ）を素数べきＲＳＡ生成アルゴリズムの出力とする。つまり、Ｎは２つの素数の積であり、（Ｅ，Ｄ）はＥ・Ｄ≡１（ｍｏｄ  λ（Ｎ））でＥ（＞２Ｌ（κ））を素数とする。ここで、λ（Ｎ）はＮのカーマイケル関数の値であり、Ｎ＝ｐ・ｑ（ｐ，ｑは素数）のとき、λ（Ｎ）＝ＬＣＭ（ｐ−１，ｑ−１）を満たす（ＬＣＭは最小公倍数）。またＬ（１κ）は、κを大きくすると  ｜Ｌ（１κ）／ｌｇ  κ｜の値が無限大に発散するような関数であるである。
２．ハッシュ関数Ｈ：｛０，１｝→ＺＮ*を一つ定め、マスタ公開鍵ＭＰＫ＝（Ｎ，Ｅ，Ｈ）およびマスタ秘密鍵ＭＳＫ＝Ｄとする。
【００３８】
・ＫＧ：ＳＫＩＤ←ＫＧ（ＭＳＫ，ＩＤ）の構成は以下の通りである。
１．ＭＳＫ＝ＤおよびＩＤを入力とし、Ｘ＝Ｈ（ＩＤ）（ｍｏｄ  Ｎ）を計算する。
２．ｘ＝ＸＤ（ｍｏｄ  Ｎ）を計算する。
３．秘密鍵をＳＫＩＤ＝ｘとする。
【００３９】
・Ｐ→Ｖ：（Ａ，ＳＴ）←Σｉｂｉ−ｃｏｍ（ＭＰＫ，ＩＤ，ＳＫＩＤ）の構成は以下の通りである。
１．ＭＰＫ＝（Ｎ，Ｅ，Ｈ），ＩＤ，ＳＫＩＤ＝ｘを入力とし、ランダムにｙ∈ＺＮ*を選択する。
２．Ｙ＝ｙＥ  ｍｏｄ  Ｎを計算する。
３．ＳＴ＝ｙとし、Ａ＝Ｙとし、コミットメントＡをＶに送信する。
【００４０】
・Ｖ→Ｐ：Ｃ←Σｉｂｉ−ｃｈ（ＭＰＫ，ＩＤ）の構成は以下の通りである。
１．ＭＰＫ，ＩＤを入力とし、｛０，...，２Ｌ（κ）−１｝からランダムにチャレンジＣを選択し、チャレンジＣをＰに送信する。
【００４１】
・Ｐ→Ｖ：Ｕ←Σｉｂｉ−ｒｅｓ（ＭＰＫ，ＩＤ，ＳＫＩＤ，Ａ，Ｃ，ＳＴ）の構成は以下の通りである。
１．ＭＰＫ，ＩＤ，ＳＫＩＤ＝ｘ，Ａ，Ｃ，ＳＴ＝ｙを入力とし、Ｃ∈｛０，...，２Ｌ（κ）−１｝であるか判定する。
２．Ｃ∈｛０，...，２Ｌ（κ）−１｝でなければ処理を終了し、Ｃ∈｛０，...，２Ｌ（κ）−１｝であればレスポンスＵ＝ｘ・ｙＣ  ｍｏｄ  Ｎを計算して、レスポンスＵをＶに送信する。
【００４２】
・Ｖ：ＤＥＣ←Σｉｂｉ−ｖｒｆｙ（ＭＰＫ，ＩＤ，Ａ，Ｃ，Ｕ）の構成は以下の通りである。
１．ＭＰＫ＝（Ｎ，Ｅ，Ｈ），ＩＤ，Ａ，Ｃ，Ｕを入力とし、Ｘ＝Ｈ（ＩＤ）（ｍｏｄ  Ｎ）を計算する。
２．ＵＥ≡Ｘ・ＡＣ  ｍｏｄ  ＮかつＡ，Ｕ∈ＺＮ*であれば、ＤＥＣ＝ａｃｃｅｐｔを出力し、そうでなければ、ＤＥＣ＝ｒｅｊｅｃｔを出力する。
【００４３】
・Special zero-knowledge：（Ａ’，Ｕ’）←Σｉｂｉ−ｓｉｍ（ＭＰＫ，ＩＤ，Ｃ）の構成は以下の通りである。
１．ＭＰＫ＝（Ｎ，Ｅ，Ｈ），ＩＤ，Ｃを入力とし、ユークリッドの互除法によりａ・Ｃ＋ｂ・Ｅ＝１を満たすａ，ｂ∈Ｚを求める。
２．ランダムにｙ’∈ＺＮ＊を選択する。
３．Ｘ’＝Ｈ（ＩＤ）およびＹ’＝Ｘ’−ａ・ｙ’Ｅ  ｍｏｄ  Ｎを計算する。
４．Ｕ’＝ Ｘ’ｂ・ｙ’Ｃ  ｍｏｄ  Ｎを計算する。
５．（Ａ’，Ｕ’）を出力する。
【００４４】
・Special soundness：ＳＫＩＤ←Σｉｂｉ−ｅｘｔ（ＭＰＫ，（Ａ，Ｃ，Ｕ），（Ａ，Ｃ’’，Ｕ’’）の構成は以下の通りである。
１．ユークリッド互除法により、ａ（Ｃ−Ｃ’’）＋ｂ・Ｅ＝１を満たすａ，ｂ∈Ｚを求める。
２．（Ｕ／Ｕ’’）Ｅ＝ＹＣ−Ｃ’’を満たす。ゆえに、Ｙ＝Ｙａ（Ｃ−Ｃ’’）＋ｂ・Ｅ＝（（Ｕ／Ｕ’’）ａ・Ｙｂ）Ｅとなるため、ｙ＝（Ｕ／Ｕ’’）ａ・Ｙｂを計算できる。Ｕ＝ｘ・ｙＣ  ｍｏｄ  Ｎからｘ＝Ｕ・ｙ−Ｃ  ｍｏｄ  Ｎであるため、ＳＫＩＤ＝ｘを計算することができる。
【００４５】
Strongly special challenge：Ｃ←Σｉｂｉ−ｃｈ（ＭＰＫ，ＩＤ）はセキュリティパラメータ１κのみに依存し、その出力であるチャレンジＣは可換群Ｇ＝Ｚ２Ｌ（κ）の要素であって、出力の分布はＧ上の一様分布である。さらに、Ｇの群演算＋は多項式時間で実行できることは明らかである。したがって、Σｉｂｉ−ｃｈ（ＭＰＫ，ＩＤ）をΣ＊ｉｂｉ−ｃｈ（１κ）とできる。
【００４６】
＜第１実施形態＞
第１実施形態を説明する。第１実施形態では、Σ＋型、またはΣ＊型のＩＢＩプロトコルＩＢＩ＝（ＳｅｔＵｐ，ＫＧ，Ｐ，Ｖ）から、ｉｍｐ−ｃａ安全性を持つＩＢＩプロトコルを構成する。本形態では、検証者が「証明者がｓｋ（ｉｄ，０）またはｓｋ（ｉｄ，１）のいずれかを持っていること」を証明する（Dual-Identity Transformation）。
【００４７】
図１に例示するように、第１実施形態の認証システム１は、鍵発行局として機能する鍵生成装置１１と、証明者として機能する証明装置１２と、検証者として機能する検証装置１３を有する。鍵生成装置１１と証明装置１２と検証装置１３は、ネットワークを通じて通信可能に構成される。
【００４８】
鍵生成装置１１は、マスタ鍵生成部１１１と、鍵生成部１１２と、制御部１１６と、記憶部１１７と、通信部１１８を有する。証明装置１２は、演算部１２１〜１２５と、制御部１２６と、記憶部１２７と、通信部１２８（出力部および入力部）を有する。検証装置１３は、演算部１３１，１３２と、判定部１３３と、制御部１３６と、記憶部１３７と、通信部１３８（出力部および入力部）を有する。鍵生成装置１１、証明装置１２、および検証装置１３のそれぞれは、例えば、通信機能を備えた公知または専用のコンピュータに特別なプログラムが読み込まれて構成される特別な装置である。
【００４９】
鍵生成装置１１、証明装置１２、および検証装置１３は、それぞれ、制御部１１６、制御部１２６、および制御部１３６の制御のもとで各処理を実行する。鍵生成装置１１、証明装置１２、および検証装置１３への入力情報は、それぞれ、記憶部１１７、記憶部１２７、および記憶部１３７に格納される。鍵生成装置１１、証明装置１２、および検証装置１３で得られた情報も、それぞれ、記憶部１１７、記憶部１２７、および記憶部１３７に格納される。記憶部１１７、記憶部１２７、および記憶部１３７に格納された情報は、必要に応じて読み出され、それぞれの処理に用いられる。
【００５０】
図２および図３を参照して、第１実施形態の認証処理を説明する。
≪ＳｅｔＵｐ’≫
鍵生成装置１１のマスタ鍵生成部１１１は、記憶部１１７に格納しておいたセキュリティパラメータ１κを入力とし、（ｍｐｋ，ｍｓｋ）←ＳｅｔＵｐ（１κ）を実行して、マスタ公開鍵とマスタ秘密鍵（ｍｐｋ，ｍｓｋ）を得て出力する。マスタ公開鍵ｍｐｋとマスタ秘密鍵ｍｓｋは記憶部１１７に格納される（ステップＳ１０１）。マスタ公開鍵ｍｐｋは通信部１１８から出力され、ネットワーク経由で証明装置１２および検証装置１３に送信される。マスタ公開鍵ｍｐｋは、それぞれ、証明装置１２および検証装置１３の通信部１２８および１３８に入力され、記憶部１２７および１３７に格納される（ステップＳ１０２，Ｓ１０３）。マスタ秘密鍵ｍｓｋは公開されない。
【００５１】
≪ＫＧ’≫
鍵生成装置１１の鍵生成部１１２は、記憶部１１７に格納しておいたマスタ秘密鍵ｍｓｋと利用者識別子ｉｄを入力とし、０または１のｂ（ｉｄ）∈｛０，１｝を選択する。鍵生成部１１２は、例えばランダムにｂ（ｉｄ）を選択する（ステップＳ１０４）。なお、利用者識別子ｉｄは公開情報である。さらに鍵生成部１１２は、ＩＤ＝Ｍ（ｉｄ，ｂ（ｉｄ））とし、ｓｋ（ｉｄ，ｂ（ｉｄ））←ＫＧ（ｍｓｋ，Ｍ（ｉｄ，ｂ（ｉｄ）））によってｓｋ（ｉｄ，ｂ（ｉｄ））を生成する。ただし、Ｍ（α，β）はαとβに対応する値である。例えば、Ｍ（α，β）はαとβに対する関数値であり、衝突耐性のあるものである。Ｍ（α，β）の具体例は、αに対応するビット列とｂ（ｉｄ）とのビット連結値である（ステップＳ１０５）。通信部１１８は、ｓｋ（ｉｄ，ｂ（ｉｄ））およびｂ（ｉｄ）に対応する秘密鍵ｓｋ’（ｉｄ，ｂ（ｉｄ））＝（ｓｋ（ｉｄ，ｂ（ｉｄ）），ｂ（ｉｄ））を出力する。秘密鍵ｓｋ’（ｉｄ，ｂ（ｉｄ））はネットワーク経由で証明装置１２に送信され、証明装置１２の通信部１２８に入力されて、記憶部１２７に格納される（ステップＳ１０７）。
【００５２】
≪Ｐ’→Ｖ’≫
証明装置１２の演算部１２１には、記憶部１２７に格納しておいたマスタ公開鍵ｍｐｋと利用者識別子ｉｄと秘密鍵ｓｋ’（ｉｄ，ｂ（ｉｄ））が入力される。演算部１２１は、秘密鍵ｓｋ’（ｉｄ，ｂ（ｉｄ））をパースし、ｓｋ（ｉｄ，ｂ（ｉｄ））とｂ（ｉｄ）を得て記憶部１２７に格納する（ステップＳ１０７）。演算部１２１は、マスタ公開鍵ｍｐｋと利用者識別子ｉｄとｓｋ（ｉｄ，ｂ（ｉｄ））とｂ（ｉｄ）を用い、（ａｂ（ｉｄ），ｓｔ）←Σｉｂｉ−ｃｏｍ（ｍｐｋ，Ｍ（ｉｄ，ｂ（ｉｄ）），ｓｋ（ｉｄ，ｂ（ｉｄ）））によってａｂ（ｉｄ）とｓｔを得て、記憶部１２７に格納する（ステップＳ１０８）。演算部１２２は、ｂ（ｉｄ）を入力としてｒｂ（ｉｄ）＝１−ｂ（ｉｄ）∈｛０，１｝を得（ステップＳ１０９）、マスタ公開鍵ｍｐｋを入力としてｃｒｂ（ｉｄ）←Σ+ｉｂｉ−ｃｈ（ｍｐｋ）によってｃｒｂ（ｉｄ）を得る（ステップＳ１１０）。ｒｂ（ｉｄ）およびｃｒｂ（ｉｄ）は記憶部１２７に格納される。演算部１２３は、マスタ公開鍵ｍｐｋと利用者識別子ｉｄとｒｂ（ｉｄ）とｃｒｂ（ｉｄ）を入力とし、（ａｒｂ（ｉｄ），ｕｒｂ（ｉｄ））←Σｉｂｉ−ｓｉｍ（ｍｐｋ，Ｍ（ｉｄ，ｒｂ（ｉｄ）），ｃｒｂ（ｉｄ））によってａｒｂ（ｉｄ）とｕｒｂ（ｉｄ）を得て、記憶部１２７に格納する（ステップＳ１１１）。通信部１２８は、ａ０とａ１をコミットメント（ａ０，ａ１）として出力する。コミットメント（ａ０，ａ１）は、ネットワーク経由で検証装置１３に送信される。コミットメント（ａ０，ａ１）は検証装置１３の通信部１３８に入力され、記憶部１３７に格納される（ステップＳ１１２）。
【００５３】
≪Ｖ’→Ｐ’≫
検証装置１３の演算部１３１が、記憶部１３７に格納しておいたマスタ公開鍵ｍｐｋと利用者識別子ｉｄのうちマスタ公開鍵ｍｐｋを入力とし、ｃ←Σ+ｉｂｉ−ｃｈ（ｍｐｋ）によってチャレンジｃを得て、記憶部１３７に格納する（ステップＳ１１３）。通信部１３８はチャレンジｃを出力する。チャレンジｃは、ネットワーク経由で証明装置１２に送信される。チャレンジｃは証明装置１２の通信部１２８に入力され、記憶部１２７に格納される（ステップＳ１１４）。
【００５４】
≪Ｐ’→Ｖ’≫
証明装置１２の演算部１２４が、チャレンジｃを入力とし、ｃｂ（ｉｄ）＝ｃ−ｃｒｂ（ｉｄ）を得て、記憶部１２７に格納する（ステップＳ１１５）。さらに演算部１２５が、記憶部１２７に格納しておいた、マスタ公開鍵ｍｐｋと利用者識別子ｉｄとｂ（ｉｄ）とｓｋ（ｉｄ，ｂ（ｉｄ））とａｂ（ｉｄ）とｃｂ（ｉｄ）と内部状態情報ｓｔを入力とし、ｕｂ（ｉｄ）←Σｉｂｉ−ｒｅｓ（ｍｐｋ，Ｍ（ｉｄ，ｂ（ｉｄ）），ｓｋ（ｉｄ，ｂ（ｉｄ）），ａｂ（ｉｄ），ｃｂ（ｉｄ），ｓｔ）によってｕｂ（ｉｄ）を得て記憶部１２７に格納する（ステップＳ１１６）。通信部１２８は、ｃ０とｕ０とｕ１をレスポンス（ｃ０，ｕ０，ｕ１）として出力する。レスポンス（ｃ０，ｕ０，ｕ１）は、ネットワーク経由で検証装置１３に送信される。レスポンス（ｃ０，ｕ０，ｕ１）は検証装置１３の通信部１３８に入力され、記憶部１３７に格納される（ステップＳ１１７）。
【００５５】
≪Ｖ’≫
検証装置１３の演算部１３２は、記憶部１３７に格納しておいたｃおよびｃ０を入力とし、ｃ１＝ｃ−ｃ０を得て記憶部１３７に格納する（ステップＳ１１８）。判定部１３３は、マスタ公開鍵ｍｐｋと利用者識別子ｉｄとａ０とｃ０とｕ０とａ１とｃ１とｕ１を入力とし、ｄｅｃ←Σｉｂｉ−ｖｒｆｙ（ｍｐｋ，Ｍ（ｉｄ，０），ａ０，ｃ０，ｕ０）によって検証結果ｄｅｃを得、ｄｅｃ’←Σｉｂｉ−ｖｒｆｙ（ｍｐｋ，Ｍ（ｉｄ，１），ａ１，ｃ１，ｕ１）によって検証結果ｄｅｃ’を得る（ステップＳ１１９）。判定部１３３は、検証結果ｄｅｃおよびｄｅｃがともにａｃｃｅｐｔ（受理）となるかを判定する（ステップＳ１２０）。判定部１３３は、検証結果ｄｅｃおよびｄｅｃ’がともにａｃｃｅｐｔであった場合にａｃｃｅｐｔを出力し（ステップＳ１２１）、そうでない場合にｒｅｊｅｃｔを出力する（ステップＳ１２２）。
【００５６】
＜第２実施形態＞
第２実施形態を説明する。第２実施形態でも、Σ＋型、またはΣ＊型のＩＢＩプロトコルＩＢＩ＝（ＳｅｔＵｐ，ＫＧ，Ｐ，Ｖ）から、ｉｍｐ−ｃａ安全性を持つＩＢＩプロトコルを構成し、検証者が「証明者がｓｋ（ｉｄ，０）またはｓｋ（ｉｄ，１）のいずれかを持っていること」を証明する（Dual-Identity Transformation）。以下では、第１実施形態との相違点を中心に説明を行い、第１実施形態と共通する事項については同じ参照符号を用いて説明を省略する。
【００５７】
図１に例示するように、第２実施形態の認証システム２は、鍵発行局として機能する鍵生成装置２１と、証明者として機能する証明装置２２と、検証者として機能する検証装置１３を有する。鍵生成装置２１と証明装置２２と検証装置１３は、ネットワークを通じて通信可能に構成される。
【００５８】
鍵生成装置２１は、マスタ鍵生成部１１１と、鍵生成部２１２と、制御部１１６と、記憶部１１７と、通信部１１８を有する。証明装置２２は、演算部２２１，１２２〜１２５と、制御部１２６と、記憶部１２７と、通信部１２８（出力部および入力部）を有する。鍵生成装置２１、および証明装置２２のそれぞれは、例えば、通信機能を備えた公知または専用のコンピュータに特別なプログラムが読み込まれて構成される特別な装置である。
【００５９】
鍵生成装置２１および証明装置２２は、それぞれ、制御部１１６および制御部１２６の制御のもとで各処理を実行する。鍵生成装置２１および証明装置２２への入力情報は、それぞれ、記憶部１１７および記憶部１２７に格納される。鍵生成装置２１および証明装置２２で得られた情報も、それぞれ、記憶部１１７および記憶部１２７に格納される。
【００６０】
図３および図４を参照して、第２実施形態の認証処理を説明する。
≪ＳｅｔＵｐ’≫
第１実施形態と同じであり、鍵生成装置２１が前述のステップＳ１０１〜Ｓ１０３と同じ処理を実行する
【００６１】
≪ＫＧ’≫
鍵生成装置２１の鍵生成部２１２は、記憶部１１７に格納しておいたマスタ秘密鍵ｍｓｋと利用者識別子ｉｄを入力とし、ｂ（ｉｄ）＝０およびｂ（ｉｄ）＝１のそれぞれについて、ｓｋ（ｉｄ，ｂ（ｉｄ））←ＫＧ（ｍｓｋ，Ｍ（ｉｄ，ｂ（ｉｄ）））によってｓｋ（ｉｄ，０）およびｓｋ（ｉｄ，１）を生成する（ステップＳ２０５）。通信部１１８が、秘密鍵ｓｋ’ｉｄ＝（ｓｋ（ｉｄ，０），ｓｋ（ｉｄ，１））を出力する。秘密鍵ｓｋ’ｉｄはネットワーク経由で証明装置２２に送信され、証明装置２２の通信部１２８に入力されて、記憶部１２７に格納される（ステップＳ２０６）。
【００６２】
≪Ｐ’→Ｖ’≫
証明装置２２の演算部２２１には、記憶部１２７に格納しておいたマスタ公開鍵ｍｐｋと利用者識別子ｉｄと秘密鍵ｓｋ’ｉｄが入力される。演算部２２１は、秘密鍵ｓｋ’ｉｄをパースし、ｓｋ（ｉｄ，０）とｓｋ（ｉｄ，１）を得て記憶部１２７に格納する（ステップＳ２０７）。演算部２２１は、０または１のｂ（ｉｄ）∈｛０，１｝を選択する。演算部２２１は、例えばランダムにｂ（ｉｄ）を選択する（ステップＳ２０８）。演算部２２１は、マスタ公開鍵ｍｐｋと利用者識別子ｉｄと選択されたｂ（ｉｄ）∈｛０，１｝とそれに対応するｓｋ（ｉｄ，ｂ（ｉｄ））を入力とし、（ａｂ（ｉｄ），ｓｔ）←Σｉｂｉ−ｃｏｍ（ｍｐｋ，Ｍ（ｉｄ，ｂ（ｉｄ）），ｓｋ（ｉｄ，ｂ（ｉｄ）））によってａｂ（ｉｄ）とｓｔを得て、記憶部１２７に格納する（ステップＳ２０９）。その後、演算部２２１が、第１実施形態で説明したステップＳ１０９〜Ｓ１１２と同じ処理を実行する。ただし、ｂ（ｉｄ）はステップＳ２０８で選択されたｂ（ｉｄ）である。
【００６３】
≪Ｖ’→Ｐ’≫
第１実施形態と同じであり、検証装置１３が、証明装置１２に代えて証明装置２２に対し、前述のステップＳ１１１〜Ｓ１１３と同じ処理を実行する。
【００６４】
≪Ｐ’→Ｖ’≫
第１実施形態と同じであり、証明装置２２が前述のステップＳ１１５〜Ｓ１１７と同じ処理を実行する。ただし、ｂ（ｉｄ）はステップＳ２０８で選択されたｂ（ｉｄ）である。
【００６５】
≪Ｖ’≫
第１実施形態と同じであり、検証装置１３が前述のステップＳ１１８〜Ｓ１２２と同じ処理を実行する。
【００６６】
＜第３実施形態＞
第３実施形態を説明する。第３実施形態では、Σ＋型、またはΣ＊型のＩＢＩプロトコルＩＢＩ＝（ＳｅｔＵｐ，ＫＧ，Ｐ，Ｖ）から、ｉｍｐ−ｃａ安全性を持つＩＢＩプロトコルを構成し、検証者が「証明者がｓｋｉｄまたはｓｋｉｄmasterのいずれかを持っていること」を証明する（Master-Identity Transformation）。以下では、第１実施形態との相違点を中心に説明を行い、第１実施形態と共通する事項については同じ参照符号を用いて説明を省略する。
【００６７】
図１に例示するように、第３実施形態の認証システム２は、鍵発行局として機能する鍵生成装置３１と、証明者として機能する証明装置３２と、検証者として機能する検証装置３３を有する。鍵生成装置３１と証明装置３２と検証装置３３は、ネットワークを通じて通信可能に構成される。
【００６８】
鍵生成装置３１は、マスタ鍵生成部３１１と、鍵生成部３１２と、制御部１１６と、記憶部１１７と、通信部１１８を有する。証明装置３２は、演算部３２１〜３２５と、制御部１２６と、記憶部１２７と、通信部１２８（出力部および入力部）を有する。検証装置３３は、演算部３３１および３３２と、判定部１３３と、制御部１３６と、記憶部１３７と、通信部１３８（出力部および入力部）を有する。鍵生成装置３１、証明装置３２、および検証装置３３のそれぞれは、例えば、通信機能を備えた公知または専用のコンピュータに特別なプログラムが読み込まれて構成される特別な装置である。
【００６９】
鍵生成装置３１、証明装置３２、および検証装置３３は、それぞれ、制御部１１６、制御部１２６、および制御部１３６の制御のもとで各処理を実行する。鍵生成装置３１、証明装置３２、および検証装置３３への入力情報は、それぞれ、記憶部１１７、記憶部１２７、および記憶部１３７に格納される。鍵生成装置３１、証明装置３２、および検証装置３３への入力情報で得られた情報も、それぞれ、記憶部１１７、記憶部１２７、および記憶部１３７に格納される。
【００７０】
図５および図６を参照して、第３実施形態の認証処理を説明する。
≪ＳｅｔＵｐ’≫
鍵生成装置３１のマスタ鍵生成部３１１は、記憶部１１７に格納しておいたセキュリティパラメータ１κを入力とし、（ｍｐｋ，ｍｓｋ）←ＳｅｔＵｐ（１κ）を実行して、マスタ公開鍵とマスタ秘密鍵（ｍｐｋ，ｍｓｋ）を得て出力する。マスタ公開鍵ｍｐｋとマスタ秘密鍵ｍｓｋは記憶部１１７に格納される（ステップＳ１０１）。マスタ鍵生成部３１１はマスタ識別子ｉｄｍａｓｔｅｒを選択して記憶部１１７に格納する。マスタ識別子ｉｄｍａｓｔｅｒは、例えばランダムに選択される（ステップＳ３００）。マスタ鍵生成部３１１は公開鍵ｍｐｋ’＝（ｍｐｋ，ｉｄｍａｓｔｅｒ）とし、通信部１１８は公開鍵ｍｐｋ’を出力する（ステップＳ３０１）。公開鍵ｍｐｋ’は、ネットワーク経由で証明装置３２および検証装置３３に送信される。公開鍵ｍｐｋ’は、それぞれ、証明装置３２および検証装置３３の通信部１２８および１３８に入力され、記憶部１２７および１３７に格納される（ステップＳ３０２，Ｓ３０３）。マスタ秘密鍵ｍｓｋは公開されない。
【００７１】
≪ＫＧ’≫
鍵生成装置３１の鍵生成部３１２は、記憶部１１７に格納しておいた利用者識別子ｉｄとマスタ識別子ｉｄｍａｓｔｅｒとが等しいかを判定する（ステップＳ３０４）。ｉｄ＝ｉｄｍａｓｔｅｒであれば、鍵生成部３１２は、⊥（エラー）を出力して（ステップＳ３０５）、認証処理を終える。ｉｄ≠ｉｄｍａｓｔｅｒであれば、鍵生成部３１２は、記憶部１１７に格納しておいたマスタ秘密鍵ｍｓｋと利用者識別子ｉｄを入力とし、ｓｋｉｄ←ＫＧ（ｍｓｋ，ｉｄ）によって秘密鍵ｓｋｉｄを生成する。通信部１１８は、秘密鍵ｓｋｉｄを出力する。秘密鍵ｓｋｉｄはネットワーク経由で証明装置３２に送信され、証明装置３２の通信部１２８に入力されて、記憶部１２７に格納される（ステップＳ３０６）。
【００７２】
≪Ｐ’→Ｖ’≫
証明装置３２の演算部３２１には、記憶部１２７に格納しておいた公開鍵ｍｐｋ’と利用者識別子ｉｄと秘密鍵ｓｋｉｄが入力される。演算部３２１は、公開鍵ｍｐｋ’をパースし、マスタ公開鍵ｍｐｋとマスタ識別子ｉｄｍａｓｔｅｒを得て記憶部１２７に格納する（ステップＳ３０７）。演算部３２１は、マスタ公開鍵ｍｐｋと利用者識別子ｉｄと秘密鍵ｓｋｉｄを用い、（ａ０，ｓｔ）←Σｉｂｉ−ｃｏｍ（ｍｐｋ，ｉｄ，ｓｋｉｄ）によってａ０とｓｔを得て、記憶部１２７に格納する（ステップＳ３０８）。演算部３２２は、マスタ公開鍵ｍｐｋを入力としてｃ１←Σ+ｉｂｉ−ｃｈ（ｍｐｋ）によってｃ１を得て、記憶部１２７に格納する（ステップＳ３１０）。演算部３２３は、マスタ公開鍵ｍｐｋとマスタ識別子ｉｄｍａｓｔｅｒとｃ１を入力とし、（ａ１，ｕ１）←Σｉｂｉ−ｓｉｍ（ｍｐｋ，ｉｄｍａｓｔｅｒ，ｃ１）によってａ１とｕ１を得て、記憶部１２７に格納する（ステップＳ３１１）。通信部１２８は、ａ０とａ１をコミットメント（ａ０，ａ１）として出力する。コミットメント（ａ０，ａ１）は、ネットワーク経由で検証装置３３に送信される。コミットメント（ａ０，ａ１）は検証装置３３の通信部１３８に入力され、記憶部１３７に格納される（ステップＳ１１２）。
【００７３】
≪Ｖ’→Ｐ’≫
検証装置３３の演算部３３１には、記憶部１３７に格納しておいた公開鍵ｍｐｋ’と利用者識別子ｉｄとが入力される。演算部３３１は、公開鍵ｍｐｋ’をパースし、マスタ公開鍵ｍｐｋとマスタ識別子ｉｄｍａｓｔｅｒを得て記憶部１３７に格納する（ステップＳ３１３）。演算部３３１は、マスタ公開鍵ｍｐｋを入力とし、ｃ←Σ+ｉｂｉ−ｃｈ（ｍｐｋ）によってチャレンジｃを得て、記憶部１３７に格納する（ステップＳ１１３）。通信部１３８はチャレンジｃを出力する。チャレンジｃは、ネットワーク経由で証明装置３２に送信される。チャレンジｃは証明装置３２の通信部１２８に入力され、記憶部１２７に格納される（ステップＳ１１４）。
【００７４】
≪Ｐ’→Ｖ’≫
証明装置３２の演算部３２４が、チャレンジｃを入力とし、ｃ０＝ｃ−ｃ１を得て、記憶部１２７に格納する（ステップＳ３１５）。さらに演算部３２５が、記憶部１２７に格納しておいた、マスタ公開鍵ｍｐｋと利用者識別子ｉｄと秘密鍵ｓｋｉｄとａ０とｃ０とｓｔを入力とし、ｕ０←Σｉｂｉ−ｒｅｓ（ｍｐｋ，ｉｄ，ｓｋｉｄ，ａ０，ｃ０，ｓｔ）によってｕ０を得て記憶部１２７に格納する（ステップＳ３１６）。通信部１２８は、ｃ０とｕ０とｕ１をレスポンス（ｃ０，ｕ０，ｕ１）として出力する。レスポンス（ｃ０，ｕ０，ｕ１）は、ネットワーク経由で検証装置３３に送信される。レスポンス（ｃ０，ｕ０，ｕ１）は検証装置３３の通信部１３８に入力され、記憶部１３７に格納される（ステップＳ１１７）。
【００７５】
≪Ｖ’≫
第１実施形態と同じであり、検証装置１３に代えて検証装置３３が前述のステップＳ１１８〜Ｓ１２２と同じ処理を実行する。
【００７６】
＜第４実施形態＞
第４実施形態を説明する。第４実施形態では、Σ＊型のＩＢＩプロトコルＩＢＩ＝（ＳｅｔＵｐ，ＫＧ，Ｐ，Ｖ）から、ｉｍｐ−ｃａ安全性を持つＩＢＩプロトコルを構成し、検証者が「証明者がｓｋ（ｉｄ，０）またはｓｋ（ｉｄ，１）のいずれかを持っていること」を証明する（Double-Parameter Transformation）。以下では、第１実施形態との相違点を中心に説明を行い、第１実施形態と共通する事項については同じ参照符号を用いて説明を省略する。
【００７７】
図１に例示するように、第４実施形態の認証システム２は、鍵発行局として機能する鍵生成装置４１と、証明者として機能する証明装置４２と、検証者として機能する検証装置４３を有する。鍵生成装置４１と証明装置４２と検証装置４３は、ネットワークを通じて通信可能に構成される。
【００７８】
鍵生成装置４１は、マスタ鍵生成部４１１と、鍵生成部４１２と、制御部１１６と、記憶部１１７と、通信部１１８を有する。証明装置４２は、演算部１２４，４２１〜４２３，４２５と、制御部１２６と、記憶部１２７と、通信部１２８（出力部および入力部）を有する。検証装置４３は、演算部４３１および４３２と、判定部４３３と、制御部１３６と、記憶部１３７と、通信部１３８（出力部および入力部）を有する。鍵生成装置４１、証明装置４２、および検証装置４３のそれぞれは、例えば、通信機能を備えた公知または専用のコンピュータに特別なプログラムが読み込まれて構成される特別な装置である。
【００７９】
鍵生成装置４１、証明装置４２、および検証装置４３は、それぞれ、制御部１１６、制御部１２６、および制御部１３６の制御のもとで各処理を実行する。鍵生成装置４１、証明装置４２、および検証装置４３への入力情報は、それぞれ、記憶部１１７、記憶部１２７、および記憶部１３７に格納される。鍵生成装置４１、証明装置４２、および検証装置４３への入力情報で得られた情報も、それぞれ、記憶部１１７、記憶部１２７、および記憶部１３７に格納される。
【００８０】
図７および図８を参照して、第４実施形態の認証処理を説明する。
≪ＳｅｔＵｐ’≫
鍵生成装置４１のマスタ鍵生成部４１１は、記憶部１１７に格納しておいたセキュリティパラメータ１κを入力とし、（ｍｐｋ０，ｍｓｋ０）←ＳｅｔＵｐ（１κ）および（ｍｐｋ１，ｍｓｋ１）←ＳｅｔＵｐ（１κ）を実行して、（ｍｐｋ０，ｍｓｋ０）および（ｍｐｋ１，ｍｓｋ１）を得て出力する。（ｍｐｋ０，ｍｓｋ０）および（ｍｐｋ１，ｍｓｋ１）は記憶部１１７に格納される。ｍｓｋ０およびｍｓｋ１は例えばランダムに生成され、ｍｐｋ０およびｍｐｋ１はｍｓｋ０およびｍｓｋ１に対応するため、通常、（ｍｐｋ０，ｍｓｋ０）と（ｍｐｋ１，ｍｓｋ１）は一致しない（ステップＳ４００）。マスタ鍵生成部４１１は、マスタ公開鍵をｍｐｋ’＝（１κ，ｍｐｋ０，ｍｐｋ１）とし、マスタ秘密鍵をｍｓｋ’＝（ｍｓｋ０，ｍｓｋ１）とし、これらを記憶部１１７に格納する。マスタ公開鍵ｍｐｋ’は通信部１１８から出力され、ネットワーク経由で証明装置４２および検証装置４３に送信される（ステップＳ４０１）。マスタ公開鍵ｍｐｋ’は、それぞれ、証明装置４２および検証装置４３の通信部１２８および１３８に入力され、記憶部４２７および４３７に格納される（ステップＳ４０２，Ｓ４０３）。マスタ秘密鍵ｍｓｋ’は公開されない。
【００８１】
≪ＫＧ’≫
鍵生成装置４１の鍵生成部４１２は、記憶部１１７に格納しておいたマスタ秘密鍵をｍｓｋ’と利用者識別子ｉｄを入力とし、マスタ秘密鍵ｍｓｋ’をパースして、ｍｓｋ０とｍｓｋ１を得る。鍵生成部４１２は、０または１のｂ（ｉｄ）∈｛０，１｝を例えばランダムに選択し、ｓｋ（ｉｄ，ｂ（ｉｄ））←ＫＧ（ｍｓｋｂ（ｉｄ），ｉｄ）によってｓｋ（ｉｄ，ｂ（ｉｄ））を生成する（ステップＳ４０５）。通信部１１８は、ｓｋ（ｉｄ，ｂ（ｉｄ））およびｂ（ｉｄ）に対応する秘密鍵ｓｋ’（ｉｄ，ｂ（ｉｄ））＝（ｓｋ（ｉｄ，ｂ（ｉｄ）），ｂ（ｉｄ））を出力する。秘密鍵ｓｋ’（ｉｄ，ｂ（ｉｄ））はネットワーク経由で証明装置４２に送信され、証明装置４２の通信部１２８に入力されて、記憶部１２７に格納される（ステップＳ４０６）。
【００８２】
≪Ｐ’→Ｖ’≫
証明装置４２の演算部４２１には、記憶部１２７に格納しておいたマスタ公開鍵ｍｐｋ’と利用者識別子ｉｄと秘密鍵ｓｋ’（ｉｄ，ｂ（ｉｄ））が入力される。演算部４２１は、マスタ公開鍵ｍｐｋ’をパースして１κとｍｐｋ０とｍｐｋ１を得、秘密鍵ｓｋ’（ｉｄ，ｂ（ｉｄ））をパースしてｓｋ（ｉｄ，ｂ（ｉｄ））とｂ（ｉｄ）を得て、これらを記憶部１２７に格納する（ステップＳ４０７）。演算部４２１は、ｍｐｋｂ（ｉｄ）とｉｄとｓｋ（ｉｄ，ｂ（ｉｄ））とｂ（ｉｄ）を用い、（ａｂ（ｉｄ），ｓｔ）←Σｉｂｉ−ｃｏｍ（ｍｐｋｂ（ｉｄ），ｉｄ，ｓｋ（ｉｄ，ｂ（ｉｄ）））によってａｂ（ｉｄ）とｓｔを得て、記憶部１２７に格納する（ステップＳ４０８）。演算部４２２は、ｂ（ｉｄ）を入力としてｒｂ（ｉｄ）＝１−ｂ（ｉｄ）∈｛０，１｝を得（ステップＳ１０９）、セキュリティパラメータ１κを入力としてｃｒｂ（ｉｄ）←Σ*ｉｂｉ−ｃｈ（１κ）によってｃｒｂ（ｉｄ）を得る（ステップＳ４１０）。ｒｂ（ｉｄ）およびｃｒｂ（ｉｄ）は記憶部１２７に格納される。演算部１２３は、ｍｐｋｒｂ（ｉｄ）とｉｄとｒｂ（ｉｄ）とｃｒｂ（ｉｄ）を入力とし、（ａｒｂ（ｉｄ），ｕｒｂ（ｉｄ））←Σｉｂｉ−ｓｉｍ（ｍｐｋｒｂ（ｉｄ），ｉｄ，ｃｒｂ（ｉｄ））によってａｒｂ（ｉｄ）とｕｒｂ（ｉｄ）を得て、記憶部１２７に格納する（ステップＳ４１１）。通信部１２８は、ａ０とａ１をコミットメント（ａ０，ａ１）として出力する。コミットメント（ａ０，ａ１）は、ネットワーク経由で検証装置４３に送信される。コミットメント（ａ０，ａ１）は検証装置４３の通信部１３８に入力され、記憶部１３７に格納される（ステップＳ１１２）。
【００８３】
≪Ｖ’→Ｐ’≫
検証装置４３の演算部４３１が、記憶部１３７に格納しておいたマスタ公開鍵ｍｐｋ’と利用者識別子ｉｄのうちマスタ公開鍵ｍｐｋ’を入力とし、マスタ公開鍵ｍｐｋ’をパースして１κとｍｐｋ０とｍｐｋ１を得（ステップＳ４１２）、ｃ←Σ*ｉｂｉ−ｃｈ（１κ）によってチャレンジｃを得て、記憶部１３７に格納する（ステップＳ４１３）。通信部１３８はチャレンジｃを出力する。チャレンジｃは、ネットワーク経由で証明装置４２に送信される。チャレンジｃは証明装置４２の通信部１２８に入力され、記憶部１２７に格納される（ステップＳ１１４）。
【００８４】
≪Ｐ’→Ｖ’≫
証明装置４２の演算部１２４が、チャレンジｃを入力とし、ｃｂ（ｉｄ）＝ｃ−ｃｒｂ（ｉｄ）を得て、記憶部１２７に格納する（ステップＳ１１５）。さらに演算部４２５が、記憶部１２７に格納しておいた、ｍｐｋｂ（ｉｄ）とｉｄとｓｋ（ｉｄ，ｂ（ｉｄ））とａｂ（ｉｄ）とｃｂ（ｉｄ）と内部状態情報ｓｔを入力とし、ｕｂ（ｉｄ）←Σｉｂｉ−ｒｅｓ（ｍｐｋｂ（ｉｄ），ｉｄ，ｓｋ（ｉｄ，ｂ（ｉｄ）），ａｂ（ｉｄ），ｃｂ（ｉｄ），ｓｔ）によってｕｂ（ｉｄ）を得て記憶部１２７に格納する（ステップＳ４１６）。通信部１２８は、ｃ０とｕ０とｕ１をレスポンス（ｃ０，ｕ０，ｕ１）として出力する。レスポンス（ｃ０，ｕ０，ｕ１）は、ネットワーク経由で検証装置４３に送信される。レスポンス（ｃ０，ｕ０，ｕ１）は検証装置４３の通信部１３８に入力され、記憶部１３７に格納される（ステップＳ１１７）。
【００８５】
≪Ｖ’≫
検証装置４３の演算部４３２は、記憶部１３７に格納しておいたｃおよびｃ０を入力とし、ｃ１＝ｃ−ｃ０を得て記憶部１３７に格納する（ステップＳ１１８）。判定部４３３は、ｍｐｋ０とｍｐｋ１とｉｄとａ０とｃ０とｕ０とａ１とｃ１とｕ１を入力とし、ｄｅｃ←Σｉｂｉ−ｖｒｆｙ（ｍｐｋ０，ｉｄ，ａ０，ｃ０，ｕ０）によって得られる検証結果ｄｅｃと、ｄｅｃ’←Σｉｂｉ−ｖｒｆｙ（ｍｐｋ１，ｉｄ，ａ１，ｃ１，ｕ１）を得る（ステップＳ４１９）。その後、判定部４３３は、第１実施形態のステップＳ１２０〜Ｓ１２２と同じ処理を実行する。
【００８６】
＜特徴＞
各実施形態の構成は、Σ＋型、およびΣ＊型のあらゆるＩＢＩプロトコルに汎用的に適用可能であり、ＩＢＩプロトコルの安全性を容易に強化することができる。
例えば、前述した参考文献３のΣ＊型ＩＢＩプロトコルの場合、攻撃者がチャレンジＣ＝０を検証者Ｐに送付した場合、検証者はレスポンスとしてＵ＝ｘ・ｙＣ  ｍｏｄ  Ｎ＝ｘを出力するため、秘密鍵ＳＫＩＤ＝ｘが攻撃者に知られてしまう。この攻撃は、ｉｍｐ−ｐａ安全性では許されていない攻撃であるが、ｉｍｐ−ｃａ安全性では許されている攻撃である。このような攻撃は、上述した実施形態の方式によって防ぐことができる。実施形態の方式では、コミットメントを生成する時点で証明装置がｃｒｂ（ｉｄ）を決定し、レスポンスでは検証装置からのチャレンジｃを分割したｃ０，ｃ１（ｃｂ（ｉｄ）＝ｃ−ｃｒｂ（ｉｄ））に対応するものを出力する。そのため、攻撃者は恣意的なチャレンジに対応するレスポンスを得ることができない。上記攻撃を成功させるためには、攻撃者はｃｒｂ（ｉｄ）＝ｃなるｃを推測する必要がある。したがって、Ｇが十分大きければ、圧倒的な確率でこの攻撃を防ぐことができる。
【００８７】
また、第１，３および４実施形態の構成において証明者の秘密鍵のデータ量は、非特許文献２の方式に比べて約１／２となり、証明装置で必要な記憶領域を削減することができる。また、第２実施形態の構成における秘密鍵のデータ量は非特許文献２の方式と同じであるが、鍵発行局の保持するマスタ秘密鍵やマスタ公開鍵のデータ量は非特許文献２の方式の１／２以下となるため、鍵生成装置で必要な記憶領域を削減することができる。
【００８８】
＜変形例等＞
なお、本発明は上述の実施の形態に限定されるものではない。例えば、上述したアルゴリズムの少なくとも一部が関数として実装されてもよい。すなわち、「写像」とはアルゴリズムおよび関数を含む概念である。また「γ１と・・・とγＩからδを得る写像」とは、δがγ１と・・・とγＩのすべてに依存する場合のみ意味するものではない。すなわち、δがγ１と・・・とγＩの少なくとも一部に非依存であったとしても、γ１と・・・とγＩに対してδを得る写像であれば「γ１と・・・とγＩからδを得る写像」に含まれる。
【００８９】
また上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００９０】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【００９１】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００９２】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。
【００９３】
上記実施形態では、コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されたが、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【符号の説明】
【００９４】
１〜４  認証システム
１１，２１，３１，４１  鍵生成装置
１２，２２，３２，４２  証明装置
１３，３３，４３  検証装置
【図１】
0005783956.tif 000002
【図２】
0005783956.tif 000003
【図３】
0005783956.tif 000004
【図４】
0005783956.tif 000005
【図５】
0005783956.tif 000006
【図６】
0005783956.tif 000007
【図７】
0005783956.tif 000008
【図８】
0005783956.tif 000009