(57)【特許請求の範囲】
【請求項１】
ｐを素数、Ｆｐをｐ元体、Ｇを零化域を求めることが計算量的に困難な有限アーベル群（記法を固定する目的のためにのみ乗法的に記す）、Ｒをコミットメントの空間、πをＧからＲへの写像、Ｃをチャレンジの空間、Ｓをメッセージの空間、φをＣとＳの集合論的積Ｃ×ＳからＦｐへの写像として、証明部側からコミットメントｒを生成して検証部側に送り、ドキュメントｍと検証部側から送られてくるチャレンジχとを用いてレスポンスｓを生成し、上記ドキュメントｍおよびチャレンジχの入力に応じてメッセージＭを生成し上記検証部側に送り、検証情報Ｉ∈Ｇ、コミットメントｒおよびレスポンスｓに基づいて上記検証部側で検証を行う認証方法であって、
（ａ）証明部側の乱数生成手段で非再現性秘密情報ｋ∈Ｇをランダムに生成するステップと、
（ｂ）証明部側のコミットメント生成手段でコミットメントｒ＝π（ｋｐ）を計算するステップと、
（ｃ）証明部側のドキュメント秘密情報計算手段でｆをＧへの秘密関数として、ドキュメント秘密情報μ＝ｆ（ｍ）を計算するステップと、
（ｄ）証明部側のメッセージ生成手段でメッセージＭを生成するステップと、
（ｅ）証明部側の指数計算手段で指数Ｃ＝φ（χ，Ｍ）を計算するステップと、
（ｆ）証明部側の第１のレスポンス計算手段でレスポンスσ＝ｋμｃを計算するステップと、
（ｇ）証明部側の第２のレスポンス計算手段でレスポンスｓ＝ｔｃσ（ただしｔは認証の特徴情報ｘおよびドキュメント秘密情報からｔ＝ｘｆ（ｍ）−１で予め生成されて証明部側に保持されているチケットである。認証の特徴情報ｘはＩｘｐ＝１である。）を計算するステップと、
（ｈ）検証部側の検証手段により、上記生成されたレスポンスｓがｒ＝π（ｓｐＩｃ）を満たすことを検証するステップとを有することを特徴とする認証方法。
【請求項２】
証明部と検証部とを具備し、ｐを素数、Ｆｐをｐ元体、Ｇを零化域を求めることが計算量的に困難な有限アーベル群、Ｒをコミットメントの空間、πをＧからＲへの写像、Ｃをチャレンジの空間、Ｓをメッセージの空間、φをＣとＳの集合論的積Ｃ×ＳからＦｐへの写像として、上記証明部側からコミットメントｒを生成して上記検証部側に送り、ドキュメントｍと上記検証部側から送られてくるチャレンジχとを用いてレスポンスｓを生成し、上記ドキュメントｍおよびチャレンジχの入力に応じてメッセージＭを生成し上記検証部側に送り、検証情報Ｉ∈Ｇ、コミットメントｒおよびレスポンスｓに基づいて上記検証部側で検証を行う認証装置であって、
上記証明部は、
（ａ）非再現性秘密情報ｋ∈Ｇをランダムに生成する手段と、
（ｂ）コミットメントｒ＝π（ｋｐ）を計算する手段と、
（ｃ）ｆをＧへの秘密関数として、ドキュメント秘密情報μ＝ｆ（ｍ）を計算する手段と、
（ｄ）メッセージＭを生成する手段と、
（ｅ）指数Ｃ＝φ（χ，Ｍ）を計算する手段と、
（ｆ）レスポンスσ＝ｋμｃを計算する手段と、
（ｇ）レスポンスｓ＝ｔｃσ（ただしｔは認証の特徴情報ｘおよびドキュメント秘密情報からｔ＝ｘｆ（ｍ）−１で予め生成されて証明部側に保持されているチケットである。
認証の特徴情報ｘはＩｘｐ＝１である。）を計算する手段とを有し、
上記検証部は、
（ｈ）上記証明部で生成されたレスポンスｓがｒ＝π（ｓｐＩｃ）を満たすことを検証する手段とを有することを特徴とする認証装置。
【請求項３】
請求項１記載の認証方法に用いられ上記証明部側に設けられた対話装置で実行する対話方法であって、
（ａ）上記対話装置の乱数生成手段で非再現性秘密情報ｋ∈Ｇをランダムに生成するステップと、
（ｂ）上記対話装置のコミットメント生成手段でコミットメントｒ＝π（ｋｐ）を計算するステップと、
（ｃ）上記対話装置のドキュメント秘密情報計算手段でｆをＧへの秘密関数として、ドキュメント秘密情報μ＝ｆ（ｍ）を計算するステップと、
（ｄ）上記対話装置のメッセージ生成手段でメッセージＭを生成するステップと、
（ｅ）上記対話装置の指数計算手段で指数Ｃ＝φ（χ，Ｍ）を計算するステップと、
（ｆ）上記対話装置の第１のレスポンス計算手段でレスポンスσ＝ｋμｃを計算するステップとからなることを特徴とする対話方法。
【請求項４】
特に、ｐ＝２であることを特徴とする請求項３に記載の対話方法。
【請求項５】
特に、ｐがＧの零化域の生成元λと互いに素であることを特徴とする請求項３に記載の対話方法。
【請求項６】
特に、Ｇが合成数ｎを法とする有理整数環の剰余類環の乗法群（Ｚ／ｎＺ）＊であることを特徴とする請求項３に記載の対話方法。
【請求項７】
特に、Ｇが合成数ｎを法とする有理整数環の剰余類環Ｚ／ｎＺ上の群スキームＥのＺ／ｎＺに値を持つ点のなす群Ｅ（Ｚ／ｎＺ）であることを特徴とする請求項３に記載の対話方法。
【請求項８】
特に、πが恒等写像であることを特徴とする請求項３に記載の対話方法。
【請求項９】
特に、πがハッシュ関数を用いて計算されることを特徴とする請求項３に記載の対話方法。
【請求項１０】
特に、φがハッシュ関数を用いて計算されることを特徴とする請求項３に記載の対話方法。
【請求項１１】
請求項３記載の対話方法を実行する上記対話装置であって、
コミットメントｒを出力し、ドキュメントｍとチャレンジχとを入力し、レスポンスσとメッセージＭとを出力するにあたって、
（ａ）情報の入出力手段と、
（ｂ）情報の記憶手段と、
（ｃ）乱数を生成する手段と、
（ｄ）Ｇにおける算法を実行する手段と、
（ｅ）πを計算する手段と、
（ｆ）固有の秘密関数ｆを計算する手段と、
（ｇ）メッセージを生成する手段と、
（ｈ）φを計算する手段とを備えることを特徴とする対話装置。
【請求項１２】
内部の実行処理過程が外部から観測することが困難であることを特徴とする請求項１１に記載の対話装置。
【請求項１３】
ＩＣカードなどの携帯可能な小型演算装置として構成されていることを特徴とする請求項１１に記載の対話装置。
【請求項１４】
固有の秘密関数ｆを計算する手段は、
（ａ）固有の秘密情報ｄを保持する手段と、
（ｂ）ハッシュ関数ｈを計算する手段とからなり、ドキュメント秘密情報μが、固有の秘密情報ｄとドキュメントｍよりハッシュ関数ｈを用いて計算されることを特徴とする請求項１１に記載の対話装置。
【請求項１５】
ドキュメントｍに応じた処理を行なう手段をさらに備えたことを特徴とする請求項１１に記載の対話装置。
【請求項１６】
ドキュメントｍがＧ、ｐ、πの少なくとも一部を規定することを特徴とする請求項１５に記載の対話装置。
【請求項１７】
ドキュメントｍがレスポンス生成の条件を規定することを特徴とする請求項１５に記載の対話装置。
【請求項１８】
ドキュメントｍが生成されるメッセージを規定することを特徴とする請求項１５に記載の対話装置。
【請求項１９】
検証情報Ｉ∈Ｇに対応する認証の特徴情報ｘ∈ＧはＩｘｐ＝１を満たし、ドキュメントｍと請求項１１に記載の固有の秘密関数ｆを有する対話装置に対して、チケットｔ∈Ｇを生成するチケット発行方法であって、
（ａ）ドキュメント秘密情報計算手段でドキュメント秘密情報μ＝ｆ（ｍ）を計算するステップと、
（ｂ）チケット計算手段でチケットｔ＝ｘμ−１を計算するステップとからなることを特徴とするチケット発行方法。
【請求項２０】
ドキュメントｍが認証の特徴情報ｘに依存することを特徴とする請求項１９に記載のチケット発行方法。
【請求項２１】
ドキュメントｍが認証の特徴情報ｘを識別する情報を含むことを特徴とする請求項１９に記載のチケット発行方法。
【請求項２２】
認証の特徴情報ｘとドキュメントｍと対話装置を識別する情報を入力し、チケットｔを出力するにあたって、
（ａ）情報の入出力手段と、
（ｂ）情報の記憶手段と、
（ｃ）固有の秘密関数ｆを計算する手段と、
（ｄ）Ｇにおける算法を実行する手段とを備え、請求項１９に記載のチケット発行を実行することを特徴とするチケット発行装置。
【請求項２３】
Ｉ１，ｔ１，．．．，ＩＮ，ｔＮを、請求項１９に記載された検証情報Ｉｉ∈Ｇと固有の秘密関数ｆを有する対話装置に対応したチケットｔｉ∈Ｇとして、合成された検証情報Ｉ＝Ｉ１・・・ＩＮに対応する合成されたチケットｔをｔ＝ｔ１・・・ｔＮとして生成することを特徴とするチケット合成方法。
【請求項２４】
複数のドキュメントｍ１，．．．，ｍＮに対して、ドキュメント秘密情報μ＝ｆ（ｍ１）・・・ｆ（ｍＮ）を計算することを特徴とする請求項１１に記載の対話装置。
【請求項２５】
請求項１１に記載の対話装置と請求項１９あるいは請求項２３に記載の検証情報Ｉに対するチケットｔとドキュメントｍとを用いて、コミットメントｒを生成し、チャレンジχに対して、メッセージＭとレスポンスｓとを
【数１】
0003812123.tif 000010
を満たすように生成する証明方法であって、
（ａ）対話装置を用いて、コミットメントｒを取得するステップと、
（ｂ）対話装置を用いて、ドキュメントｍとチャレンジχに対応するメッセージＭと第１のレスポンスσを取得するステップと、
（ｃ）指数計算手段を用いて、指数ｃ＝φ（χ，Ｍ）を計算するステップと、
（ｄ）計算手段を用いてレスポンスｓ＝ｔｃσを計算するステップとからなることを特徴とする証明方法。
【請求項２６】
チケットｔとドキュメントｍを保持し、請求項１１に記載の対話装置と通信することによって、コミットメントｒを出力し、チャレンジχを入力し、メッセージＭとレスポンスｓを出力するにあたって、
（ａ）情報の入出力手段と、
（ｂ）情報の記憶手段と、
（ｃ）Ｇにおける算法を実行する手段と、
（ｄ）φを計算する手段とを備え、請求項２５に記載の証明を実行することを特徴とする証明装置。
【請求項２７】
請求項１９あるいは請求項２３に記載の検証情報Ｉに対するチケットｔの検証方法であって、
（ａ）コミットメント受信手段でコミットメントｒを取得するステップと、
（ｂ）チャレンジ生成手段でチャレンジχをランダムに生成するステップと、
（ｃ）レスポンス受信手段でメッセージＭとレスポンスσを取得するステップと、
（ｄ）指数計算手段で指数ｃ＝φ（χ，Ｍ）を計算するステップと、
（ｅ）確認手段で関係式ｒ＝π（（ｔｃσ）ｐＩｃ）またはこの関係式と同等な関係式を満たすことを確認するステップとからなることを特徴とするチケット検証方法。
【請求項２８】
検証情報Ｉとチケットｔを保持し、コミットメントｒを入力し、チャレンジχを出力し、メッセージＭとレスポンスσを入力して正当性を検証するにあたって、
（ａ）情報の入出力手段と、
（ｂ）情報の記憶手段と、
（ｃ）乱数を生成する手段と、
（ｄ）Ｇにおける算法を実行する手段と、
（ｅ）必要ならば、πを計算する手段と、
（ｆ）φを計算する手段とを備え、少なくとも請求項２７に記載の検証を実行することを特徴とするチケット検証装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、情報セキュリティ技術に関するものであり、特に、零化域決定問題の困難性に安全性の根拠を置く認証符号方式において、システムの利用者に秘密情報に基づいた証明者の機能を付与しながら秘密情報自体を隠蔽することを可能にする方法および装置に関するものである。
【０００２】
【従来の技術】
［従来技術の概要］
従来の公開鍵暗号における復号鍵、署名における署名鍵、認証における認証鍵は、これらの秘密情報を所持するものであることを認証するための特徴情報である。例えば、ＧｕｉｌｌｏｕとＱｕｉｓｑｕａｔｅｒによって”Ａ  ｐｒａｃｔｉｃａｌ  ｚｅｒｏ−ｋｎｏｗｌｅｄｇｅ  ｐｒｏｔｏｃｏｌｆｉｔｔｅｄ  ｔｏ  ｓｅｃｕｒｉｔｙ  Ｍｉｃｒｏｐｒｏｃｅｓｓｏｒ  ｍｉｎｉｍｉｚｉｎｇｂｏｔｈ  ｔｒａｎｓｍｉｓｓｉｏｎ  ａｎｄ  Ｍｅｍｏｒｙ”，Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  ＥＵＲＯＣＲＹＰＴ’８７，Ｃ．Ｇ．Ｇｕｅｎｔｈｅｒ（ｅｄ．），Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，ｐｐ．１２３−１２８で提案された認証方式に基づく認証符号方式を例にとって説明する。
【０００３】
図１は、この認証符号方式の流れを説明する図である。
【０００４】
ｎを素因数分解の困難な合成数、Ｇを有理整数環のｎを法とする剰余類環の乗法群（Ｚ／ｎＺ）*、ｐをｎのＣａｒｍｉｃｈａｅｌ関数λ（ｎ）を割らない素数、Ｒをコミットメントの空間、πをＧからＲへの関数、Ｃをチャレンジの空間、Ｓをメッセージの空間、φをＣとＳとの集合論的積Ｃ×ＳからＦpへの写像、Ｉ∈Ｇを公開の検証情報として、Ｉｘp＝１を満たすｘ∈Ｇを認証の特徴情報とする。
【０００５】
認証の特徴情報ｘの保持者は、以下の証明者２００の動作を行なうことによって、なりすましと改竄を防いで任意のメッセージＭ∈Ｓを安全に発信することができる。
【０００６】
▲１▼乱数ｋ∈Ｇを生成し、コミットメントｒ＝π（ｋp）を送る。
【０００７】
▲２▼与えられたチャレンジχと発信するメッセージＭより指数ｃ＝φ（χ，Ｍ）を計算し、メッセージＭとレスポンスｓ＝ｋｘcを送る。
【０００８】
検証情報Ｉを知り得るものは誰でも、以下の検証者１００の動作を行なうことによって、証明者２００の動作を検証することが可能であり、証明者２００が確かに認証の特徴情報を保持し、発信されたメッセージが改竄を受けていないことを確かめることができる。
【０００９】
▲１▼コミットメントｒを与えられた後に、ランダムに生成したチャレンジχを証明者２００に送る。
【００１０】
▲２▼与えられたメッセージＭとレスポンスｓが
【００１１】
【数２】
0003812123.tif 000002
を満たすことを確かめる。
【００１２】
これらの技術は、上記の秘密情報を所持するものが、これを公開しないことを前提に作られている。それゆえに、これらの秘密情報を所持するもののみが復号できる暗号文、これらの秘密情報を所持するもののみが生成できる署名や、これらの秘密情報を所持するもの以外の誰にもなりすませない認証が可能となる。
【００１３】
したがって、上記技術は、これらの秘密情報の所持者にとって、これを暴露することが不利益な状況である場合にのみ利用できる。このような状況の典型的な例は、上記秘密情報が、特定の個人のみが所持するものであり、その個人を認証する特徴情報である場合である。
【００１４】
この場合、上記特徴情報はちょうど自宅の鍵や個人の印鑑のような役割を担っている。実際、実世界における鍵や印鑑をディジタル情報として構成することは、これらの暗号学的手法の直接的な応用として実現できることは易しい。たとえば、自宅の錠を上記Ｇｕｉｌｌｏｕ−Ｑｕｉｓｑｕａｔｅｒの方式における検証者として構成し、検証に成功した場合のみ開錠するように構成すれば、認証の特徴情報ｘの所持は、ちょうど自宅の鍵の所持に対応することになる。
【００１５】
［従来技術の問題点］
上記の、個人の自宅の鍵のように、認証の特徴情報の暴露が個人の不利益になる場合とは逆に、その暴露が暴露した者の利益につながる場合が存在する。それは、認証する者が、特定のサービスを受ける権利や資格である場合である。  この場合、上記の個人を認証する例と同様に、権利や資格を持つ者に、権利や資格を表す特徴情報を配布し、その特徴情報を所持していることを検証するというやりかたはとれない。なぜなら、特徴情報の暴露が、特徴情報の所持者には不利益にならないため、特徴情報を権利や資格を持たない第三者に教え、その第三者から利益を得るといった不正行為が可能であるからである。
【００１６】
したがって、従来は、上記の公開鍵暗号技術をそのまま使った認証方式を取らず、以下の３種の方式をとっていた。
【００１７】
▲１▼第１の方法は、個人が個人に帰属する秘密の特徴情報を保持し、権利や資格の保持を検証する側が、権利や資格を保持している個人とその個人が持つ秘密の特徴情報を保持する方法である。この方法によれば、特徴情報を漏洩させることは個人にとって不利益になるので、権利や資格の認証に利用可能である。
【００１８】
▲２▼第２の方法は、個人が個人に帰属する秘密の特徴情報を保持し、権利や資格の保持を検証する側が、権利や資格を保持している個人とその個人が持つ秘密の特徴情報に対応する公開情報を保持する方法である。この方法によれば、特徴情報を漏洩させることは個人にとって不利益になるので、権利や資格の認証に利用可能である。
【００１９】
▲３▼第３の方法は、権利や資格を付与する者が、自身が持つ特徴情報で作成した署名を権利や資格を付与される者に渡し、検証側が、その署名を検証することで、権利や資格を持つことを認証するものである。この方式の例としては、Ｄ．Ｃｈａｕｍによる”Ｏｎｌｉｎｅ  Ｃａｓｈ  Ｃｈｅｃｋｓ”，Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  ＥＵＲＯＣＲＹＰＴ’８９，Ｊ．Ｊ．Ｑｕｉｓｑｕａｔｅｒ，Ｊ．Ｖａｎｄｅｗａｌｌｅ（ｅｄ．），Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，ｐｐ．２８８−２９３がある。
【００２０】
この方法によれば、権利や資格の所持を証明する側が、特徴情報を持たないので、特徴情報の漏洩の問題は起こらない。
【００２１】
しかし、第１の方法では、検証側が権利や資格を保持している者のリストを保持しなければならない。これは、リストの記憶と管理の負荷を検証側に課すことになり、必然的に高性能な検証装置を必要とすることになる。また、権利や資格を付与する者と独立に検証装置を作ることができないので、検証装置と、権利や資格を付与する者との間の情報の交換が、常に必要になる。また、検証側が個人の特徴情報を持つことになるので、この方法によって認証される個人は、検証側による不正な特徴情報の漏洩のリスクを負うことになる。
【００２２】
第２の方法では、検証側が権利や資格を保持している者のリストを保持しなければならない。これは、リストの記憶と管理の負荷を検証側に課すことになり、必然的に高性能な検証装置を必要とすることになる。また、権利や資格を付与する者と独立に検証装置を作ることができないので、検証装置と、権利や資格を付与する者との間の情報の交換が、常に必要になる。
【００２３】
第３の方法では、配布した署名情報は誰によっても使用可能なので、その複製を防がなければならない。これは、署名値の二重使用を防ぐという方法で行われる。具体的には、一度認証に使用された署名値をすべて検証側で記憶し、検証側が二重使用でないことをチェックできるようにする。しかし、この機能を検証側に設けるためには、必然的に高性能な検証装置を必要とすることになる。また、同じ権利や資格を認証する全ての検証装置で、一度認証に使用された署名値のリストを共有しなければならず、検証装置同士の情報の交換が、常に必要となる。
【００２４】
このように、従来の３つの方式には、どれも重大な問題があり、とくに検証側を小規模な装置やソフトウエアで構成することを困難にしている。
【００２５】
これに対し、前述の権利や資格を示す特徴情報を使った認証の方式は、検証側で行うことが権利や資格を示す特徴情報を保持していることの認証だけで済むので、有利である。
【００２６】
以上述べたとおり、従来の技術では、権利や資格を認証する場合に、小規模の検証装置で構成すると認証の特徴情報が第三者に洩れる危険があり、その危険をなくそうとすれば、検証装置が大規模なものになるという問題点があった。
【００２７】
【発明が解決しようとする課題】
以上に説明してきたように、本発明は、権利や資格を認証する際に、小規模な検証装置で、認証の特徴情報が第三者に洩れることのない認証符号技術を実現することを目的としている。
【００２８】
【課題を解決するための手段】
本発明の認証符号技術は、
▲１▼チケットの発行時に定められ、公開可能な情報であるドキュメントよりドキュメント秘密情報を生成し、ドキュメント秘密情報に基づいて対話を行なう対話装置と
▲２▼ドキュメント秘密情報と認証の特徴情報より生成され、公開可能な情報であるチケットとに基づく。
【００２９】
すなわち、本発明によれば、ｐを素数、Ｆpをｐ元体、Ｇを零化域を求めることが計算量的に困難な有限アーベル群（記法を固定する目的のためにのみ乗法的に記す。例えば、楕円曲線のような慣習的に加法的に記される群に対しても、零化域を求めることが計算量的に困難である限り、本発明は適用できる）、Ｒをコミットメントの空間、πをＧからＲへの写像、Ｃをチャレンジの空間、Ｓをメッセージの空間、φをＣとＳの集合論的積Ｃ×ＳからＦpへの写像として、コミットメントｒを生成し、ドキュメントｍとチャレンジχに対してレスポンスσとメッセージＭとを生成する対話方法において、つぎのステップを実行する。
【００３０】
（ａ）非再現性秘密情報ｋ∈Ｇをランダムに生成するステップ
（ｂ）コミットメントｒ＝π（ｋp）を計算するステップ
（ｃ）ｆをＧへの秘密関数として、ドキュメント秘密情報μ＝ｆ（ｍ）を計算するステップ
（ｄ）メッセージＭを生成するステップ
（ｅ）指数Ｃ＝φ（χ，Ｍ）を計算するステップ
（ｆ）レスポンスσ＝ｋμcを計算するステップ
この構成においては、公開鍵暗号における認証の特徴情報を開示することなく、認証の特徴情報に基づいた証明の機能を配布することができる。したがって、従来不可能であった、利害関係を持たない複数の個人が同一の認証の特徴情報に基づいた証明を安全に行なえるようになった。またＧｕｉｌｌｏｕ−Ｑｕｉｓｑｕａｔｅｒ認証をベースの公開鍵暗号として採用しているので零知識性が証明されている。さらに、メッセージを安全に伝達することができる。
【００３１】
【発明の実施の形態】
実施例の詳細な説明に入る前に、本発明の利用形態について簡略に説明する。
【００３２】
図２は、本発明の全体の構成を表している。
【００３３】
チケット発行者は、固有の秘密関数で特徴付けられる対話装置３００を発行し、利用者に配布する。対話装置３００を特徴付ける秘密関数が利用者に知られると、対話装置３００の複製が自由に行なえて、チケット発行者の制御不能なチケットの濫用が可能となる。そこで、対話装置３００の秘密関数は、対話装置３００の正当な保持者であっても、これを窃取することができないように保護されるようにできる。
【００３４】
対話装置３００は、例えば、スマートカード（ＩＣカード）として構成しても良い。
【００３５】
対話装置３００は、ドキュメントと呼ばれるデータｍを入力されると、その対話装置３００に固有の秘密関数ｆを用いてドキュメント秘密情報μを生成し、ドキュメント秘密情報に基づいた対話を行なう。
【００３６】
対話は具体的には、
▲１▼コミットメントｒの出力
▲２▼チャレンジχの入力
▲３▼メッセージＭとレスポンスσの出力
という形になっている。
【００３７】
Ｇｕｉｌｌｏｕ−Ｑｕｉｓｑｕａｔｅｒ認証における証明者の行なう対話と形の上では同一である。図１はＧｕｉｌｌｏｕ−Ｑｕｉｓｑｕａｔｅｒ認証の流れを示している。
【００３８】
ドキュメントは、必ずしも、ドキュメント秘密情報を生成するために利用されるだけとは限らない。例えば、ドキュメントは対話装置３００が実行可能なプログラムやコマンド、対話装置３００の行なう処理のパラメータ、あるいは、発信するメッセージなどでありえる。
【００３９】
チケット発行者が、認証の特徴情報ｘに対応付けてチケットｔを発行するときは、認証の特徴情報に基づく対話（ｒ，χ，Ｍ，ｓ）を生成する機能を、以下に述べる方法で利用者に頒布することによって実現する。
【００４０】
チケット発行者は、チケット発行装置４００を用いて、利用者の所持する対話装置３００の秘密関数ｆと対話を生成する際に対話装置に伝達すべきドキュメントｍよりドキュメント秘密情報μを算出し、認証の特徴情報ｘとドキュメント秘密情報μより生成したチケットｔを利用者に発行する。
【００４１】
認証の特徴情報ｘとドキュメント秘密情報μとは、利用者に対して秘匿される。
【００４２】
利用者は、指定されたドキュメントｍを対話装置３００に入力することによって、対話（ｒ，χ，Ｍ，σ）を生成し、発行されたチケットｔを用いて、その対話（ｒ，χ，Ｍ，σ）をチケットの対応する認証の特徴情報に基づいた対話（ｒ，χ，Ｍ，ｓ）へ変換する。
【００４３】
ドキュメントに対話装置３００への処理の指示が記述される場合、チケットを用いた対話生成はドキュメントに記述された指示に関係付けられ、これによってチケットの有効性に条件を付けることが可能となる。
【００４４】
対話の変換は、具体的には、チャレンジχと対話装置のレスポンスσとメッセージＭとチケットｔとより、レスポンスｓを計算することが可能である。
【００４５】
変換された対話（ｒ，χ，Ｍ，ｓ）が、図１におけるＧｕｉｌｌｏｕ−Ｑｕｉｓｑｕａｔｅｒ認証の証明者が生成する対話に他ならないことを実施例において説明する。
【００４６】
チケットの対応する認証の特徴情報ｘは、各々の対話装置３００の様々なドキュメント毎に異なるドキュメント秘密情報μとは独立に生成される。
【００４７】
チケット発行者は、任意の認証の特徴情報ｘに基づく対話の機能を、認証の特徴情報自体を開示することなく任意のドキュメントと対応付けてチケットの形で利用者に頒布することができる。
【００４８】
【実施例】
【００４９】
［基本構成要素］
本発明においては、
【００５０】
【数３】
ｐ      素数
Ｆp        ｐ元体
Ｇ      零化域の決定が計算量的に困難なアーベル群
Ｄ      コミットメントの空間
π      ＧからＤへの写像
が暗号学的な基本構成要素である。
【００５１】
以後、特に説明せずに使用される数学的な概念はいずれも基礎的なものであるのでとくに説明しない。例えば、岩波数学辞典第３版、日本数学会編集、岩波書店を参照されたい。
【００５２】
一般に、アーベル群Ｇの零化域Ａｎｎ（Ｇ）とは、群の算法を乗法的に記すとして、
【００５３】
【数４】
0003812123.tif 000003
で定義される有理整数環Ｚのイデアルであり、有理整数環は単項イデアル整域であるので、Ａｎｎ（Ｇ）の生成元λ∈ＺによってＡｎｎ（Ｇ）＝λＺと書ける（ここにλＺはλの倍元の全体）。零化域を決定することは、Ａｎｎ（Ｇ）の生成元λ∈Ｚを求めることに他ならない。
【００５４】
ｎ∈Ｚを合成数とし、Ｇをｎを法とする有理整数環の剰余類環の乗法群（Ｚ／ｎＺ）*としたとき、λ＝λ（ｎ）となる。ここにλ（ｎ）はｎのＣａｒｍｉｃｈａｅｌ関数であり、ｎが２の冪の場合は
【００５５】
【数５】
0003812123.tif 000004
であり、ｎが奇素数ｐの冪の場合はλ（ｎ）＝ｎ（１−ｐ-1）であり、一般のｎに対しては、ｎ＝Πｐepをｎの素因数分解とすると、λ（ｎ）はλ（ｐep）の最小公倍数である。
【００５６】
したがって、ｎの素因数分解を既知とすれば、Ｇの零化域をｌｏｇ  ｎの多項式時間で求めることができ、また、逆に、零化域の生成元λを既知とすると、非自明な１の平方根、つまり、
【００５７】
【数６】
0003812123.tif 000005
を満たすＧを生成することによって、ｌｏｇ  ｎの確率的多項式時間でｎの素因数分解を求めることができることから、この場合の零化域決定問題は計算量的に素因数分解問題と同程度に困難であると期待できる。  また、ｐ1、ｐ2をｐ1≡ｐ2≡２  ｍｏｄ  ３となる相異なる奇素数、ｎ＝ｐ1ｐ2、ｂをｎと互いに素な整数、Ｅを同次式
【００５８】
【数７】
Ｙ2＝Ｘ3＋ｂＺ3
でＺ／ｎＺ上に定義されるアーベル概型；つまり、
【００５９】
【数８】
Ｅ＝Ｐｒｏｊ  Ｚ／ｎＺ［Ｘ，Ｙ，Ｚ］／（Ｙ2Ｚ−Ｘ3−ｂＺ3）
とし、ＧをＥのＺ／ｎＺ値点のなす有限群Ｅ（Ｚ／ｎＺ）としたとき、λはｐ1＋１とｐ2＋１の最小公倍数であり、この場合も零化域決定問題は計算量的に困難であることが期待できる。
【００６０】
πは、例えば、恒等写像ｉｄ：Ｇ→Ｇとしても良いし、あるいは、ハッシュ関数ｈを用いてｈ：Ｇ→Ｄとしても良い。
【００６１】
ハッシュ関数とは、ｈ（ｍ）＝ｈ（ｍ’）を満たす相異なるｍ、ｍ’を見い出すことが計算量的に困難であることが期待されている関数であり、例えば、ＲＳＡ  Ｄａｔａ  Ｓｅｃｕｒｉｔｙ  Ｉｎｃ．によるＭＤ５や米国連邦政府による規格ＳＨＳ（Ｓｅｃｕｒｅ  Ｈａｓｈ  Ｓｔａｎｄａｒｄ）が良く知られている。
【００６２】
πが恒等写像である場合は、もちろん、πを計算するコストは不要である。また、πがハッシュ関数であり、Ｄの元を表現するのに必要なビット長がＧの元を表現するのに必要なビット長より小さい場合には通信量を削減する効果がある。
【００６３】
例えば、素因数分解の困難な１０２４ビット程度の合成数ｎに対して、Ｇ＝（Ｚ／ｎＺ）*とし、πとしてＳＨＳを用いれば、コミットメントｒのサイズを１６０ビットまで圧縮できる。
【００６４】
ちなみに、ｐのビット長は、質疑応答型の認証の場合は４０ビット程度、署名の場合でも１６０ビット程度で良く、これがＧｕｉｌｌｏｕ−Ｑｕｉｓｑｕａｔｅｒ認証が高速に行なえることの根拠となっている。
【００６５】
［対話装置］
図３は対話装置３００の構成を示している。対話装置３００は耐タンパー性を有する容器として実装され、固有の秘密関数によって特徴付けられて、利用者に配布される。対話装置３００をスマートカードなどの携帯可能な小型演算装置として構成しても良い。対話装置３００は、入出力部３０１、記憶部３０２、ドキュメント処理部３０３、乱数生成部３０４、Ｇの算法実行部３０５、π計算部３０６、ｆ計算部３０７、φ計算部３０８およびメッセージ生成部３０９を含んで構成されている。
【００６６】
図４は対話装置３００の動作を示している。以下、対話装置３００の動作を説明する。
【００６７】
［１］乱数生成部３０４を用いて、非再現性秘密情報ｋ∈Ｇを生成し、記憶部３０２に保持する。［２］Ｇにおける算法実行部３０５とπ計算部３０６を用いて、記憶部３０２に保持された非再現性秘密情報ｋからコミットメントｒを
【００６８】
【数９】
ｒ＝π（ｋp）
として計算し、記憶部３０２に保持する。
【００６９】
もちろん、πが恒等写像である場合は、π計算部３０６は不要である。
［３］入出力部３０１を用いて、記憶部３０２に保持されたコミットメントｒを出力する。
［４］入出力部３０１を用いて、チャレンジχを入力し、記憶部３０２に保持する。
［５］入出力部３０１を用いて、ドキュメントｍを入力し、記憶部３０２に保持する。
［６］ドキュメント処理部３０３を用いて、記憶部３０２に保持されたドキュメントｍに応じた処理を行なう。
［７］対話装置固有の秘密関数ｆの計算部３０７を用いて、記憶部３０２に保持されたドキュメントｍからドキュメント秘密情報μ∈Ｇを
【００７０】
【数１０】
μ＝ｆ（ｍ）
として計算し、記憶部３０２に保持する。
【００７１】
関数ｆの計算部３０７は、例えば、対話装置固有の秘密情報ｄの記憶部３０２とハッシュ関数ｈの計算部とで構成し、
【００７２】
【数１１】
ｆ（ｍ）＝ｈ（ｄ｜ｍ）
を計算するようにしても良い。ここで、「｜」はビットの連結を表す。
［８］メッセージ生成部３０９を用いて、メッセージＭを生成し、記憶部３０２に保持する。
［９］φの計算部３０８を用いて、記憶部３０２に保持されたチャレンジχとメッセージＭから指数ｃを
【００７３】
【数１２】
ｃ＝φ（χ，Ｍ）
として計算し、記憶部３０２に保持する。
［１０］Ｇにおける算法実行部３０５を用いて、記憶部３０２に保持された非再現性秘密情報ｋとドキュメント秘密情報μと指数ｃからレスポンスσを
【００７４】
【数１３】
σ＝ｋμc
として計算し、記憶部３０２に保持する。［１１］入出力部３０１を用いて、記憶部３０２に保持されたメッセージＭとレスポンスσを出力する。  動作［６］は、応用によっては、必ずしも必須ではない。したがって、ドキュメント処理部３０３を持たない対話装置３００の構成も可能である。  ドキュメント処理部３０３を設けることによって、対話毎に対話装置３００の実行する処理を可変にでき、後述するチケットに多様な機能性を付与することができるようになる。
【００７５】
［動作の実行順序についての制約］
動作１ないし動作１１は、必ずしもこの順序で逐次的になされる必要はない。動作「い」が動作「こ」に先だって実行されなければならないという順序関係を
【００７６】
【数１４】
い→こ
で表すものとして、諸動作の実行順序についての制約を説明する。
【００７７】
【数１５】
１→２→３→４
５→６，７
４，８→９
７，９→１０→１１
は常に満たされなければならない実行順序についての制約となっている。
【００７８】
ドキュメント処理部３０３の動作が他の動作に影響を与える場合は、さらに、以下に説明するような実行順序の制約が生じる。
【００７９】
［Ｇ，ｐ，πが可変な場合］
ドキュメントｍが、Ｇを規定する場合、６→２が要請される。これは、ドキュメントｍにＧを規定するパラメターが記述されており、動作［６］において、これらのパラメターが設定され、Ｇにおける算法実行部は設定されたパラメタータにしたがって計算を行なえるように構成した場合である。
【００８０】
ドキュメントｍが、ｐを規定する場合、６→２が要請される。これは、ドキュメントｍにｐを規定するパラメターが記述されており、動作［６］において、これらのパラメターが設定され、Ｇにおける算法実行部は設定されたパラメターにしたがって計算を行なえるように構成した場合である。
【００８１】
ドキュメントｍが、πを規定する場合、６→２が要請される。これは、ドキュメントｍにπを規定するパラメターが記述されており、動作［６］において、このパラメターが設定され、πの計算部は設定されたパラメターにしたがって計算を行なえるように構成した場合である。
【００８２】
これらの例では、Ｇ，ｐ，πは対話の都度に可変だが、これらを固定する構成も、もちろん可能である。
【００８３】
［冪計算の事前実行］
ここでは、Ｇ，ｐ，πは固定されたものとする。
【００８４】
記憶部３０２に非再現性秘密情報とコミットメントの組（ｋ，ｒ）を複数保持することができるならば、動作［１］および動作［２］をこの順序で予め繰り返し実行しておくことによって、チャレンジχが入力される直前にコミットメントｒを生成しなくて良いので、対話装置の対話に要する時間を短縮することができる。
【００８５】
また、対話装置の装置毎に固有な部分は秘密関数ｆのみであり、コミットメントｒの生成部分を分離して共有化することができる。
【００８６】
図８は冪計算部を分離した構成を示している。この構成例では、対話装置３００は、レスポンス生成部３１０およびコミットメント生成部３１１に分かれ、動作［１］および動作［２］はコミットメント生成部３１１において行なわれる。なお、図８において図３に対応する箇所には対応する符号を付した。
【００８７】
コミットメント生成部３１１からレスポンス生成部３１０に、非再現性秘密情報ｋが秘密通信によって伝達される。
【００８８】
レスポンス生成部をスマートカードとして構成しても良い。
【００８９】
［レスポンス生成の条件が可変な場合］
ドキュメントｍが、レスポンス生成の条件を規定する場合、これは、ドキュメントｍにレスポンス生成の条件が記述されており、動作［６］において、条件が満たされなければ、処理を中断するように構成すれば良い。
【００９０】
ドキュメントｍに応じた処理の具体例を述べる。
【００９１】
例えば、ドキュメントｍにレスポンスの生成を許すチャレンジχの条件が記述されており、動作［６］において、情報記憶部３０２に保持されたチャレンジχが条件を満たされなければ対話装置３００の処理を中断するように構成する。
【００９２】
レスポンスの生成を許すチャレンジの条件の例を挙げる。ドキュメントｍにレスポンス生成の有効期限を規定するパラメターが記述されており、また、チャレンジχをビット列として表現した場合の特定のビットフィールドを現在時刻の表現と見なし、有効期限と現在時刻を比較し、有効期限を過ぎていた場合は対話装置３００の処理を中断するように構成する。
【００９３】
また、例えば、ドキュメント処理部３０３が現在時刻を保持する計時部を持ち、ドキュメントｍにレスポンス生成の有効期限を規定するパラメターが記述されており、動作［６］において、有効期限と現在時刻を比較し、有効期限を過ぎていた場合は対話装置３００の処理を中断するように構成する。
【００９４】
また、例えば、ドキュメント処理部３０３がカウンターを持ち、ドキュメントｍにカウンターの値をディクリメントするかしないかを規定するフラグが記述されており、動作［６］において、フラグがディクリメントを指示した場合、カウンターの値が０でなければ、カウンターの値を１だけディクリメントし、０であれば対話装置３００の処理を中断するように構成する。
【００９５】
また、例えば、ドキュメント処理部３０３がカウンターを持ち、ドキュメントｍにカウンターをディクリメントする値が記述されており、動作［６］において、カウンターの値がディクリメントする値より小さくなければカウンターの値を指示された値だけディクリメントし、そうでなければ対話装置３００の処理を中断するように構成する。
【００９６】
また、例えば、ドキュメント処理部３０３が複数のカウンターを持ち、ドキュメントｍに対応するカウンターを規定するポインターが記述されており、動作［６］において、規定されたカウンターの値が０でなければ、カウンターの値を１だけディクリメントし、０であれば対話装置３００の処理を中断するように構成する。
【００９７】
また、例えば、ドキュメント処理部３０３が複数のカウンターを持ち、ドキュメントｍに対応するカウンターを規定するポインターとディクリメントする値が記述されており、動作［６］において、規定されたカウンターの値がディクリメントする値より小さくなければカウンターの値を指示された値だけディクリメントし、そうでなければ対話装置３００の処理を中断するように構成する。
【００９８】
［メッセージの生成方法がドキュメントに規定される場合］
ドキュメントｍが、メッセージ生成の方法を規定する場合、これは、ドキュメントｍにメッセージ生成を規定するパラメターが記述されており、動作［６］において、これらのパラメターが設定され、メッセージ生成部３０９は設定されたパラメターにしたがってメッセージ生成を行なえるように構成した場合である。
【００９９】
ドキュメントｍに応じた処理の具体例を述べる。
【０１００】
最も簡単なものは、メッセージＭがドキュメントｍの関数として決まる場合、例えば、ドキュメントｍの特定のビットフィールドをメッセージＭとするように構成する。
【０１０１】
例えば、ドキュメントｍにレスポンスの生成を許すチャレンジχの条件が記述されており、動作［６］において、情報記憶部３０２に保持されたチャレンジχが条件を満たされなければ対話装置３００の処理を中断するように構成する。
【０１０２】
レスポンスの生成を許すチャレンジの条件の例を挙げる。ドキュメントｍにレスポンス生成の有効期限を規定するパラメターが記述されており、また、チャレンジχをビット列として表現した場合の特定のビットフィールドを現在時刻の表現と見なし、有効期限と現在時刻を比較し、有効期限を過ぎていた場合は対話装置３００の処理を中断するように構成する。
【０１０３】
また、例えば、ドキュメント処理部３０３が現在時刻を保持する計時部を持ち、ドキュメントｍにレスポンス生成の有効期限を規定するパラメターが記述されており、動作［６］において、有効期限と現在時刻を比較し、有効期限を過ぎていた場合は対話装置３００の処理を中断するように構成する。
【０１０４】
また、例えば、ドキュメント処理部３０３がカウンターを持ち、ドキュメントｍにカウンターの値をディクリメントするかしないかを規定するフラグが記述されており、動作［６］において、フラグがディクリメントを指示した場合、カウンターの値が０でなければ、カウンターの値を１だけディクリメントし、メッセージ生成部３０９の保持するフラグ（ディクリメントに成功に成功したか否か）をオンにし、カウンターの値が０であれば、メッセージ生成部３０９の保持するフラグをオフにして、メッセージ生成部３０９は、メッセージをカウンターの値とディクリメントに成功したか否かのフラグの値の組として生成するように構成する。
【０１０５】
また、例えば、ドキュメント処理部３０３がカウンターを持ち、ドキュメントｍにカウンターをディクリメントする値が記述されており、動作［６］において、カウンターの値がディクリメントする値より小さくなければカウンターの値を指示された値だけディクリメントし、メッセージ生成部３０９の保持するフラグ（ディクリメントに成功に成功したか否か）をオンにし、カウンターの値がディクリメントする値より小さければメッセージ生成部３０９の保持するフラグをオフにして、メッセージ生成部３０９は、メッセージをカウンターの値とディクリメントに成功したか否かのフラグの値の組として生成するように構成する。
【０１０６】
また、例えば、ドキュメント処理部３０３が複数のカウンターを持ち、ドキュメントｍに対応するカウンターを規定するポインターが記述されており、動作［６］において、規定されたカウンターの値が０でなければ、カウンターの値を１だけディクリメントし、メッセージ生成部３０９の保持するフラグをオンにし、規定されたカウンターの値が０であれば、メッセージ生成部３０９の保持するフラグをオフにして、メッセージ生成部３０９は、メッセージを規定されたカウンターの値とフラグの値の組として生成するように構成する。
【０１０７】
また、例えば、ドキュメント処理部３０３が複数のカウンターを持ち、ドキュメントｍに対応するカウンターを規定するポインターとディクリメントする値が記述されており、動作［６］において、規定されたカウンターの値がディクリメントする値より小さくなければカウンターの値を指示された値だけディクリメントし、メッセージ生成部３０９の保持するフラグをオンにし、規定されたカウンターの値がディクリメントする値より小さければメッセージ生成部３０９の保持するフラグをオフにして、メッセージ生成部３０９は、メッセージを規定されたカウンターの値とフラグの値の組として生成するように構成する。
【０１０８】
［ドキュメント処理のその他の例］
例えば、ドキュメント処理部３０３がカウンターを持ち、ドキュメントｍにインクリメントする値が記述されており、動作［６］において、カウンターの値を指示された値だけインクリメントするように構成する。
【０１０９】
また、例えば、ドキュメント処理部３０３が複数のカウンターを持ち、ドキュメントｍに対応するカウンターを規定するポインターとインクリメントする値が記述されており、動作［６］において、規定されたカウンターの値を指示された値だけインクリメントするように構成する。
【０１１０】
また、例えば、ドキュメント処理部３０３が現在時刻を保持する計時部と履歴の保持部を持ち、ドキュメントｍに履歴を記録するか記録しないかを規定するフラグが記述されており、動作［６］において、フラグが履歴の記録を指示した場合、履歴の保持部に、計時部に保持された現在時刻とドキュメントｍのタプルを保持するように構成する。
【０１１１】
［複数ドキュメントの一括処理］
以上に述べた諸例では、一回の対話において一つのドキュメントｍしか関与しないが、複数のドキュメントｍ1，．．．，ｍNが関与するように構成することも可能である。
【０１１２】
図１０は、複数ドキュメントの一括処理を行なう対話装置の動作を示している。
【０１１３】
複数のドキュメントを一回の対話において扱う場合、動作［５］ないし動作［７］を以下の動作［１０］ないし動作［１２］に置き換えれば良い。
【０１１４】
［１０］入出力部３０１を用いて、ドキュメントｍ1，．．．，ｍNを入力し、記憶部３０２に保持する。
［１１］ドキュメント処理部３０３を用いて、記憶部３０２に保持されたドキュメントｍ1，．．．，ｍNに応じた処理を順次行なう。
［１２］対話装置固有の秘密関数ｆの計算部３０７を用いて、記憶部３０２に保持されたドキュメントｍ1，．．．，ｍNからドキュメント秘密情報μ∈Ｇを
【０１１５】
【数１６】
μ＝ｆ（ｍ1）・・・ｆ（ｍN）
として計算し、記憶部３０２に保持する。
【０１１６】
もちろん、複数のドキュメントを一回の対話において扱う場合には、各ドキュメントｍiに応じた処理の実行結果が競合しないようにしなければならない。
【０１１７】
［チケット発行装置］
チケット発行装置４００は以下の検証情報Ｉおよび認証の特徴情報ｘを利用する。
【０１１８】
【数１７】
Ｉ∈Ｇ            検証情報
ｘ∈Ｇ            認証の特徴情報
とする。ここで、認証の特徴情報ｘと検証情報Ｉとは、Ｉｘp＝１という関係を満たす。
【０１１９】
Ｇの零化域Ａｎｎ（Ｇ）の生成元λを既知とする。ｐがλと互いに素ならば、
【０１２０】
【数１８】
ｐｄ≡１  ｍｏｄ  λ
を満たすｄが計算できるので任意の検証情報Ｉに対して、対応する認証の特徴情報ｘを
【０１２１】
【数１９】
ｘ＝Ｉ-d
として求めることができる。
【０１２２】
ｐ＝２の場合も、Ｇ＝（Ｚ／ｎＺ）*でｎがＢｌｕｍ数ならば、Ｉをほとんど任意に定めることができる。詳しくは、ＦｉａｔとＳｈａｍｉｒによる”Ｈｏｗｔｏ  ｐｒｏｖｅ  ｙｏｕｒｓｅｌｆ：ｐｒａｃｔｉｃａｌ    ｓｏｌｕｔｉｏｎｓｔｏ  ｉｄｅｎｔｉｆｉｃａｔｉｏｎ  ａｎｄ  ｓｉｇｎａｔｕｒｅ  ｐｒｏｂｌｅｍｓ”，Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  ＣＲＹＰＴＯ’８６，Ａ．Ｍ．Ｏｄｌｙｚｋｏ（ｅｄ．），Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，ｐｐ．１８６−１９４を参照されたい。
【０１２３】
図５はチケット発行装置の構成を示し、図６はチケット発行装置の動作を示している。チケット発行装置４００は入出力部４０１、記憶部４０２、Ｇの算法実行部４０３、ｆ計算部４０４を含んで構成されている。以下、チケット発行装置４００の動作を説明する。
［１］入出力部４０１を用いて、認証の特徴情報ｘを入力し、記憶部４０２に保持する。
［２］入出力部４０１を用いて、ドキュメントｍを入力し、記憶部４０２に保持する。
［３］入出力部４０１を用いて、対話装置３００の識別子Ｕを入力し、記憶部４０２に保持する。
［４］記憶部４０２に保持された識別子Ｕに対応する対話装置３００固有の秘密関数ｆの計算部４０４を用いて、記憶部４０２に保持されたドキュメントｍからドキュメント秘密情報μを
【０１２４】
【数２０】
μ＝ｆ（ｍ）
として計算し、記憶部４０２に保持する。
［５］Ｇにおける算法実行部４０３を用いて、記憶部４０２に保持された認証の特徴情報ｘとドキュメント秘密情報μからチケットｔを
【０１２５】
【数２１】
ｔ＝ｘμ-1
として計算し、記憶部４０２に保持する。
［６］入出力部４０１を用いて、記憶部４０２に保持されたチケットｔを出力する。
【０１２６】
対話装置３００固有の秘密関数ｆは、例えば、対話装置の項で述べたように対話装置３００固有の秘密情報ｄとハッシュ関数ｈを用いて、ｆ（ｍ）＝ｈ（ｄ｜ｍ）として計算するようにしても良い。
【０１２７】
対話装置３００固有の秘密情報ｄは、例えば、チケット発行者がランダムに生成し、対話装置３００の識別子Ｕとのタプル（Ｕ，ｄ）を保持するようにしても良い。
【０１２８】
また、チケット発行者の秘密情報Ｄを用いて、対話装置３００の識別子Ｕに対して、対話装置３００固有の秘密情報ｄを
【０１２９】
【数２２】
ｄ＝Ｕ｜Ｄ
としても良い。ただし、このようにｄを生成すると、対話装置３００の耐タンパー性が崩れた場合チケット発行者の秘密情報Ｄが漏洩するという問題をはらんでいる。
【０１３０】
ハッシュ関数ｈを用いて、
【０１３１】
【数２３】
ｄ＝ｈ（Ｕ｜Ｄ）
としてｄを生成すれば、対話装置３００にはＤを保持する必要がなく、ハッシュ関数の一方向性よりｄからＤを求めることは困難であるのでより望ましい。
【０１３２】
ドキュメントｍは、秘密関数ｆの入力値となりえる任意の値を与えることができる。
【０１３３】
さらに、ドキュメントｍは、対話装置の項で述べたように対話装置３００のドキュメント処理部３０３に与える処理を記述するようにしても良い。
【０１３４】
さらに、ドキュメントｍには、チケットを識別する情報を記述するようにしても良い。
【０１３５】
例えば、プロバイダーの識別子やチケットが対応するサービスの識別子、チケット発行順に振られるシーケンシャルＩＤが含まれても良い。
【０１３６】
また、例えば、チケットの発行者が認証の特徴情報ｘとその識別子を管理し、その識別子を含ませるようにしても良い。
【０１３７】
また、例えば、認証の特徴情報ｘに対応する公開情報Ｉから定まる値を含ませるようにしても良い。
【０１３８】
［チケット合成方法］
ここでは、Ｇ，ｐ，πはシステムに共通であり、対話装置３００は複数ドキュメントに対応するものとする。
【０１３９】
ｔ1，．．．，ｔN∈Ｇを、固有の秘密関数ｆを持つ対話装置３００に対して生成されたチケットとし、１≦ｉ≦Ｎに対して、Ｉi∈Ｇを各チケットｔiに対応する検証情報とする。
【０１４０】
合成された検証情報Ｉ＝Ｉ1・・・ＩNに対応する合成されたチケットｔを
【０１４１】
【数２４】
ｔ＝ｔ1・・・ｔN
として生成することができる。
【０１４２】
チケットｔiにドキュメントｍiが対応し、検証情報Ｉiに認証の特徴情報ｘiが対応している、つまり、Ｉiｘi P＝１とすると、ドキュメントｍiに対応するドキュメント秘密情報μi＝ｆ（ｍi）は
【０１４３】
【数２５】
μi＝ｔi -1ｘi
なので、ｘ＝ｘ1・・・ｘNとすると、ｘは合成された検証情報Ｉに対応する認証の特徴情報、つまり、Ｉｘp＝１であり、複数ドキュメントｍ1，．．．，ｍNに対応するドキュメント秘密情報μ＝ｆ（ｍ1）・・・ｆ（ｍN）は
【０１４４】
【数２６】
μｔ-1ｘ
を満たしている。
【０１４５】
［チケットを用いた証明方法］
図１１はチケットを用いた証明方法の流れを示している。
【０１４６】
以下、チケットと対話装置を用いた証明方法を説明する。
【０１４７】
利用者は、秘密関数ｆで特徴付けられる対話装置とｔ＝ｘｆ（ｍ）-1を満たすドキュメントｍとチケットｔを保持するものとする。
【０１４８】
コミットメントｒと、チャレンジχに対するメッセージＭとレスポンスｓを生成する方法は以下のとおり。
【０１４９】
［１］対話装置３００を用いて、コミットメントｒを取得する。
［２］対話装置３００を用いて、ドキュメントｍとチャレンジχに対応するメッセージＭとレスポンスσを取得する。
［３］チャレンジχと取得したメッセージＭより指数ｃをｃ＝φ（χ，Ｍ）として計算する。
【０１５０】
［４］チケットｔと指数ｃと取得したレスポンスσよりレスポンスｓを
【０１５１】
【数２７】
ｓ＝ｔcσ
として計算する。
このとき、（ｒ，χ，Ｍ，ｓ）は
【０１５２】
【数２８】
0003812123.tif 000006
を満たしている。
【０１５３】
このようにして、利用者に認証の特徴情報ｘを知らすことなく、対話装置３００とチケットｔを用いることによって、検証情報Ｉに対応する図１に記載の証明者の機能を頒布することができる。
【０１５４】
この証明者に対応する検証者は、図１に記載された従来例と全く同一なので、検証装置は唯一の検証情報Ｉを保持する必要があるだけで、極めて小規模な装置で多数の利用者の認証を、完結して行なうことができる。
【０１５５】
［Ｆｉａｔ−Ｓｈａｍｉｒ認証］
特に、ｐ＝２の場合、
【０１５６】
【数２９】
ｒ＝π（ｓ2Ｉc）
を満たしており、いわゆるＦｉａｔ−Ｓｈａｍｉｒ認証の関係を満たしている。
【０１５７】
このようにして、利用者に秘密情報ｘを知らすことなく、対話装置とチケットｔを用いることによって、検証情報Ｉに対応するＦｉａｔ−Ｓｈａｍｉｒ認証の証明者の機能を頒布することができる。
【０１５８】
なお、Ｆｉａｔ−Ｓｈａｍｉｒ認証の詳細については、前述の”Ｈｏｗ  ｔｏｐｒｏｖｅ  ｙｏｕｒｓｅｌｆ：ｐｒａｃｔｉｃａｌ    ｓｏｌｕｔｉｏｎｓｔｏ  ｉｄｅｎｔｉｆｉｃａｔｉｏｎ  ａｎｄ  ｓｉｇｎａｔｕｒｅ  ｐｒｏｂｌｅｍｓ”を参照されたい。
【０１５９】
［Ｇｕｉｌｌｏｕ−Ｑｕｉｓｑｕａｔｅｒ認証］
特に、ｐがＧの零化域の生成元λと互いに素な場合、利用者はＧｕｉｌｌｏｕ−Ｑｕｉｓｑｕａｔｅｒ認証の証明者としてふるまったことになる。
【０１６０】
このようにして、利用者に秘密情報ｘを知らすことなく、対話装置とチケットｔを用いることによって、検証情報Ｉに対応するＧｕｉｌｌｏｕ−Ｑｕｉｓｑｕａｔｅｒ認証の証明者の機能を頒布することができる。
【０１６１】
［チケット検証装置］
図９はチケット検証装置の構成を示し、図７はチケット検証装置の動作を示している。
【０１６２】
チケット検証装置は、対話装置と対話を行なうことによってチケットの検証を行なう。チケット検証装置５００は入出力部５０１、記憶部５０２、乱数生成部５０３、Ｇの算法実行部５０４、π計算部５０５、φ計算部５０６を含んで構成されている。
【０１６３】
以下、チケット検証装置５００の動作を説明する。
【０１６４】
チケット検証装置５００は、検証情報Ｉとチケットｔを記憶部５０２に保持している。
【０１６５】
［１］入出力部５０１を用いて、コミットメントｒを入力し、記憶部５０２に保持する。
［２］乱数生成部５０３を用いて、チャレンジχを生成し、記憶部５０２に保持する。
［３］入出力部５０１を用いて、記憶部５０２に保持されたチャレンジχを出力する。
［４］入出力部５０１を用いて、メッセージＭとレスポンスσを入力し、記憶部５０２に保持する。
［５］φの計算部５０６を用いて、記憶部５０２に保持されたチャレンジχとメッセージＭより指数ｃをｃ＝φ（χ，Ｍ）として計算し、記憶部５０２に保持する。
【０１６６】
［６］Ｇにおける算法実行部５０４と、必要ならば、πの計算部５０５を用いて、記憶部５０２に保持されたｃ，σ，Ｉとチケットｔから
【０１６７】
【数３０】
ｒ’＝π（（ｔcσ）pＩc）
を計算し、記憶部５０２に保持する。
【０１６８】
もちろん、πが恒等写像である場合は、πの計算部５０５は不要である。
【０１６９】
また、ｒ’は、例えば、ｒ’＝π（（ｔpＩ）cσp）
として計算しても構わない。
【０１７０】
［７］記憶部５０２に保持されたｒ，ｒ’を比較する。
【０１７１】
チケットｔがドキュメント秘密情報μと認証の特徴情報ｘに対応したものであるならば
【０１７２】
【数３１】
μ＝ｔ-1ｘ
を満たしており、ドキュメント秘密情報μに基づいた対話では、（ｒ，χ，Ｍ，σ）は
【０１７３】
【数３２】
0003812123.tif 000007
0003812123.tif 000008
を満たしている。したがって、秘密関数ｆがμ＝ｆ（ｍ）を満たす対話装置３００と検証装置５００との対話のときにはｒ＝ｒ’が満たされる。
【０１７４】
［チケットが可変な構成］
ここでは、入出力部５０１にチケットを入力し、入力されたチケットを記憶部５０２に保持する構成を述べる。
【０１７５】
動作［１］ないし動作［６］に先だって、チケット検証装置５００は、以下の動作を実行する。
【０１７６】
［８］入出力部５０１を用いて、チケットｔを入力し、記憶部５０２に保持する。
【０１７７】
このように構成することによって複数のチケットの検証を行なうことができる。
【０１７８】
また、コミットメントの空間Ｒとチャレンジの空間Ｃとが等しく、指数を生成する関数φがハッシュ関数ｈを用いて
【０１７９】
【数３３】
φ（χ，Ｍ）＝ｈ（χ｜Ｍ）
である場合、チャレンジχをコミットメントｒそのもの、つまり、χ＝ｒとして、検証に成功した対話に対して、署名（Ｍ，Ｒ，ｓ）を検証の履歴として記憶部に保持するように構成しても良い。
【０１８０】
このように構成することによってチケットの検証を確かに行なったことを第三者に証明することができる。
【０１８１】
もちろん、第三者が署名（Ｍ，Ｒ，ｓ）を検証する際の検証式は、
【０１８２】
【数３４】
0003812123.tif 000009
である。
【０１８３】
［応用例：メンバーズカード］
以上に述べてきた対話装置３００とチケットを用いた証明者の機能を、実際の応用上の局面に適用した例について述べる。
【０１８４】
まず、メンバーズカードに適用した例を図１２を用いて説明する。この応用例では、認証の特徴情報ｘをあるサービスに対応させ、チケットはそのサービスの利用資格であり、証明時に伝達されるメッセージはサービス名称とサービス利用者としての識別子、つまり、会員番号に対応する。
【０１８５】
この応用例におけるチケットは、通常、プラスティックのカード等で実現されているメンバーズカード等をビット列で実現するものである。
【０１８６】
チケット発行者はサービス提供者であり、メンバーズカード検証器１０００を（１）スマートカードリーダー５１０
（２）会員番号表示部５１１
（３）スマートカードリーダー内のＲＯＭに焼き付けられたプログラムとして実現されたチケット検証器５００
によって構成する。
【０１８７】
表示部５１１は、チケット検証に成功した場合、伝達されたメッセージ、つまり、会員番号の表示を行ない、チケット検証に失敗した場合はエラー表示を行なう。
【０１８８】
スマートカードリーダー５１０は、スマートカードを挿入するスロットを持ち、スマートカードとの通信を行なう。
【０１８９】
サービス利用者は、チケット保持部３１２、ドキュメント保持部３１３および対話装置３００からなるスマートカード２０００を所有するものとする。
【０１９０】
サービス利用者は、会員登録を行なう際、自分の所有する対話装置３００の識別子を提示して、その対話装置３００に対応するチケットを発行してもらい、例えば、所有するスマートカード２０００にドキュメントと併せて入力する。
【０１９１】
ドキュメントは、サービス名称（例えば”Ｘｅｒｏｘ  Ｃｌｕｂ”）を表すフィールドと会員番号（例えば”００１７  ２５７  ６５５３７”）を表すフィールドとからなる。
【０１９２】
サービスを利用する場合、利用者はメンバーズカード検証器１０００にスマートカード２０００を挿入し、チケット認証を行なう。
【０１９３】
ここで、対話装置３００の生成するメッセージはドキュメントそのものとなるように構成する。
【０１９４】
チケットおよびドキュメントをメンバーズカード検証器１０００に入力するスマートカードリーダー５１０とは異なる入力手段を設ければ、チケットやドキュメントは必ずしもスマートカード２０００に保持しておく必要はない。
【０１９５】
例えば、利用者は対話装置３００のみからなるスマートカード２０００を携帯し、チケットやドキュメントはスマートカード２０００とは異なる携帯型情報機器に保持したり、自宅のＰＣに保持し、利用時に携帯型通信機器を用いて取得するようにしても良い。
【０１９６】
また、チケットの発行は、必ずしも会員登録の際に行なわなくとも、利用者が既に保持していたプラステックのメンバーズカードと代替するようにしても良い。
【０１９７】
また、チケット発行者をサービス提供者とは独立に設け、サービス提供者がサービス利用者にチケットを発行する場合、独立なチケット発行者にチケット発行を委託するようにしても良い。
【０１９８】
チケット発行者を独立して設ければ、多種のサービスに対応するチケットを単一の対話装置３００に対して発行できるので、利用者は唯一の対話装置３００さへ保持していれば、複数のメンバーズカード等を純粋に電子情報としてのみ保持することが可能となる。
【０１９９】
［応用例：プリペイドカード］
つぎにプリペイドカードへの適用例について図１３を参照して説明する。
【０２００】
この応用例では、認証の特徴情報ｘをあるサービスに対応させ、チケットはそのサービスで利用されるプリペイドカードであり、証明時に伝達されるメッセージはプリペイドカードからの引き落としに成功したか否かとプリペイドカードの残高情報である。
【０２０１】
チケット発行者はサービス提供者であり、プリペイドカード取扱器１５００を（１）スマートカードリーダー５１０
（２）引き落とし額入力部５１２
（３）表示部５１３
（４）ＰＩＮ入力部５１４
（５）スマートカードリーダー内のＲＯＭに焼き付けられたプログラムとして実現されたチケット検証器５００
によって構成する。
【０２０２】
スマートカードリーダー５１０は、スマートカード２０００を挿入するスロットを持ち、スマートカード２０００との通信を行なう。
【０２０３】
引き落とし額入力部５１２は、例えば、テンキーによって構成され、引き落とし額の入力を行なう。
【０２０４】
表示部５１３は、引き落とし額入力部５１２で入力された引き落とし額を表示し、ついで、チケット検証に成功した場合、伝達されたメッセージ、つまり、引き落としに成功したか否かとプリペイドカードの残高の表示を行ない、チケット検証に失敗した場合はエラー表示を行なう。
【０２０５】
ＰＩＮ入力部５１４は、例えば、テンキーによって構成され、利用者によるＰＩＮの入力を行なう。
【０２０６】
サービス利用者は、チケット保持部３１２と対話装置３００からなるスマートカード２０００を所有するものとする。
【０２０７】
サービス利用者は、プリペイドカードの購入を行なう際、自分の所有する対話装置３００の識別子とプリペイドカードに対応付けるＰＩＮとプリペイドカードの額面を提示して、その対話装置３００に対応するチケットを発行してもらい、例えば、所有するスマートカード２０００に入力し、また、対話装置３００のカウンターにプリペイドカードの額面情報を設定する。
【０２０８】
ドキュメントは、サービス名称（例えば、”Ｘｅｒｏｘ  Ｓｔｏｒｅ”）を表すフィールドとＰＩＮ（例えば、”０９１７”）を表すフィールドとからなる。
【０２０９】
サービスを利用する場合、利用者はプリペイドカード取扱器１５００にスマートカード２０００を挿入し、チケット認証を行なう。
【０２１０】
まず、スマートカードリーダー５１０はスマートカード２０００に保持されたチケットを取得し、チケット検証器５００に設定し、対話を開始する。
【０２１１】
チケット検証器５００の送信するチャレンジの特定のビットフィールドに引き落とし額入力部５１２で入力された引き落とし額（例えば、”３５０”円）を埋め込み、また、サービス名称（例えば、”Ｘｅｒｏｘ  Ｓｔｏｒｅ”）とＰＩＮ入力部５１４より入力されたＰＩＮ（例えば、”０９１７”）を併せてドキュメントとして対話装置３００に入力する。
【０２１２】
対話装置３００のメッセージ生成部３０９（図３）が、チャレンジに埋め込まれた引き落とし額がカウンタの値（例えば、”２０００”円）より大きくなければカウンタの値を引き落とし額だけディクリメントし（つまり、”１６５０”円）、メッセージとして引き落としの成功（”ＯＫ”）とカウンタ残高（”１６５０”円）を生成する。引き落とし額がカウンタの値より大きい場合は、カウンタのディクリメントは行なわず、メッセージとして引き落としの失敗（”ＮＧ”）とカウンタ残高を生成する。
【０２１３】
チケット検証器５００は、送られたメッセージを検証し、引き落としに失敗した場合は、例えば、カード残高分のみをカードより引き落とし、差額分は現金で支払ってもらう。
【０２１４】
【発明の効果】
以上、説明してきたように、本発明は、公開鍵暗号における認証の特徴情報を開示することなく、認証の特徴情報に基づいた証明の機能を配布することができる。したがって、従来不可能であった、利害関係を持たない複数の個人が同一の認証の特徴情報に基づいた証明を安全に行なえるようになった。このことは、必ずしも個人に帰属しない性格を有するチケットを、そのまま、公開鍵暗号の認証の特徴情報に対応付けることを可能にし、チケットの検証側は、公開された唯一の検証情報に基づき公開された手順で、チケットの真贋を判定するのみで検証を行なえるので検証側の負担を大幅に軽減できる。また、チケットの所持を証明する利用者側から見ても、検証側の有する先に述べた特質は、検証側の公正が確認でき、チケットの検証に伴って個人の特定がなされない（なぜならば個人に帰属しない認証の特徴情報のみが検証に関わるので）ことなどの効用がある。さらに、利用者にとっては、チケットおよび対話装置はチケット発行者のみに理解し得るブラックボックスであり、チケットを対話装置に入力するならば、認証方式を実現するのには関与していなコバートチャネルが存在しないことを確信できないが、本発明においては、対話装置への情報伝達は、利用者にも完全な解釈を許してもプロテクト側の安全性を損ねないドキュメントとして実現し、ブラックボックスであるチケットをブラックボックスである対話装置に入力することもない。
【０２１５】
また、本発明においては、Ｇｕｉｌｌｏｕ−Ｑｕｉｓｑｕａｔｅｒ認証をベースの公開鍵暗号として採用しているが、Ｇｕｉｌｌｏｕ−Ｑｕｉｓｑｕａｔｅｒ認証はＧｕｉｌｌｏｕとＱｕｉｓｑｕａｔｅｒにより”Ａ  ’ｐａｒａｄｏｘｉｃａｌ’  ｉｄｅｎｔｉｔｙ−ｂａｓｅｄ  ｓｉｇｎａｔｕｒｅ  ｓｃｈｅｍｅｒｅｓｕｌｔｉｎｇ  ｆｒｏｍ  ｚｅｒｏ−ｋｎｏｗｌｅｄｇｅ”，Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  ＣＲＹＰＴ’８８，Ｓ．Ｇｏｌｄｗａｓｓｅｒ（ｅｄ．），Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，ｐｐ．２１６−２３１において零知識性が証明されている。
【図面の簡単な説明】
【図１】  従来技術に係わる認証方法の原理を示す図である。
【図２】  全体の構成を示す図である。
【図３】  対話装置の構成を示す図である。
【図４】  対話装置の動作を示す図である。
【図５】  チケット発行装置の構成を示す図である。
【図６】  チケット発行装置の動作を示す図である。
【図７】  チケット検証装置の動作を示す図である。
【図８】  対話装置の構成を示す図である。
【図９】  チケット検証装置の構成をを示す図である。
【図１０】  対話装置の動作を示す図である。
【図１１】  チケットを用いた証明方法の原理を示す図である。
【図１２】  応用例の構成を示す図である。
【図１３】  応用例の構成を示す図である。
【符号の説明】
１００    検証者
２００    証明者
３００    対話装置
３０１    対話装置の入出力部
３０２    対話装置の記憶部
３０３    対話装置のドキュメント処理部
３０４    対話装置の乱数生成部
３０５    対話装置のＧの算法実行部
３０６    対話装置のπ計算部
３０７    対話装置のｆ計算部
３０８    対話装置のφ計算部
３０９    対話装置のメッセージ生成部
３１０    対話装置のレスポンス生成部
３１１    対話装置のコミットメント生成部
３１２    チケット保持部
３１３    ドキュメント保持部
４００    チケット発行装置
４０１    チケット発行装置の入出力部
４０２    チケット発行装置の記憶部
４０３    チケット発行装置のＧの算法実行部
４０４    チケット発行装置のｆ計算部
５００    チケット検証装置
５０１    チケット検証装置の入出力部
５０２    チケット検証装置の記憶部
５０３    チケット検証装置の乱数生成部
５０４    チケット検証装置のＧの算法実行部
５０５    チケット検証装置のπ計算部
５０６    チケット検証装置のφ計算部
５１０    スマートカードリーダー
５１１    会員番号表示部
５１２    引き落とし額入力部
５１３    表示部
５１４    ＰＩＮ入力部
１０００    メンバーズカード検証器
１５００    プリペイカード取扱器
２０００    スマートカード
【図１】
0003812123.tif 000011
【図２】
0003812123.tif 000012
【図３】
0003812123.tif 000013
【図４】
0003812123.tif 000014
【図５】
0003812123.tif 000015
【図６】
0003812123.tif 000016
【図７】
0003812123.tif 000017
【図８】
0003812123.tif 000018
【図９】
0003812123.tif 000019
【図１０】
0003812123.tif 000020
【図１１】
0003812123.tif 000021
【図１２】
0003812123.tif 000022
【図１３】
0003812123.tif 000023