説明

安全で小額の信用課金をサービスプロバイダが認証可能に測定するための方法及び装置

【課題】サービスプロバイダのサービスにアクセスすることを可能とする方法及び装置を提供する。
【解決手段】外部サービスプロバイダを通じて所望のサービスを要求する工程と、ハッシュツリー及びハッシュツリーのルート値のデジタル署名を生成する工程と、デジタル署名及びルート値を外部サービスプロバイダに送信する工程と、外部サービスプロバイダがデジタル署名を受け付けた場合に、一又は複数のトークンを次のパケットとともに外部サービスプロバイダに提供する工程と、外部サービスプロバイダがトークンを受け付けている間において、所望のサービスの利用を継続する工程とを方法が含む。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、ネットワーク通信とともに用いられる課金メカニズムに関する。特に、本発明は、課金の正確性の安全が効果的に暗号化されて保たれる課金メカニズムに関する。
【背景技術】
【0002】
サービスプロバイダがそのユーザに対して高度なサービスを提供するために他のサービスプロバイダと協力することが好ましい例として考えられる。会社Aが自らのネットワークを通じてインターネット接続サービスを提供している場合には、会社Aのユーザは一般的に会社Aのネットワークからしかインターネットサービスを受けることができない。しかしながら、ビジネスの見地に立てば、会社Aが会社Bと協力して他のネットワークを通じてインターネット接続を提供することは効果的である。協力関係には、会社Aが会社Bのユーザにサービスを提供する合意(例えば、会社Bのネットワークを使用したユーザに会社Aが適切に課金する処理)だけではなくて、会社Bが会社Aのユーザにサービスを提供する合意も含まれる。会社Aは、同様のサービスを会社Bのユーザに提供することについて合意してもよい。
【0003】
しかしながら、このような構成を提供しようとすると、多くの問題が生じる。第1に、会社Aは、そのユーザに対して適切に課金するために、正確な課金情報を取得しなければならない。第2に、会社Aのユーザによって会社Bのネットワークが実際よりも多く利用されたと会社Bが欺けないようにしなければならない。第3に、会社Aのユーザが会社Bのネットワークに無料で接続できないようにしなければならない。従って、課金メカニズムは、全てのユーザによる利用に対して課金できなければならない。
【0004】
従来技術によってこれらの問題を解決するためには、追加コストが大幅にかかってしまう。これらの追加コストは、金銭的なコストだけではなく、計算に必要な時間量、計算に必要な記憶容量、様々な機関が有する装置に必要な電力などである。計算、記憶、電力などについて制約を受ける携帯端末をユーザが用いる場合に、これらの要素は特に重要である。
【0005】
上述した状況を十分に効果的に扱うことが可能な方法、システム及び装置に関する従来技術は、我々の知る限りでは存在していない。
【0006】
一つの単純な解決方法は、様々な商業者によって提供されるサービスに対する支払いとして、銀行によって発行される“電子コイン”をユーザが支払う小額課金を用いる方法である。ユーザが事前にコインを購入しておき、システムがコインを引き落とす。例えば、インターネットサービスに接続された場合に、外部サービスプロバイダ(FSP;Forign Service Provider)のネットワークを通じて送信されたデータのパケットのそれぞれに一のコインをユーザが含める。外部サービスプロバイダは、コインが有効であることを認めるメカニズムを有している。コインが有効であることを認めた後に、外部サービスプロバイダは、そのコインに対応するパケットを送信する。最終的に、外部サービスプロバイダは、これらのコインの全てをホームサービスプロバイダに提供して、ネットワークの使用量を受け取る。電子支払いシステムは、他の機関が偽造できない有効な電子コインをホームサービスプロバイダのみが発行できるという意味で安全である。
【発明の開示】
【発明が解決しようとする課題】
【0007】
この単純な解決方法は、多くの欠点を有している。最初に、この解決方法は、ホームサービスプロバイダのためにうまく拡張できない。ホームサービスプロバイダは、ユーザによって用いられる全ての電子コインを発行して、発行された電子コインを各ユーザに届けなければならない。上述した例のように、外部サービスプロバイダを通じてユーザが送信するパケット毎にコインが用いられた場合には、ホームサービスプロバイダが発行しなければならないコインの量は、外部サービスプロバイダに課されるトラフィックの合計量に比例する。この合計量は非常に多量であるため、ホームサービスプロバイダに設けられた一の集中サーバが十分な量のコインを発行することは非現実的である。
【0008】
第2に、ホームサービスプロバイダは、コインが戻ってきた際に各コインを認証しなければならない。ホームサービスプロバイダがこの動作を行う二つの方法は、発行された各コインのリストを保持する方法、又は、外部サービスプロバイダと同じ認証手順を行う方法である。いずれの方法においても、ユーザによって用いられたコインの合計量に計算量が比例するため、この計算を実現することは難しい。最初の方法では、全てのコインに関する巨大なテーブルを記憶するために必要な記憶容量が非常に高価である。二つ目の方法では、記憶容量には大きな影響を与えないが、外部サービスプロバイダと同様の認証手順を行うCPUに大きな影響を与える。また、この認証手順は、テーブル検索よりも時間がかかる。
【0009】
本発明は、上述した課題を解決するためになされたものであり、サービスプロバイダのサービスにアクセスすることを可能とする方法及び装置を提供することを目的とする。
【課題を解決するための手段】
【0010】
サービスプロバイダのサービスにアクセスすることを可能とする方法及び装置である。一の実施形態では、外部サービスプロバイダを通じて所望のサービスを要求する工程と、ハッシュツリー及び前記ハッシュツリーのルート値のデジタル署名を生成する工程と、前記デジタル署名及び前記ルート値を前記外部サービスプロバイダに送信する工程と、前記外部サービスプロバイダが前記デジタル署名を受け付けた場合に、一又は複数のトークンを次のパケットとともに前記外部サービスプロバイダに提供する工程と、前記外部サービスプロバイダが前記トークンを受け付けている間において、前記所望のサービスの利用を継続する工程とを方法が含む。
【発明の効果】
【0011】
本発明によれば、サービスプロバイダのサービスにアクセスすることを可能とする方法及び装置を提供することができる。
【発明を実施するための最良の形態】
【0012】
本発明の一実施形態は、ホームサービスプロバイダ(HSP;Home Service Provider)が外部サービスプロバイダ(FSP;Forign Service Provider)と協力して、外部サービスプロバイダからサービスの提供を受けるホームサービスプロバイダのユーザから正確な課金情報を取得することを可能とする方法、構成及びシステムを含む。この方法、構成及びシステムは、全ての機関に対して効果的であり、ホームサービスプロバイダのためにうまく拡張可能で安全な課金枠組みに関する。
【0013】
本発明の一実施形態では、小額課金枠組み(microcredit scheme)に含まれるユーザ(U)は、そのユーザにのみ関連付けられた小額課金貨幣(microcredit token,以下において、単にトークンと称する)を効率的に発行することができる。具体的には、ユーザのトークンについては、そのユーザを除いた他のユーザの誰も生成することができない。ユーザは、公開鍵及び秘密鍵のペア(好ましくはHSPや他の信頼された第三者機関によって認証された公開鍵及び秘密鍵のペア)を有しており、生成された複数のトークンに対して、その秘密鍵を用いてデジタルサインを施すことが好ましい。HSPや他の信頼された第三者機関からユーザが取得する証明書は、認証可能な方法で記述されたデジタルサインを含む。デジタルサインは、ユーザの名称、公開鍵、使用が認められたサービスなどの様々な属性に加えて、証明書の有効期間などの他の属性を連結する情報である。一実施形態では、ユーザは、一つ又は複数のトークンを一度にFSPに供給し、FSPは、トークン(好ましくは、トークン及び証明書)を有効化した後に(又は、トークンを有効化している間に)、トークンに対応する量のサービスや物をユーザに提供する。
【0014】
他の実施形態では、FSPは、HSPのユーザから受信したトークンをHSPに送信する。FSPは、トークンの値に基づいてHSPから対価を受け取ることが好ましい。トークンを記憶するFSPの記憶容量の削減やHSPへの送信に用いられる周波数帯域の削減を図るために、FSPは、最初にトークンを集めることが好ましい。例えば、FSPは、ユーザから最後に受信したトークンのみを記憶(又は/及び送信)し、トークンを有効化するために必要な何らかの付属情報を記憶(又は/及び送信)してもよい。
【0015】
図9は、ツリーの一例である。最後のトークン及び共通ノードが記憶されると、ユーザ装置は認証処理を補助するために追加を送信してもよい。図9は、この点を示している。図9に示すように、ノード3は、ノード2,4,5,8,9,10,11に対応するトークンの共通ノードである。ノード6を受信した際に、その共通ノード(7,2)のみをFSPが保持している場合には、ノード8が用いられると、ユーザはノード3を再度供給する。
【0016】
または、FSPは、トークンが有効でないことを証明する証明負荷がユーザ側にある場合には、トークンを有効化するために必要な情報さえも記憶していなくてもよい。または、FSPは、抽選方式で、小さな割合(%)のトークンのみを記憶(又は/及び送信)して、元々期待していた以上の対価をHSPが支払う。
【0017】
他の実施形態では、HSPがトークンをFSPから受信し、HSPのユーザに対して適切に課金するために、これらのトークンを用いる。HSPがFSPから受信したトークンを有効化して、ユーザが消費したトークンと同等の適切なユーザ課金情報を適用することが好ましい。本発明に係る実施形態によれば、各トークンは、いくつのトークンが既に用いられたかを判定するメカニズム(及び、トークンの数が正しくないことが特定された場合に、有効化の認証は失敗に終わるメカニズム)を実現する。HSPは、トークンを認証するために必要ななんらかの付属情報をトークンとともに記憶してもよい。または、HSPは、トークンが有効でないことを証明する証明負荷がユーザ側にある場合には、トークンを有効化するために必要な付属情報を記憶しなくてもよい。または、HSPは、抽選方式で、小さな割合(%)のトークンのみを有効化(又は/及び記憶)して、元々期待していた以上の対価がHSPからFSPに支払われる。一の実施形態において、小額課金枠組みのように、FSPとの間にセッションが張られている間にユーザが用いたトークンをHSPが有効化する作業量は、ユーザが用いたトークンの数に比例しない一方で代わりにユーザが用いたトークンの数の対数に比例する。
【0018】
他の実施形態では、ユーザは、密ハッシュツリーを用いてトークンを生成してもよい。様々な実施形態で詳細に説明するように、密ハッシュツリーは、トークンの認証のために必要な記憶容量、消費量及び送信量の削減に寄与する。
【0019】
本発明の一実施形態では、システムが前払い取引ではなくて信用取引であるため(実際にはユーザがトークンを生成するため)、及び、効率的なデータ構造が採用されているため、全ての機関の効率性やHSPの拡張性を実現できる。その結果、サービスや商品の提供に広く適用可能であり、効率的で安全な課金メカニズムが構築される。
【0020】
従って、ホームサービスプロバイダ(HSP)(会社A)、外部サービスプロバイダ(FSP)(会社B)及びHSPのユーザの間で使用される本実施形態の解決方法は多くの権利範囲を含む。第1に、HSPとユーザとの関係については、本技術は、証拠を残し、又は、HSPがユーザにどれだけ課金すればよいかを示す。第2に、HSPとFSPとの関係については、本技術は、証拠を残し、FSPがHSPにどれだけ課金すればよいかを示す。第3に、FSPとユーザとの関係については、本課金メカニズムは、前述した二つの関係において必要な課金の証拠をFSPに送信した際にのみ、ユーザがFSPを介してサービスに接続可能とするメカニズムを提供する。最後に、基本的な課金メカニズムは、効果的であり、FSPのサービスを利用する際に障壁とならない。
【0021】
証拠は、全ての機関の間で行われる課金の正確性を強化する。すなわち、FSPは、HSPのユーザによるリソースの利用を過度に申告することができず、HSPは、HSPのユーザ(FSP又はHSPのリソースを利用するユーザ)に対して過度に課金することができず、ユーザは、リソースの利用に対する課金を否定することができない。
【0022】
このような課金メカニズムは、効率的である場合には、インターネット上における第三者機関サービスの安全な提供、例えば、映画や音楽などのデジタルストリームの安全な提供及び安全な支払いを含む様々なアプリケーションに適用される。
【0023】
本明細書で記述される課金メカニズムは上述した問題を解決する。一実施形態では、課金メカニズムは、大きな追加コストを生じることなく、解決方法が協力関係を阻害することもない。
【0024】
以下において、本発明を完全に説明するために様々な詳細について記述する。しかしながら、本技術分野の当業者にとっては明らかなように、これらの特定の詳述がなくても、本発明を実施することは可能である。換言すると、本発明が不明瞭となることを防ぐために、広く知られている構成や装置がブロック図に詳細に示されている。
【0025】
以下に示す本実施形態の一部分は、コンピュータのメモリー内のデータビットを処理する模式的な構成やアルゴリズムについて開示する。これらのアルゴリズムや構成は、データ処理技術に携わる当業者やデータ処理技術の本質を効果的に他の当業者に伝える当業者が用いる手段である。ここで、アルゴリズムは、一般的に、所望の結果を導く一貫した一連の処理であると考えられる。処理には、物理的な数を物理的に扱うことが要求される。必須ではないが通常は、これらの数は、電気的又は磁気的な信号の形態をとっており、記憶、転送、結合、比較され、取り扱われる。慣用表現を主とした理由から必要に応じて、これらの信号については、ビット、値、要素、符号、記号、用語、数及び色などと称する。
【0026】
しかしながら、当然のように、これらの用語や類似の用語は、適切な物理的な数に対応付いており、これらの数に適用される便利なラベルに過ぎない。以下に示すように、特に特定しない限り、「処理」、「演算」、「計算」、「判定」及び「表示」などとして使用される用語は、本明細書を通じて、コンピュータシステムや類似の電気的な演算装置の動作や処理について言及すると理解されるべきである。また、このような用語は、コンピュータシステムのレジスタやメモリ内の物理的な(かつ、電気的な)数として表されるデータを取り扱ったり、変換したりして、コンピュータシステムのレジスタ、メモリ及びその他の情報記憶部、送信装置、表示装置内の物理的な数として表される他のデータとすることとして理解されるべきである。
【0027】
本発明は、以下に示す動作を行う装置にも関する。この装置は、要求される目的のために構成された特定の装置であってもよく、コンピュータに記憶されたコンピュータプログラムによって動作したり、再構成されたりする汎用コンピュータであってもよい。このようなコンピュータプログラムは、読み出し可能な記憶媒体に格納されていてもよい。なお、記憶媒体とは、特に限定する訳ではないが、様々なタイプのディスク、例えば、フロッピーディスク、光学ディスク、CD−ROM、磁気的な光学ディスク(MO)、読み出し専用メモリ(ROM)、読み出し書き込みメモリ(RAM)、EPROM、EEPROM、磁気カード、光学カードであってもよく、電気的な指示を記憶することに適していれば、どのような媒体であってもよい。また、記憶媒体は、コンピュータシステムのバスに接続可能である。
【0028】
以下で用いられるアルゴリズムや表示装置は、特定のコンピュータや他の装置に暗示的に関係すると解釈されるべきではない。様々な汎用システムが以下で示す記述に従ったプログラムと共に用いられてもよく、簡便に構成されており、要求される処理を行う特定の装置が用いられてもよい。これらの様々なシステムに要求される構成は、以下の記述によって明らかとなるであろう。加えて、本発明は、特定のプログラム言語に従って記述されていない。本明細書で示される本発明に関する記述を行うために、様々なプログラミング言語が用いられてもよいと理解すべきである。
【0029】
機械が読み出し可能な媒体は、機械(例えば、コンピュータ)によって読み出し可能な情報を格納したり、送信したりするメカニズムであれば、どのようなメカニズムをも含む。例えば、機械が読み出し可能な媒体は、読み出し専用メモリ(ROM)、読み出し書き込みメモリ(RAM)、磁気ディスク媒体、光学記憶媒体、フラッシュメモリを含む。また、機械が読み出し可能な媒体は、電気的、光学的、聴覚的又は他の形式の伝達信号(例えば、搬送波、赤外線信号、デジタル信号など)なども含む。
【0030】
[前書き]
(モデル及び注釈)
以下に示すモデルは、ホームサービスプロバイダ(HSP)、外部サービスプロバイダ(FSP)及びユーザ(U)が含まれる。「ユーザ」は、ユーザ個人及びユーザ装置を示すことに留意すべきである。公開鍵や共通鍵が存在する基盤を前提としており、HSP及びユーザの双方は、一対の鍵である公開鍵及び秘密鍵を有している。一対の鍵は、「Sk、Pk」として表され、Skは、メッセージに付される署名を演算するための秘密鍵であり、Pkは、Skに対応する公開鍵である。電子署名(Sk,M)は、メッセージMに付される署名σを署名鍵Skで暗号化するアルゴリズムを示しており、Vf(Pk,M,σ)は、認証アルゴリズムを示している。説明を明確にするために、特定の個人に属する鍵について下付文字で示す。従って、HSP用の一対の鍵は、(PkHSP、SkHSP)と示され、ユーザ用の一対の鍵は、(Pk、Sk)と示される。
【0031】
以下において、{0,1}を全てのビット列を示すものとする。ビット列については、その長さを|s|と示す。Hは、bビットのペイロードとvビットの初期ベクトル(IV)を入力してvビットの出力を得る暗号圧縮機能を示す。全ての広く知られた構造として、b≧2vであると想定する。本明細書で示す構造は、一般的にb=2vである。これらの暗号圧縮機能は衝突抑制であると想定される。すなわち、H(IV,m)=H(IV,m)などのように二つの異なる入力を区別することは難しい。IVは、固定であり、公開されていると想定される。IVは、ハッシュ機能に関するものとして常に明確に記述される訳ではないことに留意すべきである。これらの暗号圧縮機能の実際例は、SHA−1やMD5で公開されている。前者の圧縮機能では、出力及びIVのサイズは20バイトであり、後者の圧縮機能では、出力及びIVのサイズは16バイトである。双方のペイロードのサイズは64バイトである。本実施形態の技術で用いられる枠組みは、圧縮機能によって圧縮されるペイロードよりも大きいデータは扱わない。しかしながら、圧縮機能によって圧縮されるペイロードよりも大きいデータは扱う技術として、ハッシュやマークルツリーなどのような様々な標準技術が存在する。
【0032】
ビット長を保つ機能fについては、{0,1}→{0,1}であり、整数i≧1である場合に、fは、f−畳み込み合成を示す。すなわち、i=1である場合には、f(x)=f(x)であり、i>1である場合には、f(x)=f(fk−1(x))である。機能fは、xがランダムに選択されたf(x)が与えられた場合に、f(z)=f(x)のような元の値zを見つけることがほとんどできない程難しい一方通行の機能である。一方通行の機能fは、一方通行の繰り返しであり、任意のiによってf(x)が与えられた場合に、f(z)=f(x)のような元の値zを見つけることがほとんどできない程難しい。実際には、一般的な予備機能として、ハッシュ機能Hによって一方通行の繰り返しを開始し、その長さを維持するためにペイロードの一部にパディングビットが埋め込まれる。
【0033】
最後に、実際の数字rについて、rの上限として
【数1】

【0034】
すなわち、r以上の最も小さい整数値がセットされる。同様に、rの下限として
【数2】

【0035】
すなわち、r以下の最も大きい整数値がセットされる。
【0036】
(マークルツリー)
以下において、マークルツリー(Merkle tree)について説明する。各値が{0,1}であるm個の値x,・・・,xがあると想定する。簡略化するために、mは2乗であると想定する。H:{0,1}2n→{0,1}は、2nビットをnビットに変換する暗号ハッシュ機能であるとする。ハッシュ機能Hによってx,・・・,xに対応付けられたマークルツリーは、各ノードが特定の値(v)に対応付けられた正規二分木である。マークルツリーでは、m個の葉があり、各葉iの値(l)=x,1≦i≦mである。内部の頂点vとして、値C(v)及び値C(v)が左及び右の子を示す。oが連鎖処理を示すとすると、値(v)=H(IV,値(C(v))o値(C(v)))となる。
【0037】
マークルツリーは、デジタル署名においてダイジェストデータとして用いられ、署名されたダイジェストは、ルートに対応付けられた値となる。また、基礎となる圧縮機能が衝突抑制である場合には、マークルツリーのルートの値が同じである二つの異なるメッセージを見分けることは困難である。
【0038】
(密ハッシュツリー)
本発明の一実施形態において、蜜ハッシュツリーを生成する手法について説明する。これらの方法は、内部頂点に番号が割り振られている点を除いて、マークルツリーと類似する。簡略化するために、m個の値x,・・・,xがあり、mは、kが正の整数である場合に2と等しいと想定して説明する。マークルツリーと同様に、深さがk+1である正規二分木が生成され、以下の手順で各頂点に値が割り当てられる。H:{0,1}2n→{0,1}は、暗号ハッシュ機能であるとする。次に、以下に示すように2つの色分けに分類する方法がツリーの各ノードに適用される。ルートは、白色に色分けされる。ルートの左側の子は、灰色に色分けされ、ルートの右側の子は白色に色分けされる。我々の手法では、ツリーの各頂点は、頂点がその親の左側の子である場合には灰色に色分けされ、頂点がその親の右側の子である場合には白色に色分けされる。最終的に、灰色に色分けされたノードに対して横幅方向から順に番号が割り振られる。すなわち、ツリーのトップから順に次のレベルに下っていき、各灰色ノードに左から右に順に番号が割り振られる。
【0039】
例えば、ナンバー1がルートの左側の子に割り振られる。ナンバー2がルートの左側の子の左の子に割り振られる。ナンバー3がルートの右側の子の左の子に割り振られる。ナンバー4がルートの左側の子の左の子に割り振られる。ナンバー5がルートの左側の子の右の子の左の子に割り振られる。ナンバー6がルートの右側の子の左の子の左の子に割り振られる。ナンバー7がルートの右側の子の右の子の左の子に割り振られる。以下同様である。
【0040】
i番目の頂点にはgv(i)が割り振られる。図7A及び図7Bは、23個の頂点を有しており、15個の小額課金取引に用いられる密ハッシュツリーの一例を示している。各内部ノードには、その子のハッシュ値と同じ値が割り当てられている。各左の子には、上から下へ、左から右へ順に番号が割り振られている。図7Bは、23個の頂点を有するマークルツリーを示している。ハッシュツリーは、基本部分として15個の頂点を有するが、8個の頂点が追加的に下にぶら下がっている。このツリーは、8個の小額課金取引にしか用いることができない。内部頂点を用いることによって、同じサイズのツリーでほぼ2倍の小額課金取引を可能とすることによって、全体として効果的な改善が図られる。
【0041】
密ハッシュツリーで与えられる頂点には共通ノード(CoNodes)の概念が用いられる。頂点vについて、CoNodes(v)は、頂点vからルートへの道筋にある頂点(兄弟)のセットである。Sib(v)及びParent(v)がそれぞれ頂点vの兄弟及び親を示しているとすると、CoNodes(v)は以下の式によって表される。
【数3】

【0042】
最終的に、共通ノードのセットでは、値(CoNodes(v))は、頂点vの共通ノードに割り当てられた値を示す。
【0043】
一実施形態において、共通ノードについて、ルートの値を計算する処理は以下に示す通りである。i番目の灰色頂点に割り振られる値をvとし、i番目の灰色頂点からルート頂点への道筋にある全ての頂点である兄弟の値をv,・・・vとする。ルートの値は、hとして算出される。ここで、h=H(v o v)であり、h=H([hi−1,v]であり、[h,v]は、vが左側の子である場合にはv o hと等しく、vが右側の子である場合にはh o vと等しい。
【0044】
上述したように、密ハッシュツリーの番号割振りの一例について説明したが、親ノードが子ノードよりも前にくれば、どのような番号割振りを用いてもよい。この場合に、k番目の小額課金は、k番目の番号が割り振られたノードの子のうち、k番目のノードの共通ノードを含む。このような番号割振りによれば、ユーザの送信コスト及びFSPの認証コストについて効果を有する。しかしながら、他の番号割振りでは、k番目の小額課金がlog(k)よりも長い認証パスを有することもある。予め定められた順序で横方向に番号をノードに割振ることによって、ツリーを「横切る」際にメモリと演算とのトレードオフが好ましい関係となる(ツリーを横切ることは、k−1番目の小額課金を演算した後にユーザがキャッシュメモリに格納するツリー情報の総量とキャッシュメモリに格納されたツリー情報からk番目の小額課金を演算する演算量とのトレードオフを伴う。実際に、トレードオフは、マークルツリーで見つけられた最も良いトレードオフよりも良好である。この理由は、密ハッシュツリーは、マークルツリーと異なり、内部ノードの全てを用いるからである。ツリーについてルートノードの値を演算するためには、n個のハッシュ値が要求される。密ハッシュでは、n個の小額貨幣が生成可能であるのに対して、マークルツリーでは、{(n+1)/2}個の小額貨幣しか生成することができない。この2倍の関係は横切りアルゴリズム演算に引き継がれるため、予め順序が定められた横断密ハッシュツリーでは、一の小額課金に対して半分の演算量しか必要にならない。特に断らない限りは、以下において、横幅方向に番号を割振る密ハッシュツリーについて主に説明する。
【0045】
(課金メカニズムの一例に関する様々な実施形態)
本発明の実施形態は、ホームサービスプロバイダ(HSP)と関係を有するユーザにサービスを外部サービスプロバイダ(FSP)が提供することを可能とする安全な課金方法、構成及びシステムを提供するように構成されている。ユーザは、HSPとの関係を有することによって、好ましくは信用取引で、FSPのサービスを受けることが可能である。その後、HSPは、ユーザが提供を受けたサービスに対して、適切な対価をFSPに支払う。ユーザは、HSPから請求を受けることが好ましい。FSP及びHSPは同じ装置であってもよい。従って、本発明の実施形態に係る課金メカニズムは、第三者機関によるサービスの提供に限定されるものではない。
【0046】
ここで記載する実施形態に係る課金技術は、二つの決定的な特徴、すなわち、安全及び効率を含む。第1の特徴は、不正なFSP、HSP及びユーザが正確な課金を妨げることを防止する暗号化による安全である。具体的には、FSPがユーザによるサービスの利用量を過度に申告すること、(FSPに対して)、HSPがFSPのネットワークをユーザした利用量を少なく申告すること、又は、(ユーザに対して)、HSPがFSPのネットワークをユーザした利用量を過度に申告すること、(HSP及びFSPのいずれかに対して)、ユーザがFSPのネットワークの利用量をごまかすことを暗号化によって不可能にすることである。以下において詳細に説明するように、ユーザは、拒否できないように認証してトークンを消費するため、トークンは支払いを否認不可能である。支払いを否認不可能であることは請求に疑義を生じない。請求の疑義を解決するには費用が発生し、これらの費用は一般的にユーザの負担となるため、これは非常に重要である。つまり、課金の正確性が暗号化によって保たれ、強化される。
【0047】
第2の特徴は、効率であり、これも重要である。本発明の実施形態は、協力的なビジネスの関係の発展を容易にすることを可能とし、この関係の妨げとならない。一の実施形態では、課金メカニズムは、これを利用する機関に対して可能な限り透過的である。以下において詳細に説明するように、ここで記載する実施形態は、従来技術の方法に比べて演算効率が高い。
【0048】
HSPのユーザがFSPのサービス(対価を条件とする)の利用を許可することについてHSP及びFSPが合意していると想定すると、FSPのサービスを利用しようとするユーザは、(HSPのユーザであるため)HSPとの関係をFSPに明示する。本発明の一の実施形態では、これはデジタル証明書の利用によって実現される。例えば、FSPが知っている公開鍵をHSPが有している場合に、HSPは、ユーザがHSPの顧客であることを証明する証明書を秘密鍵によって生成できる。この証明書は、例えば、
【数4】

【0049】
の形式を有している。証明書では、ユーザ名、ユーザの公開鍵Pk及び証明書の有効期間を示す値を含む「デジタル文書」に、HSPが秘密鍵PkHSPを用いて署名する。または、HSPは、他の方法を用いて、ユーザがHSPの顧客であることをFSPに証明してもよい。HSPではない信頼された機関が証明書を生成してもよく、HSPの顧客であることをユーザが証明することを可能とする他のメカニズムを用いてもよい。これによって、安全性の観点から、ユーザがHSPの顧客であること及びユーザの公開鍵が本物であることをFSPが確認する。
【0050】
(小額課金貨幣(トークン)の生成)
一の実施形態では、ユーザは、自身のトークンを生成する。ユーザのトークンを他の構成要素が生成してもよいことは勿論である。例えば、HSPがユーザのトークンを生成してもよいが、(以下で詳細に説明するように)HSPが全てのユーザのトークンを生成することはHSPの拡張性を低下させる。ユーザが自身のトークンを生成することによってHSPの処理負荷が軽減される。または、ユーザのトークンを他の構成要素が生成してもよい。しかしながら、これらの構成要素は、ユーザの同意なしにトークンをFSPに提示しないように信頼されていなければならない。また、ユーザ以外の構成要素がユーザのトークンを生成することは、支払いを拒否できないという効果をなくしてしまう(例えば、他の誰かがユーザのトークンを生成すると、ユーザは、他の誰かによってトークンが消費されたと主張することができる)。
【0051】
ユーザは、マークルツリーや密ハッシュツリーなどのようなハッシュツリーを用いてトークンを生成することが好ましい。これは、効率的な面で好ましい。SHA−1のように、ハッシュ機能は、軽い演算処理で強力な暗号化が得られることで従来から知られている。トークンは他の方法で生成されてもよいことは勿論である。例えば、ユーザは、HSPから直接トークンを受信する。このような場合には、HSPが銀行のように振る舞い、FSPが商業者のように振舞うという「支払い」手順が潜在的に存在する。この場合に、一の実施形態では、HSPは、まとめや認証を効率的に行うという特徴を有する好ましい支払い手順を提供する密ハッシュツリーを用いてトークンを生成する。さらに、ツリーが分かれている場合には、HSPによって発行された同一の署名を複数のユーザが用いることができる。従って、本発明の一実施形態は、支払い手順の枠組みを用いることが可能であり、従来技術に比べて有利な点を有する。
【0052】
他の実施形態では、ユーザは、公開鍵による署名手順を用いて自身のトークンを生成することが可能であり、FSPに提示される署名として支払いを拒否できない署名を生成する。しかしながら、公開鍵による署名手順のアルゴリズムは、ハッシュ機能よりも演算量の面で効率が落ちてしまう。従って、一の実施形態では、公開鍵による暗号化の利用を減らすために、公開鍵による署名を個々のトークンに適用しない。一方で、一の実施形態では、支払いを拒否できないようにするために、公開鍵による署名アルゴリズムは、ハッシュツリーのルートの署名として(一度だけ)用いられる。この支払いを拒否できない署名は、ツリーに関する全てのトークンがユーザの識別子に対応付けられるように、ユーザの識別子とハッシュツリーの全体とを対応付ける。従って、一の署名に係る負荷は多くの取引で償還される。
【0053】
一の実施形態では、一回のセットアップ段階がある。一回のセットアップ段階は、以下のステップによって実行される。
【0054】
1.HSPは、公開鍵(PkHSP)及び秘密鍵(SkHSP)のペアを生成する。HSPは、取引がある各ユーザ及び各FSPに公開鍵を提供する。
【0055】
2.各ユーザは、公開鍵(Pk)及び秘密鍵(Sk)のペアを生成する。ユーザは、PkをHSPに提供して、対応する秘密鍵を知っていることを証明する。この処理は、一連のチャレンジメッセージに署名すること、又は、ゼロ知識証明を提供することによって完了する。
【0056】
3.ユーザが秘密鍵を知っていることの証明に成功し、HSPの加入者であると認定された場合には、HSPは、証明書データ(CertData=〈U,Pk,dexp,dissue,II〉を生成する。なお、dexp及びdissueは、証明書の満了データ及び開始データであり、IIは、どのサービスが認定されたかを示す方針特定情報などである。満了データの日付は、実際の日付であってもよく、開始日付から換算して証明書が有効である期間を特定する日付(例えば、365日)であってもよい。
【0057】
4.HSPは、σ=Sign(SkHSP,CertData)を演算して、(σ,CertData)をユーザに提供する。公開鍵の枠組みでは、HSPが証明書の発行元である点に留意すべきである。
【0058】
5.ユーザは、Vf(PkHSP,CertData,σ)=1であることを確認する。1である場合には、ユーザはこれを受け入れ、1でない場合には、ユーザはその旨をHSPに知らせる。
【0059】
一の実施形態では、ハッシュツリーは密ハッシュツリーである。一の実施形態では、ハッシュツリーの生成は以下のステップで構築される。
【0060】
1.ユーザは、最初に必要なトークンの数であるmを算出する。この算出は正確でなくてもよい。ユーザが少なく算出した場合には、ユーザはトークンを取引中にさらに生成すればよい。しかしながら、処理効率の観点でいえば、ユーザは可能な限り正確に算出すべきである。
【0061】
2.ユーザは、m+1のビット列をランダムに生成する。各ビット列は、暗号化に適した長さnビット(例えば、n=160ビット)を有することが好ましい。
【0062】
3.ユーザは、m+1個の葉(2m+1個のノード)を有する(略)正規二分木を生成する。ユーザは、ランダムに生成されたビット列を葉に割り当てる。
【0063】
4.ユーザは、内部ノードの子の値に従って、各内部ノード(ルートノードを含む)に割り振る値を演算する。例えば、ユーザは、Value(v)=H(IV,Value(C(v) o value(C(v)))の式に従って内部ノードの値を演算する。C及びCは、内部ノードの子である。
【0064】
図4は、一実施形態において、密ハッシュツリーを構築する処理を示すフロー図である。処理は、ハードウェア(回路、デジタルロジックなど)、ソフトウェア(汎用コンピュータや個別機器などで行われる処理)又はこれらの組合せである処理ロジックによって実行される。
【0065】
図4に示すように、処理ロジックは、送信が要求されるパケットの上限を算出する処理(ステップ401)を開始する。この上限はmで表される。次に処理ロジックは、m個の葉を有する二分木を生成する(ステップ402)。処理ロジックは、二分木を生成した後に、ランダムなnビット値を各葉に割り当てる(ステップ403)。nは、ハッシュ機能のペイロードサイズである。nビット値が各内部ノードに割り当てられると、処理ロジックは、子の一連のハッシュ値として出力される値を各内部ノードに割り当てる(ステップ404)。
【0066】
そして、処理ロジックは、ノードを色分け(分類)する(ステップ405)。一の実施形態では、処理ロジックは、ルートに白色を割り当て、左の子の頂点に灰色を割り当て、右の子の頂点に白色を割り当てる。ノードの色分けが終わると、処理ロジックは、灰色のノードに番号を割り振る(ステップ406)。一実施形態では、処理ロジックは、レベル毎に木の横方向に左から右へ横断して、灰色のノードに番号を割り振る。処理ロジックは、ルートの左の子に1を割り当てて、順に番号を割り振る。色分けアルゴリズムは、説明を目的とするものであり、ノードを二つに分類する方法としてどのようなメカニズムを用いてもよい。
【0067】
この手順としては、様々なバリエーションが考えられる。例えば、ツリーは二分木である必要はないが、二分木は、各ノードが有する兄弟が少ないため、共通ノードが少ない傾向を有する点で好ましい。また、内部ノードは、異なる式に従って演算されてもよい(例えば、ノードの見出し番号、トークンの宛先となるFSPの識別子及びその他の情報を各ハッシュの入力が含む)。
【0068】
(課金手順の概略の流れ)
上述したように、ユーザは、ツリーのルートに関するデジタル署名をその秘密鍵を用いて生成することが好ましい。ツリーのルートに対する値として値(ルート)が算出されたとする。ユーザの署名は、Sk(値(ルート))として算出される。ユーザは、(ルート値の他に)サイン書類に追加情報を含めてもよい。例えば、ユーザは、トークンの宛先となるFSPの識別子、ツリーからFSPが取得するトークンの最大値、HSPからFSPがトークンの対価を受け取る前に満たさなければならない条件、その他の情報を含めてもよい。ユーザがFSPからのサービスへのセッションを開始する場合に、ユーザは、ルート値、ルート値に対する署名、公開鍵、ユーザとHSPとの関係を証明する信頼された機関からの証明書を、(好ましくは、セッション開始時に)FSPに送信する。これらの情報をFSPが既に有している場合には、ユーザがこれらの情報を送信する必要はない。例えば、過去にユーザがFSPに接続したことがある場合には、FSPは、証明書を既に有している。一部分が既に消費された古いツリーを用いた新しいセッションの開始をユーザが要求する場合には、FSPは、ルート値及びルート値に対する署名を有していてもよい。
【0069】
ユーザの公開鍵及び(署名された他の情報とともに)署名されたルート値を含むユーザの署名を受信すると、FSPは、署名手順の認証アルゴリズムによって署名が正当であることを認証する。署名手順としては、従来技術で広く知られているように、認証手順は、一般的に、署名、公開鍵及び入力されたメッセージを用いて、書名が有効であるか否かを示す真偽値;Vf(σ,PK,M)=0 or 1を出力する。FSPは、同様の手順によって、信頼された機関によって発行された証明書を認証する。
【0070】
一の実施形態では、FSPがユーザから受け取る「支払い」は、(上述したように、署名及び証明書情報に加えることが可能な)プレハッシュイメージによって構成される。プレハッシュイメージは、ハッシュツリーの生成に伴うハッシュ機能の入力である。本実施形態で用いられるように、ハッシュ機能は、(入力から出力を容易に演算できるが、出力から入力を演算することが難しい)一方通行であるため、FSPは、プレハッシュイメージを自身で演算することは難しい。トークンがハッシュツリーを用いて生成されていなければ、支払いは異なった形式を採ることは勿論である。例えば、ユーザがトークンを署名手順で生成した場合には、各トークンはデジタル署名によって構成される。但し、これは演算量が多くなることに留意すべきである。
【0071】
セッション開始時に、ユーザ及びFSPは、支払いの生成方法について交渉することが好ましい。例えば、支払いは、FSPがサービスを提供する前になされたり、FSPが全てのサービスを提供した後になされたりする。これらの手順のいずれにも共通することであるが、本発明の実施形態はもっと柔軟な手順を可能とする。例えば、FSPのサービスが小さく個別の部分に分けられる場合には、FSPは、「順次増やしながら」サービスを提供してもよい。すなわち、FSPは、追加のトークンをユーザが納めた後に、個別の部分のサービスを提供する。例えば、FSPは、映像をストリーム配信するサービスをユーザに提供する場合には、k番目のトークンを受信した後に、ストリームに含まれるk番目のフレームを送信する。簡潔で一般的に説明するために、以下において、ユーザがトークンをFSPに順次納めるケースについて説明する。
【0072】
ユーザが密ハッシュツリーを用いる本発明の一実施形態では、k番目のトークンは、gv(k)の値を含んでおり、gv(k)は、横幅方向に番号が割振られる密ハッシュツリーにおけるk番目の灰色頂点(ツリーにおけるk番目の左側の子)、及び、共通ノードの値(CoNodes(gv(k))である。密ハッシュツリーのノードには、異なった手順で番号が割振られてもよい(例えば、ツリーにおけるk番目のノードは、右側から番号が割振られるツリーにおけるk番目の右側の子、又は、他の番号割振り手順が用いられてもよい)。しかしながら、本実施形態では、簡潔に説明するために、上述した手順で番号が割振られるものとする。詳細に説明したように、効率が落ちるが、密ハッシュツリーではなくて、マークルツリーを本発明に用いてもよいことは、当業者にとって明らかである。
【0073】
ユーザは、ハッシュツリーの生成方法に類似した手順でk番目のトークンを演算してもよい。ユーザがハッシュツリーを演算する際に用いたn+1の葉の値は、ツリーに含まれる全てのノードの値を再演算するために必要な全ての情報をユーザに提供する。従って、各ノードの値は、k番目のトークンの値に対応する。簡潔にするために、ユーザは、小さな秘密の「種」を用いてn+1の葉の値を演算してもよい。この種を用いることによって、ユーザは、k番目のトークンを演算するために必要などの葉の値であっても再演算することができる。この種は、不正な攻撃に対する耐性を保つために十分な長さ(例えば、80ビット以上の長さ)を有するべきである。小さな種の値を用いることによって、n+1個の値をユーザが記憶しておくことを防ぐことができる。または、ユーザは、再演算を行わなくてもよいように、ツリーに含まれる全てのノードの値を記憶していてもよい。または、ユーザは、ユーザが有する記憶容量とトークンのために必要な値の再演算に必要な再演算量との最適なトレードオフの関係を選択してもよい。マークルツリーの場合には、演算量と記憶容量とのトレードオフについて広く知られた関係が存在する。具体的には、次のマークルの道筋を演算するためには、logmの演算量及びlogmの記憶容量が必要であり、mはツリーの葉に割振られた番号である。密ハッシュツリーに含まれるノードの番号が異なった手順で割振られる場合には、子とその親との間にノードを挿入するためにツリーの構造を若干修正して、密ハッシュツリーで「横方向に番号を割振る手順」にこの方法を拡張して用いることができる。この拡張機能では、灰色のノードには、親の左の子がその親よりも先になって右の子が後になるように、左から右へ番号が割り振られる。以前の処理では、k番目のトークンは、k番目の灰色のノードの値とともに、その共通ノードの値によって構成される。この場合では、共通ノードは、密ハッシュツリーに「挿入」されたノードの一つとなる。密ハッシュツリーで効率的に横方向に番号を割振る手順(又は、密ハッシュツリーの若干の変更)については、様々な方法が用いられてもよい。
【0074】
k番目の部分を受信するためには、ユーザはk番目のトークンをFSPに送信する。共通ノードのgv(k)がj<kであるgv(j)の値に対応しており、k>1であり、かつ、番号の割振り方が通常である密ハッシュツリーが用いられる場合であって、これらの共通ノードの値をFSPが記憶している場合には、これらの共通ノードの値をFSPに再送しなくてもよい。
【0075】
FSPは、gv(k)の値及びユーザが署名したハッシュツリーのルートの値であるCoNodes(gv(k)の値によって、k番目のトークンを認証する。具体的には、実際のハッシュツリーの内部ノードの値(例えば、Value(v)=H(IV,Value(C(v)) o Value(C(v))))を演算する際に用いる方法と同様に、FSPは、H(IV,Value(gv(k)) o CoNodes(Sibling(gv(k)))によってValue(Parent(gv(k))を演算するなどして、gv(k)及びCoNodes(gv(k))の仮の値を用いて、ルートノードの仮の値を演算する。FSPは、ルートノードの仮の値が(認証された)ユーザの署名に含まれる実際のルート値と同じである場合には、k番目のトークンを有効なものとして受け入れる。それ以外の場合には、FSPは、k番目のトークンを受け入れない。FSPは、トークンが有効であるか否かに応じて、ユーザへのサービスを継続又は中断する。
【0076】
上述したように、FSPは、ユーザから以前に提示されたノード及び共通ノードの値を記憶する。これによって、FSPは、k番目のトークンを認証するために必要な時間を削減する。例えば、これらの値の全てをFSPが記憶している場合には、Praent(gv(k))に対応する値は既に記憶されている。このような場合には、FSPは、gv(k)とその兄弟ノードがハッシュ関数によってこれらの親の値となること(すなわち、(H(IV,Value(gv(k)) o CoNodes(Sibling(gv(k)))がValue(Parent(gv(k))と等しいこと)のみを確認すればよい。
【0077】
FSPとユーザとの間でセッションが終了した場合、又は、トークンを扱うためのハッシュツリーをFSP及びユーザが使用しなくなった場合には、FSPは、記憶容量を削減するために、最後にユーザから送信されたトークンのみを記憶する。最後のトークンがgv(k)及びその共通ノードによって構成されている場合について考える。FSPは、(好ましくは見出しkとともに)gv(k)の値のみを記憶して、共通ノードの値をメモリから削除するという選択肢を有する。これの効果は、FSPに必要とされるメモリ容量の削減に他ならない。これのマイナス効果は、共通ノードの値が認証に必要なため、省略されたトークンを認証することができなくなってしまうことである。
【0078】
以下の記述において、省略されたトークンは、否認不可能トークン又は否認不可能小額課金と称する。その理由は、否認不可能トークンを認証することができなくなったとしても、トークンが有効であればユーザは否認することができないからである。k番目の否認不可能小額課金が有効でないことを証明するためには、ユーザは、ハッシュ関数によってユーザが署名したルート値を生成するgv(k)の共通ノードの値とともに、小額課金に含まれるものとは異なるgv(k)の値を生成できなければならない。ユーザがこれをできない場合には(なお、ハッシュ機能の衝突抑制によって、トークンが有効である場合には不可能である)、否認不可能トークンは有効であるとみなされる。自己を防衛するために、ユーザは、ハッシュツリーの生成に用いられる種の値を記憶しておくことが好ましい。ユーザは、別々のハッシュツリーを生成するために交互に用いられる第2の種の値を記憶していることも好ましい。つまり、有効な否認不可能トークンは、ユーザの協力なしではトークンを認証することができないが、ユーザがトークンを消費したことを否認できない証拠となる。従って、(HSP、FSP及びユーザの間で合意が継続している場合には)、(省略された)否認不可能トークンのみをFSPが記憶することが許容される。
【0079】
ユーザが、「マルチ署名」又は「ひとまとめの署名」を可能とする署名手順で署名を生成した場合には、FSPは複数の署名を記憶するために必要な記憶容量を削減できる。従って、複数のトークンを記憶するために必要な記憶容量も削減できる。例えば、ユーザがRSA署名手順を用いる場合には、複数の書類に付される多くのRSA署名は、単に一つにまとめられて(RSAモジュールのモジュロをとって)、各書類の許可を示しており、認証可能で簡易なマルチ署名としてまとめられる。このように、ひとまとめの署名は、この設定では複数署名よりも有効である。また、ユーザは、ひとまとめにされる複数の書類に複数の機関によって付される複数署名を可能とする署名手順を用いてもよい。ユーザがこのような署名手順を用いる場合には、FSPは、記憶容量(及び、HSPに署名を送信する際の周波数帯域)を削減するために、ユーザの署名をひとまとめにできる。本発明の他の実施形態では、HSPは、暗号化された安全な「グループ署名」手順を設定することができる。また、ユーザは、この手順を用いて書名を生成することができる。この場合には、FSPはユーザを識別することができないが、ユーザがHSPの本当のユーザであることがグループ署名手順の暗号化によって保障される。しかしながら、FSPは、(同じセッション内に限られるが)同じ署名によって行われる通信を関連付けることができる。関連付けが可能な理由は、トークンが一つの署名に関連付けられるからである。一般的に、グループ署名では、グループマネージャ以外が二つの署名をまとめることができない。HSPは、グループ署名手順でグループマネージャとして機能するため、署名したユーザと署名とを対応付けることが可能である。
【0080】
FSP及びユーザは、セッションの終了後に、前のセッションで用いたハッシュツリーを継続して用いて、前のセッションで最後に用いられたトークンに続くトークンで開始してもよい。
【0081】
FSPがユーザから受信したトークンの対価を要求しようとする場合には、FSPは、ユーザから受信した最後のトークンをHSPに送信することが好ましい。最後のトークンについては、(全ての必要な共通ノードの値が含まれており)認証可能又は否認不可能である。FSPは、署名された情報(用いられたハッシュツリーのルート値を含むことが好ましい)とともに、ユーザの署名を送信することが好ましい。FSPは、いくつかの最後のトークンを一回の送信で送れるように、最後のトークンの送信を遅延させることが好ましい。
【0082】
トークンが否認不可能であるが認証できなかった場合に、HSPは、トークンが有効であることを示す追加保証をFSPに要求する。例えば、HSPは、FSPの暗号鍵を用いて、否認不可能なトークンの認定について生じる解決費用をHSPに返済することを保証する署名をFSPに要求する。HSP及びFSPの間には他の合意があってもよい。
【0083】
認証可能なトークンをFSPから受信すると、HSPは、FSPが認証する方法と同様に、トークンを認証する。k番目のトークンが送信されてきた場合には、HSPは、一の署名認証及び
【数5】

【0084】
ハッシュ演算を行うことによって、k番目のトークンを認証する。HSPの認証負荷は、上述した支払い手順と同様にkに比例せずに、kの対数に比例する。これは、HSPの処理負荷を大幅に軽減し、支払い方法の拡張性を大幅に向上する。トークンが有効であるとHSPが判定した場合には、HSPは、トークンを記憶するとともに、ユーザにサービスを提供したことに対して適切な対価をFSPに支払う。
【0085】
否認不可能トークンをHSPが受信した場合には、HSPはこれを認証できない。しかしながら、HSPは、ルート値(又は、他の情報)に対するユーザの署名の有効性を確認できる。書名が有効である場合には、HSPは、(将来的に疑義が生じた場合に備えて)トークンを記憶するとともに、HSP及びFSPの合意に従って適切な対価をFSPに支払う。HSPは、更なる可能性についてトークンの有効性を確認した後に、ユーザに対する課金を請求する。
【0086】
(フロー図の一例)
図1は、一実施形態において、サーバへの接続を可能とする外部サービスを安全に使用するユーザの処理を示すフロー図である。処理は、ハードウェア(回路、デジタルロジックなど)、ソフトウェア(汎用コンピュータや個別機器などで行われる処理)又はこれらの組合せである処理ロジックによって実行される。
【0087】
図1に示すように、処理は、処理ロジックによって開始される。処理ロジックは、外部サービスプロバイダ(FSP)を通じて所望のサービスに接続(アクセス)する(ステップ101)。次に、処理ロジックは、ハッシュツリーのルート値に応じて、密ハッシュツリー及びデジタル署名を生成する(ステップ102)。そして、処理ロジックは、デジタル署名、ルート値及び証明書をFSPに送信する(ステップ103)。
【0088】
処理ロジックは、FSPが署名を受け付けるか否かを判定する(ステップ104)。FSPが署名を受け付けなかった場合には、処理ロジックは処理を終了する。FSPが署名を受け付けた場合には、処理ロジックは、次の小額課金貨幣(トークン)を次のパケットとともにFSPに送信する(ステップ105)。そして、処理ロジックは、小額課金貨幣(トークン)をFSPが受け付けるか否かを判定する(ステップ106)。FSPがトークンを受け付けなかった場合には、処理ロジックは処理を終了する。FSPがトークンを受け付けた場合には、処理ロジックは、このサービスの継続をユーザが希望するか否かを判定する(ステップ107)。サービスの継続を希望しない場合には、処理ロジックは処理を終了する。サービスの継続を希望する場合には、処理ロジックは、ステップ105の処理に移り、処理を継続する。
【0089】
ユーザがトークンを使い果たした場合には、ユーザは、他の密ハッシュツリーを生成するとともにルートに署名して、妥当な情報をFSPに提供する。この結果、他の署名演算及び認証が必要となるが、望ましくない。しかしながら、ハッシュの処理負荷は、署名に比べて軽く、ユーザは、多量のトークンを生成することによって、わずかな代償で備えることができる。密ハッシュツリーを用いる顕著な効果は、認証時間が灰色の頂点の対数に比例することである。通常のツリーを用いる場合には、認証時間は、ツリーの高さに比例するであろう。後者では、ユーザが最終的に使用するトークンよりも多量のトークンを生成した場合に、認証時間が致命的に長くなる。
【0090】
図2は、一実施形態において、外部サービスプロバイダが安全にサービスをユーザに提供する処理を示すフロー図である。図2に示す処理は処理ロジックによって実行される。処理ロジックは、ハードウェア(回路、デジタルロジックなど)、ソフトウェア(汎用コンピュータや個別機器などで行われる処理)又はこれらの組合せであってもよい。
【0091】
図2に示すように、処理は、FSPの処理ロジックによって開始される。FSPの処理ロジックは、サービス要求をユーザから受信する(ステップ201)。そして、FSPの処理ロジックは、デジタル署名、ルート値及び証明書を受信する(ステップ202)。処理ロジック及びFSPは、署名を受け付けるか否かを判定する。署名を受け付けない場合には、処理ロジックは処理を終了する。署名を受け付ける場合には、FSPの処理ロジックは、ステップ204の処理に移り、要求されたサービスを提供する。また、FSPの処理ロジックは、小額課金貨幣(トークン)を待つ(ステップ205)。
【0092】
処理ロジックは、小額課金貨幣(トークン)をユーザが送信するか、及び/又は、ユーザがサービスの継続を要求するかを判定する(ステップ206)。そうでない場合には、処理ロジックは処理を終了する。そうである場合には、処理ロジックは、小額課金貨幣(トークン)が有効であるかを判定する(ステップ207)。トークンが有効でない場合には、処理ロジックは処理を終了する。トークンが有効である場合には、処理ロジックはステップ204の処理に移り、処理を継続する。
【0093】
図3は、一実施形態において、ホームサービスプロバイダが、外部サービスプロバイダを通じたサービスへのアクセスに対して、正確で安全に課金する処理を示すフロー図である。処理は、処理ロジックによって実行される。処理ロジックは、ハードウェア(回路、デジタルロジックなど)、ソフトウェア(汎用コンピュータや個別機器などで行われる処理)又はこれらの組合せであってもよい。
【0094】
図3に示すように、処理は、処理ロジックによって開始される。処理ロジックは、FSPから受信する小額課金貨幣(トークン)を待つ(ステップ301)。処理ロジックが小額課金貨幣(トークン)を受信した場合には(ステップ302)、処理ロジックは、トークンが有効であるかを判定する(ステップ303)。トークンが有効でない場合には、処理ロジックは、問題解決方針に従って処理を進め(ステップ304)、処理を終了する。トークンが有効である場合には、処理ロジックは、小額課金貨幣(トークン)の数に応じて、ユーザへの課金額を加算して(ステップ305)、処理を終了する。
【0095】
(構成及びシステムの一例)
個々の構成が図5に示されている。この構成は、本発明の一実施形態に係るユーザ装置、HSP装置、及び/又は、FSP装置であってもよい。
【0096】
図5は、一実施形態に係るユーザ装置、HSP装置又はFSP装置を示すブロック図である。図5に示すように、制御部501は、記憶部502に接続されている。制御部501は、本実施形態で記載された一又は複数の処理を実行する。記憶部502は、データ又は/及び指示を制御部501に供給して、制御部501とともに動作する。記憶部502は、暗号鍵を記憶していてもよい。システム500は、通信ネットワーク503に接続されており、通信ネットワーク503と情報を交換する。システム500の詳細について以下で説明する。
【0097】
本発明の一の実施形態に係るユーザ、外部サービスプロバイダ及びホームサービスプロバイダを有するシステム構成が図6に示されている。
【0098】
図6は、ユーザ、HSP及びFSPを有するシステム構成を示す図である。図6に示すように、ユーザ装置601は、通信ネットワーク610を介してFSP装置602と通信可能である。同様に、FSP装置602は、通信ネットワーク611を介してHSP装置603と通信可能である。通信ネットワーク610及び611は、異なる通信ネットワークであってもよいことに留意すべきである。ユーザ装置601は、FSP装置602にサービスを要求したり、FSP装置602からサービスを受けたりするために、ユーザによって生成されたトークンがFSP装置602に提供される通信ネットワーク610を用いる。同様に、FSP装置602は、課金を行うためにサービス利用情報がHSP装置603に提供される課金段階を行うために、通信ネットワーク611を用いる。
【0099】
(その他の実施形態)
その他の実施形態では、処理が以下のように行われる。
【0100】
1.ユーザは、どの程度のサービスの利用を希望するかを、取引が行われる数の観点で算出する。ここでは、この数はmによって表される。この算出は必ずしも正確でなくてもよく、上述したように、ユーザは、追加のトークンをいつでも生成することができる。正確性によって処理効率が向上するため、ユーザは、少なめに算出するよりも、多めに算出するほうが好ましい。
【0101】
2.ユーザは、(m+1)=2の葉(これは灰色の頂点に対応する)を有する密ハッシュツリーを構築する。rがツリーのルートを表すものとする。ユーザは、σ=Sign(Sk、FSP、Value(r))を演算する。ユーザは、〈h Value(r),σ,CertData,σ〉をFSPに送信するととともに、正式にサービス要求を行う。
【0102】
3.FSPは、要求されたサービスをユーザが本当に利用することが可能か確かめるために、IIを調べる。次に、FSPは、証明書データCertDataによって、dissue<dexpであるかを認証する。最後に、FSPは、Vf(PkHSP,CertData,σ)=1であり、かつ、Vf(Pk,Value(r),σ)=1であるかを判定する。これらが正しい場合には、FSPは、サービス要求を受け付ける。そうでなければ、FSPは、例えば、サービスの提供を拒否するなどのように、適切な方針に従って処理を進める。また、証明書手順が取消メカニズムとともに動作する場合には、証明書は有効性のために確認される。行われた処理は、本手順と本質的に無関係である。
【0103】
4.各期間iにおいて、ユーザがサービスの継続を希望する場合には、ユーザは、i番目のトークンをFSPに提供する。i番目のトークンは、Value(gv(i))及び(後続がある場合には)Value(Sib(gv(i))である。
【0104】
5.FSPは、i≦(m−1)/2である場合には、hv=H(Value(gv(i)) o Value(Sib(gv(i)))を演算し、その他の場合には、単にhv=H(Value(gv(i)))を演算する。iが偶数である場合には、FSPは、hv=Value(gv(i/2))であるかを確認する。そうでない場合には、FSPは、hv=Value(Sib(gv((i−1)=2)))であるかを確認する。FSPがこれらの演算を行うことが可能なのは、Value(gv(i/2))及びValue(Sib(gv((i−1)=2)))を反復
【数6】

【0105】
で受信するためである。これらの確認が成功した場合には、FSPは、ユーザのトークンを受け付ける。そうでなければ、FSPは、ユーザのトークンを拒否して、恐らくは何らかの警告とともにサービスを終了するなどのように適切な方針を適用する。
【0106】
(課金)
ユーザが適切な署名手順を用いる場合には、HSPは、FSPが可能であるように、メモリを節約するために署名をバッチ処理することができる。また、HSPは、FSPと同様に、署名の認証をバッチ処理することができる。
【0107】
本発明の実施形態にかかる方法及びシステムは、「抽選方式」手順で機関が課金することと互換性があり、特に、HSP及びFSPは、メモリや送信の必要量をさらに削減することが可能である。この手順では、ユーザによって支払われたトークンを償還しなくてもよくすること、又は、その期待値が何回も償還されるようにすることが可能である。HSP及びFSPは、当選したトークンのみを記憶すればよい。抽選システムの不利な点は三要素である。
【0108】
1.機関の間で行われる課金は、FSPの運、不運に左右されるため(ユーザの運、不運に左右されるため)、全体として正確ではない。
【0109】
2.手順の隠れた不正確さが高額な課金について議論を引き起こす
3.(FSP及びHSPがトークンの数の対数に比例するメモリ容量のみを必要とするため)小額課金手順が潜在的に指数関数に従ってメモリの必要量を削減することを可能とするのに対して、抽選システムは、定常的な要素についてメモリの必要量を削減可能である。
【0110】
このような抽選方式手順は、小額支払い手順とともに従来技術で記載されているが、本発明の小額課金手順にこの手順を適用することは、もし望めば容易である。
【0111】
トークンのサイズ(帯域幅)とHSPがトークンを認証するのに必要な時間との間にトレードオフの関係があることについて着目する価値がある。一の実施形態では、横幅方向に番号を割振る密ハッシュツリーを用いると、k番目のトークンはO(log(k))のノード値によって構成されており、O(log(k))回の認証が行われる。ハッシュチェインは一定のサイズを有する一方でO(k)回の認証回数が必要となる。二分木のノードの値をハッシュチェインに置き換えることによって、トレードオフの関係を見つけることが可能である。チェインが長さlを有する場合には、密ハッシュ/ハッシュチェイン小額課金手順のハイブリッドを得る。k番目のトークンのサイズは、最も大きい1+log(k/l)となり、認証時間は、最も大きいl(log(k/l))となる。
【0112】
(ポーリング)
本実施形態に係る手順において、不正が行われる危険性の増加によって徒労に終わる演算の減少を図るために、少なくとも2つの場所でポーリングを組み込んでもよい。1番目については、FSPがトークンをユーザから受信した場合に、FSPは、直ちにトークンを認証するか否かを所定の確率に従って選択することができる(但し、これは、必ず認証される最初のトークン及び最後のトークンには当てはまらない)。ユーザが不正を行おうとしたケースにおいて、最後のトークンが認証された場合又はユーザに請求するために用いられる有効なトークンが以前にいくつかある場合には、ユーザはほとんど捕まらない。このようなユーザの振る舞いをFSPが監視していれば、ポーリングを行う確率を動的に変更することができる。
【0113】
また、請求調整段階にポーリングを組み合わせることもできる。例えば、FSPを通じたサービスへのアクセスをユーザが終了したと想定する。さらに、彼らが生成した密ハッシュツリーのルートがそれぞれr,・・・,rであり、彼らが用いたサービスの総量がそれぞれt,・・・,tであると想定する。請求調整時には、FSPは、<Value(r),t>,・・・,<Value(r),t>をHSPに送信する。次に、HSPは、i,・・・,i∈{1,・・・,s}を示すkのセットを取り出して、これらをFSPに送信する。最終的に、FSPは、
【数7】

【0114】
を送信する。これらは、FSPがHSPに送信するために準備した値によって構成される。しかしながら、最初の段階でFSPが<Value(r),t>,・・・,<Value(r),t>を送信しているため、FSPは自身を約束する。今、HSPは、送信された値を通常行うように認証する。いれかの認証が失敗した場合には、HSPは、警告を発するとともに、恐らくペナルティをFSPに課す。
【数8】

【0115】
の中から後に疑義が生じた場合には、それはHSPによって直接取り扱われる。一方で、他のユーザについて疑義が生じた場合には、HSPは、ユーザからFSPに送信した情報を要求することができる。FSPが不正を行った場合には、r,・・・,rが既に約束されているため、FSPは捕まる。一方で、FSPが不正を行っていない場合には、HSPは、他のユーザに対する利用証明を生成することができる。
【0116】
ユーザが利用したよりも多いサービスについて課金されていると主張するという意味で、課金に関する疑義が生じた場合には、HSP及びFSPの双方は、〈t,Value(r),σ,Value(gv(t)),Value(CoNodes(gv(t)))〉を提示することによって、正確な量を証明できる。Value(gv(t))及びValue(CoNodes(gv(t)))を用いて演算されたルート値がValue(r)と一致し、Vf(Pk,Value(r),σ)=1である場合には、Value(gv(t))がHSP又はFSPに知られていたか、又は、H内で衝突が生じたかという結論となる。Hが衝突抑制機能を有しているとすると、Value(gv(t))をHSP又はFSPが受信しているケースとなる。この値は、ユーザに秘密裏に生成され、事前に明かされないため、ユーザが送信したケースとなる。
【0117】
(密ハッシュを用いた小額支払い)
密ハッシュツリーを小額支払い手順に用いてもよい。例えば、ユーザは、密ハッシュツリーを生成して、署名されたルート値をHSPに提供するとともに、ツリー内の金銭の値(トークンの数)を通知する。HSPは、ルート値及び金銭の値に署名して、ユーザに課金するとともに、署名をユーザに返信する。ユーザは、小額課金手順と同様に、これらのトークンをFSPに提供する。ハッシュチェインに基づいたこのような手順の有効な点は、商業者によって送信されたトークンを有効化する銀行の演算処理が、消費されたトークンの数に比例するのではなくて、消費されたトークンの数の対数に比例する。同時に、商業者とユーザとの間の通信の複雑さが、商業者及びユーザの双方が行うべき処理時間の長さと同様に一定となる。
【0118】
また、本発明の実施形態では、一のツリー及び一の署名が複数の商業者用に用いられてもよい。例えば、ユーザは、複数の密ハッシュサブツリーを含むツリーを構築する。なお、各密ハッシュサブツリーは、異なるFSPに対応する。各FSPは、そのFSPのサブツリーからプレハッシュイメージを伴うトークンを取得する。
【0119】
ユーザが従来の署名手順を用いており、ユーザの公開鍵が通常の方法で確認される場合には、ユーザがFSPと行う取引は匿名で行われない。ユーザとFSPとの間である程度の匿名性を保つためには、グループ署名が用いられてもよい。例えば、G.Ateniese,J.Camenisch,M.Joye及びG.Tsudik著、「結託耐性を有するグループ署名手順の実践及び安全性(A Practical and Provably Secure Coalition−Resistance Group Sigature Scheme)」、In Proc. of CRYPTO 2000で記述された手順が用いられてもよい。なお、この手順は最新の技術である。各ユーザは、署名鍵を設定するために、グループ管理者として機能するHSPに登録する。異なる信用レベルに応じてグループ公開鍵のクラスが分かれていてもよい。FSPからのサービスを要求する場合に、ユーザは、ハッシュツリーのルート値に署名鍵で署名する。FSPは、HSPによって管理されるグループにユーザが本当に含まれているか、及び、HSPが十分な信用をユーザに与えているかを調べる。FSPは、与えられた信用量を上限としてトークンを受け付ける。一方で、グループ署名手順が用いられるため、FSPは、ユーザの識別情報を知らない。請求調整時に、FSPは、通常と同様に、ユーザの識別情報を判定し、それによって課金するために、署名を「解く」ことが可能なHSPにユーザの署名を転送する。ユーザがHSPにも匿名性を保ちたいと希望するのならば、HSPは、ブラインド署名を用いてルート値に署名する。このような小額支払い手順では、ユーザは、HSP及びFSPが共謀してユーザと取引を行う恐れなしに、これらのトークンをFSPに提供することができる。
【0120】
しかしながら、両方のケースにおいても、全てのハッシュ値が同じツリーのルート値に結びついているため、セッションにおける個々の取引間にはある程度の対応付けがある。しかしならが、それらのセッション間では対応関係はない。
【0121】
(密ハッシュツリーの多様性)
密ハッシュツリーについて若干の多様性があることを想像することができる。例えば、ツリーは、二分木ではなくて、k分木であってもよい。頂点に関する共通ノードの数は深度に比例しているため、このような手法の有効な点を見つけることができなかった。k分木では、i番目の灰色の頂点は、証明のサイズO(klog(i))を有する。他の方法は、頂点の色分け手法を異ならせることである。本実施形態では、左の子毎に色分けを行うが、これに代えて、任意の頂点を灰色に色分けするとともに、その兄弟を白色とする。本実施形態に係る手順は、この設定に拡張可能である。同様に、灰色の頂点の番号の割振り方法についても考慮したい。例えば、横幅方向ではなくて、深さ方向にまず番号を割振る場合には、FSPは、最大のO(logm)の値のみを記憶すればよい。なお、mはツリーのサイズである。しかしながら、この手順の不利な点は、各葉に対する最大の証明サイズがO(logm)であるときに、頂点の深さが深ければ、対応する証明も長くなることである。横幅方向にまず番号を割振ることによって、葉の頂点は、本発明のトークンでなくてもよい。
【0122】
本実施形態で記載した技術は、物やサービス(特に、電気的なもの)の提供を伴う多くのシナリオに適用可能である。例えば、このようなアプリケーションについて以下に例示する。ネットワークサービスプロバイダは、一の顧客が多くのユーザに帯域幅を再販することが可能であるという潜在的な問題を抱えており、ネットワークサービスプロバイダのこれらの潜在的な顧客が奪われてしまう。帯域幅の再販を抑制するために、ネットワークサービスプロバイダは、利用量に応じてそのユーザに課金することが(定率で課金するよりも)好ましい。本実施形態で記述した小額課金手順は、ネットワークサービスプロバイダによるこのような課金を可能とする。ユーザのトラフィックを取り扱うために、ネットワークサービスプロバイダは、ネットワークサービスプロバイダが課金に用いることが可能なトークンを送信情報の中に含めることを単に要求するだけでよい。利用にトークンが必要である場合には、利益を得るために追加料金を上乗せしなければならず、他のユーザがネットワークサービスプロバイダと直接取引きすることによって、この追加料金の支払いを避けることができるため、帯域幅の再販を試みるユーザの意欲が低減する。上述したように、ネットワークサービスプロバイダのメモリ及び演算の必要量は、(どのようなハッシュツリーを用いても)消費されたトークンの数の対数に比例するため、(特に)ネットワークサービスプロバイダが多大なトラフィック量を取り扱う場合であっても、小額課金手順の管理は、ネットワークサービスプロバイダによるネットワーク及び顧客の管理にわずかな処理負荷しか追加しない。これは、従来の手法、すなわち、取り扱われるトラフィック量に応じて直線的に演算量が増加し、拡張性が大きく劣る小額支払い手順と対象的である。
【0123】
(コンピュータシステムの一例)
図8は、本実施形態に係る一又は複数の処理を実行するコンピュータシステムの一例を示すブロック図である。図8に示すように、コンピュータシステム800は、クライアント850又はサーバ800のコンピュータシステムの一例であってもよい。コンピュータシステム800は、情報を通信する通信手段又はバス811と、情報を処理し、バス811に接続された制御部812とによって構成される。制御部812は、特に限定されないが、マイクロプロセッサ(マイコン)、例えば、Pentium(登録商標),PowerPC(登録商標)、Alpha(登録商標)などを含む。
【0124】
システム800は、制御部812によって実行される指示や情報を記憶しており、バス811に接続された読出し書込み可能メモリ(RAM)又は動的記憶部(メインメモリ)804をさらに含む。メインメモリ804は、制御部812が指示を実行する間における一時変数やその他の中間情報を記憶する。
【0125】
コンピュータシステム800は、制御部812用の静的な情報や指示を記憶しており、バス811に接続された読出し専用メモリ(ROM)及び/又は他の静的メモリ806と、磁気ディスク、光学ディスク及びこれに類するディスクドライブなどのデータ格納メモリ807をさらに含む。データ格納メモリ807は、情報や指示を記憶しており、バス811に接続されている。
【0126】
コンピュータシステム800は、コンピュータのユーザに対して情報を表示し、バス811に接続されたCRT(cathode ray tube)ディスプレイや液晶表示ディスプレイ(LCD)などの表示部821を有する。英数字又は他のキーを含む英数字入力822は、バス811に接続されており、情報及び選択コマンドを制御部812に送る。追加ユーザ入力部は、バス811に接続されており、方向情報や選択コマンドを制御部812に送るとともに、表示部821上のカーソルの動きを制御するカーソルコントローラ823であり、トラックボール、トラックパッド、ペン又は方向キーなどである。
【0127】
バス811に接続される他の装置は、指示、データ又は他の情報をメディア(紙、フィルム又はこれに類するメディアなど)上に印刷するために用いられるプリンタ824である。さらに、音録音部や音再生部、例えば、スピーカ及び/又はマイクロフォンなどは、コンピュータシステム800のオーディオインターフェースとして機能し、バス811に選択的に接続される。バス811に接続される他の装置は、電話又はPDAと通信を行う有線/無線の通信機能部825である。
【0128】
一の実施形態では、システム800は、バス811に接続された外部ネットワークインターフェース820を含む。これは、ネットワークインターフェースカード(NIC)を含む。
【0129】
システム800内のいずれか又は全ての構成、及び、関連するハードウェアは、本発明で用いられることに留意すべきである。しかしながら、他のコンピュータシステムの構成が、いくつかの又は全ての構成を含んでいてもよい。
【0130】
その技術分野で通常の知識を有する当業者は、上述した実施形態を読んだ後であれば、本発明の様々な代替例や変形例が明らかとなるであろう。図面を参照して説明された特定の実施形態については、いずれも限定を加えることを意図していないと理解すべきである。従って、様々な実施形態の詳細は、請求項の範囲を限定することを意図しておらず、請求項に開示された特徴のみが、本発明の本質部分であると考えるべきである。
【図面の簡単な説明】
【0131】
【図1】本発明の一実施形態において、サービスへのアクセスを提供する外部サービスをユーザが安全に用いるための処理を示すフロー図である。
【図2】本発明の一実施形態において、サービスを安全にユーザに提供するための外部サービスプロバイダの処理を示すフロー図である。
【図3】本発明の一実施形態において、外部サービスプロバイダを通じてユーザが接続するサービスに対して正確で安全な課金を提供するホームサービスプロバイダの処理を示すフロー図である。
【図4】本発明の一実施形態において、密ハッシュツリーを形成する処理を示すフロー図である。
【図5】本発明の一実施形態に係るユーザ装置、ホームサービスプロバイダ及び外部サービスプロバイダの構成を示すブロック図である。
【図6】本発明の一実施形態に係るユーザ装置、ホームサービスプロバイダ及び外部サービスプロバイダを含むシステム構成を示すブロック図である。
【図7】本発明の一実施形態に係る密ハッシュツリー及びマークル(Merkle)ツリーの一例を示す図である。
【図8】本実施形態において、本明細書に記載された一の処理又は複数の処理を行うコンピュータシステムの一例を示す図である。
【図9】本発明の一実施形態に係るツリーの一例を示す図である。
【符号の説明】
【0132】
500…システム、501…制御部、502…記憶部、503…通信ネットワーク、601…ユーザ装置、602…FSP装置、603…HSP装置、610…通信ネットワーク、611…通信ネットワーク、800…コンピュータシステム、800…サーバ、804…メインメモリ、806…静的メモリ、807…データ格納メモリ、811…バス、812…制御部、820…外部ネットワークインターフェース、821…表示部、822…英数字入力部、823…カーソルコントローラ、824…プリンタ、825…通信機能部、850…クライアント

【特許請求の範囲】
【請求項1】
外部サービスプロバイダを通じて所望のサービスを要求する工程と、
ハッシュツリー及び前記ハッシュツリーのルート値のデジタル署名を生成する工程と、
前記デジタル署名及び前記ルート値を前記外部サービスプロバイダに送信する工程と、
前記外部サービスプロバイダが前記デジタル署名を受け付けた場合に、一又は複数のトークンを次のパケットとともに前記外部サービスプロバイダに提供する工程と、
前記外部サービスプロバイダが前記トークンを受け付けている間において、前記所望のサービスの利用を継続する工程とを含むことを特徴とする方法。
【請求項2】
ユーザ装置が一又は複数の前記トークンを生成する工程を含むことを特徴とする請求項1に記載の方法。
【請求項3】
前記ユーザ装置が前記ハッシュツリーを用いて前記トークンを生成することを特徴とする請求項2に記載の方法。
【請求項4】
前記ハッシュツリーは、密ハッシュツリーであり、
前記密ハッシュツリーを構築する工程をさらに含み、
前記密ハッシュツリーは、
必要であると算出された前記トークンの数と同数である複数のビット列をランダムに生成し、
算出された前記トークンに1を加えた数と同数である複数の葉を有する二分木を構築し、
ランダムな前記ビット列を前記葉に割り当て、
内部ノードの子の値に従って各内部ノードに割り当てられる値を演算することによって構築されることを特徴とする請求項3に記載の方法。
【請求項5】
前記複数のビット列を生成する工程は、一の種から前記複数のビット列を生成する工程を含むことを特徴とする請求項4に記載の方法。
【請求項6】
前記ランダムなビット列は、暗号化に適した長さを有することを特徴とする請求項4に記載の方法。
【請求項7】
前記ハッシュツリーは、マークルツリー及び密ハッシュツリーによって構成されるグループの中から選択されたものであることを特徴とする請求項3に記載の方法。
【請求項8】
ユーザ装置が、公開鍵署名を用いて前記ハッシュツリーの前記ルートに署名する公開鍵署名手順を用いて、一又は複数の前記トークンを生成することを特徴とする請求項1に記載の方法。
【請求項9】
秘密鍵を用いて前記ハッシュツリーの前記ルート値の前記デジタル署名を生成する工程を含むことを特徴とする請求項1に記載の方法。
【請求項10】
ユーザ装置が、前記トークンの宛先となる前記外部サービスプロバイダの識別情報によって構成される一又は複数のグループ、前記外部サービスプロバイダが受信する前記トークンの最大値、及び、前記トークンの対価を受け取る前に前記外部サービスプロバイダが満たすべき条件を、一又は複数の前記トークンのそれぞれに含めることを特徴とする請求項1に記載の方法。
【請求項11】
前記ハッシュツリーの前記ルート値の前記デジタル署名と、ユーザ装置の公開鍵と、前記ユーザと当該ユーザのサービスプロバイダとの関係を証明する信頼された機関から受け取る証明書とを前記外部サービスプロバイダに送信する工程を含むことを特徴とする請求項1に記載の方法。
【請求項12】
前記トークンは、支払いの否認が不可能なトークンであることを特徴とする請求項1に記載の方法。
【請求項13】
密ハッシュツリーを生成する工程と、
署名のためにホームサービスプロバイダに前記ルート値を提供する工程と、
前記密ハッシュツリーの金銭の値を前記ホームサービスプロバイダに通知する工程と、
前記密ハッシュツリーに基づいて金銭を前記外部サービスプロバイダに提供する工程を含むことを特徴とする請求項1に記載の方法。
【請求項14】
外部サービスプロバイダを通じて所望のサービスを要求する外部ネットワークインターフェースと、
記憶部と、
前記外部ネットワークインターフェース及び前記記憶部に接続された制御部とを備え、
前記制御部は、
ハッシュツリー及び前記ハッシュツリーのルート値のデジタル署名を、前記記憶部を用いて生成し、
前記外部ネットワークインターフェースを介して、前記デジタル署名及び前記ルート値を前記外部サービスプロバイダに送信し、
前記外部サービスプロバイダが前記デジタル署名を受け付けた場合に、一又は複数のトークンを次のパケットとともに前記外部サービスプロバイダに提供し、
前記外部サービスプロバイダが前記トークンを受け付けている間において、前記所望のサービスの利用を継続することを特徴とする装置。
【請求項15】
ユーザ装置が一又は複数の前記トークンを生成することを特徴とする請求項14に記載の装置。
【請求項16】
前記ユーザ装置が前記ハッシュツリーを用いて前記トークンを生成することを特徴とする請求項15に記載の装置。
【請求項17】
前記ハッシュツリーは、マークルツリー及び密ハッシュツリーによって構成されるグループの中から選択されたものであることを特徴とする請求項16に記載の装置。
【請求項18】
前記制御部は、公開鍵署名を用いて前記ハッシュツリーの前記ルートに署名する公開鍵署名手順を用いて、一又は複数の前記トークンを生成することを特徴とする請求項14に記載の装置。
【請求項19】
前記制御部は、前記トークンの宛先となる前記外部サービスプロバイダの識別情報によって構成される一又は複数のグループ、前記外部サービスプロバイダが受信する前記トークンの最大値、及び、前記トークンの対価を受け取る前に前記外部サービスプロバイダが満たすべき条件を、一又は複数の前記トークンのそれぞれに含めることを特徴とする請求項14に記載の装置。
【請求項20】
前記制御部は、前記ハッシュツリーの前記ルート値の前記デジタル署名と、ユーザ装置の公開鍵と、前記ユーザと当該ユーザのサービスプロバイダとの関係を証明する信頼された機関から受け取る証明書とを、前記外部ネットワークインターフェースを介して前記外部サービスプロバイダに送信することを特徴とする請求項14に記載の装置。
【請求項21】
前記トークンは、支払いの否認が不可能なトークンであることを特徴とする請求項14に記載の装置。
【請求項22】
前記制御部は、
署名のためにホームサービスプロバイダに密ハッシュツリーのルート値を提供し、
前記ホームサービスプロバイダが前記外部サービスプロバイダにサービスの対価を支払うことを可能とする前記密ハッシュツリーの金銭の値を前記ホームサービスプロバイダに通知することを特徴とする請求項14に記載の装置。
【請求項23】
外部サービスプロバイダを通じて所望のサービスを要求する手段と、
ハッシュツリー及び前記ハッシュツリーのルート値のデジタル署名を生成する手段と、
前記デジタル署名及び前記ルート値を前記外部サービスプロバイダに送信する手段と、
前記外部サービスプロバイダが前記デジタル署名を受け付けた場合に、一又は複数のトークンを次のパケットとともに前記外部サービスプロバイダに提供する手段と、
前記外部サービスプロバイダが前記トークンを受け付けている間において、前記所望のサービスの利用を継続する手段とを備えることを特徴とする装置。
【請求項24】
複数の指示を格納する一又は複数の記憶媒体を有しており、システムによって実行される場合に、システムに方法を実行させる製造物であって、
外部サービスプロバイダを通じて所望のサービスを要求する工程と、
ハッシュツリー及び前記ハッシュツリーのルート値のデジタル署名を生成する工程と、
前記デジタル署名及び前記ルート値を前記外部サービスプロバイダに送信する工程と、
前記外部サービスプロバイダが前記デジタル署名を受け付けた場合に、一又は複数のトークンを次のパケットとともに前記外部サービスプロバイダに提供する工程と、
前記外部サービスプロバイダが前記トークンを受け付けている間において、前記所望のサービスの利用を継続する工程とを実行させることを特徴とする製造物。
【請求項25】
サービスを供給するサービスプロバイダとは異なるサービスプロバイダを有するユーザから前記サービスを要求するサービス要求を受信する工程と、
デジタル署名、ルート値及び証明書を前記ユーザから受信する工程と、
前記デジタル署名が受付可能であり、一又は複数のトークンをユーザから受信したと判定したことに応じて、前記ユーザに前記サービスを提供する工程とを含むことを特徴とする方法。
【請求項26】
認証アルゴリズムを用いて前記ユーザからの前記デジタル署名を認証することを特徴とする請求項25に記載の方法。
【請求項27】
前記認証アルゴリズムは、前記デジタル署名、公開鍵及びメッセージに基づいて、前記デジタル署名が有効であるかを示すブーリーン値を出力することを特徴とする請求項26に記載の方法。
【請求項28】
一又は複数の前記トークンは、プレハッシュイメージを含むことを特徴とする請求項25に記載の方法。
【請求項29】
前記トークンを受信した後に前記サービスを提供する工程をさらに含むことを特徴とする請求項25に記載の方法。
【請求項30】
前記トークンを受信する前に前記サービスを提供する工程をさらに含むことを特徴とする請求項25に記載の方法。
【請求項31】
複数の前記トークンの受信に連動して、前記サービスを順次提供する工程をさらに含むことを特徴とする請求項25に記載の方法。
【請求項32】
前記トークンは、支払いの否認が不可能なトークンであることを特徴とする請求項25に記載の方法。
【請求項33】
前記ユーザの前記デジタル署名及び署名された情報とともに、一又は複数の前記トークンを前記ユーザのホームサービスプロバイダに送信する工程を含むことを特徴とする請求項25に記載の方法。
【請求項34】
前記署名された情報は、ハッシュツリーのルート値を含むことを特徴とする請求項33に記載の方法。
【請求項35】
受信した複数の前記トークンの一部分を認証するとともに、前記トークンの有効性に関して以前に行われた前記ユーザの不正行為に基づいてポーリングを調整する工程を含むことを特徴とする請求項25に記載の方法。
【請求項36】
サービスを供給するサービスプロバイダとは異なるサービスプロバイダを有するユーザ装置から所望のサービスを要求するサービス要求を受信し、デジタル署名、ルート値及び証明書を前記ユーザ装置から受信する外部ネットワークインターフェースと、
プログラム指示を記憶する記憶部と、
外部ネットワークインターフェース及び記憶部に接続された制御部とを備え、
前記制御部は、
前記プログラム指示は、前記デジタル署名が受付可能かを前記制御部に判定させ、一又は複数のトークンを前記制御部に受信させ、前記デジタル署名が受付可能であり、一又は複数の前記トークンをユーザから受信したと判定したことに応じて、前記制御部に前記所望のサービスを前記ユーザに提供させることを特徴とする外部サービスプロバイダ。
【請求項37】
前記制御部は、認証アルゴリズムを用いて前記ユーザからの前記デジタル署名を認証することを特徴とする請求項36に記載の外部サービスプロバイダ。
【請求項38】
一又は複数の前記トークンは、プレハッシュイメージを含むことを特徴とする請求項36に記載の外部サービスプロバイダ。
【請求項39】
前記トークンは、支払いの否認が不可能なトークンであることを特徴とする請求項36に記載の外部サービスプロバイダ。
【請求項40】
前記制御部は、前記外部ネットワークインターフェースを介して、前記ユーザの前記デジタル署名及び署名された情報とともに、一又は複数の前記トークンを前記ユーザのホームサービスプロバイダに送信することを特徴とする請求項36に記載の外部サービスプロバイダ。
【請求項41】
サービスを供給するサービスプロバイダとは異なるサービスプロバイダを有するユーザから前記サービスを要求するサービス要求を受信する手段と、
デジタル署名、ルート値及び証明書を前記ユーザから受信する手段と、
前記デジタル署名が受付可能であり、一又は複数のトークンをユーザから受信したと判定したことに応じて、前記ユーザに前記サービスを提供する手段とを備えることを特徴とする装置。
【請求項42】
複数の指示を格納する一又は複数の記憶媒体を有しており、システムによって実行される場合に、システムに方法を実行させる製造物であって、
サービスを供給するサービスプロバイダとは異なるサービスプロバイダを有するユーザから前記サービスを要求するサービス要求を受信する工程と、
デジタル署名、ルート値及び証明書を前記ユーザから受信する工程と、
前記デジタル署名が受付可能であり、一又は複数のトークンをユーザから受信したと判定したことに応じて、前記ユーザに前記サービスを提供する工程とを実行させることを特徴とする製造物。
【請求項43】
ユーザのサービスプロバイダとは異なるサービスプロバイダからユーザトークンを受信する工程と、
前記ユーザトークンが有効であるかを判定する工程と、
前記ユーザトークンが有効である場合に、前記ユーザトークンに基づいて前記ユーザに課金する工程とを含むことを特徴とする方法。
【請求項44】
前記ユーザトークンが有効でない場合に、問題解決方針に従って処理を進める工程を含むことを特徴とする請求項43に記載の方法。
【請求項45】
ユーザのサービスプロバイダとは異なるサービスプロバイダからユーザトークンを受信する外部ネットワークインターフェースと、
プログラム指示を記憶する記憶部と、
前記外部ネットワークインターフェース及び記憶部に接続された制御部とを備え、
前記制御部は、前記ユーザトークンが有効であるかを判定するとともに、前記ユーザトークンが有効である場合に、前記ユーザトークンに基づいて前記ユーザに課金する前記プログラム指示を実行することを特徴とするホームサービスプロバイダ。
【請求項46】
前記ユーザトークンが有効でない場合に、問題解決方針に従って処理を進めることを特徴とする請求項45に記載のホームサービスプロバイダ。
【請求項47】
ユーザのサービスプロバイダとは異なるサービスプロバイダからユーザトークンを受信する手段と、
前記ユーザトークンが有効であるかを判定する手段と、
前記ユーザトークンが有効である場合に、前記ユーザトークンに基づいて前記ユーザに課金する手段とを備えることを特徴とする装置。
【請求項48】
前記ユーザトークンが有効でない場合に、問題解決方針に従って処理を進める手段を備えることを特徴とする請求項47に記載の装置。
【請求項49】
複数の指示を格納する一又は複数の記憶媒体を有しており、システムによって実行される場合に、システムに方法を実行させる製造物であって、
ユーザのサービスプロバイダとは異なるサービスプロバイダからユーザトークンを受信する工程と、
前記ユーザトークンが有効であるかを判定する工程と、
前記ユーザトークンが有効である場合に、前記ユーザトークンに基づいて前記ユーザに課金する工程とを実行させることを特徴とする製造物。
【請求項50】
前記ユーザトークンが有効でない場合に、問題解決方針に従って処理を進める工程を含むことを特徴とする請求項49に記載の製造物。
【請求項51】
送信されるべきパケットの数を判定する工程と、
前記パケットの数と同数である複数の葉を有する二分木を生成する工程と、
前記二分木の前記葉のそれぞれにランダム値を割り当てる工程と、
子の値の一連のハッシュ値として出力される値を各内部ノードに割り当てる工程と、
ルートに関して左側の子の全てに番号を割振る工程とを含むことを特徴とする方法。
【請求項52】
外部サービスプロバイダを通じて所望のサービスを要求する外部ネットワークインターフェースと、
プログラム指示を記憶する記憶部と、
前記外部ネットワークインターフェース及び前記記憶部に接続された制御部とを備え、
前記制御部は、送信されるべきパケットの数を判定し、前記パケットの数と同数である複数の葉を有する二分木を生成し、前記二分木の前記葉のそれぞれにランダム値を割り当て、子の値の一連のハッシュ値として出力される値を各内部ノードに割り当て、ルートに関して左側の子の全てに番号を割振る前記プログラム指示を実行することを特徴とする装置。
【請求項53】
送信されるべきパケットの数を判定する手段と、
前記パケットの数と同数である複数の葉を有する二分木を生成する手段と、
前記二分木の前記葉のそれぞれにランダム値を割り当てる手段と、
子の値の一連のハッシュ値として出力される値を各内部ノードに割り当てる手段と、
ルートに関して左側の子の全てに番号を割振る手段とを備えることを特徴とする装置。
【請求項54】
複数の指示を格納する一又は複数の記憶媒体を有しており、システムによって実行される場合に、システムに方法を実行させる製造物であって、
送信されるべきパケットの数を判定する工程と、
前記パケットの数と同数である複数の葉を有する二分木を生成する工程と、
前記二分木の前記葉のそれぞれにランダム値を割り当てる工程と、
子の値の一連のハッシュ値として出力される値を各内部ノードに割り当てる工程と、
ルートに関して左側の子の全てに番号を割振る工程とを実行させることを特徴とする製造物。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7A】
image rotate

【図7B】
image rotate

【図8】
image rotate

【図9】
image rotate


【公表番号】特表2007−505555(P2007−505555A)
【公表日】平成19年3月8日(2007.3.8)
【国際特許分類】
【出願番号】特願2006−526050(P2006−526050)
【出願日】平成16年2月6日(2004.2.6)
【国際出願番号】PCT/US2004/003438
【国際公開番号】WO2005/027008
【国際公開日】平成17年3月24日(2005.3.24)
【公序良俗違反の表示】
(特許庁注:以下のものは登録商標)
1.フロッピー
【出願人】(392026693)株式会社エヌ・ティ・ティ・ドコモ (5,876)
【Fターム(参考)】