(57)【特許請求の範囲】
【請求項１】
第１公開鍵を公開する認証装置と第２公開鍵を公開する協調装置を有し、被認証装置の本人性を証明する本人性証明システムであって、
前記認証装置は、
前記第１公開鍵ｙ１と、前記第１公開鍵ｙ１と対をなす第１秘密鍵ｘ１を生成する第１鍵生成部と、
前記被認証装置が前記第１公開鍵ｙ１と前記第２公開鍵ｙ２を用いて秘密情報Ｗを暗号化した第１暗号文Ｃの秘密情報Ｗと、前記被認証装置が第１公開鍵ｙ１と前記第２公開鍵ｙ２を用いて秘密情報Ｗ’と付随情報Ａを基に生成された第２暗号文Ｃ’の秘密情報Ｗ’とが、等しいこともしくは所定の距離以内であることを、前記協調装置と協調して秘密情報Ｗと秘密情報Ｗ’を知ることなく確認する第１暗号文確認部と、
前記第１暗号文Ｃ、前記第２暗号文Ｃ’、前記付随情報Ａ、および前記第１暗号文確認部と前記協調装置との処理で生成されたデータＤを、当該被認証装置を特定する情報Ｉと対応つけて記録する認証記録部と、
を備え、
前記協調装置は、
前記第２公開鍵ｙ２と、前記第２公開鍵ｙ２と対をなす第２秘密鍵ｘ２を生成する第２鍵生成部と、
前記被認証装置が前記第１公開鍵ｙ１と前記第２公開鍵ｙ２を用いて秘密情報Ｗを暗号化した第１暗号文Ｃの秘密情報Ｗと、前記被認証装置が第１公開鍵と前記第２公開鍵を用いて秘密情報Ｗ’と付随情報Ａを基に生成された第２暗号文Ｃ’の秘密情報Ｗ’とが、等しいこともしくは所定の距離以内であることを、前記認証装置と協調して秘密情報Ｗと秘密情報Ｗ’を知ることなく確認する第２暗号文確認部と
を備える
本人性証明システム。
【請求項２】
請求項１記載の本人性証明システムであって、
ｐとｑはｑ｜ｐ−１を満たす素数、ｑはｋビット、ｇはｇｑ＝１ｍｏｄｐを満たす２以上ｐ未満の整数、ｙ＝ｙ１ｙ２ｍｏｄｐ、乱数ｒは１以上ｑ未満の整数、Ａ、Ｗ、Ｗ’は０以上ｑ未満の整数であり、
前記第１暗号文Ｃは、
Ｃ＝（Ｇ，Ｙ）＝（ｇｒｍｏｄｐ，ｙｒ＋Ｗｍｏｄｐ）
のように求められたものであり、
前記第２暗号文Ｃ’は、
Ｃ’＝（Ｇ’，Ｙ’）＝（ｇｒｍｏｄｐ，ｙｒ＋（Ｗ’（+）Ａ）ｍｏｄｐ）
ただし、（＋）は２つの数値を２進数表現で表して対応するビットごとに排他的論理和を求める演算を示す記号
のように求められたものであり、
前記第１暗号文確認部と前記第２暗号文確認部は、第１暗号文Ｃと付随情報Ａを用いて、秘密情報Ｗを知ることなくＷ（＋）Ａの暗号文である第３暗号文Ｃ”＝（Ｇ”，Ｙ”）を協調して求め、第２暗号文Ｃ’と第３暗号文Ｃ”とを用いて、秘密情報Ｗと秘密情報Ｗ’を知ることなくＷ＝Ｗ’であることを協調して確認し、その結果を認証結果Ｆとし、
前記認証記録部は、前記第３暗号文Ｃ”と前記認証結果Ｆも記録する
ことを特徴とする本人性証明システム。
【請求項３】
請求項２記載の本人性証明システムであって、
乱数ｔ、乱数ｕは１以上ｑ未満の整数であり、
前記のＷ＝Ｗ’であることを協調して確認する処理は、
前記第１暗号文確認部が、
ｃ１＝（Ｇ１，Ｙ１）＝（（Ｇ”／Ｇ’）ｔｍｏｄｐ，（Ｙ”／Ｙ’）ｔｍｏｄｐ）
を求めて前記協調装置に送信し、
前記第２暗号文確認部が、
ｃ２＝（Ｇ２，Ｙ２）＝（Ｇ１ｕｍｏｄｐ，Ｙ１ｕｍｏｄｐ）
ｄ２＝Ｇ２＾ｘ２
ただし、＾は累乗を示す記号
を求めて前記認証装置に送信し、
前記第１暗号文確認部が、
ｄ１＝Ｇ２＾ｘ１
を求め、
Ｙ２／（ｄ１ｄ２）＝１
が成り立てば秘密情報Ｗと秘密情報Ｗ’とが等しいと判断し、成り立たなければ等しくないと判断する
ことを特徴とする本人性証明システム。
【請求項４】
請求項１記載の本人性証明システムであって、
ｐとｑはｑ｜ｐ−１を満たす素数、ｑはｋビット、ｇはｇｑ＝１ｍｏｄｐを満たす２以上ｐ未満の整数、ｙ＝ｙ１ｙ２ｍｏｄｐ、乱数ｒは１以上ｑ未満の整数、Ａ、Ｗ、Ｗ’は０以上ｑ未満の整数であり、
前記第１暗号文Ｃは、
Ｃ＝（Ｇ，Ｙ）＝（ｇｒｍｏｄｐ，ｙｒ＋Ｗｍｏｄｐ）
のように求められたものであり、
前記第２暗号文Ｃ’は、
Ｃ’＝（Ｇ’，Ｙ’）＝（ｇｒｍｏｄｐ，ｙｒ＋（Ｗ’（+）Ａ）ｍｏｄｐ）
ただし、（＋）は２つの数値を２進数表現で表して対応するビットごとに排他的論理和を求める演算
のように求められたものであり、
前記第１暗号文確認部と前記第２暗号文確認部は、第２暗号文Ｃ’と付随情報Ａを用いて、秘密情報Ｗ’を知ることなくＷ’の暗号文である第３暗号文Ｃ”＝（Ｇ”，Ｙ”）を協調して求め、第１暗号文Ｃと第３暗号文Ｃ”とを用いて、秘密情報Ｗと秘密情報Ｗ’を知ることなくＷ＝Ｗ’であることを協調して確認し、その結果を認証結果Ｆとし、
前記認証記録部は、前記第３暗号文Ｃ”と前記認証結果Ｆも記録する
ことを特徴とする本人性証明システム。
【請求項５】
請求項２から４のいずれかに記載の本人性証明システムであって、
前記認証装置は、
前記付随情報が所定の情報であるかを確認する付随情報確認部も備えており、
前記付随情報が所定の情報でない場合は、処理を終了する
ことを特徴とする本人性証明システム。
【請求項６】
請求項２、４、５のいずれかに記載の本人性証明システムであって、
前記秘密情報Ｗと前記秘密情報Ｗ’は生体情報であり、
Ｗ＝Ｗ’であることを協調して確認する代わりに、ＷとＷ’とが所定の距離以内であることを協調して確認する
ことを特徴とする本人性証明システム。
【請求項７】
請求項２から６のいずれかに記載の本人性証明システムの処理が正しく実行されたかを検証する検証装置であって、
被認証装置を特定する情報Ｉ、付随情報Ａ，第１暗号文Ｃ、第２暗号文Ｃ’、第３暗号文Ｃ”、認証結果Ｆ、データＤを受信する検証受信部と、
被認証装置を特定する情報Ｉ、付随情報Ａ，第１暗号文Ｃ、第２暗号文Ｃ’、第３暗号文Ｃ”、認証結果Ｆ、データＤを用いて、認証が正しく実行されたかを検証する実行検証部と、
を備える検証装置。
【請求項８】
第１公開鍵を公開する認証装置と第２公開鍵を公開する協調装置を用いて、被認証装置の本人性を証明する本人性証明方法であって、
前記認証装置が、前記第１公開鍵ｙ１と、前記第１公開鍵ｙ１と対をなす第１秘密鍵ｘ１を生成する第１鍵生成ステップと、
前記協調装置が、前記第２公開鍵ｙ２と、前記第２公開鍵ｙ２と対をなす第２秘密鍵ｘ２を生成する第２鍵生成ステップと、
前記認証装置と前記協調装置が、前記被認証装置が前記第１公開鍵ｙ１と前記第２公開鍵ｙ２を用いて秘密情報Ｗを暗号化した第１暗号文Ｃの秘密情報Ｗと、前記被認証装置が第１公開鍵ｙ１と前記第２公開鍵ｙ２を用いて秘密情報Ｗ’と付随情報Ａを基に生成された第２暗号文Ｃ’の秘密情報Ｗ’とが、等しいこともしくは所定の距離以内であることを、協調して秘密情報Ｗと秘密情報Ｗ’を知ることなく確認する暗号文確認ステップと、
前記認証装置が、前記第１暗号文Ｃ、前記第２暗号文Ｃ’、前記付随情報Ａ、および前記第１暗号文確認部と前記協調装置との処理で生成されたデータＤを、当該被認証装置を特定する情報Ｉと対応つけて記録する認証記録ステップと
を有する本人性証明方法。
【請求項９】
請求項８記載の本人性証明方法であって、
ｐとｑはｑ｜ｐ−１を満たす素数、ｑはｋビット、ｇはｇｑ＝１ｍｏｄｐを満たす２以上ｐ未満の整数、ｙ＝ｙ１ｙ２ｍｏｄｐ、乱数ｒは１以上ｑ未満の整数、Ａ、Ｗ、Ｗ’は０以上ｑ未満の整数であり、
前記第１暗号文Ｃは、
Ｃ＝（Ｇ，Ｙ）＝（ｇｒｍｏｄｐ，ｙｒ＋Ｗｍｏｄｐ）
のように求められたものであり、
前記第２暗号文Ｃ’は、
Ｃ’＝（Ｇ’，Ｙ’）＝（ｇｒｍｏｄｐ，ｙｒ＋（Ｗ’（+）Ａ）ｍｏｄｐ）
ただし、（＋）は２つの数値を２進数表現で表して対応するビットごとに排他的論理和を求める演算を示す記号
のように求められたものであり、
前記暗号文確認ステップは、第１暗号文Ｃと付随情報Ａを用いて、秘密情報Ｗを知ることなくＷ（＋）Ａの暗号文である第３暗号文Ｃ”＝（Ｇ”，Ｙ”）を協調して求め、第２暗号文Ｃ’と第３暗号文Ｃ”とを用いて、秘密情報Ｗと秘密情報Ｗ’を知ることなくＷ＝Ｗ’であることを協調して確認し、その結果を認証結果Ｆとし、
前記認証記録ステップは、前記第３暗号文Ｃ”と前記認証結果Ｆも記録する
ことを特徴とする本人性証明方法。
【請求項１０】
請求項９記載の本人性証明方法であって、
乱数ｔ、乱数ｕは１以上ｑ未満の整数であり、
前記のＷ＝Ｗ’であることを協調して確認する処理は、
前記認証装置が、
ｃ１＝（Ｇ１，Ｙ１）＝（（Ｇ”／Ｇ’）ｔｍｏｄｐ，（Ｙ”／Ｙ’）ｔｍｏｄｐ）
を求めて前記協調装置に送信し、
前記協調装置が、
ｃ２＝（Ｇ２，Ｙ２）＝（Ｇ１ｕｍｏｄｐ，Ｙ１ｕｍｏｄｐ）
ｄ２＝Ｇ２＾ｘ２
ただし、＾は累乗を示す記号
を求めて前記認証装置に送信し、
前記認証装置が、
ｄ１＝Ｇ２＾ｘ１
を求め、
Ｙ２／（ｄ１ｄ２）＝１
が成り立てば秘密情報Ｗと秘密情報Ｗ’とが等しいと判断し、成り立たなければ等しくないと判断する
ことを特徴とする本人性証明方法。
【請求項１１】
請求項８記載の本人性証明システムであって、
ｐとｑはｑ｜ｐ−１を満たす素数、ｑはｋビット、ｇはｇｑ＝１ｍｏｄｐを満たす２以上ｐ未満の整数、ｙ＝ｙ１ｙ２ｍｏｄｐ、乱数ｒは１以上ｑ未満の整数、Ａ、Ｗ、Ｗ’は０以上ｑ未満の整数であり、
前記第１暗号文Ｃは、
Ｃ＝（Ｇ，Ｙ）＝（ｇｒｍｏｄｐ，ｙｒ＋Ｗｍｏｄｐ）
のように求められたものであり、
前記第２暗号文Ｃ’は、
Ｃ’＝（Ｇ’，Ｙ’）＝（ｇｒｍｏｄｐ，ｙｒ＋（Ｗ’（+）Ａ）ｍｏｄｐ）
ただし、（＋）は２つの数値を２進数表現で表して対応するビットごとに排他的論理和を求める演算
のように求められたものであり、
前記暗号文確認ステップは、第２暗号文Ｃ’と付随情報Ａを用いて、秘密情報Ｗ’を知ることなくＷ’の暗号文である第３暗号文Ｃ”＝（Ｇ”，Ｙ”）を協調して求め、第１暗号文Ｃと第３暗号文Ｃ”とを用いて、秘密情報Ｗと秘密情報Ｗ’を知ることなくＷ＝Ｗ’であることを協調して確認し、その結果を認証結果Ｆとし、
前記認証記録ステップは、前記第３暗号文Ｃ”と前記認証結果Ｆも記録する
ことを特徴とする本人性証明方法。
【請求項１２】
請求項９から１１のいずれかに記載の本人性証明方法であって、
前記認証装置は、
前記付随情報が所定の情報であるかを確認する付随情報確認部も備えており、
前記付随情報が所定の情報でない場合は、処理を終了する
ことを特徴とする本人性証明方法。
【請求項１３】
請求項９、１１、１２のいずれかに記載の本人性証明方法であって、
前記秘密情報Ｗと前記秘密情報Ｗ’は生体情報であり、
Ｗ＝Ｗ’であることを協調して確認する代わりに、ＷとＷ’とが所定の距離以内であることを協調して確認する
ことを特徴とする本人性証明方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は情報セキュリティ技術に関し、パスワード認証や生体認証等、所有物を用いない認証において本人性を第三者に証明する本人性証明システム、検証装置、本人性証明方法に関する。
【背景技術】
【０００２】
認証において本人性を第三者に証明する有効な技術として電子署名がある。「本人性」とは被認証者を偽ることができない性質を指し、「第三者に証明する」とは、ある認証行為の被認証者を第三者に認めさせることである。このような本人性の第三者への証明力は、ログデータの真正性を保証する場合等に有用であるといえる。
【０００３】
電子署名を用いた認証は、ＩＣカード等、秘密情報を格納する所有物を必要とする場合がある。一方、所有物を用いない認証手段として、記憶に基づくＩＤ・パスワード認証（ＰＩＮを含む）や、生体情報に基づく生体認証等が挙げられる。特にＩＤ・パスワード認証は最も普及している認証方法といえる。また、最近ではセキュリティ向上のため、ＩＤ・パスワード認証とＩＣカードを用いた認証の組合せ等、性質の異なる認証を併用した多要素認証の実用化も進んでいる。関連する技術として、生体情報を明かさずに生体認証を行う方法が知られており、例えば非特許文献１の５２４ページの７行目から１６行目に示されている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Berry Schoenmakers and Pim Tuyls, "Efficient Binary Conversion for Paillier Encrypted Values," S. Vaudenay(Ed.): EUROCRYPT 2006, LNCS 4004, pp. 522-537, 2006.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、一般に所有物を用いない認証では、認証に用いる秘密情報（パスワードや生体情報）を認証者が予め知っている必要があるため、認証者によるなりすましや当該秘密情報の漏洩等により、本人性の第三者への証明力は電子署名に比べ劣るといえる。また、非特許文献１の方法は、本人性の第三者への証明力は考慮されておらず、その方法は自明でないと考えられる。
【０００６】
このような状況において、本発明が解決しようとする課題は、所有物を用いない認証において本人性の第三者への証明力を高めることである。
【課題を解決するための手段】
【０００７】
本発明の本人性証明システムは、第１公開鍵を公開する認証装置と第２公開鍵を公開する協調装置を有し、被認証装置の本人性を証明する。認証装置は、第１鍵生成部、第１暗号文確認部、認証記録部を備える。協調装置は、第２鍵生成部と第２暗号文確認部を備える。
【０００８】
第１鍵生成部は、第１公開鍵ｙ１と、第１公開鍵ｙ１と対をなす第１秘密鍵ｘ１を生成する。第１暗号文確認部は、被認証装置が第１公開鍵ｙ１と第２公開鍵ｙ２を用いて秘密情報Ｗを暗号化した第１暗号文Ｃの秘密情報Ｗと、被認証装置が第１公開鍵ｙ１と第２公開鍵ｙ２を用いて秘密情報Ｗ’と付随情報Ａを基に生成された第２暗号文Ｃ’の秘密情報Ｗ’とが、等しいこともしくは所定の距離以内であることを、第２暗号文確認部と協調して秘密情報Ｗと秘密情報Ｗ’を知ることなく確認する。認証記録部は、第１暗号文Ｃ、第２暗号文Ｃ’、付随情報Ａ、および第１暗号文確認部と協調装置との処理で生成されたデータＤを、当該被認証装置を特定する情報Ｉと対応つけて記録する。
【０００９】
第２鍵生成部は、第２公開鍵ｙ２と、第２公開鍵ｙ２と対をなす第２秘密鍵ｘ２を生成する。第２暗号文確認部は、被認証装置が第１公開鍵ｙ１と第２公開鍵ｙ２を用いて秘密情報Ｗを暗号化した第１暗号文Ｃの秘密情報Ｗと、被認証装置が第１公開鍵と第２公開鍵を用いて秘密情報Ｗ’と付随情報Ａを基に生成された第２暗号文Ｃ’の秘密情報Ｗ’とが、等しいこともしくは所定の距離以内であることを、第１暗号文確認部と協調して秘密情報Ｗと秘密情報Ｗ’を知ることなく確認する。
【発明の効果】
【００１０】
本発明の本人性証明システムによれば、認証装置と協調装置とが協調することで、秘密情報Ｗと秘密情報Ｗ’を知ることなく、登録しておいた暗号文（第１暗号文）の秘密情報Ｗと、認証処理で生成された暗号文（第２暗号文）の秘密情報Ｗ’とが等しいこと、もしくは所定の距離以内であることを確認できる。したがって、所有物を用いない認証において本人性の第三者への証明力を高めることができる。
【図面の簡単な説明】
【００１１】
【図１】本発明の本人性証明システムとその周辺装置等の構成を示す図。
【図２】本発明の本人性証明システムとその周辺装置等の処理フローを示す図。
【図３】実施例２と実施例２変形例と実施例３の事前処理と登録処理の処理フローを示す図。
【図４】実施例２と実施例３の認証処理の処理フローを示す図。
【図５】実施例２と実施例２変形例と実施例３の検証処理の処理フローを示す図。
【図６】実施例２変形例の認証処理の処理フローを示す図。
【発明を実施するための形態】
【００１２】
以下、本発明の実施の形態について、詳細に説明する。
【実施例１】
【００１３】
図１に本発明の本人性証明システムとその周辺装置等の構成を示す。また、図２に本発明の本人性証明システムとその周辺装置等の処理フローを示す。本発明の本人性証明システムは、第１公開鍵を公開する認証装置と第２公開鍵を公開する協調装置を有し、被認証装置の本人性を証明する。また、検証装置は、本人性証明システムの処理が正しく実行されたかを検証する。被認証装置１００、認証装置２００、協調装置３００、検証装置４００は、ネットワーク９００を介して接続されている。被認証装置１００は、被認証受信部１１０、第１暗号化部１２０、第２暗号化部１３０、被認証記録部１９０を備える。認証装置２００は、第１鍵生成部２０１、第１暗号文確認部２３０、認証記録部２９０を備える。協調装置３００は、第２鍵生成部３０１、第２暗号文確認部３３０、協調記録部３９０を備える。検証装置４００は、検証受信部４１０、実行検証部４２０、検証記録部４９０を備える。
【００１４】
あらかじめ、第１鍵生成部２０１は、第１公開鍵ｙ１と、第１公開鍵ｙ１と対をなす第１秘密鍵ｘ１を生成し、第２鍵生成部３０１は、第２公開鍵ｙ２と、第２公開鍵ｙ２と対をなす第２秘密鍵ｘ２を生成する。被認証受信部１１０や検証受信部４１０は、第１公開鍵ｙ１と第２公開鍵ｙ２を取得しておく。被認証記録部１９０、認証記録部２９０、協調記録部３９０、検証記録部４９０は、あらかじめ暗号化に使用する公開鍵やパラメータなどを記録しておく。公開鍵は、第１公開鍵ｙ１と第２公開鍵ｙ２自体でもよいし、これらを用いて生成された公開鍵でもよい。例えば、公開鍵をｙ＝ｙ１ｙ２としてもよい。
【００１５】
［登録処理（Ｓ１０）］
第１暗号化部１２０は、第１公開鍵ｙ１と第２公開鍵ｙ２を用いて秘密情報Ｗを暗号化した第１暗号文Ｃを求める。なお、「第１公開鍵ｙ１と第２公開鍵ｙ２を用いて」とは、「第１公開鍵ｙ１と第２公開鍵ｙ２を用いて生成した公開鍵ｙを用いて」を含む意味である。また、秘密情報Ｗは、パスワードでもよいし、生体情報でもよい。そして、被認証装置１００は暗号文Ｃを認証装置２００に送信する（Ｓ１２０）。このときに、被認証装置１００を特定する情報Ｉを一緒に送信してもよい。認証装置２００の認証記録部２９０は、暗号文Ｃと被認証装置を特定する情報Ｉとを対応つけて記録する（Ｓ２１０）。
【００１６】
［認証処理（Ｓ２０）］
第２暗号化部１３０は、第１公開鍵ｙ１と第２公開鍵ｙ２を用いて秘密情報Ｗ’と付随情報Ａを基に生成された第２暗号文Ｃ’を求め、付随情報Ａと第２暗号文Ｃ’を認証装置２００に送信する（Ｓ１３０）。「付随情報Ａ」とは、認証時刻や認証目的等を示す任意の情報である。このときに、被認証装置１００を特定する情報Ｉを一緒に送信してもよい。
【００１７】
第１暗号文確認部２３０と第２暗号文確認部３３０は、第１暗号文Ｃの秘密情報Ｗと第２暗号文Ｃ’の秘密情報Ｗ’とが等しいこともしくは所定の距離以内であることを、協調して秘密情報Ｗと秘密情報Ｗ’を知ることなく確認する（Ｓ２２０）。なお、秘密情報Ｗと秘密情報Ｗ’を知ることなく処理する暗号技術はいくつか知られており、後述する。秘密情報Ｗがパスワードのように等しくなければならない情報の場合には、等しい場合を認証成功とし（Ｓ２３０）、等しくない場合には認証失敗とする（Ｓ２４０）。また、秘密情報Ｗが生体情報のようにノイズなどにより必ずしも等しくならない情報の場合には、所定の距離以内のときを認証成功とし（Ｓ２３０）、所定の距離より遠いときを認証失敗とする（Ｓ２４０）。認証記録部２９０は、第１暗号文Ｃ、第２暗号文Ｃ’、付随情報Ａ、認証結果Ｆ、およびステップＳ２２０の第１暗号文確認部２３０と第２暗号文確認部３３０との協調処理で生成されたデータＤを、被認証装置１００を特定する情報Ｉと対応つけて記録する（Ｓ２５０）。
【００１８】
［ステップＳ２２０のための暗号化技術］
ここで、ステップＳ２２０で用いる暗号化技術の例として、ElGamal暗号を用いた方法について説明する。ElGamal暗号は、Ｇを位数qの巡回群、ｇを群Ｇの生成元、秘密鍵を０以上ｑ未満のランダムな整数ｘ、公開鍵ｙをｙ＝ｇｘとする（Ｇを乗法的に記述する）。ただし、ｑは十分大きく（例えば１６０ビット）、素数であることが望ましい。そして平文ｍを群Ｇの元とし、ｍの暗号文をＥ（ｍ）＝（ｇｒ，ｍｙｒ）とする。ただし、ｒは０以上ｑ未満のランダムな整数である。Ｅ（ｍ）の復号は、秘密鍵ｘを用いて行う。すなわち、
ｍ＝（ｍｙｒ）／（ｇｒ）ｘ
の関係式から得られる。
【００１９】
以上の準備の下、秘密情報Ｗと秘密情報Ｗ’を知ることなく処理する方法例について説明する。認証装置２００によって生成される第１秘密鍵ｘ１を０以上ｑ未満のランダムな整数とし、第１公開鍵ｙ１をｙ１＝ｇ＾ｘ１とする。同様に、協調装置３００によって生成される第２秘密鍵ｘ２を０以上ｑ未満のランダムな整数とし、第２公開鍵ｙ２をｙ２＝ｇ＾ｘ２とする。なお、＾は累乗を示す記号とする。そして
ｙ＝ｙ１ｙ２＝ｇ＾（ｘ１＋ｘ２），
ｘ＝ｘ１＋ｘ２
とする。そして、第１暗号文Ｃと第２暗号文Ｃ’は、例えば
Ｃ＝Ｅ（Ｗ）＝（ｇ＾ｒ１，Ｗｙ＾ｒ１），
Ｃ’＝Ｅ（Ａ，Ｅ（Ｗ’））
ただし、Ｅ（Ｗ’）＝（ｇ＾ｒ２，Ｗ’ｙ＾ｒ２）
のように求められた暗号文とする。
【００２０】
ステップＳ２２０では、認証装置２００および協調装置３００は、まず、協調してＣ’を復号し、Ｅ（Ｗ’）とＡを求める。そして、認証装置２００および協調装置３００は、それぞれ、
（Ｃ／Ｅ（Ｗ’））＾ｓ１＝（Ｅ（Ｗ）／Ｅ（Ｗ‘））＾ｓ１
＝（（ｇ＾ｒ１／ｇ＾ｒ２）＾ｓ１，（（Ｗｙ＾ｒ１）／（Ｗ’ｙ＾ｒ２））＾ｓ１）
＝（ｇ＾（（ｒ１−ｒ２）ｓ１），（（Ｗ／Ｗ’）＾ｓ１）ｙ＾（（ｒ１−ｒ２）ｓ１）),
（Ｃ／Ｅ（Ｗ’））ｓ２＝（Ｅ（Ｗ）／Ｅ（Ｗ‘））＾ｓ２
＝（（ｇ＾ｒ１／ｇ＾ｒ２）＾ｓ２，（（Ｗｙ＾ｒ１）／（Ｗ’ｙ＾ｒ２））＾ｓ２）
＝（ｇ＾（（ｒ１−ｒ２）ｓ２），（（Ｗ／Ｗ’）＾ｓ２）ｙ＾（（ｒ１−ｒ２）ｓ２）),
を計算して互いに送信する。ここで、ｓ１，ｓ２，ｒ１，ｒ２は０以上ｑ未満のランダムな整数とする。次に認証装置２００および協調装置３００は
ｅ＝（（Ｅ（Ｗ）／Ｅ（Ｗ’））＾ｓ１）／（（Ｅ（Ｗ）／Ｅ（Ｗ’））＾ｓ２）
＝（ｇ＾（（ｒ１−ｒ２）（ｓ１−ｓ２）），
（（Ｗ／Ｗ’）＾（ｓ１−ｓ２））ｙ＾（（ｒ１−ｒ２）（ｓ１−ｓ２））)
を計算し、ｅを復号する。復号の手順は、認証装置２００および協調装置３００は、それぞれ、
ｅ１＝（ｇ＾（（ｒ１−ｒ２）（ｓ１−ｓ２））＾ｘ１，
ｅ２＝（ｇ＾（（ｒ１−ｒ２）（ｓ１−ｓ２））＾ｘ２
を計算して互いに送信し、最終的に認証装置２００および協調装置３００はｅの復号結果（Ｗ／Ｗ’）＾（ｓ１−ｓ２）を、
（Ｗ／Ｗ’）＾（ｓ１−ｓ２）
＝（（Ｗ／Ｗ’）＾（ｓ１−ｓ２））ｙ＾（（ｒ１−ｒ２）（ｓ１−ｓ２））／（ｅ１ｅ２）
のように求めればよい。
【００２１】
ｅ１ｅ２＝（（ｇ＾（（ｒ１−ｒ２）（ｓ１−ｓ２））＾ｘ１）（（ｇ＾（（ｒ１−ｒ２）（ｓ１−ｓ２））＾ｘ２）
＝（ｇ＾（（ｒ１−ｒ２）（ｓ１−ｓ２））＾（ｘ１＋ｘ２）
＝（ｇ＾（（ｒ１−ｒ２）（ｓ１−ｓ２））＾ｘ
＝ｙ＾（（ｒ１−ｒ２）（ｓ１−ｓ２）
であるから、ｅは正しく復号できることが分かる。そして復号結果（Ｗ／Ｗ’）＾（ｓ１−ｓ２）は、Ｗ＝Ｗ’であれば１になる。そして、Ｗ≠Ｗ’であればｓ１，ｓ２が０以上ｑ未満のランダムな整数であるから、復号結果もランダムとなり、ｑが大きいほど復号結果が１となる確率は小さくなる。したがって、復号結果が１であればＷ＝Ｗ’と判定し、そうでなければＷ≠Ｗ’と判定する。
【００２２】
他の方法として、Ｗ，Ｗ’をビット毎に暗号化し、Ｗ，Ｗ’の復元を困難としつつ，等号判定、距離計算、大小比較やそれらの組合せを計算する手法も知られている。ここで「距離」とは秘密情報Ｗと秘密情報Ｗ’の違いを数値化したものであり、どのように数値化するかは適宜設計すればよい。例えば、ｎを２以上の整数とし、Ｗ，Ｗ’をｎ次ベクトルＷ＝（ｗ１,…,ｗｎ），Ｗ’＝（ｗ１’,…,ｗｎ’）とし，Ｗ，Ｗ’の距離を
｜ｗ１−ｗ１’｜＋｜ｗ２−ｗ２’｜＋…＋｜ｗｎ−ｗｎ’｜
と定義すればよい。ただし、｜ｘ｜は、ｘの絶対値を表す。以下では参考文献１（Go Yamamoto, Koji Chida, Anderson C. A. Nascimento, Koutarou Suzuki, Shigenori Uchiyama: Efficient, Non-optimistic Secure Circuit Evaluation Based on the ElGamal Encryption. WISA 2005: 328-342.）に示された方法を用いる例について説明する。
【００２３】
この方法は、ElGamal暗号を若干変形した暗号を用いる。Ｇを位数ｑの巡回群、gを群Ｇの生成元、秘密鍵ｘを０以上ｑ未満のランダムな整数、公開鍵ｙをｙ＝ｇｘとする（Ｇを乗法的に記述する。ただし、参考文献１では加法的に記述している。）。ｑは十分大きく（例えば１６０ビット）、素数であることが望ましい。そして平文ｍを０以上ｑ未満の整数とし、ｍの暗号文をＥ（ｍ）＝（ｇｒ，ｙｍ＋ｒ）とする。ただし、ｒは０以上ｑ未満のランダムな整数である。Ｅ（ｍ）の復号は、秘密鍵ｘを用いて行う。すなわち、
ｙｍ＝ｙｍ＋ｒ／（ｇｒ）ｘ
の関係式からｙｍを求め，ｙおよびｙｍからｍを得る。
【００２４】
以上の準備の下、秘密情報Ｗと秘密情報Ｗ’を知ることなくＷ＝Ｗ’であるか確認する方法例について説明する。簡単のためにＷ，Ｗ’はＬビットの整数とする（整数のベクトルで考えても良い）。Ｗ，Ｗ’の下位i番目のビットをそれぞれＷｉ，Ｗｉ’とする。Ｗ＝Ｗ’であるかどうかは。
【００２５】
Ｗ＝Ｗ’⇔Ｗｉ＝Ｗｉ’（ｉ＝１，…，Ｌ）
であるから、
（Ｗ１（＋）Ｗ１’）∨（Ｗ２（＋）Ｗ２’）∨…∨（ＷＬ（＋）ＷＬ’）
ただし、（＋）は排他的論理和を示す記号
が０であればＷ＝Ｗ’とし、１であればＷ≠Ｗ’と判定できる。そこで当該論理式を用いればよい。
【００２６】
具体的には、認証装置２００によって生成される第１秘密鍵ｘ１を０以上ｑ未満のランダムな整数とし、第１公開鍵ｙ１をｙ１＝ｇ＾ｘ１とする。同様に、協調装置３００によって生成される第２秘密鍵ｘ２を０以上ｑ未満のランダムな整数とし、第２公開鍵ｙ２をｙ２＝ｇ＾ｘ２とする。そして
ｙ＝ｙ１ｙ２＝ｇ＾（ｘ１＋ｘ２），
ｘ＝ｘ１＋ｘ２
とする。
【００２７】
ここで、（＋）を２つの数値を２進数表現で表して対応するビットごとに排他的論理和を求める演算を示す記号とし、Ｗ”＝Ｗ’（＋）Ａ、Ｗ”の下位i番目のビットをＷｉ”とする。そして、第１暗号文Ｃは秘密情報Ｗをビット単位で暗号化した暗号文Ｅ（Ｗｉ）（ただし、ｉ＝１，…，Ｌ）の集まり、第２暗号文Ｃ’はＷ”をビット単位で暗号化した暗号文Ｅ（Ｗｉ”）（ただし、ｉ＝１，…，Ｌ）の集まりとする。Ｗｉ，Ｗｉ”の暗号文はそれぞれ、
Ｅ（Ｗｉ）＝（ｇ＾ｒｉ，ｙ＾（Ｗｉ＋ｒｉ）），
Ｅ（Ｗｉ”）＝（ｇ＾ｒｉ’，Ｗ”ｙ＾ｒｉ’）
ただし、ｉ＝１，…，Ｌ
であり、これらの暗号文が第１暗号文Ｃ，第２暗号文Ｃ’として与えられているとする。ここで、ｒｉとｒｉ’（ｉ＝１，…，Ｌ）は０以上ｑ未満のランダムな整数とする。
【００２８】
ステップＳ２２０では、認証装置２００は１ビットの乱数ｔｉおよび０以上ｑ未満のランダムな整数ｕｉ（ｉ＝１，…，Ｌ）を生成し、ｔｉが０であれば
ｅｉ＝（（ｇ＾ｒｉ）＾ｕｉ，（ｙ＾（Ｗｉ＋ｒｉ））＾ｕｉ）
を計算し、ｔｉが１であれば
ｅｉ＝（（ｇ＾ｒｉ）＾（−ｕｉ），（ｙ＾（Ｗｉ＋ｒｉ））＾ｕｉ）
を計算する。すると，ｅｉはＷｉ（＋）ｔｉの暗号文とみなすことができ、乱数ビットｔｉを知らない限り、ｅｉを復号してもＷｉが知られることはない。このことを利用し、認証装置２００および協調装置３００は協力してｅｉを復号し、復号結果Ｗｉ（＋）ｔｉは協調装置３００のみ得るようにする。具体的には、認証装置２００がｅｉを協調装置３００に送信する。そして、協調装置３００がｅｉを復号する。
【００２９】
Ｗｉ（＋）ｔｉを得た協調装置３００は，Ｗｉ（＋）ｔｉおよびＥ（Ｗｉ”）から、（Ｗｉ（＋）ｔｉ）（＋）Ｗｉ”の暗号文Ｅ（（Ｗｉ（＋）ｔｉ）（＋）Ｗｉ”）を計算し、認証装置２００に送信する。これは先述の認証装置２００がｅｉを求めた手続き同様であり、ｔｉ，Ｅ（Ｗｉ）をそれぞれ、Ｗｉ（＋）ｔｉ，Ｅ（Ｗｉ”）に置き換えればよい。そして、認証装置２００は、ｔｉおよびＥ（（Ｗｉ（＋）ｔｉ）（＋）Ｗｉ”）から
Ｅ（（（Ｗｉ（＋）ｔｉ）（＋）Ｗｉ”）（＋）ｔｉ）＝Ｅ（Ｗｉ（＋）Ｗｉ”）
を得る。これは先述の認証装置２００の手続きにおいてｔｉ，Ｅ（Ｗｉ）をそれぞれｔｉ，Ｅ（（Ｗｉ（＋）ｔｉ）（＋）Ｗｉ”）に置き換えればよい。ここまででＷｉ，Ｗｉ”の復元を困難としつつＷｉ（＋）Ｗｉ”の暗号文Ｅ（Ｗｉ（＋）Ｗｉ”）を生成できた。上述の処理は、一般性を失うこと無く、１ビットデータａ，ｂの暗号文Ｅ（ａ），Ｅ（ｂ）から、ａ，ｂの復元を困難としつつ、排他的論理和結果の暗号文Ｅ（ａ（＋）ｂ）の計算を行う手続きに他ならない。また、Ｗｉ”は、Ｗｉ”＝Ｗ’（＋）Ａであるから、秘密情報Ｗ’は、
Ｗ’＝Ｗｉ”（＋）Ａ
である。したがって、暗号文Ｅ（Ｗｉ（＋）Ｗｉ”）とＡを暗号化した暗号文Ｅ（Ａ）から、Ｗｉ（＋）Ｗｉ”を復元困難としつつ暗号文Ｅ（Ｗｉ（＋）Ｗｉ’）を求めることができる。
【００３０】
次に、Ｅ（Ｗｉ（＋）Ｗｉ’）とＥ（Ｗｊ（＋）Ｗｊ’）から
Ｅ（Ｗｉ（＋）Ｗｉ’）∨Ｅ（Ｗｊ（＋）Ｗｊ’）
を計算する方法について説明する。この計算を繰り返すことにより
（Ｗ１（＋）Ｗ１’）∨（Ｗ２（＋）Ｗ２’）∨…∨（ＷＬ（＋）ＷＬ’）
の暗号文を計算でき、当該暗号文を復号することで最終結果を得ることができる。したがって当該計算は、一般性を失うこと無く、Ｅ（ａ），Ｅ（ｂ）から、ａ，ｂの復元を困難としつつＥ（ａ∨ｂ）を計算する方法に他ならない。いま
Ｅ（ａ）＝（ｇ＾ｒａ，ｙ＾（ａ＋ｒａ））
Ｅ（ｂ）＝（ｇ＾ｒｂ，ｙ＾（ｂ＋ｒｂ））
ただしｒａ，ｒｂは０以上q未満のランダムな整数
としたとき、
Ｅ（ａ）Ｅ（ｂ）＝（ｇ＾（ｒａ＋ｒｂ），ｙ＾（ａ＋ｒａ＋ｂ＋ｒｂ））
＝Ｅ（ａ＋ｂ）
となる。すなわち、Ｅ（ａ），Ｅ（ｂ）から、ａ，ｂの復元を困難としつつ加算結果の暗号文Ｅ（ａ＋ｂ）を計算することができる。さらに、０以上ｑ未満の整数ｃについて、
Ｅ（ａ）＾ｃ＝（（ｇ＾ｒａ）＾ｃ，（ｙ＾（ａ＋ｒａ））＾ｃ）＝Ｅ（ａｃ）
であるため、Ｅ（ａ），ｃから、ａ，ｂの復元を困難としつつ定数倍結果の暗号文Ｅ（ａｃ）を計算することができる。一方、
ａ∨ｂ＝２−１（（ａ＋ｂ）+（ａ（＋）ｂ））
であるため、上述の加算、定数倍および排他的論理和についてａ，ｂの復元を困難としつつ計算することで、論理和の暗号文Ｅ（ａ∨ｂ）が得られることが分かる。なお、
ａ∧ｂ＝２−１（（ａ＋ｂ）−（ａ（＋）ｂ））
であり、Ｅ（ａ）／Ｅ（ｂ）＝Ｅ（ａ−ｂ）であるから、ａ，ｂの復元を困難としつつ論理積の暗号文Ｅ（ａ∧ｂ）を計算することもできる。さらに、排他的論理和、論理和、論理積の組合せについても、ａ，ｂの復元を困難としつつ計算可能であることも分かる。距離計算や比較演算など多くの演算は論理和と論理積の組合せで計算できることから、距離計算、比較演算、およびその組合せについてもａ，ｂの復元を困難としつつ計算可能である。
【００３１】
［検証処理（Ｓ３０）］
認証装置２００は、被認証装置１００を特定する情報Ｉ（被認証者情報）、付随情報Ａ，第１暗号文Ｃ、第２暗号文Ｃ’、認証結果Ｆ、ステップＳ２２０の処理で生成されたデータＤを検証装置４００に送る（Ｓ２６０）。検証受信部４１０は、被認証装置１００を特定する情報Ｉ、付随情報Ａ，第１暗号文Ｃ、第２暗号文Ｃ’、認証結果Ｆ、データＤを受信する。そして、実行検証部４２０は、被認証装置１００を特定する情報Ｉ、付随情報Ａ，第１暗号文Ｃ、第２暗号文Ｃ’、認証結果Ｆ、データＤを用いて、認証が正しく実行されたかを検証する（Ｓ４１０）。この検証でも、秘密情報Ｗがパスワードのように等しくなければならない情報の場合には、等しい場合を検証成功とし（Ｓ４２０）、等しくない場合には検証失敗とする（Ｓ４３０）。また、秘密情報Ｗが生体情報のようにノイズなどにより必ずしも等しくならない情報の場合には、所定の距離以内のときを検証成功とし（Ｓ４２０）、所定の距離より遠いときを検証失敗とする（Ｓ４３０）。
【００３２】
本発明の本人性証明システムによれば、認証装置２００と協調装置３００とが協調することで、秘密情報Ｗと秘密情報Ｗ’を知ることなく、登録しておいた暗号文（第１暗号文Ｃ）の秘密情報Ｗと、認証処理で生成された暗号文（第２暗号文Ｃ）の秘密情報Ｗ’とが等しいこと、もしくは所定の距離以内であることを確認できる。したがって、所有物を用いない認証において本人性の第三者への証明力を高めることができる。
【実施例２】
【００３３】
実施例２の本人性証明システムと周辺装置等の構成も図１に示す。実施例２では実施例１よりも具体的な処理（実施例１の下位概念）を説明する。図３に実施例２の事前処理と登録処理の処理フローを、図４に実施例２の認証処理の処理フローを、図５に実施例２の検証処理の処理フローを示す。実施例２の本人性証明システムは、第１公開鍵を公開する認証装置と第２公開鍵を公開する協調装置を有し、被認証装置の本人性を証明する。また、検証装置は、本人性証明システムの処理が正しく実行されたかを検証する。被認証装置１００、認証装置２００、協調装置３００、検証装置４００は、ネットワーク９００を介して接続されている。被認証装置１００は、被認証受信部１１０、第１暗号化部１２０、第２暗号化部１３０、被認証記録部１９０を備える。認証装置２００は、第１鍵生成部２０１、第１暗号文確認部２３０、認証記録部２９０を備える。協調装置３００は、第２鍵生成部３０１、第２暗号文確認部３３０、協調記録部３９０を備える。検証装置４００は、検証受信部４１０、実行検証部４２０、検証記録部４９０を備える。実施例２では、認証装置２００は、さらに付随情報確認部２２０を備えてもよい。本実施例では、ｐとｑはｑ｜ｐ−１を満たす素数、ｑはｋビット、ｇはｇｑ＝１ｍｏｄｐを満たす２以上ｐ未満の整数、乱数ｒは１以上ｑ未満の整数、Ａ、Ｗ、Ｗ’は０以上ｑ未満の整数であり、（＋）は２つの数値を２進数表現で表して対応するビットごとに排他的論理和を求める演算を示す記号、＾は累乗を示す記号とする。
【００３４】
［事前処理（Ｓ８０）］
第１鍵生成部２０１は、第１公開鍵ｙ１と、第１公開鍵ｙ１と対をなす第１秘密鍵ｘ１を生成し（Ｓ２０１）、第２鍵生成部３０１は、第２公開鍵ｙ２と、第２公開鍵ｙ２と対をなす第２秘密鍵ｘ２を生成する（Ｓ３０１）。そして、公開鍵ｙを
ｙ＝ｙ１ｙ２ｍｏｄｐ
のように定める。そして、被認証記録部１９０と検証記録部４９０は、ｐ，ｑ，ｇ，ｙを記録する。認証記録部２９０は、ｐ，ｑ，ｇ，ｘ１，ｙを記録する。協調記録部３９０、ｐ，ｑ，ｇ，ｘ２，ｙを記録する。
【００３５】
［登録処理（Ｓ１０）］
被認証装置１００には、被認証装置１００または被認証者を特定する情報Ｉ（被認証者情報）と秘密情報Ｗ（パスワード、生体情報など）が入力される（Ｓ１２１）。なお、被認証装置１００にあらかじめ情報Ｉが記録されている場合は、情報Ｉを入力する必要はない。第１暗号化部１２０は、公開鍵ｙを用いて秘密情報Ｗを暗号化した第１暗号文Ｃを
Ｃ＝（Ｇ，Ｙ）＝（ｇｒｍｏｄｐ，ｙｒ＋Ｗｍｏｄｐ）
のように求める（Ｓ１２２）。そして、被認証装置１００は情報Ｉと暗号文Ｃを認証装置２００に送信する（Ｓ１２０）。このときに、被認証装置１００を特定する情報Ｉを一緒に送信してもよい。認証装置２００の認証記録部２９０は、暗号文Ｃと被認証装置を特定する情報Ｉとを対応つけて記録する（Ｓ２１０）。
【００３６】
［認証処理（Ｓ２０）］
被認証装置１００には、被認証装置１００または被認証者を特定する情報Ｉ（被認証者情報）と秘密情報Ｗ’（パスワード、生体情報など）が入力される（Ｓ１３１）。なお、被認証装置１００にあらかじめ情報Ｉが記録されている場合は、情報Ｉを入力する必要はない。被認証装置１００の第２暗号化部１３０は、公開鍵ｙを用いて秘密情報Ｗ’と付随情報Ａを基に生成された第２暗号文Ｃ’を
Ｃ’＝（Ｇ’，Ｙ’）＝（ｇｒｍｏｄｐ，ｙｒ＋（Ｗ’（+）Ａ）ｍｏｄｐ）
のように求め（Ｓ１３２）、付随情報Ａと第２暗号文Ｃ’を認証装置２００に送信する（Ｓ１３０）。「付随情報Ａ」とは、認証時刻や認証目的等を示す任意の情報である。このときに、被認証装置１００を特定する情報Ｉを一緒に送信してもよい。
【００３７】
認証装置２００が付随情報確認部２２０を備える場合には、付随情報確認部２２０は、付随情報Ａが所定の情報かを確認し、所定の情報でない場合には処理を終了する（Ｓ２２１）。所定の情報とは、例えば、認証処理を行う時刻に範囲が定められている場合は、時刻の範囲内の情報である。この例の場合、付随情報Ａとして送られた時刻の情報が当該範囲内でない場合は処理が終了する。このように、付随情報確認部２２０を備えることで、認証処理に対するポリシーがある場合に対応できる。
【００３８】
第１暗号文確認部２３０と第２暗号文確認部３３０は、第１暗号文Ｃの秘密情報Ｗと第２暗号文Ｃ’の秘密情報Ｗ’とが等しいこともしくは所定の距離以内であることを、協調して秘密情報Ｗと秘密情報Ｗ’を知ることなく確認する（Ｓ２２０）。具体的には、まず、秘密情報Ｗを知ることなくＷ（＋）Ａの暗号文である第３暗号文Ｃ”＝（Ｇ”，Ｙ”）を協調して求める（Ｓ２２２）。そして、第２暗号文Ｃ’と第３暗号文Ｃ”とを用いて、秘密情報Ｗと秘密情報Ｗ’を知ることなく秘密情報Ｗと秘密情報Ｗ’が等しいこともしくは所定の距離以内であることを協調して確認する（Ｓ２２３）。なお、ステップＳ２２２，Ｓ２２３の処理は、前述のステップＳ２２０のための暗号化技術を用いればよい。例えば、関数ｆを
ｆ（Ｗ，Ｗ’）＝１      ただし、Ｗ＝Ｗ’
ｆ（Ｗ，Ｗ’）＝０      ただし、Ｗ≠Ｗ’
となる関数とし、この関数ｆを実行する秘密計算方法を設計すればよい。この場合、認証結果Ｆ＝ｆ（Ｗ，Ｗ’）とすればよい。
【００３９】
秘密情報Ｗがパスワードのように等しくなければならない情報の場合には、等しい場合を認証成功とし（Ｓ２３０）、等しくない場合には認証失敗とする（Ｓ２４０）。また、秘密情報Ｗが生体情報のようにノイズなどにより必ずしも等しくならない情報の場合には、所定の距離以内のときを認証成功とし（Ｓ２３０）、所定の距離より遠いときを認証失敗とする（Ｓ２４０）。
【００４０】
認証記録部２９０は、第１暗号文Ｃ、第２暗号文Ｃ’、第３暗号文Ｃ”、付随情報Ａ、認証結果Ｆ、およびステップＳ２２２とＳ２２３の第１暗号文確認部２３０と第２暗号文確認部３３０との協調処理で生成されたデータＤを、被認証装置１００を特定する情報Ｉと対応つけて記録する（Ｓ２５０）。
【００４１】
［検証処理（Ｓ３０）］
認証装置２００は、被認証装置１００を特定する情報Ｉ（被認証者情報）、付随情報Ａ，第１暗号文Ｃ、第２暗号文Ｃ’、第３暗号文Ｃ”、認証結果Ｆ、ステップＳ２２２とＳ２２３の処理で生成されたデータＤを検証装置４００に送る（Ｓ２６０）。検証受信部４１０は、被認証装置１００を特定する情報Ｉ、付随情報Ａ，第１暗号文Ｃ、第２暗号文Ｃ’、認証結果Ｆ、データＤを受信する。そして、実行検証部４２０は、被認証装置１００を特定する情報Ｉ、付随情報Ａ，第１暗号文Ｃ、第２暗号文Ｃ’、第３暗号文Ｃ”、認証結果Ｆ、データＤを用いて、認証が正しく実行されたかを検証する（Ｓ４１０）。具体的には、前述のステップＳ２２０のための暗号化技術を用いればよい。
【００４２】
この検証でも、秘密情報Ｗがパスワードのように等しくなければならない情報の場合には、等しい場合を検証成功とし（Ｓ４２０）、等しくない場合には検証失敗とする（Ｓ４３０）。また、秘密情報Ｗが生体情報のようにノイズなどにより必ずしも等しくならない情報の場合には、所定の距離以内のときを検証成功とし（Ｓ４２０）、所定の距離より遠いときを検証失敗とする（Ｓ４３０）。
【００４３】
このような構成と処理なので、実施例２の本人性証明システムも、実施例１と同様の効果が得られる。
【００４４】
［変形例］
本変形例では、実施例２のステップＳ２２３の具体例を示す。なお、本変形例は、パスワードのように等しいことが確認できた場合にのみ認証成功と判断する秘密情報に限って適用できる。図６は、本変形例の認証処理の処理フローを示す図である。図６は、図４の処理フローとはステップＳ２２３’の部分のみが異なるので、以下ではこの部分を説明する。なお、乱数ｔ、乱数ｕは１以上ｑ未満の整数とする。
【００４５】
ステップＳ２２２が終了した後、第１暗号文確認部２３０は、
ｃ１＝（Ｇ１，Ｙ１）＝（（Ｇ”／Ｇ’）ｔｍｏｄｐ，（Ｙ”／Ｙ’）ｔｍｏｄｐ）
を求めて第２暗号文確認部３３０に送信する（Ｓ２２４）。第２暗号文確認部３３０は、
ｃ２＝（Ｇ２，Ｙ２）＝（Ｇ１ｕｍｏｄｐ，Ｙ１ｕｍｏｄｐ）
ｄ２＝Ｇ２＾ｘ２
を求めて第１暗号文確認部２３０に送信する（Ｓ２２５）。第１暗号文確認部２３０は、
ｄ１＝Ｇ２＾ｘ１
を求める（Ｓ２２６）。そして、第１暗号文確認部２３０は、
Ｙ２／（ｄ１ｄ２）＝１
が成り立つかを確認し（Ｓ２２７）、成り立てば秘密情報Ｗと秘密情報Ｗ’とが等しいと判断して認証成功とし（Ｓ２３０）、成り立たなければ等しくないと判断して認証失敗とする（Ｓ２４０）。
【００４６】
その他の構成と処理は実施例２と同じである。したがって、本変形例も実施例２と同様の効果が得られる。
【実施例３】
【００４７】
実施例３の本人性証明システムと周辺装置等の構成も図１に示す。実施例３でも実施例２と同じように実施例１よりも具体的な処理（実施例１の下位概念）を説明する。図３に実施例３の事前処理と登録処理の処理フローを、図４に実施例３の認証処理の処理フローを、図５に実施例３の検証処理の処理フローを示す。本実施例では、ｐとｑはｑ｜ｐ−１を満たす素数、ｑはｋビット、ｇはｇｑ＝１ｍｏｄｐを満たす２以上ｐ未満の整数、乱数ｒは１以上ｑ未満の整数、Ａ、Ｗ、Ｗ’は０以上ｑ未満の整数であり、（＋）は２つの数値を２進数表現で表して対応するビットごとに排他的論理和を求める演算を示す記号、＾は累乗を示す記号とする。
【００４８】
被認証装置１００、認証装置２００、協調装置３００、検証装置４００の構成は実施例２と同じである。また、事前処理Ｓ８０と登録処理Ｓ１０は、実施例２と同じである。
【００４９】
［認証処理（Ｓ２０）］
ステップＳ１３０、Ｓ２２１は実施例２と同じである。
【００５０】
実施例３では、第１暗号文確認部２３０と第２暗号文確認部３３０は、まず、秘密情報Ｗ’を知ることなくＷ’の暗号文である第３暗号文Ｃ”＝（Ｇ”，Ｙ”）を協調して求める（Ｓ２２２’）。そして、第１暗号文Ｃと第３暗号文Ｃ”とを用いて、秘密情報Ｗと秘密情報Ｗ’を知ることなく秘密情報Ｗと秘密情報Ｗ’が等しいこともしくは所定の距離以内であることを協調して確認する（Ｓ２２３’）。なお、ステップＳ２２２，Ｓ２２３の処理は、前述のステップＳ２２０のための暗号化技術を用いればよい。例えば、関数ｆを
ｆ（Ｗ，Ｗ’）＝１      ただし、Ｗ＝Ｗ’
ｆ（Ｗ，Ｗ’）＝０      ただし、Ｗ≠Ｗ’
となる関数とし、この関数ｆを実行する秘密計算方法を設計すればよい。この場合、認証結果Ｆ＝ｆ（Ｗ，Ｗ’）とすればよい。
【００５１】
秘密情報Ｗがパスワードのように等しくなければならない情報の場合には、等しい場合を認証成功とし（Ｓ２３０）、等しくない場合には認証失敗とする（Ｓ２４０）。また、秘密情報Ｗが生体情報のようにノイズなどにより必ずしも等しくならない情報の場合には、所定の距離以内のときを認証成功とし（Ｓ２３０）、所定の距離より遠いときを認証失敗とする（Ｓ２４０）。
【００５２】
認証記録部２９０は、第１暗号文Ｃ、第２暗号文Ｃ’、第３暗号文Ｃ”、付随情報Ａ、認証結果Ｆ、およびステップＳ２２２’とＳ２２３’の第１暗号文確認部２３０と第２暗号文確認部３３０との協調処理で生成されたデータＤを、被認証装置１００を特定する情報Ｉと対応つけて記録する（Ｓ２５０）。
【００５３】
［検証処理（Ｓ３０）］
認証装置２００は、被認証装置１００を特定する情報Ｉ（被認証者情報）、付随情報Ａ，第１暗号文Ｃ、第２暗号文Ｃ’、第３暗号文Ｃ”、認証結果Ｆ、ステップＳ２２２’とＳ２２３’の処理で生成されたデータＤを検証装置４００に送る（Ｓ２６０）。検証受信部４１０は、被認証装置１００を特定する情報Ｉ、付随情報Ａ，第１暗号文Ｃ、第２暗号文Ｃ’、認証結果Ｆ、データＤを受信する。そして、実行検証部４２０は、被認証装置１００を特定する情報Ｉ、付随情報Ａ，第１暗号文Ｃ、第２暗号文Ｃ’、第３暗号文Ｃ”、認証結果Ｆ、データＤを用いて、認証が正しく実行されたかを検証する（Ｓ４１０）。具体的には、前述のステップＳ２２０のための暗号化技術を用いればよい。
【００５４】
このような構成と処理なので、実施例２の本人性証明システムも、実施例１と同様の効果が得られる。
【００５５】
プログラム、記録媒体
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００５６】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００５７】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００５８】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００５９】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００６０】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００６１】
本発明は、本人性の確認が必要な暗号通信や情報管理用のシステムに利用できる。
【符号の説明】
【００６２】
１００  被認証装置                    １１０  被認証受信部
１２０  第１暗号化部                  １３０  第２暗号化部
１９０  被認証記録部                  ２００  認証装置
２０１  第１鍵生成部                  ２２０  付随情報確認部
２３０  第１暗号文確認部              ２９０  認証記録部
３００  協調装置                      ３０１  第２鍵生成部
３３０  第２暗号文確認部              ３９０  協調記録部
４００  検証装置                      ４１０  検証受信部
４２０  実行検証部                    ４９０  検証記録部
９００  ネットワーク
【図１】
0005406796.tif 000002
【図２】
0005406796.tif 000003
【図３】
0005406796.tif 000004
【図４】
0005406796.tif 000005
【図５】
0005406796.tif 000006
【図６】
0005406796.tif 000007