(57)【要約】【課題】サービスプロバイダのサービスにアクセスすることを可能とする方法及び装置を提供する。【解決手段】外部サービスプロバイダを通じて所望のサービスを要求する工程と、ハッシュツリー及びハッシュツリーのルート値のデジタル署名を生成する工程と、デジタル署名及びルート値を外部サービスプロバイダに送信する工程と、外部サービスプロバイダがデジタル署名を受け付けた場合に、一又は複数のトークンを次のパケットとともに外部サービスプロバイダに提供する工程と、外部サービスプロバイダがトークンを受け付けている間において、所望のサービスの利用を継続する工程とを方法が含む。【選択図】図１
2007505555.tif 000002
【特許請求の範囲】
【請求項１】
外部サービスプロバイダを通じて所望のサービスを要求する工程と、
ハッシュツリー及び前記ハッシュツリーのルート値のデジタル署名を生成する工程と、
前記デジタル署名及び前記ルート値を前記外部サービスプロバイダに送信する工程と、
前記外部サービスプロバイダが前記デジタル署名を受け付けた場合に、一又は複数のトークンを次のパケットとともに前記外部サービスプロバイダに提供する工程と、
前記外部サービスプロバイダが前記トークンを受け付けている間において、前記所望のサービスの利用を継続する工程とを含むことを特徴とする方法。
【請求項２】
ユーザ装置が一又は複数の前記トークンを生成する工程を含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記ユーザ装置が前記ハッシュツリーを用いて前記トークンを生成することを特徴とする請求項２に記載の方法。
【請求項４】
前記ハッシュツリーは、密ハッシュツリーであり、
前記密ハッシュツリーを構築する工程をさらに含み、
前記密ハッシュツリーは、
必要であると算出された前記トークンの数と同数である複数のビット列をランダムに生成し、
算出された前記トークンに１を加えた数と同数である複数の葉を有する二分木を構築し、
ランダムな前記ビット列を前記葉に割り当て、
内部ノードの子の値に従って各内部ノードに割り当てられる値を演算することによって構築されることを特徴とする請求項３に記載の方法。
【請求項５】
前記複数のビット列を生成する工程は、一の種から前記複数のビット列を生成する工程を含むことを特徴とする請求項４に記載の方法。
【請求項６】
前記ランダムなビット列は、暗号化に適した長さを有することを特徴とする請求項４に記載の方法。
【請求項７】
前記ハッシュツリーは、マークルツリー及び密ハッシュツリーによって構成されるグループの中から選択されたものであることを特徴とする請求項３に記載の方法。
【請求項８】
ユーザ装置が、公開鍵署名を用いて前記ハッシュツリーの前記ルートに署名する公開鍵署名手順を用いて、一又は複数の前記トークンを生成することを特徴とする請求項１に記載の方法。
【請求項９】
秘密鍵を用いて前記ハッシュツリーの前記ルート値の前記デジタル署名を生成する工程を含むことを特徴とする請求項１に記載の方法。
【請求項１０】
ユーザ装置が、前記トークンの宛先となる前記外部サービスプロバイダの識別情報によって構成される一又は複数のグループ、前記外部サービスプロバイダが受信する前記トークンの最大値、及び、前記トークンの対価を受け取る前に前記外部サービスプロバイダが満たすべき条件を、一又は複数の前記トークンのそれぞれに含めることを特徴とする請求項１に記載の方法。
【請求項１１】
前記ハッシュツリーの前記ルート値の前記デジタル署名と、ユーザ装置の公開鍵と、前記ユーザと当該ユーザのサービスプロバイダとの関係を証明する信頼された機関から受け取る証明書とを前記外部サービスプロバイダに送信する工程を含むことを特徴とする請求項１に記載の方法。
【請求項１２】
前記トークンは、支払いの否認が不可能なトークンであることを特徴とする請求項１に記載の方法。
【請求項１３】
密ハッシュツリーを生成する工程と、
署名のためにホームサービスプロバイダに前記ルート値を提供する工程と、
前記密ハッシュツリーの金銭の値を前記ホームサービスプロバイダに通知する工程と、
前記密ハッシュツリーに基づいて金銭を前記外部サービスプロバイダに提供する工程を含むことを特徴とする請求項１に記載の方法。
【請求項１４】
外部サービスプロバイダを通じて所望のサービスを要求する外部ネットワークインターフェースと、
記憶部と、
前記外部ネットワークインターフェース及び前記記憶部に接続された制御部とを備え、
前記制御部は、
ハッシュツリー及び前記ハッシュツリーのルート値のデジタル署名を、前記記憶部を用いて生成し、
前記外部ネットワークインターフェースを介して、前記デジタル署名及び前記ルート値を前記外部サービスプロバイダに送信し、
前記外部サービスプロバイダが前記デジタル署名を受け付けた場合に、一又は複数のトークンを次のパケットとともに前記外部サービスプロバイダに提供し、
前記外部サービスプロバイダが前記トークンを受け付けている間において、前記所望のサービスの利用を継続することを特徴とする装置。
【請求項１５】
ユーザ装置が一又は複数の前記トークンを生成することを特徴とする請求項１４に記載の装置。
【請求項１６】
前記ユーザ装置が前記ハッシュツリーを用いて前記トークンを生成することを特徴とする請求項１５に記載の装置。
【請求項１７】
前記ハッシュツリーは、マークルツリー及び密ハッシュツリーによって構成されるグループの中から選択されたものであることを特徴とする請求項１６に記載の装置。
【請求項１８】
前記制御部は、公開鍵署名を用いて前記ハッシュツリーの前記ルートに署名する公開鍵署名手順を用いて、一又は複数の前記トークンを生成することを特徴とする請求項１４に記載の装置。
【請求項１９】
前記制御部は、前記トークンの宛先となる前記外部サービスプロバイダの識別情報によって構成される一又は複数のグループ、前記外部サービスプロバイダが受信する前記トークンの最大値、及び、前記トークンの対価を受け取る前に前記外部サービスプロバイダが満たすべき条件を、一又は複数の前記トークンのそれぞれに含めることを特徴とする請求項１４に記載の装置。
【請求項２０】
前記制御部は、前記ハッシュツリーの前記ルート値の前記デジタル署名と、ユーザ装置の公開鍵と、前記ユーザと当該ユーザのサービスプロバイダとの関係を証明する信頼された機関から受け取る証明書とを、前記外部ネットワークインターフェースを介して前記外部サービスプロバイダに送信することを特徴とする請求項１４に記載の装置。
【請求項２１】
前記トークンは、支払いの否認が不可能なトークンであることを特徴とする請求項１４に記載の装置。
【請求項２２】
前記制御部は、
署名のためにホームサービスプロバイダに密ハッシュツリーのルート値を提供し、
前記ホームサービスプロバイダが前記外部サービスプロバイダにサービスの対価を支払うことを可能とする前記密ハッシュツリーの金銭の値を前記ホームサービスプロバイダに通知することを特徴とする請求項１４に記載の装置。
【請求項２３】
外部サービスプロバイダを通じて所望のサービスを要求する手段と、
ハッシュツリー及び前記ハッシュツリーのルート値のデジタル署名を生成する手段と、
前記デジタル署名及び前記ルート値を前記外部サービスプロバイダに送信する手段と、
前記外部サービスプロバイダが前記デジタル署名を受け付けた場合に、一又は複数のトークンを次のパケットとともに前記外部サービスプロバイダに提供する手段と、
前記外部サービスプロバイダが前記トークンを受け付けている間において、前記所望のサービスの利用を継続する手段とを備えることを特徴とする装置。
【請求項２４】
複数の指示を格納する一又は複数の記憶媒体を有しており、システムによって実行される場合に、システムに方法を実行させる製造物であって、
外部サービスプロバイダを通じて所望のサービスを要求する工程と、
ハッシュツリー及び前記ハッシュツリーのルート値のデジタル署名を生成する工程と、
前記デジタル署名及び前記ルート値を前記外部サービスプロバイダに送信する工程と、
前記外部サービスプロバイダが前記デジタル署名を受け付けた場合に、一又は複数のトークンを次のパケットとともに前記外部サービスプロバイダに提供する工程と、
前記外部サービスプロバイダが前記トークンを受け付けている間において、前記所望のサービスの利用を継続する工程とを実行させることを特徴とする製造物。
【請求項２５】
サービスを供給するサービスプロバイダとは異なるサービスプロバイダを有するユーザから前記サービスを要求するサービス要求を受信する工程と、
デジタル署名、ルート値及び証明書を前記ユーザから受信する工程と、
前記デジタル署名が受付可能であり、一又は複数のトークンをユーザから受信したと判定したことに応じて、前記ユーザに前記サービスを提供する工程とを含むことを特徴とする方法。
【請求項２６】
認証アルゴリズムを用いて前記ユーザからの前記デジタル署名を認証することを特徴とする請求項２５に記載の方法。
【請求項２７】
前記認証アルゴリズムは、前記デジタル署名、公開鍵及びメッセージに基づいて、前記デジタル署名が有効であるかを示すブーリーン値を出力することを特徴とする請求項２６に記載の方法。
【請求項２８】
一又は複数の前記トークンは、プレハッシュイメージを含むことを特徴とする請求項２５に記載の方法。
【請求項２９】
前記トークンを受信した後に前記サービスを提供する工程をさらに含むことを特徴とする請求項２５に記載の方法。
【請求項３０】
前記トークンを受信する前に前記サービスを提供する工程をさらに含むことを特徴とする請求項２５に記載の方法。
【請求項３１】
複数の前記トークンの受信に連動して、前記サービスを順次提供する工程をさらに含むことを特徴とする請求項２５に記載の方法。
【請求項３２】
前記トークンは、支払いの否認が不可能なトークンであることを特徴とする請求項２５に記載の方法。
【請求項３３】
前記ユーザの前記デジタル署名及び署名された情報とともに、一又は複数の前記トークンを前記ユーザのホームサービスプロバイダに送信する工程を含むことを特徴とする請求項２５に記載の方法。
【請求項３４】
前記署名された情報は、ハッシュツリーのルート値を含むことを特徴とする請求項３３に記載の方法。
【請求項３５】
受信した複数の前記トークンの一部分を認証するとともに、前記トークンの有効性に関して以前に行われた前記ユーザの不正行為に基づいてポーリングを調整する工程を含むことを特徴とする請求項２５に記載の方法。
【請求項３６】
サービスを供給するサービスプロバイダとは異なるサービスプロバイダを有するユーザ装置から所望のサービスを要求するサービス要求を受信し、デジタル署名、ルート値及び証明書を前記ユーザ装置から受信する外部ネットワークインターフェースと、
プログラム指示を記憶する記憶部と、
外部ネットワークインターフェース及び記憶部に接続された制御部とを備え、
前記制御部は、
前記プログラム指示は、前記デジタル署名が受付可能かを前記制御部に判定させ、一又は複数のトークンを前記制御部に受信させ、前記デジタル署名が受付可能であり、一又は複数の前記トークンをユーザから受信したと判定したことに応じて、前記制御部に前記所望のサービスを前記ユーザに提供させることを特徴とする外部サービスプロバイダ。
【請求項３７】
前記制御部は、認証アルゴリズムを用いて前記ユーザからの前記デジタル署名を認証することを特徴とする請求項３６に記載の外部サービスプロバイダ。
【請求項３８】
一又は複数の前記トークンは、プレハッシュイメージを含むことを特徴とする請求項３６に記載の外部サービスプロバイダ。
【請求項３９】
前記トークンは、支払いの否認が不可能なトークンであることを特徴とする請求項３６に記載の外部サービスプロバイダ。
【請求項４０】
前記制御部は、前記外部ネットワークインターフェースを介して、前記ユーザの前記デジタル署名及び署名された情報とともに、一又は複数の前記トークンを前記ユーザのホームサービスプロバイダに送信することを特徴とする請求項３６に記載の外部サービスプロバイダ。
【請求項４１】
サービスを供給するサービスプロバイダとは異なるサービスプロバイダを有するユーザから前記サービスを要求するサービス要求を受信する手段と、
デジタル署名、ルート値及び証明書を前記ユーザから受信する手段と、
前記デジタル署名が受付可能であり、一又は複数のトークンをユーザから受信したと判定したことに応じて、前記ユーザに前記サービスを提供する手段とを備えることを特徴とする装置。
【請求項４２】
複数の指示を格納する一又は複数の記憶媒体を有しており、システムによって実行される場合に、システムに方法を実行させる製造物であって、
サービスを供給するサービスプロバイダとは異なるサービスプロバイダを有するユーザから前記サービスを要求するサービス要求を受信する工程と、
デジタル署名、ルート値及び証明書を前記ユーザから受信する工程と、
前記デジタル署名が受付可能であり、一又は複数のトークンをユーザから受信したと判定したことに応じて、前記ユーザに前記サービスを提供する工程とを実行させることを特徴とする製造物。
【請求項４３】
ユーザのサービスプロバイダとは異なるサービスプロバイダからユーザトークンを受信する工程と、
前記ユーザトークンが有効であるかを判定する工程と、
前記ユーザトークンが有効である場合に、前記ユーザトークンに基づいて前記ユーザに課金する工程とを含むことを特徴とする方法。
【請求項４４】
前記ユーザトークンが有効でない場合に、問題解決方針に従って処理を進める工程を含むことを特徴とする請求項４３に記載の方法。
【請求項４５】
ユーザのサービスプロバイダとは異なるサービスプロバイダからユーザトークンを受信する外部ネットワークインターフェースと、
プログラム指示を記憶する記憶部と、
前記外部ネットワークインターフェース及び記憶部に接続された制御部とを備え、
前記制御部は、前記ユーザトークンが有効であるかを判定するとともに、前記ユーザトークンが有効である場合に、前記ユーザトークンに基づいて前記ユーザに課金する前記プログラム指示を実行することを特徴とするホームサービスプロバイダ。
【請求項４６】
前記ユーザトークンが有効でない場合に、問題解決方針に従って処理を進めることを特徴とする請求項４５に記載のホームサービスプロバイダ。
【請求項４７】
ユーザのサービスプロバイダとは異なるサービスプロバイダからユーザトークンを受信する手段と、
前記ユーザトークンが有効であるかを判定する手段と、
前記ユーザトークンが有効である場合に、前記ユーザトークンに基づいて前記ユーザに課金する手段とを備えることを特徴とする装置。
【請求項４８】
前記ユーザトークンが有効でない場合に、問題解決方針に従って処理を進める手段を備えることを特徴とする請求項４７に記載の装置。
【請求項４９】
複数の指示を格納する一又は複数の記憶媒体を有しており、システムによって実行される場合に、システムに方法を実行させる製造物であって、
ユーザのサービスプロバイダとは異なるサービスプロバイダからユーザトークンを受信する工程と、
前記ユーザトークンが有効であるかを判定する工程と、
前記ユーザトークンが有効である場合に、前記ユーザトークンに基づいて前記ユーザに課金する工程とを実行させることを特徴とする製造物。
【請求項５０】
前記ユーザトークンが有効でない場合に、問題解決方針に従って処理を進める工程を含むことを特徴とする請求項４９に記載の製造物。
【請求項５１】
送信されるべきパケットの数を判定する工程と、
前記パケットの数と同数である複数の葉を有する二分木を生成する工程と、
前記二分木の前記葉のそれぞれにランダム値を割り当てる工程と、
子の値の一連のハッシュ値として出力される値を各内部ノードに割り当てる工程と、
ルートに関して左側の子の全てに番号を割振る工程とを含むことを特徴とする方法。
【請求項５２】
外部サービスプロバイダを通じて所望のサービスを要求する外部ネットワークインターフェースと、
プログラム指示を記憶する記憶部と、
前記外部ネットワークインターフェース及び前記記憶部に接続された制御部とを備え、
前記制御部は、送信されるべきパケットの数を判定し、前記パケットの数と同数である複数の葉を有する二分木を生成し、前記二分木の前記葉のそれぞれにランダム値を割り当て、子の値の一連のハッシュ値として出力される値を各内部ノードに割り当て、ルートに関して左側の子の全てに番号を割振る前記プログラム指示を実行することを特徴とする装置。
【請求項５３】
送信されるべきパケットの数を判定する手段と、
前記パケットの数と同数である複数の葉を有する二分木を生成する手段と、
前記二分木の前記葉のそれぞれにランダム値を割り当てる手段と、
子の値の一連のハッシュ値として出力される値を各内部ノードに割り当てる手段と、
ルートに関して左側の子の全てに番号を割振る手段とを備えることを特徴とする装置。
【請求項５４】
複数の指示を格納する一又は複数の記憶媒体を有しており、システムによって実行される場合に、システムに方法を実行させる製造物であって、
送信されるべきパケットの数を判定する工程と、
前記パケットの数と同数である複数の葉を有する二分木を生成する工程と、
前記二分木の前記葉のそれぞれにランダム値を割り当てる工程と、
子の値の一連のハッシュ値として出力される値を各内部ノードに割り当てる工程と、
ルートに関して左側の子の全てに番号を割振る工程とを実行させることを特徴とする製造物。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク通信とともに用いられる課金メカニズムに関する。特に、本発明は、課金の正確性の安全が効果的に暗号化されて保たれる課金メカニズムに関する。
【背景技術】
【０００２】
サービスプロバイダがそのユーザに対して高度なサービスを提供するために他のサービスプロバイダと協力することが好ましい例として考えられる。会社Ａが自らのネットワークを通じてインターネット接続サービスを提供している場合には、会社Ａのユーザは一般的に会社Ａのネットワークからしかインターネットサービスを受けることができない。しかしながら、ビジネスの見地に立てば、会社Ａが会社Ｂと協力して他のネットワークを通じてインターネット接続を提供することは効果的である。協力関係には、会社Ａが会社Ｂのユーザにサービスを提供する合意（例えば、会社Ｂのネットワークを使用したユーザに会社Ａが適切に課金する処理）だけではなくて、会社Ｂが会社Ａのユーザにサービスを提供する合意も含まれる。会社Ａは、同様のサービスを会社Ｂのユーザに提供することについて合意してもよい。
【０００３】
しかしながら、このような構成を提供しようとすると、多くの問題が生じる。第１に、会社Ａは、そのユーザに対して適切に課金するために、正確な課金情報を取得しなければならない。第２に、会社Ａのユーザによって会社Ｂのネットワークが実際よりも多く利用されたと会社Ｂが欺けないようにしなければならない。第３に、会社Ａのユーザが会社Ｂのネットワークに無料で接続できないようにしなければならない。従って、課金メカニズムは、全てのユーザによる利用に対して課金できなければならない。
【０００４】
従来技術によってこれらの問題を解決するためには、追加コストが大幅にかかってしまう。これらの追加コストは、金銭的なコストだけではなく、計算に必要な時間量、計算に必要な記憶容量、様々な機関が有する装置に必要な電力などである。計算、記憶、電力などについて制約を受ける携帯端末をユーザが用いる場合に、これらの要素は特に重要である。
【０００５】
上述した状況を十分に効果的に扱うことが可能な方法、システム及び装置に関する従来技術は、我々の知る限りでは存在していない。
【０００６】
一つの単純な解決方法は、様々な商業者によって提供されるサービスに対する支払いとして、銀行によって発行される“電子コイン”をユーザが支払う小額課金を用いる方法である。ユーザが事前にコインを購入しておき、システムがコインを引き落とす。例えば、インターネットサービスに接続された場合に、外部サービスプロバイダ（ＦＳＰ；Ｆｏｒｉｇｎ  Ｓｅｒｖｉｃｅ  Ｐｒｏｖｉｄｅｒ）のネットワークを通じて送信されたデータのパケットのそれぞれに一のコインをユーザが含める。外部サービスプロバイダは、コインが有効であることを認めるメカニズムを有している。コインが有効であることを認めた後に、外部サービスプロバイダは、そのコインに対応するパケットを送信する。最終的に、外部サービスプロバイダは、これらのコインの全てをホームサービスプロバイダに提供して、ネットワークの使用量を受け取る。電子支払いシステムは、他の機関が偽造できない有効な電子コインをホームサービスプロバイダのみが発行できるという意味で安全である。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
この単純な解決方法は、多くの欠点を有している。最初に、この解決方法は、ホームサービスプロバイダのためにうまく拡張できない。ホームサービスプロバイダは、ユーザによって用いられる全ての電子コインを発行して、発行された電子コインを各ユーザに届けなければならない。上述した例のように、外部サービスプロバイダを通じてユーザが送信するパケット毎にコインが用いられた場合には、ホームサービスプロバイダが発行しなければならないコインの量は、外部サービスプロバイダに課されるトラフィックの合計量に比例する。この合計量は非常に多量であるため、ホームサービスプロバイダに設けられた一の集中サーバが十分な量のコインを発行することは非現実的である。
【０００８】
第２に、ホームサービスプロバイダは、コインが戻ってきた際に各コインを認証しなければならない。ホームサービスプロバイダがこの動作を行う二つの方法は、発行された各コインのリストを保持する方法、又は、外部サービスプロバイダと同じ認証手順を行う方法である。いずれの方法においても、ユーザによって用いられたコインの合計量に計算量が比例するため、この計算を実現することは難しい。最初の方法では、全てのコインに関する巨大なテーブルを記憶するために必要な記憶容量が非常に高価である。二つ目の方法では、記憶容量には大きな影響を与えないが、外部サービスプロバイダと同様の認証手順を行うＣＰＵに大きな影響を与える。また、この認証手順は、テーブル検索よりも時間がかかる。
【０００９】
本発明は、上述した課題を解決するためになされたものであり、サービスプロバイダのサービスにアクセスすることを可能とする方法及び装置を提供することを目的とする。
【課題を解決するための手段】
【００１０】
サービスプロバイダのサービスにアクセスすることを可能とする方法及び装置である。一の実施形態では、外部サービスプロバイダを通じて所望のサービスを要求する工程と、ハッシュツリー及び前記ハッシュツリーのルート値のデジタル署名を生成する工程と、前記デジタル署名及び前記ルート値を前記外部サービスプロバイダに送信する工程と、前記外部サービスプロバイダが前記デジタル署名を受け付けた場合に、一又は複数のトークンを次のパケットとともに前記外部サービスプロバイダに提供する工程と、前記外部サービスプロバイダが前記トークンを受け付けている間において、前記所望のサービスの利用を継続する工程とを方法が含む。
【発明の効果】
【００１１】
本発明によれば、サービスプロバイダのサービスにアクセスすることを可能とする方法及び装置を提供することができる。
【発明を実施するための最良の形態】
【００１２】
本発明の一実施形態は、ホームサービスプロバイダ（ＨＳＰ；Ｈｏｍｅ  Ｓｅｒｖｉｃｅ  Ｐｒｏｖｉｄｅｒ）が外部サービスプロバイダ（ＦＳＰ；Ｆｏｒｉｇｎ  Ｓｅｒｖｉｃｅ  Ｐｒｏｖｉｄｅｒ）と協力して、外部サービスプロバイダからサービスの提供を受けるホームサービスプロバイダのユーザから正確な課金情報を取得することを可能とする方法、構成及びシステムを含む。この方法、構成及びシステムは、全ての機関に対して効果的であり、ホームサービスプロバイダのためにうまく拡張可能で安全な課金枠組みに関する。
【００１３】
本発明の一実施形態では、小額課金枠組み（ｍｉｃｒｏｃｒｅｄｉｔ  ｓｃｈｅｍｅ）に含まれるユーザ（Ｕ）は、そのユーザにのみ関連付けられた小額課金貨幣（ｍｉｃｒｏｃｒｅｄｉｔ  ｔｏｋｅｎ，以下において、単にトークンと称する）を効率的に発行することができる。具体的には、ユーザのトークンについては、そのユーザを除いた他のユーザの誰も生成することができない。ユーザは、公開鍵及び秘密鍵のペア（好ましくはＨＳＰや他の信頼された第三者機関によって認証された公開鍵及び秘密鍵のペア）を有しており、生成された複数のトークンに対して、その秘密鍵を用いてデジタルサインを施すことが好ましい。ＨＳＰや他の信頼された第三者機関からユーザが取得する証明書は、認証可能な方法で記述されたデジタルサインを含む。デジタルサインは、ユーザの名称、公開鍵、使用が認められたサービスなどの様々な属性に加えて、証明書の有効期間などの他の属性を連結する情報である。一実施形態では、ユーザは、一つ又は複数のトークンを一度にＦＳＰに供給し、ＦＳＰは、トークン（好ましくは、トークン及び証明書）を有効化した後に（又は、トークンを有効化している間に）、トークンに対応する量のサービスや物をユーザに提供する。
【００１４】
他の実施形態では、ＦＳＰは、ＨＳＰのユーザから受信したトークンをＨＳＰに送信する。ＦＳＰは、トークンの値に基づいてＨＳＰから対価を受け取ることが好ましい。トークンを記憶するＦＳＰの記憶容量の削減やＨＳＰへの送信に用いられる周波数帯域の削減を図るために、ＦＳＰは、最初にトークンを集めることが好ましい。例えば、ＦＳＰは、ユーザから最後に受信したトークンのみを記憶（又は／及び送信）し、トークンを有効化するために必要な何らかの付属情報を記憶（又は／及び送信）してもよい。
【００１５】
図９は、ツリーの一例である。最後のトークン及び共通ノードが記憶されると、ユーザ装置は認証処理を補助するために追加を送信してもよい。図９は、この点を示している。図９に示すように、ノード３は、ノード２，４，５，８，９，１０，１１に対応するトークンの共通ノードである。ノード６を受信した際に、その共通ノード（７，２）のみをＦＳＰが保持している場合には、ノード８が用いられると、ユーザはノード３を再度供給する。
【００１６】
または、ＦＳＰは、トークンが有効でないことを証明する証明負荷がユーザ側にある場合には、トークンを有効化するために必要な情報さえも記憶していなくてもよい。または、ＦＳＰは、抽選方式で、小さな割合（％）のトークンのみを記憶（又は／及び送信）して、元々期待していた以上の対価をＨＳＰが支払う。
【００１７】
他の実施形態では、ＨＳＰがトークンをＦＳＰから受信し、ＨＳＰのユーザに対して適切に課金するために、これらのトークンを用いる。ＨＳＰがＦＳＰから受信したトークンを有効化して、ユーザが消費したトークンと同等の適切なユーザ課金情報を適用することが好ましい。本発明に係る実施形態によれば、各トークンは、いくつのトークンが既に用いられたかを判定するメカニズム（及び、トークンの数が正しくないことが特定された場合に、有効化の認証は失敗に終わるメカニズム）を実現する。ＨＳＰは、トークンを認証するために必要ななんらかの付属情報をトークンとともに記憶してもよい。または、ＨＳＰは、トークンが有効でないことを証明する証明負荷がユーザ側にある場合には、トークンを有効化するために必要な付属情報を記憶しなくてもよい。または、ＨＳＰは、抽選方式で、小さな割合（％）のトークンのみを有効化（又は／及び記憶）して、元々期待していた以上の対価がＨＳＰからＦＳＰに支払われる。一の実施形態において、小額課金枠組みのように、ＦＳＰとの間にセッションが張られている間にユーザが用いたトークンをＨＳＰが有効化する作業量は、ユーザが用いたトークンの数に比例しない一方で代わりにユーザが用いたトークンの数の対数に比例する。
【００１８】
他の実施形態では、ユーザは、密ハッシュツリーを用いてトークンを生成してもよい。様々な実施形態で詳細に説明するように、密ハッシュツリーは、トークンの認証のために必要な記憶容量、消費量及び送信量の削減に寄与する。
【００１９】
本発明の一実施形態では、システムが前払い取引ではなくて信用取引であるため（実際にはユーザがトークンを生成するため）、及び、効率的なデータ構造が採用されているため、全ての機関の効率性やＨＳＰの拡張性を実現できる。その結果、サービスや商品の提供に広く適用可能であり、効率的で安全な課金メカニズムが構築される。
【００２０】
従って、ホームサービスプロバイダ（ＨＳＰ）（会社Ａ）、外部サービスプロバイダ（ＦＳＰ）（会社Ｂ）及びＨＳＰのユーザの間で使用される本実施形態の解決方法は多くの権利範囲を含む。第１に、ＨＳＰとユーザとの関係については、本技術は、証拠を残し、又は、ＨＳＰがユーザにどれだけ課金すればよいかを示す。第２に、ＨＳＰとＦＳＰとの関係については、本技術は、証拠を残し、ＦＳＰがＨＳＰにどれだけ課金すればよいかを示す。第３に、ＦＳＰとユーザとの関係については、本課金メカニズムは、前述した二つの関係において必要な課金の証拠をＦＳＰに送信した際にのみ、ユーザがＦＳＰを介してサービスに接続可能とするメカニズムを提供する。最後に、基本的な課金メカニズムは、効果的であり、ＦＳＰのサービスを利用する際に障壁とならない。
【００２１】
証拠は、全ての機関の間で行われる課金の正確性を強化する。すなわち、ＦＳＰは、ＨＳＰのユーザによるリソースの利用を過度に申告することができず、ＨＳＰは、ＨＳＰのユーザ（ＦＳＰ又はＨＳＰのリソースを利用するユーザ）に対して過度に課金することができず、ユーザは、リソースの利用に対する課金を否定することができない。
【００２２】
このような課金メカニズムは、効率的である場合には、インターネット上における第三者機関サービスの安全な提供、例えば、映画や音楽などのデジタルストリームの安全な提供及び安全な支払いを含む様々なアプリケーションに適用される。
【００２３】
本明細書で記述される課金メカニズムは上述した問題を解決する。一実施形態では、課金メカニズムは、大きな追加コストを生じることなく、解決方法が協力関係を阻害することもない。
【００２４】
以下において、本発明を完全に説明するために様々な詳細について記述する。しかしながら、本技術分野の当業者にとっては明らかなように、これらの特定の詳述がなくても、本発明を実施することは可能である。換言すると、本発明が不明瞭となることを防ぐために、広く知られている構成や装置がブロック図に詳細に示されている。
【００２５】
以下に示す本実施形態の一部分は、コンピュータのメモリー内のデータビットを処理する模式的な構成やアルゴリズムについて開示する。これらのアルゴリズムや構成は、データ処理技術に携わる当業者やデータ処理技術の本質を効果的に他の当業者に伝える当業者が用いる手段である。ここで、アルゴリズムは、一般的に、所望の結果を導く一貫した一連の処理であると考えられる。処理には、物理的な数を物理的に扱うことが要求される。必須ではないが通常は、これらの数は、電気的又は磁気的な信号の形態をとっており、記憶、転送、結合、比較され、取り扱われる。慣用表現を主とした理由から必要に応じて、これらの信号については、ビット、値、要素、符号、記号、用語、数及び色などと称する。
【００２６】
しかしながら、当然のように、これらの用語や類似の用語は、適切な物理的な数に対応付いており、これらの数に適用される便利なラベルに過ぎない。以下に示すように、特に特定しない限り、「処理」、「演算」、「計算」、「判定」及び「表示」などとして使用される用語は、本明細書を通じて、コンピュータシステムや類似の電気的な演算装置の動作や処理について言及すると理解されるべきである。また、このような用語は、コンピュータシステムのレジスタやメモリ内の物理的な（かつ、電気的な）数として表されるデータを取り扱ったり、変換したりして、コンピュータシステムのレジスタ、メモリ及びその他の情報記憶部、送信装置、表示装置内の物理的な数として表される他のデータとすることとして理解されるべきである。
【００２７】
本発明は、以下に示す動作を行う装置にも関する。この装置は、要求される目的のために構成された特定の装置であってもよく、コンピュータに記憶されたコンピュータプログラムによって動作したり、再構成されたりする汎用コンピュータであってもよい。このようなコンピュータプログラムは、読み出し可能な記憶媒体に格納されていてもよい。なお、記憶媒体とは、特に限定する訳ではないが、様々なタイプのディスク、例えば、フロッピーディスク、光学ディスク、ＣＤ−ＲＯＭ、磁気的な光学ディスク（ＭＯ）、読み出し専用メモリ（ＲＯＭ）、読み出し書き込みメモリ（ＲＡＭ）、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気カード、光学カードであってもよく、電気的な指示を記憶することに適していれば、どのような媒体であってもよい。また、記憶媒体は、コンピュータシステムのバスに接続可能である。
【００２８】
以下で用いられるアルゴリズムや表示装置は、特定のコンピュータや他の装置に暗示的に関係すると解釈されるべきではない。様々な汎用システムが以下で示す記述に従ったプログラムと共に用いられてもよく、簡便に構成されており、要求される処理を行う特定の装置が用いられてもよい。これらの様々なシステムに要求される構成は、以下の記述によって明らかとなるであろう。加えて、本発明は、特定のプログラム言語に従って記述されていない。本明細書で示される本発明に関する記述を行うために、様々なプログラミング言語が用いられてもよいと理解すべきである。
【００２９】
機械が読み出し可能な媒体は、機械（例えば、コンピュータ）によって読み出し可能な情報を格納したり、送信したりするメカニズムであれば、どのようなメカニズムをも含む。例えば、機械が読み出し可能な媒体は、読み出し専用メモリ（ＲＯＭ）、読み出し書き込みメモリ（ＲＡＭ）、磁気ディスク媒体、光学記憶媒体、フラッシュメモリを含む。また、機械が読み出し可能な媒体は、電気的、光学的、聴覚的又は他の形式の伝達信号（例えば、搬送波、赤外線信号、デジタル信号など）なども含む。
【００３０】
［前書き］
（モデル及び注釈）
以下に示すモデルは、ホームサービスプロバイダ（ＨＳＰ）、外部サービスプロバイダ（ＦＳＰ）及びユーザ（Ｕ）が含まれる。「ユーザ」は、ユーザ個人及びユーザ装置を示すことに留意すべきである。公開鍵や共通鍵が存在する基盤を前提としており、ＨＳＰ及びユーザの双方は、一対の鍵である公開鍵及び秘密鍵を有している。一対の鍵は、「Ｓｋ、Ｐｋ」として表され、Ｓｋは、メッセージに付される署名を演算するための秘密鍵であり、Ｐｋは、Ｓｋに対応する公開鍵である。電子署名（Ｓｋ，Ｍ）は、メッセージＭに付される署名σを署名鍵Ｓｋで暗号化するアルゴリズムを示しており、Ｖｆ（Ｐｋ，Ｍ，σ）は、認証アルゴリズムを示している。説明を明確にするために、特定の個人に属する鍵について下付文字で示す。従って、ＨＳＰ用の一対の鍵は、（ＰｋＨＳＰ、ＳｋＨＳＰ）と示され、ユーザ用の一対の鍵は、（ＰｋＵ、ＳｋＵ）と示される。
【００３１】
以下において、｛０，１｝＊を全てのビット列を示すものとする。ビット列については、その長さを｜ｓ｜と示す。Ｈは、ｂビットのペイロードとｖビットの初期ベクトル（ＩＶ）を入力してｖビットの出力を得る暗号圧縮機能を示す。全ての広く知られた構造として、ｂ≧２ｖであると想定する。本明細書で示す構造は、一般的にｂ＝２ｖである。これらの暗号圧縮機能は衝突抑制であると想定される。すなわち、Ｈ（ＩＶ，ｍ１）＝Ｈ（ＩＶ，ｍ２）などのように二つの異なる入力を区別することは難しい。ＩＶは、固定であり、公開されていると想定される。ＩＶは、ハッシュ機能に関するものとして常に明確に記述される訳ではないことに留意すべきである。これらの暗号圧縮機能の実際例は、ＳＨＡ−１やＭＤ５で公開されている。前者の圧縮機能では、出力及びＩＶのサイズは２０バイトであり、後者の圧縮機能では、出力及びＩＶのサイズは１６バイトである。双方のペイロードのサイズは６４バイトである。本実施形態の技術で用いられる枠組みは、圧縮機能によって圧縮されるペイロードよりも大きいデータは扱わない。しかしながら、圧縮機能によって圧縮されるペイロードよりも大きいデータは扱う技術として、ハッシュやマークルツリーなどのような様々な標準技術が存在する。
【００３２】
ビット長を保つ機能ｆについては、｛０，１｝ｎ→｛０，１｝ｎであり、整数ｉ≧１である場合に、ｆｉは、ｆ−畳み込み合成を示す。すなわち、ｉ＝１である場合には、ｆｉ（ｘ）＝ｆ（ｘ）であり、ｉ＞１である場合には、ｆｋ（ｘ）＝ｆ（ｆｋ−１（ｘ））である。機能ｆは、ｘがランダムに選択されたｆ（ｘ）が与えられた場合に、ｆ（ｚ）＝ｆ（ｘ）のような元の値ｚを見つけることがほとんどできない程難しい一方通行の機能である。一方通行の機能ｆは、一方通行の繰り返しであり、任意のｉによってｆｉ（ｘ）が与えられた場合に、ｆ（ｚ）＝ｆ（ｘ）のような元の値ｚを見つけることがほとんどできない程難しい。実際には、一般的な予備機能として、ハッシュ機能Ｈによって一方通行の繰り返しを開始し、その長さを維持するためにペイロードの一部にパディングビットが埋め込まれる。
【００３３】
最後に、実際の数字ｒについて、ｒの上限として
【数１】
2007505555.tif 000003
【００３４】
すなわち、ｒ以上の最も小さい整数値がセットされる。同様に、ｒの下限として
【数２】
2007505555.tif 000004
【００３５】
すなわち、ｒ以下の最も大きい整数値がセットされる。
【００３６】
（マークルツリー）
以下において、マークルツリー（Ｍｅｒｋｌｅ  ｔｒｅｅ）について説明する。各値が｛０，１｝ｎであるｍ個の値ｘ１，・・・，ｘｍがあると想定する。簡略化するために、ｍは２乗であると想定する。Ｈ：｛０，１｝２ｎ→｛０，１｝ｎは、２ｎビットをｎビットに変換する暗号ハッシュ機能であるとする。ハッシュ機能Ｈによってｘ１，・・・，ｘｍに対応付けられたマークルツリーは、各ノードが特定の値（ｖ）に対応付けられた正規二分木である。マークルツリーでは、ｍ個の葉があり、各葉ｉの値（ｌｉ）＝ｘｉ，１≦ｉ≦ｍである。内部の頂点ｖとして、値Ｃ０（ｖ）及び値Ｃ１（ｖ）が左及び右の子を示す。ｏが連鎖処理を示すとすると、値（ｖ）＝Ｈ（ＩＶ，値（Ｃ０（ｖ））ｏ値（Ｃ０（ｖ）））となる。
【００３７】
マークルツリーは、デジタル署名においてダイジェストデータとして用いられ、署名されたダイジェストは、ルートに対応付けられた値となる。また、基礎となる圧縮機能が衝突抑制である場合には、マークルツリーのルートの値が同じである二つの異なるメッセージを見分けることは困難である。
【００３８】
（密ハッシュツリー）
本発明の一実施形態において、蜜ハッシュツリーを生成する手法について説明する。これらの方法は、内部頂点に番号が割り振られている点を除いて、マークルツリーと類似する。簡略化するために、ｍ個の値ｘ１，・・・，ｘｍがあり、ｍは、ｋが正の整数である場合に２ｋと等しいと想定して説明する。マークルツリーと同様に、深さがｋ+1である正規二分木が生成され、以下の手順で各頂点に値が割り当てられる。Ｈ：｛０，１｝２ｎ→｛０，１｝ｎは、暗号ハッシュ機能であるとする。次に、以下に示すように２つの色分けに分類する方法がツリーの各ノードに適用される。ルートは、白色に色分けされる。ルートの左側の子は、灰色に色分けされ、ルートの右側の子は白色に色分けされる。我々の手法では、ツリーの各頂点は、頂点がその親の左側の子である場合には灰色に色分けされ、頂点がその親の右側の子である場合には白色に色分けされる。最終的に、灰色に色分けされたノードに対して横幅方向から順に番号が割り振られる。すなわち、ツリーのトップから順に次のレベルに下っていき、各灰色ノードに左から右に順に番号が割り振られる。
【００３９】
例えば、ナンバー１がルートの左側の子に割り振られる。ナンバー２がルートの左側の子の左の子に割り振られる。ナンバー３がルートの右側の子の左の子に割り振られる。ナンバー４がルートの左側の子の左の子に割り振られる。ナンバー５がルートの左側の子の右の子の左の子に割り振られる。ナンバー６がルートの右側の子の左の子の左の子に割り振られる。ナンバー７がルートの右側の子の右の子の左の子に割り振られる。以下同様である。
【００４０】
ｉ番目の頂点にはｇｖ（ｉ）が割り振られる。図７Ａ及び図７Ｂは、２３個の頂点を有しており、１５個の小額課金取引に用いられる密ハッシュツリーの一例を示している。各内部ノードには、その子のハッシュ値と同じ値が割り当てられている。各左の子には、上から下へ、左から右へ順に番号が割り振られている。図７Ｂは、２３個の頂点を有するマークルツリーを示している。ハッシュツリーは、基本部分として１５個の頂点を有するが、８個の頂点が追加的に下にぶら下がっている。このツリーは、８個の小額課金取引にしか用いることができない。内部頂点を用いることによって、同じサイズのツリーでほぼ２倍の小額課金取引を可能とすることによって、全体として効果的な改善が図られる。
【００４１】
密ハッシュツリーで与えられる頂点には共通ノード（ＣｏＮｏｄｅｓ）の概念が用いられる。頂点ｖについて、ＣｏＮｏｄｅｓ（ｖ）は、頂点ｖからルートへの道筋にある頂点（兄弟）のセットである。Ｓｉｂ（ｖ）及びＰａｒｅｎｔ（ｖ）がそれぞれ頂点ｖの兄弟及び親を示しているとすると、ＣｏＮｏｄｅｓ（ｖ）は以下の式によって表される。
【数３】
2007505555.tif 000005
【００４２】
最終的に、共通ノードのセットでは、値（ＣｏＮｏｄｅｓ（ｖ））は、頂点ｖの共通ノードに割り当てられた値を示す。
【００４３】
一実施形態において、共通ノードについて、ルートの値を計算する処理は以下に示す通りである。ｉ番目の灰色頂点に割り振られる値をｖとし、ｉ番目の灰色頂点からルート頂点への道筋にある全ての頂点である兄弟の値をｖ１，・・・ｖｌとする。ルートの値は、ｈｌとして算出される。ここで、ｈ１＝Ｈ（ｖ  ｏ  ｖ１）であり、ｈｉ＝Ｈ（[ｈｉ−１，ｖｉ]であり、[ｈｉ，ｖｉ]は、ｖｉが左側の子である場合にはｖｉ  ｏ  ｈｉと等しく、ｖｉが右側の子である場合にはｈｉ  ｏ  ｖｉと等しい。
【００４４】
上述したように、密ハッシュツリーの番号割振りの一例について説明したが、親ノードが子ノードよりも前にくれば、どのような番号割振りを用いてもよい。この場合に、ｋ番目の小額課金は、ｋ番目の番号が割り振られたノードの子のうち、ｋ番目のノードの共通ノードを含む。このような番号割振りによれば、ユーザの送信コスト及びＦＳＰの認証コストについて効果を有する。しかしながら、他の番号割振りでは、ｋ番目の小額課金がｌｏｇ（ｋ）よりも長い認証パスを有することもある。予め定められた順序で横方向に番号をノードに割振ることによって、ツリーを「横切る」際にメモリと演算とのトレードオフが好ましい関係となる（ツリーを横切ることは、ｋ−１番目の小額課金を演算した後にユーザがキャッシュメモリに格納するツリー情報の総量とキャッシュメモリに格納されたツリー情報からｋ番目の小額課金を演算する演算量とのトレードオフを伴う。実際に、トレードオフは、マークルツリーで見つけられた最も良いトレードオフよりも良好である。この理由は、密ハッシュツリーは、マークルツリーと異なり、内部ノードの全てを用いるからである。ツリーについてルートノードの値を演算するためには、ｎ個のハッシュ値が要求される。密ハッシュでは、ｎ個の小額貨幣が生成可能であるのに対して、マークルツリーでは、｛（ｎ＋１）／２｝個の小額貨幣しか生成することができない。この２倍の関係は横切りアルゴリズム演算に引き継がれるため、予め順序が定められた横断密ハッシュツリーでは、一の小額課金に対して半分の演算量しか必要にならない。特に断らない限りは、以下において、横幅方向に番号を割振る密ハッシュツリーについて主に説明する。
【００４５】
（課金メカニズムの一例に関する様々な実施形態）
本発明の実施形態は、ホームサービスプロバイダ（ＨＳＰ）と関係を有するユーザにサービスを外部サービスプロバイダ（ＦＳＰ）が提供することを可能とする安全な課金方法、構成及びシステムを提供するように構成されている。ユーザは、ＨＳＰとの関係を有することによって、好ましくは信用取引で、ＦＳＰのサービスを受けることが可能である。その後、ＨＳＰは、ユーザが提供を受けたサービスに対して、適切な対価をＦＳＰに支払う。ユーザは、ＨＳＰから請求を受けることが好ましい。ＦＳＰ及びＨＳＰは同じ装置であってもよい。従って、本発明の実施形態に係る課金メカニズムは、第三者機関によるサービスの提供に限定されるものではない。
【００４６】
ここで記載する実施形態に係る課金技術は、二つの決定的な特徴、すなわち、安全及び効率を含む。第１の特徴は、不正なＦＳＰ、ＨＳＰ及びユーザが正確な課金を妨げることを防止する暗号化による安全である。具体的には、ＦＳＰがユーザによるサービスの利用量を過度に申告すること、（ＦＳＰに対して）、ＨＳＰがＦＳＰのネットワークをユーザした利用量を少なく申告すること、又は、（ユーザに対して）、ＨＳＰがＦＳＰのネットワークをユーザした利用量を過度に申告すること、（ＨＳＰ及びＦＳＰのいずれかに対して）、ユーザがＦＳＰのネットワークの利用量をごまかすことを暗号化によって不可能にすることである。以下において詳細に説明するように、ユーザは、拒否できないように認証してトークンを消費するため、トークンは支払いを否認不可能である。支払いを否認不可能であることは請求に疑義を生じない。請求の疑義を解決するには費用が発生し、これらの費用は一般的にユーザの負担となるため、これは非常に重要である。つまり、課金の正確性が暗号化によって保たれ、強化される。
【００４７】
第２の特徴は、効率であり、これも重要である。本発明の実施形態は、協力的なビジネスの関係の発展を容易にすることを可能とし、この関係の妨げとならない。一の実施形態では、課金メカニズムは、これを利用する機関に対して可能な限り透過的である。以下において詳細に説明するように、ここで記載する実施形態は、従来技術の方法に比べて演算効率が高い。
【００４８】
ＨＳＰのユーザがＦＳＰのサービス（対価を条件とする）の利用を許可することについてＨＳＰ及びＦＳＰが合意していると想定すると、ＦＳＰのサービスを利用しようとするユーザは、（ＨＳＰのユーザであるため）ＨＳＰとの関係をＦＳＰに明示する。本発明の一の実施形態では、これはデジタル証明書の利用によって実現される。例えば、ＦＳＰが知っている公開鍵をＨＳＰが有している場合に、ＨＳＰは、ユーザがＨＳＰの顧客であることを証明する証明書を秘密鍵によって生成できる。この証明書は、例えば、
【数４】
2007505555.tif 000006
【００４９】
の形式を有している。証明書では、ユーザ名、ユーザの公開鍵ＰｋＵ及び証明書の有効期間を示す値を含む「デジタル文書」に、ＨＳＰが秘密鍵ＰｋＨＳＰを用いて署名する。または、ＨＳＰは、他の方法を用いて、ユーザがＨＳＰの顧客であることをＦＳＰに証明してもよい。ＨＳＰではない信頼された機関が証明書を生成してもよく、ＨＳＰの顧客であることをユーザが証明することを可能とする他のメカニズムを用いてもよい。これによって、安全性の観点から、ユーザがＨＳＰの顧客であること及びユーザの公開鍵が本物であることをＦＳＰが確認する。
【００５０】
（小額課金貨幣（トークン）の生成）
一の実施形態では、ユーザは、自身のトークンを生成する。ユーザのトークンを他の構成要素が生成してもよいことは勿論である。例えば、ＨＳＰがユーザのトークンを生成してもよいが、（以下で詳細に説明するように）ＨＳＰが全てのユーザのトークンを生成することはＨＳＰの拡張性を低下させる。ユーザが自身のトークンを生成することによってＨＳＰの処理負荷が軽減される。または、ユーザのトークンを他の構成要素が生成してもよい。しかしながら、これらの構成要素は、ユーザの同意なしにトークンをＦＳＰに提示しないように信頼されていなければならない。また、ユーザ以外の構成要素がユーザのトークンを生成することは、支払いを拒否できないという効果をなくしてしまう（例えば、他の誰かがユーザのトークンを生成すると、ユーザは、他の誰かによってトークンが消費されたと主張することができる）。
【００５１】
ユーザは、マークルツリーや密ハッシュツリーなどのようなハッシュツリーを用いてトークンを生成することが好ましい。これは、効率的な面で好ましい。ＳＨＡ−１のように、ハッシュ機能は、軽い演算処理で強力な暗号化が得られることで従来から知られている。トークンは他の方法で生成されてもよいことは勿論である。例えば、ユーザは、ＨＳＰから直接トークンを受信する。このような場合には、ＨＳＰが銀行のように振る舞い、ＦＳＰが商業者のように振舞うという「支払い」手順が潜在的に存在する。この場合に、一の実施形態では、ＨＳＰは、まとめや認証を効率的に行うという特徴を有する好ましい支払い手順を提供する密ハッシュツリーを用いてトークンを生成する。さらに、ツリーが分かれている場合には、ＨＳＰによって発行された同一の署名を複数のユーザが用いることができる。従って、本発明の一実施形態は、支払い手順の枠組みを用いることが可能であり、従来技術に比べて有利な点を有する。
【００５２】
他の実施形態では、ユーザは、公開鍵による署名手順を用いて自身のトークンを生成することが可能であり、ＦＳＰに提示される署名として支払いを拒否できない署名を生成する。しかしながら、公開鍵による署名手順のアルゴリズムは、ハッシュ機能よりも演算量の面で効率が落ちてしまう。従って、一の実施形態では、公開鍵による暗号化の利用を減らすために、公開鍵による署名を個々のトークンに適用しない。一方で、一の実施形態では、支払いを拒否できないようにするために、公開鍵による署名アルゴリズムは、ハッシュツリーのルートの署名として（一度だけ）用いられる。この支払いを拒否できない署名は、ツリーに関する全てのトークンがユーザの識別子に対応付けられるように、ユーザの識別子とハッシュツリーの全体とを対応付ける。従って、一の署名に係る負荷は多くの取引で償還される。
【００５３】
一の実施形態では、一回のセットアップ段階がある。一回のセットアップ段階は、以下のステップによって実行される。
【００５４】
１．ＨＳＰは、公開鍵（ＰｋＨＳＰ）及び秘密鍵（ＳｋＨＳＰ）のペアを生成する。ＨＳＰは、取引がある各ユーザ及び各ＦＳＰに公開鍵を提供する。
【００５５】
２．各ユーザは、公開鍵（ＰｋＵ）及び秘密鍵（ＳｋＵ）のペアを生成する。ユーザは、ＰｋＵをＨＳＰに提供して、対応する秘密鍵を知っていることを証明する。この処理は、一連のチャレンジメッセージに署名すること、又は、ゼロ知識証明を提供することによって完了する。
【００５６】
３．ユーザが秘密鍵を知っていることの証明に成功し、ＨＳＰの加入者であると認定された場合には、ＨＳＰは、証明書データ（ＣｅｒｔＤａｔａＵ＝〈Ｕ，ＰｋＵ，ｄｅｘｐ，ｄｉｓｓｕｅ，IIｕ〉を生成する。なお、ｄｅｘｐ及びｄｉｓｓｕｅは、証明書の満了データ及び開始データであり、IIｕは、どのサービスが認定されたかを示す方針特定情報などである。満了データの日付は、実際の日付であってもよく、開始日付から換算して証明書が有効である期間を特定する日付（例えば、３６５日）であってもよい。
【００５７】
４．ＨＳＰは、σＵ＝Ｓｉｇｎ（ＳｋＨＳＰ，ＣｅｒｔＤａｔａＵ）を演算して、（σＵ，ＣｅｒｔＤａｔａＵ）をユーザに提供する。公開鍵の枠組みでは、ＨＳＰが証明書の発行元である点に留意すべきである。
【００５８】
５．ユーザは、Ｖｆ（ＰｋＨＳＰ，ＣｅｒｔＤａｔａＵ，σＵ）＝１であることを確認する。１である場合には、ユーザはこれを受け入れ、１でない場合には、ユーザはその旨をＨＳＰに知らせる。
【００５９】
一の実施形態では、ハッシュツリーは密ハッシュツリーである。一の実施形態では、ハッシュツリーの生成は以下のステップで構築される。
【００６０】
１．ユーザは、最初に必要なトークンの数であるｍを算出する。この算出は正確でなくてもよい。ユーザが少なく算出した場合には、ユーザはトークンを取引中にさらに生成すればよい。しかしながら、処理効率の観点でいえば、ユーザは可能な限り正確に算出すべきである。
【００６１】
２．ユーザは、ｍ＋１のビット列をランダムに生成する。各ビット列は、暗号化に適した長さｎビット（例えば、ｎ＝１６０ビット）を有することが好ましい。
【００６２】
３．ユーザは、ｍ＋１個の葉（２ｍ＋１個のノード）を有する（略）正規二分木を生成する。ユーザは、ランダムに生成されたビット列を葉に割り当てる。
【００６３】
４．ユーザは、内部ノードの子の値に従って、各内部ノード（ルートノードを含む）に割り振る値を演算する。例えば、ユーザは、Ｖａｌｕｅ（ｖ）＝Ｈ（ＩＶ，Ｖａｌｕｅ（Ｃ０（ｖ）  ｏ  ｖａｌｕｅ（Ｃ１（ｖ）））の式に従って内部ノードの値を演算する。Ｃ０及びＣ１は、内部ノードの子である。
【００６４】
図４は、一実施形態において、密ハッシュツリーを構築する処理を示すフロー図である。処理は、ハードウェア（回路、デジタルロジックなど）、ソフトウェア（汎用コンピュータや個別機器などで行われる処理）又はこれらの組合せである処理ロジックによって実行される。
【００６５】
図４に示すように、処理ロジックは、送信が要求されるパケットの上限を算出する処理（ステップ４０１）を開始する。この上限はｍで表される。次に処理ロジックは、ｍ個の葉を有する二分木を生成する（ステップ４０２）。処理ロジックは、二分木を生成した後に、ランダムなｎビット値を各葉に割り当てる（ステップ４０３）。ｎは、ハッシュ機能のペイロードサイズである。ｎビット値が各内部ノードに割り当てられると、処理ロジックは、子の一連のハッシュ値として出力される値を各内部ノードに割り当てる（ステップ４０４）。
【００６６】
そして、処理ロジックは、ノードを色分け（分類）する（ステップ４０５）。一の実施形態では、処理ロジックは、ルートに白色を割り当て、左の子の頂点に灰色を割り当て、右の子の頂点に白色を割り当てる。ノードの色分けが終わると、処理ロジックは、灰色のノードに番号を割り振る（ステップ４０６）。一実施形態では、処理ロジックは、レベル毎に木の横方向に左から右へ横断して、灰色のノードに番号を割り振る。処理ロジックは、ルートの左の子に１を割り当てて、順に番号を割り振る。色分けアルゴリズムは、説明を目的とするものであり、ノードを二つに分類する方法としてどのようなメカニズムを用いてもよい。
【００６７】
この手順としては、様々なバリエーションが考えられる。例えば、ツリーは二分木である必要はないが、二分木は、各ノードが有する兄弟が少ないため、共通ノードが少ない傾向を有する点で好ましい。また、内部ノードは、異なる式に従って演算されてもよい（例えば、ノードの見出し番号、トークンの宛先となるＦＳＰの識別子及びその他の情報を各ハッシュの入力が含む）。
【００６８】
（課金手順の概略の流れ）
上述したように、ユーザは、ツリーのルートに関するデジタル署名をその秘密鍵を用いて生成することが好ましい。ツリーのルートに対する値として値（ルート）が算出されたとする。ユーザの署名は、ＳｋＵ（値（ルート））として算出される。ユーザは、（ルート値の他に）サイン書類に追加情報を含めてもよい。例えば、ユーザは、トークンの宛先となるＦＳＰの識別子、ツリーからＦＳＰが取得するトークンの最大値、ＨＳＰからＦＳＰがトークンの対価を受け取る前に満たさなければならない条件、その他の情報を含めてもよい。ユーザがＦＳＰからのサービスへのセッションを開始する場合に、ユーザは、ルート値、ルート値に対する署名、公開鍵、ユーザとＨＳＰとの関係を証明する信頼された機関からの証明書を、（好ましくは、セッション開始時に）ＦＳＰに送信する。これらの情報をＦＳＰが既に有している場合には、ユーザがこれらの情報を送信する必要はない。例えば、過去にユーザがＦＳＰに接続したことがある場合には、ＦＳＰは、証明書を既に有している。一部分が既に消費された古いツリーを用いた新しいセッションの開始をユーザが要求する場合には、ＦＳＰは、ルート値及びルート値に対する署名を有していてもよい。
【００６９】
ユーザの公開鍵及び（署名された他の情報とともに）署名されたルート値を含むユーザの署名を受信すると、ＦＳＰは、署名手順の認証アルゴリズムによって署名が正当であることを認証する。署名手順としては、従来技術で広く知られているように、認証手順は、一般的に、署名、公開鍵及び入力されたメッセージを用いて、書名が有効であるか否かを示す真偽値；Ｖｆ（σ，ＰＫ，Ｍ）＝０  ｏｒ  １を出力する。ＦＳＰは、同様の手順によって、信頼された機関によって発行された証明書を認証する。
【００７０】
一の実施形態では、ＦＳＰがユーザから受け取る「支払い」は、（上述したように、署名及び証明書情報に加えることが可能な）プレハッシュイメージによって構成される。プレハッシュイメージは、ハッシュツリーの生成に伴うハッシュ機能の入力である。本実施形態で用いられるように、ハッシュ機能は、（入力から出力を容易に演算できるが、出力から入力を演算することが難しい）一方通行であるため、ＦＳＰは、プレハッシュイメージを自身で演算することは難しい。トークンがハッシュツリーを用いて生成されていなければ、支払いは異なった形式を採ることは勿論である。例えば、ユーザがトークンを署名手順で生成した場合には、各トークンはデジタル署名によって構成される。但し、これは演算量が多くなることに留意すべきである。
【００７１】
セッション開始時に、ユーザ及びＦＳＰは、支払いの生成方法について交渉することが好ましい。例えば、支払いは、ＦＳＰがサービスを提供する前になされたり、ＦＳＰが全てのサービスを提供した後になされたりする。これらの手順のいずれにも共通することであるが、本発明の実施形態はもっと柔軟な手順を可能とする。例えば、ＦＳＰのサービスが小さく個別の部分に分けられる場合には、ＦＳＰは、「順次増やしながら」サービスを提供してもよい。すなわち、ＦＳＰは、追加のトークンをユーザが納めた後に、個別の部分のサービスを提供する。例えば、ＦＳＰは、映像をストリーム配信するサービスをユーザに提供する場合には、ｋ番目のトークンを受信した後に、ストリームに含まれるｋ番目のフレームを送信する。簡潔で一般的に説明するために、以下において、ユーザがトークンをＦＳＰに順次納めるケースについて説明する。
【００７２】
ユーザが密ハッシュツリーを用いる本発明の一実施形態では、ｋ番目のトークンは、ｇｖ（ｋ）の値を含んでおり、ｇｖ（ｋ）は、横幅方向に番号が割振られる密ハッシュツリーにおけるｋ番目の灰色頂点（ツリーにおけるｋ番目の左側の子）、及び、共通ノードの値（ＣｏＮｏｄｅｓ（ｇｖ（ｋ））である。密ハッシュツリーのノードには、異なった手順で番号が割振られてもよい（例えば、ツリーにおけるｋ番目のノードは、右側から番号が割振られるツリーにおけるｋ番目の右側の子、又は、他の番号割振り手順が用いられてもよい）。しかしながら、本実施形態では、簡潔に説明するために、上述した手順で番号が割振られるものとする。詳細に説明したように、効率が落ちるが、密ハッシュツリーではなくて、マークルツリーを本発明に用いてもよいことは、当業者にとって明らかである。
【００７３】
ユーザは、ハッシュツリーの生成方法に類似した手順でｋ番目のトークンを演算してもよい。ユーザがハッシュツリーを演算する際に用いたｎ＋１の葉の値は、ツリーに含まれる全てのノードの値を再演算するために必要な全ての情報をユーザに提供する。従って、各ノードの値は、ｋ番目のトークンの値に対応する。簡潔にするために、ユーザは、小さな秘密の「種」を用いてｎ＋１の葉の値を演算してもよい。この種を用いることによって、ユーザは、ｋ番目のトークンを演算するために必要などの葉の値であっても再演算することができる。この種は、不正な攻撃に対する耐性を保つために十分な長さ（例えば、８０ビット以上の長さ）を有するべきである。小さな種の値を用いることによって、ｎ＋１個の値をユーザが記憶しておくことを防ぐことができる。または、ユーザは、再演算を行わなくてもよいように、ツリーに含まれる全てのノードの値を記憶していてもよい。または、ユーザは、ユーザが有する記憶容量とトークンのために必要な値の再演算に必要な再演算量との最適なトレードオフの関係を選択してもよい。マークルツリーの場合には、演算量と記憶容量とのトレードオフについて広く知られた関係が存在する。具体的には、次のマークルの道筋を演算するためには、ｌｏｇｍの演算量及びｌｏｇ２ｍの記憶容量が必要であり、ｍはツリーの葉に割振られた番号である。密ハッシュツリーに含まれるノードの番号が異なった手順で割振られる場合には、子とその親との間にノードを挿入するためにツリーの構造を若干修正して、密ハッシュツリーで「横方向に番号を割振る手順」にこの方法を拡張して用いることができる。この拡張機能では、灰色のノードには、親の左の子がその親よりも先になって右の子が後になるように、左から右へ番号が割り振られる。以前の処理では、ｋ番目のトークンは、ｋ番目の灰色のノードの値とともに、その共通ノードの値によって構成される。この場合では、共通ノードは、密ハッシュツリーに「挿入」されたノードの一つとなる。密ハッシュツリーで効率的に横方向に番号を割振る手順（又は、密ハッシュツリーの若干の変更）については、様々な方法が用いられてもよい。
【００７４】
ｋ番目の部分を受信するためには、ユーザはｋ番目のトークンをＦＳＰに送信する。共通ノードのｇｖ（ｋ）がｊ＜ｋであるｇｖ（ｊ）の値に対応しており、ｋ＞１であり、かつ、番号の割振り方が通常である密ハッシュツリーが用いられる場合であって、これらの共通ノードの値をＦＳＰが記憶している場合には、これらの共通ノードの値をＦＳＰに再送しなくてもよい。
【００７５】
ＦＳＰは、ｇｖ（ｋ）の値及びユーザが署名したハッシュツリーのルートの値であるＣｏＮｏｄｅｓ（ｇｖ（ｋ）の値によって、ｋ番目のトークンを認証する。具体的には、実際のハッシュツリーの内部ノードの値（例えば、Ｖａｌｕｅ（ｖ）＝Ｈ（ＩＶ，Ｖａｌｕｅ（Ｃ０（ｖ））  ｏ  Ｖａｌｕｅ（Ｃ１（ｖ））））を演算する際に用いる方法と同様に、ＦＳＰは、Ｈ（ＩＶ，Ｖａｌｕｅ（ｇｖ（ｋ））  ｏ  ＣｏＮｏｄｅｓ（Ｓｉｂｌｉｎｇ（ｇｖ（ｋ）））によってＶａｌｕｅ（Ｐａｒｅｎｔ（ｇｖ（ｋ））を演算するなどして、ｇｖ（ｋ）及びＣｏＮｏｄｅｓ（ｇｖ（ｋ））の仮の値を用いて、ルートノードの仮の値を演算する。ＦＳＰは、ルートノードの仮の値が（認証された）ユーザの署名に含まれる実際のルート値と同じである場合には、ｋ番目のトークンを有効なものとして受け入れる。それ以外の場合には、ＦＳＰは、ｋ番目のトークンを受け入れない。ＦＳＰは、トークンが有効であるか否かに応じて、ユーザへのサービスを継続又は中断する。
【００７６】
上述したように、ＦＳＰは、ユーザから以前に提示されたノード及び共通ノードの値を記憶する。これによって、ＦＳＰは、ｋ番目のトークンを認証するために必要な時間を削減する。例えば、これらの値の全てをＦＳＰが記憶している場合には、Ｐｒａｅｎｔ（ｇｖ（ｋ））に対応する値は既に記憶されている。このような場合には、ＦＳＰは、ｇｖ（ｋ）とその兄弟ノードがハッシュ関数によってこれらの親の値となること（すなわち、（Ｈ（ＩＶ，Ｖａｌｕｅ（ｇｖ（ｋ））  ｏ  ＣｏＮｏｄｅｓ（Ｓｉｂｌｉｎｇ（ｇｖ（ｋ）））がＶａｌｕｅ（Ｐａｒｅｎｔ（ｇｖ（ｋ））と等しいこと）のみを確認すればよい。
【００７７】
ＦＳＰとユーザとの間でセッションが終了した場合、又は、トークンを扱うためのハッシュツリーをＦＳＰ及びユーザが使用しなくなった場合には、ＦＳＰは、記憶容量を削減するために、最後にユーザから送信されたトークンのみを記憶する。最後のトークンがｇｖ（ｋ）及びその共通ノードによって構成されている場合について考える。ＦＳＰは、（好ましくは見出しｋとともに）ｇｖ（ｋ）の値のみを記憶して、共通ノードの値をメモリから削除するという選択肢を有する。これの効果は、ＦＳＰに必要とされるメモリ容量の削減に他ならない。これのマイナス効果は、共通ノードの値が認証に必要なため、省略されたトークンを認証することができなくなってしまうことである。
【００７８】
以下の記述において、省略されたトークンは、否認不可能トークン又は否認不可能小額課金と称する。その理由は、否認不可能トークンを認証することができなくなったとしても、トークンが有効であればユーザは否認することができないからである。ｋ番目の否認不可能小額課金が有効でないことを証明するためには、ユーザは、ハッシュ関数によってユーザが署名したルート値を生成するｇｖ（ｋ）の共通ノードの値とともに、小額課金に含まれるものとは異なるｇｖ（ｋ）の値を生成できなければならない。ユーザがこれをできない場合には（なお、ハッシュ機能の衝突抑制によって、トークンが有効である場合には不可能である）、否認不可能トークンは有効であるとみなされる。自己を防衛するために、ユーザは、ハッシュツリーの生成に用いられる種の値を記憶しておくことが好ましい。ユーザは、別々のハッシュツリーを生成するために交互に用いられる第２の種の値を記憶していることも好ましい。つまり、有効な否認不可能トークンは、ユーザの協力なしではトークンを認証することができないが、ユーザがトークンを消費したことを否認できない証拠となる。従って、（ＨＳＰ、ＦＳＰ及びユーザの間で合意が継続している場合には）、（省略された）否認不可能トークンのみをＦＳＰが記憶することが許容される。
【００７９】
ユーザが、「マルチ署名」又は「ひとまとめの署名」を可能とする署名手順で署名を生成した場合には、ＦＳＰは複数の署名を記憶するために必要な記憶容量を削減できる。従って、複数のトークンを記憶するために必要な記憶容量も削減できる。例えば、ユーザがＲＳＡ署名手順を用いる場合には、複数の書類に付される多くのＲＳＡ署名は、単に一つにまとめられて（ＲＳＡモジュールのモジュロをとって）、各書類の許可を示しており、認証可能で簡易なマルチ署名としてまとめられる。このように、ひとまとめの署名は、この設定では複数署名よりも有効である。また、ユーザは、ひとまとめにされる複数の書類に複数の機関によって付される複数署名を可能とする署名手順を用いてもよい。ユーザがこのような署名手順を用いる場合には、ＦＳＰは、記憶容量（及び、ＨＳＰに署名を送信する際の周波数帯域）を削減するために、ユーザの署名をひとまとめにできる。本発明の他の実施形態では、ＨＳＰは、暗号化された安全な「グループ署名」手順を設定することができる。また、ユーザは、この手順を用いて書名を生成することができる。この場合には、ＦＳＰはユーザを識別することができないが、ユーザがＨＳＰの本当のユーザであることがグループ署名手順の暗号化によって保障される。しかしながら、ＦＳＰは、（同じセッション内に限られるが）同じ署名によって行われる通信を関連付けることができる。関連付けが可能な理由は、トークンが一つの署名に関連付けられるからである。一般的に、グループ署名では、グループマネージャ以外が二つの署名をまとめることができない。ＨＳＰは、グループ署名手順でグループマネージャとして機能するため、署名したユーザと署名とを対応付けることが可能である。
【００８０】
ＦＳＰ及びユーザは、セッションの終了後に、前のセッションで用いたハッシュツリーを継続して用いて、前のセッションで最後に用いられたトークンに続くトークンで開始してもよい。
【００８１】
ＦＳＰがユーザから受信したトークンの対価を要求しようとする場合には、ＦＳＰは、ユーザから受信した最後のトークンをＨＳＰに送信することが好ましい。最後のトークンについては、（全ての必要な共通ノードの値が含まれており）認証可能又は否認不可能である。ＦＳＰは、署名された情報（用いられたハッシュツリーのルート値を含むことが好ましい）とともに、ユーザの署名を送信することが好ましい。ＦＳＰは、いくつかの最後のトークンを一回の送信で送れるように、最後のトークンの送信を遅延させることが好ましい。
【００８２】
トークンが否認不可能であるが認証できなかった場合に、ＨＳＰは、トークンが有効であることを示す追加保証をＦＳＰに要求する。例えば、ＨＳＰは、ＦＳＰの暗号鍵を用いて、否認不可能なトークンの認定について生じる解決費用をＨＳＰに返済することを保証する署名をＦＳＰに要求する。ＨＳＰ及びＦＳＰの間には他の合意があってもよい。
【００８３】
認証可能なトークンをＦＳＰから受信すると、ＨＳＰは、ＦＳＰが認証する方法と同様に、トークンを認証する。ｋ番目のトークンが送信されてきた場合には、ＨＳＰは、一の署名認証及び
【数５】
2007505555.tif 000007
【００８４】
ハッシュ演算を行うことによって、ｋ番目のトークンを認証する。ＨＳＰの認証負荷は、上述した支払い手順と同様にｋに比例せずに、ｋの対数に比例する。これは、ＨＳＰの処理負荷を大幅に軽減し、支払い方法の拡張性を大幅に向上する。トークンが有効であるとＨＳＰが判定した場合には、ＨＳＰは、トークンを記憶するとともに、ユーザにサービスを提供したことに対して適切な対価をＦＳＰに支払う。
【００８５】
否認不可能トークンをＨＳＰが受信した場合には、ＨＳＰはこれを認証できない。しかしながら、ＨＳＰは、ルート値（又は、他の情報）に対するユーザの署名の有効性を確認できる。書名が有効である場合には、ＨＳＰは、（将来的に疑義が生じた場合に備えて）トークンを記憶するとともに、ＨＳＰ及びＦＳＰの合意に従って適切な対価をＦＳＰに支払う。ＨＳＰは、更なる可能性についてトークンの有効性を確認した後に、ユーザに対する課金を請求する。
【００８６】
（フロー図の一例）
図１は、一実施形態において、サーバへの接続を可能とする外部サービスを安全に使用するユーザの処理を示すフロー図である。処理は、ハードウェア（回路、デジタルロジックなど）、ソフトウェア（汎用コンピュータや個別機器などで行われる処理）又はこれらの組合せである処理ロジックによって実行される。
【００８７】
図１に示すように、処理は、処理ロジックによって開始される。処理ロジックは、外部サービスプロバイダ（ＦＳＰ）を通じて所望のサービスに接続（アクセス）する（ステップ１０１）。次に、処理ロジックは、ハッシュツリーのルート値に応じて、密ハッシュツリー及びデジタル署名を生成する（ステップ１０２）。そして、処理ロジックは、デジタル署名、ルート値及び証明書をＦＳＰに送信する（ステップ１０３）。
【００８８】
処理ロジックは、ＦＳＰが署名を受け付けるか否かを判定する（ステップ１０４）。ＦＳＰが署名を受け付けなかった場合には、処理ロジックは処理を終了する。ＦＳＰが署名を受け付けた場合には、処理ロジックは、次の小額課金貨幣（トークン）を次のパケットとともにＦＳＰに送信する（ステップ１０５）。そして、処理ロジックは、小額課金貨幣（トークン）をＦＳＰが受け付けるか否かを判定する（ステップ１０６）。ＦＳＰがトークンを受け付けなかった場合には、処理ロジックは処理を終了する。ＦＳＰがトークンを受け付けた場合には、処理ロジックは、このサービスの継続をユーザが希望するか否かを判定する（ステップ１０７）。サービスの継続を希望しない場合には、処理ロジックは処理を終了する。サービスの継続を希望する場合には、処理ロジックは、ステップ１０５の処理に移り、処理を継続する。
【００８９】
ユーザがトークンを使い果たした場合には、ユーザは、他の密ハッシュツリーを生成するとともにルートに署名して、妥当な情報をＦＳＰに提供する。この結果、他の署名演算及び認証が必要となるが、望ましくない。しかしながら、ハッシュの処理負荷は、署名に比べて軽く、ユーザは、多量のトークンを生成することによって、わずかな代償で備えることができる。密ハッシュツリーを用いる顕著な効果は、認証時間が灰色の頂点の対数に比例することである。通常のツリーを用いる場合には、認証時間は、ツリーの高さに比例するであろう。後者では、ユーザが最終的に使用するトークンよりも多量のトークンを生成した場合に、認証時間が致命的に長くなる。
【００９０】
図２は、一実施形態において、外部サービスプロバイダが安全にサービスをユーザに提供する処理を示すフロー図である。図２に示す処理は処理ロジックによって実行される。処理ロジックは、ハードウェア（回路、デジタルロジックなど）、ソフトウェア（汎用コンピュータや個別機器などで行われる処理）又はこれらの組合せであってもよい。
【００９１】
図２に示すように、処理は、ＦＳＰの処理ロジックによって開始される。ＦＳＰの処理ロジックは、サービス要求をユーザから受信する（ステップ２０１）。そして、ＦＳＰの処理ロジックは、デジタル署名、ルート値及び証明書を受信する（ステップ２０２）。処理ロジック及びＦＳＰは、署名を受け付けるか否かを判定する。署名を受け付けない場合には、処理ロジックは処理を終了する。署名を受け付ける場合には、ＦＳＰの処理ロジックは、ステップ２０４の処理に移り、要求されたサービスを提供する。また、ＦＳＰの処理ロジックは、小額課金貨幣（トークン）を待つ（ステップ２０５）。
【００９２】
処理ロジックは、小額課金貨幣（トークン）をユーザが送信するか、及び／又は、ユーザがサービスの継続を要求するかを判定する（ステップ２０６）。そうでない場合には、処理ロジックは処理を終了する。そうである場合には、処理ロジックは、小額課金貨幣（トークン）が有効であるかを判定する（ステップ２０７）。トークンが有効でない場合には、処理ロジックは処理を終了する。トークンが有効である場合には、処理ロジックはステップ２０４の処理に移り、処理を継続する。
【００９３】
図３は、一実施形態において、ホームサービスプロバイダが、外部サービスプロバイダを通じたサービスへのアクセスに対して、正確で安全に課金する処理を示すフロー図である。処理は、処理ロジックによって実行される。処理ロジックは、ハードウェア（回路、デジタルロジックなど）、ソフトウェア（汎用コンピュータや個別機器などで行われる処理）又はこれらの組合せであってもよい。
【００９４】
図３に示すように、処理は、処理ロジックによって開始される。処理ロジックは、ＦＳＰから受信する小額課金貨幣（トークン）を待つ（ステップ３０１）。処理ロジックが小額課金貨幣（トークン）を受信した場合には（ステップ３０２）、処理ロジックは、トークンが有効であるかを判定する（ステップ３０３）。トークンが有効でない場合には、処理ロジックは、問題解決方針に従って処理を進め（ステップ３０４）、処理を終了する。トークンが有効である場合には、処理ロジックは、小額課金貨幣（トークン）の数に応じて、ユーザへの課金額を加算して（ステップ３０５）、処理を終了する。
【００９５】
（構成及びシステムの一例）
個々の構成が図５に示されている。この構成は、本発明の一実施形態に係るユーザ装置、ＨＳＰ装置、及び／又は、ＦＳＰ装置であってもよい。
【００９６】
図５は、一実施形態に係るユーザ装置、ＨＳＰ装置又はＦＳＰ装置を示すブロック図である。図５に示すように、制御部５０１は、記憶部５０２に接続されている。制御部５０１は、本実施形態で記載された一又は複数の処理を実行する。記憶部５０２は、データ又は／及び指示を制御部５０１に供給して、制御部５０１とともに動作する。記憶部５０２は、暗号鍵を記憶していてもよい。システム５００は、通信ネットワーク５０３に接続されており、通信ネットワーク５０３と情報を交換する。システム５００の詳細について以下で説明する。
【００９７】
本発明の一の実施形態に係るユーザ、外部サービスプロバイダ及びホームサービスプロバイダを有するシステム構成が図６に示されている。
【００９８】
図６は、ユーザ、ＨＳＰ及びＦＳＰを有するシステム構成を示す図である。図６に示すように、ユーザ装置６０１は、通信ネットワーク６１０を介してＦＳＰ装置６０２と通信可能である。同様に、ＦＳＰ装置６０２は、通信ネットワーク６１１を介してＨＳＰ装置６０３と通信可能である。通信ネットワーク６１０及び６１１は、異なる通信ネットワークであってもよいことに留意すべきである。ユーザ装置６０１は、ＦＳＰ装置６０２にサービスを要求したり、ＦＳＰ装置６０２からサービスを受けたりするために、ユーザによって生成されたトークンがＦＳＰ装置６０２に提供される通信ネットワーク６１０を用いる。同様に、ＦＳＰ装置６０２は、課金を行うためにサービス利用情報がＨＳＰ装置６０３に提供される課金段階を行うために、通信ネットワーク６１１を用いる。
【００９９】
（その他の実施形態）
その他の実施形態では、処理が以下のように行われる。
【０１００】
１．ユーザは、どの程度のサービスの利用を希望するかを、取引が行われる数の観点で算出する。ここでは、この数はｍによって表される。この算出は必ずしも正確でなくてもよく、上述したように、ユーザは、追加のトークンをいつでも生成することができる。正確性によって処理効率が向上するため、ユーザは、少なめに算出するよりも、多めに算出するほうが好ましい。
【０１０１】
２．ユーザは、（ｍ＋１）＝２ｋの葉（これは灰色の頂点に対応する）を有する密ハッシュツリーを構築する。ｒがツリーのルートを表すものとする。ユーザは、σｒ＝Ｓｉｇｎ（ＳｋＵ、ＦＳＰ、Ｖａｌｕｅ（ｒ））を演算する。ユーザは、〈ｈ  Ｖａｌｕｅ（ｒ），σｒ，ＣｅｒｔＤａｔａＵ，σＵ〉をＦＳＰに送信するととともに、正式にサービス要求を行う。
【０１０２】
３．ＦＳＰは、要求されたサービスをユーザが本当に利用することが可能か確かめるために、IIＵを調べる。次に、ＦＳＰは、証明書データＣｅｒｔＤａｔａＵによって、ｄｉｓｓｕｅ＜ｄｅｘｐであるかを認証する。最後に、ＦＳＰは、Ｖｆ（ＰｋＨＳＰ，ＣｅｒｔＤａｔａＵ，σＵ）＝１であり、かつ、Ｖｆ（ＰｋＵ，Ｖａｌｕｅ（ｒ），σｒ）＝１であるかを判定する。これらが正しい場合には、ＦＳＰは、サービス要求を受け付ける。そうでなければ、ＦＳＰは、例えば、サービスの提供を拒否するなどのように、適切な方針に従って処理を進める。また、証明書手順が取消メカニズムとともに動作する場合には、証明書は有効性のために確認される。行われた処理は、本手順と本質的に無関係である。
【０１０３】
４．各期間ｉにおいて、ユーザがサービスの継続を希望する場合には、ユーザは、ｉ番目のトークンをＦＳＰに提供する。ｉ番目のトークンは、Ｖａｌｕｅ（ｇｖ（ｉ））及び（後続がある場合には）Ｖａｌｕｅ（Ｓｉｂ（ｇｖ（ｉ））である。
【０１０４】
５．ＦＳＰは、ｉ≦（ｍ−１）／２である場合には、ｈｖ＝Ｈ（Ｖａｌｕｅ（ｇｖ（ｉ））  ｏ  Ｖａｌｕｅ（Ｓｉｂ（ｇｖ（ｉ）））を演算し、その他の場合には、単にｈｖ＝Ｈ（Ｖａｌｕｅ（ｇｖ（ｉ）））を演算する。ｉが偶数である場合には、ＦＳＰは、ｈｖ＝Ｖａｌｕｅ（ｇｖ（ｉ／２））であるかを確認する。そうでない場合には、ＦＳＰは、ｈｖ＝Ｖａｌｕｅ（Ｓｉｂ（ｇｖ（（ｉ−１）＝２）））であるかを確認する。ＦＳＰがこれらの演算を行うことが可能なのは、Ｖａｌｕｅ（ｇｖ（ｉ／２））及びＶａｌｕｅ（Ｓｉｂ（ｇｖ（（ｉ−１）＝２）））を反復
【数６】
2007505555.tif 000008
【０１０５】
で受信するためである。これらの確認が成功した場合には、ＦＳＰは、ユーザのトークンを受け付ける。そうでなければ、ＦＳＰは、ユーザのトークンを拒否して、恐らくは何らかの警告とともにサービスを終了するなどのように適切な方針を適用する。
【０１０６】
（課金）
ユーザが適切な署名手順を用いる場合には、ＨＳＰは、ＦＳＰが可能であるように、メモリを節約するために署名をバッチ処理することができる。また、ＨＳＰは、ＦＳＰと同様に、署名の認証をバッチ処理することができる。
【０１０７】
本発明の実施形態にかかる方法及びシステムは、「抽選方式」手順で機関が課金することと互換性があり、特に、ＨＳＰ及びＦＳＰは、メモリや送信の必要量をさらに削減することが可能である。この手順では、ユーザによって支払われたトークンを償還しなくてもよくすること、又は、その期待値が何回も償還されるようにすることが可能である。ＨＳＰ及びＦＳＰは、当選したトークンのみを記憶すればよい。抽選システムの不利な点は三要素である。
【０１０８】
１．機関の間で行われる課金は、ＦＳＰの運、不運に左右されるため（ユーザの運、不運に左右されるため）、全体として正確ではない。
【０１０９】
２．手順の隠れた不正確さが高額な課金について議論を引き起こす
３．（ＦＳＰ及びＨＳＰがトークンの数の対数に比例するメモリ容量のみを必要とするため）小額課金手順が潜在的に指数関数に従ってメモリの必要量を削減することを可能とするのに対して、抽選システムは、定常的な要素についてメモリの必要量を削減可能である。
【０１１０】
このような抽選方式手順は、小額支払い手順とともに従来技術で記載されているが、本発明の小額課金手順にこの手順を適用することは、もし望めば容易である。
【０１１１】
トークンのサイズ（帯域幅）とＨＳＰがトークンを認証するのに必要な時間との間にトレードオフの関係があることについて着目する価値がある。一の実施形態では、横幅方向に番号を割振る密ハッシュツリーを用いると、ｋ番目のトークンはＯ（ｌｏｇ（ｋ））のノード値によって構成されており、Ｏ（ｌｏｇ（ｋ））回の認証が行われる。ハッシュチェインは一定のサイズを有する一方でＯ（ｋ）回の認証回数が必要となる。二分木のノードの値をハッシュチェインに置き換えることによって、トレードオフの関係を見つけることが可能である。チェインが長さｌを有する場合には、密ハッシュ／ハッシュチェイン小額課金手順のハイブリッドを得る。ｋ番目のトークンのサイズは、最も大きい１＋ｌｏｇ（ｋ／ｌ）となり、認証時間は、最も大きいｌ＊（ｌｏｇ（ｋ／ｌ））となる。
【０１１２】
（ポーリング）
本実施形態に係る手順において、不正が行われる危険性の増加によって徒労に終わる演算の減少を図るために、少なくとも２つの場所でポーリングを組み込んでもよい。１番目については、ＦＳＰがトークンをユーザから受信した場合に、ＦＳＰは、直ちにトークンを認証するか否かを所定の確率に従って選択することができる（但し、これは、必ず認証される最初のトークン及び最後のトークンには当てはまらない）。ユーザが不正を行おうとしたケースにおいて、最後のトークンが認証された場合又はユーザに請求するために用いられる有効なトークンが以前にいくつかある場合には、ユーザはほとんど捕まらない。このようなユーザの振る舞いをＦＳＰが監視していれば、ポーリングを行う確率を動的に変更することができる。
【０１１３】
また、請求調整段階にポーリングを組み合わせることもできる。例えば、ＦＳＰを通じたサービスへのアクセスをユーザが終了したと想定する。さらに、彼らが生成した密ハッシュツリーのルートがそれぞれｒ１，・・・，ｒｓであり、彼らが用いたサービスの総量がそれぞれｔ１，・・・，ｔｓであると想定する。請求調整時には、ＦＳＰは、＜Ｖａｌｕｅ（ｒ１），ｔ１＞，・・・，＜Ｖａｌｕｅ（ｒｓ），ｔｓ＞をＨＳＰに送信する。次に、ＨＳＰは、ｉ１，・・・，ｉｋ∈｛１，・・・，ｓ｝を示すｋのセットを取り出して、これらをＦＳＰに送信する。最終的に、ＦＳＰは、
【数７】
2007505555.tif 000009
【０１１４】
を送信する。これらは、ＦＳＰがＨＳＰに送信するために準備した値によって構成される。しかしながら、最初の段階でＦＳＰが＜Ｖａｌｕｅ（ｒ１），ｔ１＞，・・・，＜Ｖａｌｕｅ（ｒｓ），ｔｓ＞を送信しているため、ＦＳＰは自身を約束する。今、ＨＳＰは、送信された値を通常行うように認証する。いれかの認証が失敗した場合には、ＨＳＰは、警告を発するとともに、恐らくペナルティをＦＳＰに課す。
【数８】
2007505555.tif 000010
【０１１５】
の中から後に疑義が生じた場合には、それはＨＳＰによって直接取り扱われる。一方で、他のユーザについて疑義が生じた場合には、ＨＳＰは、ユーザからＦＳＰに送信した情報を要求することができる。ＦＳＰが不正を行った場合には、ｒ１，・・・，ｒｓが既に約束されているため、ＦＳＰは捕まる。一方で、ＦＳＰが不正を行っていない場合には、ＨＳＰは、他のユーザに対する利用証明を生成することができる。
【０１１６】
ユーザが利用したよりも多いサービスについて課金されていると主張するという意味で、課金に関する疑義が生じた場合には、ＨＳＰ及びＦＳＰの双方は、〈ｔ，Ｖａｌｕｅ（ｒ），σｒ，Ｖａｌｕｅ（ｇｖ（ｔ）），Ｖａｌｕｅ（ＣｏＮｏｄｅｓ（ｇｖ（ｔ）））〉を提示することによって、正確な量を証明できる。Ｖａｌｕｅ（ｇｖ（ｔ））及びＶａｌｕｅ（ＣｏＮｏｄｅｓ（ｇｖ（ｔ）））を用いて演算されたルート値がＶａｌｕｅ（ｒ）と一致し、Ｖｆ（ＰｋＵ，Ｖａｌｕｅ（ｒ），σｒ）＝１である場合には、Ｖａｌｕｅ（ｇｖ（ｔ））がＨＳＰ又はＦＳＰに知られていたか、又は、Ｈ内で衝突が生じたかという結論となる。Ｈが衝突抑制機能を有しているとすると、Ｖａｌｕｅ（ｇｖ（ｔ））をＨＳＰ又はＦＳＰが受信しているケースとなる。この値は、ユーザに秘密裏に生成され、事前に明かされないため、ユーザが送信したケースとなる。
【０１１７】
（密ハッシュを用いた小額支払い）
密ハッシュツリーを小額支払い手順に用いてもよい。例えば、ユーザは、密ハッシュツリーを生成して、署名されたルート値をＨＳＰに提供するとともに、ツリー内の金銭の値（トークンの数）を通知する。ＨＳＰは、ルート値及び金銭の値に署名して、ユーザに課金するとともに、署名をユーザに返信する。ユーザは、小額課金手順と同様に、これらのトークンをＦＳＰに提供する。ハッシュチェインに基づいたこのような手順の有効な点は、商業者によって送信されたトークンを有効化する銀行の演算処理が、消費されたトークンの数に比例するのではなくて、消費されたトークンの数の対数に比例する。同時に、商業者とユーザとの間の通信の複雑さが、商業者及びユーザの双方が行うべき処理時間の長さと同様に一定となる。
【０１１８】
また、本発明の実施形態では、一のツリー及び一の署名が複数の商業者用に用いられてもよい。例えば、ユーザは、複数の密ハッシュサブツリーを含むツリーを構築する。なお、各密ハッシュサブツリーは、異なるＦＳＰに対応する。各ＦＳＰは、そのＦＳＰのサブツリーからプレハッシュイメージを伴うトークンを取得する。
【０１１９】
ユーザが従来の署名手順を用いており、ユーザの公開鍵が通常の方法で確認される場合には、ユーザがＦＳＰと行う取引は匿名で行われない。ユーザとＦＳＰとの間である程度の匿名性を保つためには、グループ署名が用いられてもよい。例えば、Ｇ．Ａｔｅｎｉｅｓｅ，Ｊ．Ｃａｍｅｎｉｓｃｈ，Ｍ．Ｊｏｙｅ及びＧ．Ｔｓｕｄｉｋ著、「結託耐性を有するグループ署名手順の実践及び安全性（Ａ  Ｐｒａｃｔｉｃａｌ  ａｎｄ  Ｐｒｏｖａｂｌｙ  Ｓｅｃｕｒｅ  Ｃｏａｌｉｔｉｏｎ−Ｒｅｓｉｓｔａｎｃｅ  Ｇｒｏｕｐ  Ｓｉｇａｔｕｒｅ  Ｓｃｈｅｍｅ）」、Ｉｎ  Ｐｒｏｃ．  ｏｆ  ＣＲＹＰＴＯ  ２０００で記述された手順が用いられてもよい。なお、この手順は最新の技術である。各ユーザは、署名鍵を設定するために、グループ管理者として機能するＨＳＰに登録する。異なる信用レベルに応じてグループ公開鍵のクラスが分かれていてもよい。ＦＳＰからのサービスを要求する場合に、ユーザは、ハッシュツリーのルート値に署名鍵で署名する。ＦＳＰは、ＨＳＰによって管理されるグループにユーザが本当に含まれているか、及び、ＨＳＰが十分な信用をユーザに与えているかを調べる。ＦＳＰは、与えられた信用量を上限としてトークンを受け付ける。一方で、グループ署名手順が用いられるため、ＦＳＰは、ユーザの識別情報を知らない。請求調整時に、ＦＳＰは、通常と同様に、ユーザの識別情報を判定し、それによって課金するために、署名を「解く」ことが可能なＨＳＰにユーザの署名を転送する。ユーザがＨＳＰにも匿名性を保ちたいと希望するのならば、ＨＳＰは、ブラインド署名を用いてルート値に署名する。このような小額支払い手順では、ユーザは、ＨＳＰ及びＦＳＰが共謀してユーザと取引を行う恐れなしに、これらのトークンをＦＳＰに提供することができる。
【０１２０】
しかしながら、両方のケースにおいても、全てのハッシュ値が同じツリーのルート値に結びついているため、セッションにおける個々の取引間にはある程度の対応付けがある。しかしならが、それらのセッション間では対応関係はない。
【０１２１】
（密ハッシュツリーの多様性）
密ハッシュツリーについて若干の多様性があることを想像することができる。例えば、ツリーは、二分木ではなくて、ｋ分木であってもよい。頂点に関する共通ノードの数は深度に比例しているため、このような手法の有効な点を見つけることができなかった。ｋ分木では、ｉ番目の灰色の頂点は、証明のサイズＯ（ｋｌｏｇｋ（ｉ））を有する。他の方法は、頂点の色分け手法を異ならせることである。本実施形態では、左の子毎に色分けを行うが、これに代えて、任意の頂点を灰色に色分けするとともに、その兄弟を白色とする。本実施形態に係る手順は、この設定に拡張可能である。同様に、灰色の頂点の番号の割振り方法についても考慮したい。例えば、横幅方向ではなくて、深さ方向にまず番号を割振る場合には、ＦＳＰは、最大のＯ（ｌｏｇ２ｍ）の値のみを記憶すればよい。なお、ｍはツリーのサイズである。しかしながら、この手順の不利な点は、各葉に対する最大の証明サイズがＯ（ｌｏｇ２ｍ）であるときに、頂点の深さが深ければ、対応する証明も長くなることである。横幅方向にまず番号を割振ることによって、葉の頂点は、本発明のトークンでなくてもよい。
【０１２２】
本実施形態で記載した技術は、物やサービス（特に、電気的なもの）の提供を伴う多くのシナリオに適用可能である。例えば、このようなアプリケーションについて以下に例示する。ネットワークサービスプロバイダは、一の顧客が多くのユーザに帯域幅を再販することが可能であるという潜在的な問題を抱えており、ネットワークサービスプロバイダのこれらの潜在的な顧客が奪われてしまう。帯域幅の再販を抑制するために、ネットワークサービスプロバイダは、利用量に応じてそのユーザに課金することが（定率で課金するよりも）好ましい。本実施形態で記述した小額課金手順は、ネットワークサービスプロバイダによるこのような課金を可能とする。ユーザのトラフィックを取り扱うために、ネットワークサービスプロバイダは、ネットワークサービスプロバイダが課金に用いることが可能なトークンを送信情報の中に含めることを単に要求するだけでよい。利用にトークンが必要である場合には、利益を得るために追加料金を上乗せしなければならず、他のユーザがネットワークサービスプロバイダと直接取引きすることによって、この追加料金の支払いを避けることができるため、帯域幅の再販を試みるユーザの意欲が低減する。上述したように、ネットワークサービスプロバイダのメモリ及び演算の必要量は、（どのようなハッシュツリーを用いても）消費されたトークンの数の対数に比例するため、（特に）ネットワークサービスプロバイダが多大なトラフィック量を取り扱う場合であっても、小額課金手順の管理は、ネットワークサービスプロバイダによるネットワーク及び顧客の管理にわずかな処理負荷しか追加しない。これは、従来の手法、すなわち、取り扱われるトラフィック量に応じて直線的に演算量が増加し、拡張性が大きく劣る小額支払い手順と対象的である。
【０１２３】
（コンピュータシステムの一例）
図８は、本実施形態に係る一又は複数の処理を実行するコンピュータシステムの一例を示すブロック図である。図８に示すように、コンピュータシステム８００は、クライアント８５０又はサーバ８００のコンピュータシステムの一例であってもよい。コンピュータシステム８００は、情報を通信する通信手段又はバス８１１と、情報を処理し、バス８１１に接続された制御部８１２とによって構成される。制御部８１２は、特に限定されないが、マイクロプロセッサ（マイコン）、例えば、Ｐｅｎｔｉｕｍ（登録商標），ＰｏｗｅｒＰＣ（登録商標）、Ａｌｐｈａ（登録商標）などを含む。
【０１２４】
システム８００は、制御部８１２によって実行される指示や情報を記憶しており、バス８１１に接続された読出し書込み可能メモリ（ＲＡＭ）又は動的記憶部（メインメモリ）８０４をさらに含む。メインメモリ８０４は、制御部８１２が指示を実行する間における一時変数やその他の中間情報を記憶する。
【０１２５】
コンピュータシステム８００は、制御部８１２用の静的な情報や指示を記憶しており、バス８１１に接続された読出し専用メモリ（ＲＯＭ）及び／又は他の静的メモリ８０６と、磁気ディスク、光学ディスク及びこれに類するディスクドライブなどのデータ格納メモリ８０７をさらに含む。データ格納メモリ８０７は、情報や指示を記憶しており、バス８１１に接続されている。
【０１２６】
コンピュータシステム８００は、コンピュータのユーザに対して情報を表示し、バス８１１に接続されたＣＲＴ（ｃａｔｈｏｄｅ  ｒａｙ  ｔｕｂｅ）ディスプレイや液晶表示ディスプレイ（ＬＣＤ）などの表示部８２１を有する。英数字又は他のキーを含む英数字入力８２２は、バス８１１に接続されており、情報及び選択コマンドを制御部８１２に送る。追加ユーザ入力部は、バス８１１に接続されており、方向情報や選択コマンドを制御部８１２に送るとともに、表示部８２１上のカーソルの動きを制御するカーソルコントローラ８２３であり、トラックボール、トラックパッド、ペン又は方向キーなどである。
【０１２７】
バス８１１に接続される他の装置は、指示、データ又は他の情報をメディア（紙、フィルム又はこれに類するメディアなど）上に印刷するために用いられるプリンタ８２４である。さらに、音録音部や音再生部、例えば、スピーカ及び／又はマイクロフォンなどは、コンピュータシステム８００のオーディオインターフェースとして機能し、バス８１１に選択的に接続される。バス８１１に接続される他の装置は、電話又はＰＤＡと通信を行う有線／無線の通信機能部８２５である。
【０１２８】
一の実施形態では、システム８００は、バス８１１に接続された外部ネットワークインターフェース８２０を含む。これは、ネットワークインターフェースカード（ＮＩＣ）を含む。
【０１２９】
システム８００内のいずれか又は全ての構成、及び、関連するハードウェアは、本発明で用いられることに留意すべきである。しかしながら、他のコンピュータシステムの構成が、いくつかの又は全ての構成を含んでいてもよい。
【０１３０】
その技術分野で通常の知識を有する当業者は、上述した実施形態を読んだ後であれば、本発明の様々な代替例や変形例が明らかとなるであろう。図面を参照して説明された特定の実施形態については、いずれも限定を加えることを意図していないと理解すべきである。従って、様々な実施形態の詳細は、請求項の範囲を限定することを意図しておらず、請求項に開示された特徴のみが、本発明の本質部分であると考えるべきである。
【図面の簡単な説明】
【０１３１】
【図１】本発明の一実施形態において、サービスへのアクセスを提供する外部サービスをユーザが安全に用いるための処理を示すフロー図である。
【図２】本発明の一実施形態において、サービスを安全にユーザに提供するための外部サービスプロバイダの処理を示すフロー図である。
【図３】本発明の一実施形態において、外部サービスプロバイダを通じてユーザが接続するサービスに対して正確で安全な課金を提供するホームサービスプロバイダの処理を示すフロー図である。
【図４】本発明の一実施形態において、密ハッシュツリーを形成する処理を示すフロー図である。
【図５】本発明の一実施形態に係るユーザ装置、ホームサービスプロバイダ及び外部サービスプロバイダの構成を示すブロック図である。
【図６】本発明の一実施形態に係るユーザ装置、ホームサービスプロバイダ及び外部サービスプロバイダを含むシステム構成を示すブロック図である。
【図７】本発明の一実施形態に係る密ハッシュツリー及びマークル（Ｍｅｒｋｌｅ）ツリーの一例を示す図である。
【図８】本実施形態において、本明細書に記載された一の処理又は複数の処理を行うコンピュータシステムの一例を示す図である。
【図９】本発明の一実施形態に係るツリーの一例を示す図である。
【符号の説明】
【０１３２】
５００…システム、５０１…制御部、５０２…記憶部、５０３…通信ネットワーク、６０１…ユーザ装置、６０２…ＦＳＰ装置、６０３…ＨＳＰ装置、６１０…通信ネットワーク、６１１…通信ネットワーク、８００…コンピュータシステム、８００…サーバ、８０４…メインメモリ、８０６…静的メモリ、８０７…データ格納メモリ、８１１…バス、８１２…制御部、８２０…外部ネットワークインターフェース、８２１…表示部、８２２…英数字入力部、８２３…カーソルコントローラ、８２４…プリンタ、８２５…通信機能部、８５０…クライアント
【図１】
2007505555.tif 000011
【図２】
2007505555.tif 000012
【図３】
2007505555.tif 000013
【図４】
2007505555.tif 000014
【図５】
2007505555.tif 000015
【図６】
2007505555.tif 000016
【図７Ａ】
2007505555.tif 000017
【図７Ｂ】
2007505555.tif 000018
【図８】
2007505555.tif 000019
【図９】
2007505555.tif 000020
【国際調査報告】
2007505555.tif 000021
2007505555.tif 000022