方法、電子決済システム、コンピュータ・プログラム、発行者、アクセプタ、バリデータ、エミッタ（取引を自動的に妥当性検査する方法、電子支払いシステム、およびコンピュータ・プログラム）
【課題】改善されたセキュアで匿名の取引システムおよび取引方法を提供すること。
【解決手段】本発明は、署名鍵（ｐｋＢ，ｓｋＢ）を有する発行者と、エミッタ鍵（ｐｋＵ，ｓｋＵ）を有するエミッタと、一意のアイデンティティ（ｉｄＭ）および取引に対する限度（ＮＭ）を有するアクセプタと、バリデータとの間の取引を自動的に妥当性検査する方法に関する。本発明は、さらに、銀行コンピュータ・システム（１０１）、ユーザ・コンピュータ・システム（１０２）、商店コンピュータ・システム（１０３）、およびバリデータ・コンピュータ・システム（１０１）を含む電子決済システム（１００）と、コンピュータ・プログラムと、コンピュータ・プログラム製品とに関する。
【解決手段】本発明は、署名鍵（ｐｋＢ，ｓｋＢ）を有する発行者と、エミッタ鍵（ｐｋＵ，ｓｋＵ）を有するエミッタと、一意のアイデンティティ（ｉｄＭ）および取引に対する限度（ＮＭ）を有するアクセプタと、バリデータとの間の取引を自動的に妥当性検査する方法に関する。本発明は、さらに、銀行コンピュータ・システム（１０１）、ユーザ・コンピュータ・システム（１０２）、商店コンピュータ・システム（１０３）、およびバリデータ・コンピュータ・システム（１０１）を含む電子決済システム（１００）と、コンピュータ・プログラムと、コンピュータ・プログラム製品とに関する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、署名鍵を有する発行者と、エミッタ（ｅｍｉｔｔｅｒ）鍵を有するエミッタと、一意のアイデンティティおよび取引に対する限度を有するアクセプタと、バリデータとの間の取引を自動的に妥当性検査する方法に関する。本発明は、さらに、銀行コンピュータ・システムと、ユーザ・コンピュータ・システムと、商店コンピュータ・システムと、バリデータ・コンピュータ・システムとを含む電子決済システム、コンピュータ・プログラム、ならびにコンピュータ・プログラム製品に関する。
【背景技術】
【０００２】
取引を実行し、妥当性検査する方法およびシステムは、さまざまな競合する目的に直面する。一方では、これらの方法およびシステムは、ある取引に参加する誰もが、たとえば偽のアイデンティティを装うことまたは故意に取引額を変更することによって不相応な利益を得ることができなくなるように、証明可能に正しく、セキュアであらねばならないが、他方では、参加者のアイデンティティおよび参加者の正確な対話は、しばしば、匿名のままにならなければならない。それと同時に、取引プロトコルを実施する動作ｄは、計算的に効率的であり、標準的な手順に従わなければならない。
【０００３】
商品およびサービスについてオンラインで、特にインターネットを介して支払うための電子決済システムは、電子商取引システムの特に重要な例である。高速、セキュア、匿名、かつ実施しやすい電子決済システムがなければ、電子商取引の成長が危険にさらされる可能性がある。その結果、複数の電子決済システムが、研究者と金融機関の両方によって開発されてきた。そのようなシステムの一例が、参照によって本明細書に組み込まれ、ＣＨＬシステムと呼ばれる、J. Camenisch, S. Hohenberger and A. Lysyanskayaによる論文"CompactE-Cash" published in EUROCRYPT, Vol. 3494 of LNCS, pages 302-321, 2005に記載されている。ＣＨＬシステムは、証明可能にセキュアかつ匿名である、すなわち、硬貨をこのシステム内で再利用することはできないが、銀行または硬貨発行者は、硬貨が銀行にもう一度預けられる時に、商店またはアクセプタでその硬貨を使ったユーザまたはエミッタのアイデンティティを回復することができない。
【０００４】
しかし、このシステムおよび類似するシステムは、１つの不利益を有する。これらは、電子マネー・ロンダリングを受けやすい。さまざまなシナリオで、たとえば任意の２つの当事者の間の大量のキャッシュ・フローを含み、表す大量の取引が、検出されるか、防がれるか、報告されなければならない。応用例に、たとえば脱税、汚職、および大がかりな詐欺の防止が含まれる。M. Stadler, J.-M. Piveteau and J. Camenischによる論文"Fair BlindSignatures" at EUROCRYPT '95, Vol. 921 of LNCS, pages 209-219, 1995に記載のシステムでは、ｓが、マネー・ロンダリングを防ぐためにいつでもユーザの匿名性を取り消すことができる信頼のおける第三者機関を有する。しかし、第三者を有することは、電子決済システムに関する主要な欠点である。というのは、このシステムのユーザが、どの情況の下でも、彼らの匿名性が取り消され得ることを絶対に確信できないからである。他のシステム、たとえば、T.Okamoto and K. Ohtaによる論文"Disposable Zero-Knowledge Authentications andtheir Applications to Untraceable Electronic Cash" in CRYPTO, Vol. 435 ofLNCS, pages 481-496, 1990に記載の電子決済システムは、不正使用を防ぐために、限られた形の匿名性だけをユーザに提供する。このシステムでは、ユーザの硬貨は、匿名であるが、互いにリンクされ得る。これは、電子決済システムの匿名性を厳しく制限する。
【非特許文献１】J. Camenisch, S. Hohenberger and A.Lysyanskayaによる論文"Compact E-Cash" published in EUROCRYPT, Vol. 3494 ofLNCS, pages 302-321, 2005
【非特許文献２】M. Stadler, J.-M. Piveteau and J.Camenischによる論文"Fair Blind Signatures" at EUROCRYPT '95, Vol. 921 ofLNCS, pages 209-219, 1995
【非特許文献３】T. Okamoto and K. Ohtaによる論文"DisposableZero-Knowledge Authentications and their Applications to Untraceable ElectronicCash" in CRYPTO, Vol. 435 of LNCS, pages 481-496, 1990
【非特許文献４】"Jan Camenisch and IvanDamgard. Verifable encryption, group encryption, and their applications togroup signatures and signature sharing schemes. In Tatsuaki Okamoto, editor,Advances in Cryptology | ASIACRYPT '00, volume 1976 of LNCS, pages 331-345.Springer Verlag, 2000"
【非特許文献５】"Dan Boneh and MatthewFranklin. Identity-based encryption from the Weil pairing. In Joe Kilian,editor, Advances in Cryptology | CRYPTO '01, volume 2139 of LNCS, pages213-229. Springer Verlag, 2001"
【非特許文献６】"Jan Camenisch and AnnaLysyanskaya. A signature scheme with ecient protocols. In Stelvio Cimato,Clemente Galdi, and Giuseppe Persiano, editors, Security in CommunicationNetworks '02, volume 2576 of LNCS, pages 268{289. Springer Verlag, 2002"
【非特許文献７】"Jan Camenisch, SusanHohenberger, and Anna Lysyanskaya. Compact E-Cash. In Ronald Cramer, editor,Advances in Cryptology { EUROCRYPT '05, volume 3494 of LNCS, pages 302-321,2005"
【非特許文献８】Stefan Brandsによる論文、"UntraceableOff-Line Cash in Wallets with Observers", published in CRYPTO '93, Vol.773 of LNCS, page 302, 1994
【発明の開示】
【発明が解決しようとする課題】
【０００５】
その結果、改善されたセキュアで匿名の取引システムおよび取引方法の必要が存在する。電子マネー・ロンダリングを防ぐのを助けることができる電子決済システムを考案することが、特定の課題である。
【課題を解決するための手段】
【０００６】
本発明の一態様によれば、署名鍵を有する発行者と、エミッタ鍵を有するエミッタと、一意のアイデンティティおよび取引に対する限度を有するアクセプタと、バリデータとの間の取引を自動的に妥当性検査する方法が提供される。この方法は、
−エミッタによって発行者から証明書を回収するステップであって、証明書が、発行者の署名鍵およびエミッタのエミッタ鍵に基づいて発行者とエミッタとの間の第１の２当事者プロトコルを使用して計算される、ステップと、
−エミッタによってアクセプタで証明書を使うステップであって、マネー・ロンダリング検査値が、証明書、エミッタとアクセプタとの間の取引番号、アクセプタによって生成される取引チャレンジ値、およびアクセプタの一意のアイデンティティに基づいてエミッタとアクセプタとの間の第２の２当事者プロトコルを使用して計算される、ステップと、
−アクセプタによってバリデータに証明書、取引チャレンジ値、およびマネー・ロンダリング検査値を預けるステップと、
−マネー・ロンダリング検査値をより以前の取引でバリデータに既に預けられたマネー・ロンダリング検査値と比較することによって、エミッタとアクセプタとの間の取引の回数がアクセプタの取引に対する限度未満であることを検証することによって、バリデータによって取引を妥当性検査するステップと、
を含む。
【０００７】
エミッタとアクセプタとの間の取引の回数がアクセプタの取引に対する限度未満であることを検証することによって、任意の１つのエミッタとアクセプタとの間の異常に大量の取引を検出することができる。
【０００８】
第１の態様の改善された実施形態によれば、使うステップで、知識の証明が、エミッタによって計算され、アクセプタに送信され、預けるステップで、証明が、バリデータに預けられ、妥当性検査するステップが、さらに、証明が、アクセプタの一意のアイデンティティ、証明書、およびマネー・ロンダリング検査値に関して有効であることを検証するステップを含む。知識の証明を計算し、検証することによって、この方法の完全性を実施することができる。
【０００９】
第１の態様のさらなる改善された実施形態によれば、妥当性検査するステップで、バリデータが、証明がアクセプタの取引に対する限度に基づいて計算されたことを検証する。証明がアクセプタの取引に対する限度に基づいて計算されたことを検証することによって、バリデータは、アクセプタが証明の計算中に取引に対する偽の限度を使用することを試みていたかどうかを検出することができる。
【００１０】
第１の態様のさらなる改善された実施形態によれば、バリデータが、より以前の取引でバリデータに預けられたマネー・ロンダリング検査値が現在の取引のマネー・ロンダリング検査値と等しいことを検出する場合に、妥当性検査するステップが、さらに、証明書を拒否するステップと、より以前の取引で使用された取引チャレンジ値および証明書を取り出すステップとを含み、より以前の取引で使用された取引チャレンジ値と取引チャレンジ値とが異なる場合に、エミッタのアイデンティティが、より以前の取引および現在の取引で使用される証明書に基づいてバリデータによって計算される。マネー・ロンダリング検査値および取引チャレンジ値を、以前の取引のこれらの値を用いて検証することによって、取引に対する限度を超えることを試みる当事者を、識別し、罰することができる。
【００１１】
第１の態様のさらなる改善された実施形態によれば、妥当性検査するステップで、バリデータが、証明書をより以前の取引で預けられた証明書と比較し、バリデータが、より以前の取引でバリデータに預けられた証明書が現在の取引の証明書と等しいことを検出する場合に、妥当性検査するステップが、さらに、より以前の取引で使用された取引チャレンジ値を取り出すステップと、より以前の取引で使用された取引チャレンジ値と取引チャレンジ値とが等しい場合に、証明書がバリデータによって拒否されるステップと、より以前の取引で使用された取引チャレンジ値と取引チャレンジ値とが異なる場合に、エミッタのアイデンティティが、より以前の取引および現在の取引で使用される証明書に基づいてバリデータによって計算されるステップとを含む。証明書および取引チャレンジ値を、より以前の取引のこれらの値を用いて検証することによって、超過して使うことを試みる当事者を、識別し、罰することができる。
【００１２】
第１の態様のさらなる改善された実施形態によれば、回収するステップで、エミッタが、ウォレット秘密の知識の証明を発行者に提供し、証明書が、ウォレット秘密に基づき、使うステップで、ウォレット検査値が、計算され、アクセプタに転送され、預けるステップで、ウォレット検査値が、バリデータに預けられ、妥当性検査するステップで、証明書またはマネー・ロンダリング検査値がより以前の取引でバリデータに預けられ、現在の取引の取引チャレンジ値がより以前の取引で使用された取引チャレンジ値と等しいことをバリデータが検出する場合に、現在の取引およびより以前の取引のウォレット検査値に基づいて、エミッタのウォレット秘密が、バリデータによって計算される。エミッタのウォレットが超過して使われるか取引の限度を超える場合にエミッタのウォレット秘密を計算することによって、エミッタのすべての証明書を識別することができる。
【００１３】
第１の態様のさらなる改善された実施形態によれば、使うステップで、アクセプタが、取引番号が取引に対する限度未満であることを検証し、取引番号が取引に対する限度を超える場合に取引を中止する。特定の取引の取引番号がアクセプタの取引に対する限度未満であることを検証することによって、アクセプタ自体が、その所定の取引限度を超える取引を防ぐことができる。
【００１４】
本発明の第２の態様によれば、電子決済システムが開示される。この電子決済システムは、硬貨を妥当性検査するために、所定の額面金額の硬貨を発行する銀行コンピュータ・システムと、硬貨を発するユーザ・コンピュータ・システムと、硬貨を受け入れる商店コンピュータ・システムと、バリデータ・コンピュータ・システムとを含み、銀行コンピュータ・システムと、ユーザ・コンピュータ・システムと、商店コンピュータ・システムと、バリデータ・コンピュータ・システムとが、データ・ネットワークによって機能的に接続される。硬貨は、第１の態様による方法に従って引き出され、発せられ、預けられ、妥当性検査される。銀行コンピュータ・システム、ユーザ・コンピュータ・システム、商店コンピュータ・システム、およびバリデータ・コンピュータ・システムを有する電子決済システムを提供することによって、これらの実体の間の取引を、電子マネー・ロンダリングの危険を導入せずに、セキュアに、匿名で、効率的にオンラインで実行することができる。
【００１５】
本発明の第３および第４の態様によれば、コンピュータ・プログラムおよびコンピュータ・プログラム製品が開示される。これらは、コンピュータ・システムの少なくとも１つのプロセッサによって実行可能なプログラム命令を含み、少なくとも１つのプロセッサによるプログラム命令の実行時に、本発明の第１の態様による発行者、エミッタ、アクセプタ、またはバリデータのすべてのステップが実行される。コンピュータ・プログラムまたはコンピュータ・プログラム製品を提供することによって、第１の態様による方法による動作を、簡単に提供し、コンピュータ・システムに配布することができる。
【００１６】
本発明およびその実施形態は、添付図面と共に解釈される時に、本発明による現在好ましいがそれでも例示的な実施形態の次の詳細な説明を参照することによってより十分に諒解されるであろう。
【発明を実施するための最良の形態】
【００１７】
図１に、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１と、ユーザ・コンピュータ・システム１０２と、商店コンピュータ・システム１０３とを含む電子決済システム１００を示す。組み合わされた銀行およびバリデータ・コンピュータ・システム１０１と、ユーザ・コンピュータ・システム１０２と、商店コンピュータ・システム１０３とは、データ・ネットワーク１０４によって接続される。
【００１８】
組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、次で発行者またはバリデータとも称する銀行Ｂに属する。電子決済システムの規約に従って、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１が、電子決済システム１００の硬貨の発行と受入の両方の責任を負うと仮定する。その結果、単一の実体だけが、図１に示され、次で説明される。しかし、両方の役割すなわち、下でさらに説明する、硬貨を発行する役割および硬貨を妥当性検査する役割を、別々の実体すなわち、別々の発行者およびバリデータによって実行できることは、当業者に明白であろう。
【００１９】
銀行Ｂは、次で証明書Ｓとも称する所定の額面金額の硬貨を、次でエミッタとも称するユーザＵに、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１とユーザ・コンピュータ・システム１０２との間の第１の２当事者プロトコルによって発行することができる。組み合わされた銀行およびバリデータ・コンピュータ・システム１０１によって発行された証明書Ｓを認証するために、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、署名鍵（ｐｋＢ，ｓｋＢ）を含む。署名鍵（ｐｋＢ，ｓｋＢ）は、２部分非対称署名鍵であり、その第１部分は、公開鍵ｐｋＢであり、その第２部分は、セキュア鍵または秘密鍵ｓｋＢである。
【００２０】
署名鍵（ｐｋＢ，ｓｋＢ）は、証明書Ｓの生成中に組み合わされた銀行およびバリデータ・コンピュータ・システム１０１によって使用される。これは、署名アルゴリズムを使用して、ユーザ・コンピュータ・システム１０２によって供給される値に署名することによって行うことができる。代替案では、署名鍵（ｐｋＢ，ｓｋＢ）を、証明書Ｓを計算するために第１の２当事者プロトコルでの組み合わされた銀行およびバリデータ・コンピュータ・システム１０１の入力として使用することができ、ここで、署名鍵（ｐｋＢ，ｓｋＢ）の秘密鍵ｓｋＢは、明らかにされない。
【００２１】
ユーザ・コンピュータ・システム１０２は、エミッタ鍵（ｐｋＵ，ｓｋＵ）を含み、このエミッタ鍵（ｐｋＵ，ｓｋＵ）も、公開鍵ｐｋＵおよび秘密鍵ｓｋＵを有する２部分鍵である。さらに、ユーザ・コンピュータ・システム１０２は、ウォレット秘密ｓを含み、このウォレット秘密ｓは、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１によって発行された証明書Ｓを表す通し番号Ｓｉを生成するのに使用される。やはり、エミッタ鍵の秘密鍵ｓｋＵ、ウォレット秘密ｓ、および導出される通し番号Ｓｉは、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１に開示されない。その代わりに、ユーザ・コンピュータ・システム１０２だけが、これらおよびさらなるパラメータの知識を、第１の２当事者プロトコルで組み合わされた銀行およびバリデータ・コンピュータ・システム１０１に証明する。
【００２２】
商店コンピュータ・システム１０３は、一意のアイデンティティｉｄＭによって識別される。さらに、商店コンピュータ・システム１０３は、取引に対する限度ＮＭに関連し、取引に対する限度ＮＭは、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１とユーザ・コンピュータ・システム１０２の両方に既知である。取引に対する限度ＮＭは、たとえば、任意の単一のユーザ・コンピュータ・システム１０２と商店コンピュータ・システム１０３との間で所与のコンテキストで実行されることを許可される取引の回数を制限することができる。
【００２３】
証明書Ｓの性質に応じて、証明書Ｓは、取引額に対する限度を表すこともできる。たとえば、各証明書Ｓが、１ドルという所定の額を有する場合に、取引に対する限度ＮＭに１００がセットされているならば、ユーザは、商店コンピュータ・システム１０３に関連する商店Ｍで１００ドルだけを使うことができる。取引に対する限度ＮＭおよび証明書Ｓの他の定義を設け、電子決済システム１００または他の証明書発行システムおよび証明書償還システムと共に使用することができる。電子決済システム１００には、たとえば、異なる額を有する証明書Ｓ、たとえば、１セント、１０セント、１ドル、１０ドル、および１００ドルの関連する額を有する証明書が存在することができる。同様に、取引に対する限度ＮＭは、単一の購入について、固定された時間期間、たとえば１週間、１ヵ月、または１年について有効とすることができ、あるいは、証明書Ｓ、署名鍵（ｐｋＢ，ｓｋＢ）、エミッタ鍵（ｐｋＵ，ｓｋＵ）、または商店コンピュータ・システム１０３の一意のアイデンティティｉｄＭの寿命全体にわたって有効とすることができる。
【００２４】
第２の２当事者プロトコルでは、ユーザ・コンピュータ・システム１０２は、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１によって前に発行された証明書Ｓをそのユーザ・コンピュータ・システム１０２が所有することを商店コンピュータ・システム１０３に証明する。このために、証明πが、ユーザ・コンピュータ・システム１０２によって計算される。さらに、ユーザ・コンピュータ・システム１０２は、商店コンピュータ１０３によって生成された取引チャレンジ値ｒ１に基づいて、マネー・ロンダリング検査値Ｖｊを計算する。マネー・ロンダリング検査値Ｖｊは、商店ＭとユーザＵとの間の取引に対する限度ＮＭを超えないことを実施する。
【００２５】
ユーザ・コンピュータ・システム１０２が、商店コンピュータ・システム１０３と共に第２の２当事者プロトコルを使用する取引にかかわる前に、ユーザ・コンピュータ・システム１０２は、その商店コンピュータ・システム１０３と共に既に実行された取引の回数を検査する。正直なユーザ・コンピュータ・システム１０２は、取引に対する限度ＮＭを超えている場合には取引にかかわらない。同様に、商店コンピュータ・システム１０３は、取引に対する限度ＮＭを超えている場合には取引にかかわらない。この正直を実施するために、基礎になる数学的プロパティは、商店コンピュータ・システム１０３が、公開鍵ｐｋＵごとに、取引に対する限度ＮＭが許容するのと同一の個数の異なる取引チャレンジ値ｒ１だけを生成することができる。その結果、両方の当事者が、特定のユーザ・コンピュータ・システム１０２との取引に対する限度ＮＭを超える回数の取引が行われることを許可しない。しかし、ユーザ・コンピュータ・システム１０２と商店コンピュータ・システム１０３の両方が不正直である場合には、これらは、前に、より以前の取引で使用された取引チャレンジ値ｒ１を再利用するか、偽の証明πを生成することを強いられる。
【００２６】
第３の２当事者プロトコルでは、商店コンピュータ・システム１０３は、ユーザ・コンピュータ・システム１０２から入手した証明書Ｓを、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１に預ける。証明書Ｓの他に、商店コンピュータ・システム１０３は、ユーザ・コンピュータ・システム１０２との第２の２当事者プロトコルで計算された取引チャレンジ値ｒ１、マネー・ロンダリング検査値Ｖｊ、および証明πも預ける。次に、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、証明πが、証明書Ｓを預けることを試みている商店コンピュータ・システム１０３の証明書Ｓ、取引チャレンジ値ｒ１、一意のアイデンティティｉｄＭ、および取引に対する限度ＮＭに関して実際に有効であることを検証する。証明πが無効である場合には、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、預かりを拒否する。これは、特に、証明書Ｓに関連する額が、商店Ｍの貸方に記入されないことを意味する。
【００２７】
さらに、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、証明書Ｓが、より以前の取引で預けられたかどうかを検査する。そうである場合には、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、違反者を識別するために取引チャレンジ値ｒ１を調査する。同一の取引チャレンジ値ｒ１’がより以前の取引で使用されたことが検出される場合には、商店Ｍに、証明書Ｓを２回預けることを試みたことの責任がある。その結果、証明書Ｓは、拒否され、任意選択として、商店Ｍの一意のアイデンティティｉｄＭを、公表することができる。取引チャレンジ値ｒ１とｒ１’とが異なる場合には、ユーザＵに責任がある。この場合に、現在の取引および前の取引に基づいて、ユーザＵの公開鍵ｐｋＵを判定することができる。その結果、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、詐欺的なユーザ・コンピュータ・システム１０２のアイデンティティを暴露することができ、あるいは、エミッタ鍵（ｐｋＵ，ｓｋＵ）に関連するウォレット秘密ｓを暴露することができる。この場合に、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、ユーザ・コンピュータ・システム１０２に発行されたすべての証明書Ｓを識別でき、したがって、そのユーザ・コンピュータ・システム１０２を含む取引を識別することができる。
【００２８】
もう１つのステップで、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、マネー・ロンダリング検査値Ｖｊをより以前の取引のマネー・ロンダリング検査値と比較することによって、取引の限度を超えていないことをも検証する。組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、商店コンピュータ・システム１０３が、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１に前に預けられたマネー・ロンダリング検査値Ｖｊを預けることを試みていることを検出する場合に、１つまたは複数の違反者を識別するために、取引チャレンジ値ｒ１をも調査する。より以前の取引が、現在の取引と同一の取引チャレンジ値ｒ１に基づく場合には、商店コンピュータ・システム１０３だけに責任がある。電子決済システム１００のセキュリティ・セッティングに応じて、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、証明書Ｓの預かりを拒否するか、詐欺的な商店Ｍの一意のアイデンティティｉｄＭを公表するか、その両方を行うことができる。取引チャレンジ値が異なる場合には、ユーザ・コンピュータ・システムも、故意に取引に対する限度ＮＭを超えており、上で説明したようにこれを罰することができる。
【００２９】
発行者兼バリデータである銀行Ｂの役割、エミッタであるユーザＵの役割、およびアクセプタである商店Ｍの役割は、たとえば専用のコンピュータ・システムである組み合わされた銀行およびバリデータ・コンピュータ・システム１０１、ユーザ・コンピュータ・システム１０２、ならびに商店コンピュータ・システム１０３による、または汎用コンピュータ・システムである組み合わされた銀行およびバリデータ・コンピュータ・システム１０１、ユーザ・コンピュータ・システム１０２、ならびに商店コンピュータ・システム１０３で稼動するソフトウェア・モジュールによる、あるいはその組合せによるなど、ハードまたはソフトウェアで実施することができる。コンピュータ可読媒体を、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１、ユーザ・コンピュータ・システム１０２、または商店コンピュータ・システム１０３に含め、たとえば組み合わされた銀行およびバリデータ・コンピュータ・システム１０１、ユーザ・コンピュータ・システム１０２、または商店コンピュータ・システム１０３に含まれるプロセッサによって実行可能なプログラムのプログラム命令を実施することができる。コンピュータ可読媒体は、たとえば、ＣＤ−ＲＯＭ、フラッシュ・メモリ・カード、ハード・ディスク、または任意の他の適切なコンピュータ可読媒体とすることができる。
【００３０】
図２から図５に、本発明の実施形態による方法の流れ図を示す。
【００３１】
図２に、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１とユーザ・コンピュータ・システム１０２との間で実行される第１の２当事者プロトコル２００を示す。第１の２当事者プロトコル２００は、電子決済システム１００内で取引を実行するためのシステム・パラメータと、ユーザ・コンピュータ・システム１０２によって組み合わされた銀行およびバリデータ・コンピュータ・システム１０１から硬貨を引き出すためのシステム・パラメータとをセット・アップするように働く。
【００３２】
ステップ２０１で、電子決済システム１００の重要なシステム・パラメータをセット・アップする。具体的に言うと、セキュリティ・パラメータｋ、双一次写像ｅ、ウォレット・サイズｌ、および双一次写像ｅ上のハッシュ関数Ｈ１およびＨ２が、定義される。これらのパラメータは、ユーザ・コンピュータ・システム１０２がそのウォレットに保管できる証明書Ｓの個数のシステム境界をセットする。
【００３３】
ステップ２０２で、発行者である銀行Ｂは、公開鍵ｐｋＢおよび秘密鍵ｓｋＢを含む非対称の署名鍵（ｐｋＢ，ｓｋＢ）を生成する。
【００３４】
ステップ２０３で、エミッタであるユーザＵも、ユーザ・コンピュータ・システム１０２の公開鍵ｐｋＵおよび秘密鍵ｓｋＵを含む非対称のエミッタ鍵（ｐｋＵ，ｓｋＵ）を生成する。
【００３５】
ステップ２０４で、ユーザ・コンピュータ・システム１０２は、ランダムな値、具体的にはウォレット秘密ｓおよびｔを生成し、このウォレット秘密ｓおよびｔは、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１から引き出される証明書Ｓまたは硬貨のそれぞれの一意の通し番号Ｓｉを生成するのに使用される。生成されたランダムな値すなわちウォレット秘密ｓおよびｔは、ユーザ・コンピュータ・システム１０２によって秘密に保たれる。
【００３６】
ステップ２０５で、ユーザ・コンピュータ・システム１０２は、秘密鍵ｓｋＵとランダムな値すなわちウォレット秘密ｓおよびｔとの知識を組み合わされた銀行およびバリデータ・コンピュータ・システム１０１に証明する。さらに、ユーザ・コンピュータ・システム１０２は、その秘密鍵ｓｋＵとウォレット秘密ｓに対する署名σを入手する。その結果、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、ウォレット秘密ｓの検証可能な暗号化を、この暗号化に対するユーザ署名と共に入手する。組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、エミッタ鍵の秘密鍵ｓｋＵまたはウォレット秘密ｓに関して何も知るようにならない。
【００３７】
ステップ２０６で、ユーザ・コンピュータ・システム１０２は、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１から引き出された証明書Ｓを保管する。実際には、２ｌ個の証明書を含む証明書の組全体を、一緒に引き出し、保管することができ、各証明書Ｓは、通し番号Ｓｉによって表される。証明書は、ＣＨＬシステムによれば、サイズＯ（ｌ＋ｋ）の特にコンパクトな形で保管することができ、ここで、ｋは、システムのセキュリティ・パラメータである。
【００３８】
図３に、ユーザ・コンピュータ・システム１０２に発行された証明書Ｓを使うためにユーザ・コンピュータ・システム１０２と商店コンピュータ・システム１０３との間で実行される第２の２当事者プロトコル２１０を示す。
【００３９】
ステップ２１１で、ユーザ・コンピュータ・システム１０２は、特定の商店コンピュータ・システム１０３との取引に対する限度ＮＭを検査する。正直なユーザ・コンピュータ・システム１０２は、取引に対する限度ＮＭに既に達している場合には、商店コンピュータ・システム１０３との取引にかかわらない。この検査に基づいて、ユーザ・コンピュータ・システム１０２は、ユーザ・コンピュータ・システム１０２と商店コンピュータ・システム１０３との間の前の取引の番号ｊをも計算する。ユーザ・コンピュータ・システム１０２は、通常は次の未使用の証明書Ｓに関連する、現在の取引に使用される通し番号Ｓｉのインデックスｉをも判定する。同様に、商店コンピュータ・システム１０３は、ユーザ・コンピュータ・システム１０２との取引に対する限度ＮＭ未満であるかどうかを判定する。
【００４０】
ステップ２１２で、商店コンピュータ・システム１０３は、たとえば取引チャレンジ値ｒ１およびｒ２を含む、取引チャレンジ値を生成する。次に、取引チャレンジ値ｒ１およびｒ２は、ユーザ・コンピュータ・システム１０２に転送される。
【００４１】
ステップ２１３で、ユーザ・コンピュータ・システム１０２は、通し番号Ｓｉを有する証明書Ｓと取引チャレンジ値ｒ１およびｒ２とに基づいて、ウォレット検査値Ｔｉを計算する。ユーザ・コンピュータ・システム１０２は、ユーザ・コンピュータ・システム１０２と商店コンピュータ・システム１０３との間のｊ番目の取引のマネー・ロンダリング検査値Ｖｊをも計算する。
【００４２】
ステップ２１４で、使用される証明書Ｓが、ｉ番目の通し番号Ｓｉとそれに関連するウォレット検査値Ｔｉおよびマネー・ロンダリング検査値Ｖｊとを商店コンピュータ・システム１０３に送信することによって、商店コンピュータ・システム１０３に送られる。
【００４３】
ステップ２１５で、値ｉ、ｊ、ｓｋＵ、ｓ、およびσの知識の証明πが、商店コンピュータ・システム１０３のためにユーザ・コンピュータ・システム１０２によって生成される。この証明πは、ユーザ・コンピュータ・システム１０２と商店コンピュータ・システム１０３との間で対話的にまたはＦｉａｔ−Ｓｈａｍｉｒヒューリスティックを使用して非対話的に実行することができる。
【００４４】
ステップ２１６で、商店コンピュータ・システム１０３が、証明πを検証する。証明πが、この取引で使用される通し番号Ｓｉに関して有効である場合には、商店コンピュータ・システム１０３は、たとえば支払いに関して、通し番号Ｓｉおよび証明πに関連する証明書Ｓを受け入れる。
【００４５】
図４に、証明書Ｓがより以前の取引で既に使われているかどうかを判定するのに使用される、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１によって実行される妥当性検査手順の第１部分２２０を示す。
【００４６】
ステップ２２１で、商店コンピュータ・システム１０３は、取引チャレンジ値ｒ１およびｒ２と、証明書Ｓの通し番号Ｓｉと、ウォレット検査値Ｔｉと、マネー・ロンダリング検査値Ｖｊとを含む証明書Ｓ、ならびに証明πをサブミットする。この形で、商店コンピュータ・システム１０３は、たとえば関連する金額が組み合わされた銀行およびバリデータ・コンピュータ・システム１０１によって貸方記入されることを要求することによって、証明書Ｓに関連する額を償還することを試みる。
【００４７】
ステップ２２２で、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、証明πが通し番号Ｓｉと取引チャレンジ値ｒ１およびｒ２とに関して有効であることを検証する。証明πが有効でない場合には、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、即座にその取引の受入を拒否する。
【００４８】
ステップ２２３で、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、通し番号Ｓｉに関連する証明書Ｓが、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１に前に預けられたことがないことを検証する。
【００４９】
証明書Ｓが、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１に前に預けられたことがある場合には、ステップ２２４で、さらなる検査を実行し、同一の取引チャレンジ値ｒ１がより以前の取引で使用されたかどうかを検証する。
【００５０】
そうである場合には、商店コンピュータ・システム１０３が、証明書Ｓの２回目の預け入れを試みている。その結果、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、ステップ２２５でこの証明書を拒否する。
【００５１】
そうでない場合には、ユーザが、二重に使っており、銀行Ｂによって罰せられなければならない。この場合に、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、商店コンピュータ・システム１０３からの証明書を受け入れるが、ステップ２２６で、公開鍵ｐｋＵに関連するユーザ・コンピュータ・システム１０２を識別する。
【００５２】
任意選択のステップ２２７では、図２に示された引出プロトコル中に使用される電子決済システム１００のセキュリティ・セッティングに応じて、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１が、現在の取引と、同一の通し番号Ｓｉが使用されたより以前の取引とに基づいて、ユーザ・コンピュータ・システム１０２のウォレット秘密ｓを計算することができる。
【００５３】
その結果、ステップ２２８で、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、ウォレット秘密ｓまたは公開鍵ｐｋＵに基づいて、ユーザ・コンピュータ・システム１０２に発行された証明書Ｓの他のすべての通し番号Ｓｉを識別することができる。
【００５４】
ステップ２２３でテストされた通し番号Ｓｉが一意である場合には、妥当性検査は、図５に示された第２部分２３０で継続され、この第２部分２３０は、現在の取引が取引に対する限度ＮＭを超えないことを検証するのに使用される。
【００５５】
ステップ２３１で、この取引について計算されたマネー・ロンダリング検査値Ｖｊを検証する。これは、現在のマネー・ロンダリング検査値Ｖｊを、より以前の取引でステップ２３２で組み合わされた銀行およびバリデータ・コンピュータ・システム１０１に既にサブミットされている以前のマネー・ロンダリング検査値Ｖｊと比較することによって行われる。
【００５６】
マネー・ロンダリング検査値Ｖｊが一意である場合には、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、ステップ２３３で、サブミットされた証明書Ｓを受け入れ、この方法は終了する。
【００５７】
そうでない場合には、さらなるステップ２３４で、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、同一の取引チャレンジ値ｒ２が現在の取引およびより以前の取引で使用されたかどうかを検証する。
【００５８】
同一の取引チャレンジ値ｒ２が使用された場合には、商店コンピュータ・システム１０３だけに責任がある。この場合には、ステップ２３５で、証明書を拒否し、この取引に関連する額は、商店コンピュータ・システム１０３に貸方記入されなくなる。
【００５９】
そうでない場合には、ユーザにも責任がある。その結果、ステップ２３６、２３７、および２３８で、上で説明したように、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１によって、公開鍵ｐｋＵに関連するユーザ・コンピュータ・システム１０２が識別され、そのウォレット秘密ｓが暗号化解除され、この情報に基づいて、このユーザの証明書Ｓの他の通し番号Ｓｉが、計算される。さらに、商店Ｍも、ステップ２３５で現在の証明書を拒否することによって罰せられる。
【００６０】
基礎になる問題の数学的複雑さに起因して、図２から図５に提示された流れ図は、電子決済システム１００の情報フローの高水準の概要を提示することしかできない。組み合わされた銀行およびバリデータ・コンピュータ・システム１０１と、ユーザ・コンピュータ・システム１０２と、商店コンピュータ・システム１０３との間のプロトコルを実施するために行われる詳細な動作は、次の数学的説明で詳細に示す。
【００６１】
セキュリティの定義
ＣＨＬシステムの定義は、二重使用を超える違反を処理するために一般化される。本明細書のオフライン電子マネー・シナリオは、アルゴリズムＢＫｅｙｇｅｎ、ＵＫｅｙｇｅｎ、Ｗｉｔｈｄｒａｗ、Ｓｐｅｎｄ、Ｄｅｐｏｓｉｔ、｛ＤｅｔｅｃｔＶｉｏｌａｔｉｏｎ（ｉ）、ＩｄｅｎｔｉｆｙＶｉｏｌａｔｏｒ（ｉ）、ＶｅｒｉｆｙＶｉｏｌａｔｉｏｎ（ｉ）｝、Ｔｒａｃｅ、およびＶｅｒｉｆｙＯｗｎｅｒｓｈｉｐと一緒に、３つの通常のプレイヤすなわち、ユーザ、銀行、および商店からなる。形式ばらずに言うと、ＢＫｅｙｇｅｎおよびＵＫｅｙｇｅｎは、それぞれ銀行およびユーザの鍵生成アルゴリズムである。ユーザは、２ｌ個の硬貨のウォレットを入手するためにＷｉｔｈｄｒａｗ中に銀行と対話し、銀行は、任意選択のトレーシング情報をデータベースＤに保管する。Ｓｐｅｎｄでは、ユーザは、そのユーザのウォレットからの１つの硬貨を商店で使い、その結果、この商店は、その硬貨の通し番号Ｓを入手し、商店Ｍは、硬貨のロケータすなわちマネー・ロンダリング検査値Ｖおよび有効性の証明πを記録する。Ｄｅｐｏｓｉｔでは、正直な商店Ｍがユーザから硬貨Ｃ＝（Ｓ，Ｖ，π）を受け入れる時に、必ず、銀行が預け入れについてこの硬貨を受け入れることの保証がある。銀行は、Ｃ＝（Ｓ，Ｖ，π）をデータベースＬに保管する。しかし、この点で、銀行は、Ｃがシステム条件のいずれかに違反するかどうかを判定する必要がある。
【００６２】
違反ｉのそれぞれについて、アルゴリズムのタプル｛ＤｅｔｅｃｔＶｉｏｌａｔｉｏｎ（ｉ），ＩｄｅｎｔｉｆｙＶｉｏｌａｔｏｒ（ｉ），ＶｅｒｉｆｙＶｉｏｌａｔｉｏｎ（ｉ）｝が定義される。ここでは、２つの違反がある。
【００６３】
違反１（二重使用）：ＤｅｔｅｃｔＶｉｏｌａｔｉｏｎ（１）で、銀行が、Ｌ内の２つの硬貨Ｃ１＝（Ｓ１，Ｖ１，π１）およびＣ２＝（Ｓ２，Ｖ２，π２）が、同一の通し番号Ｓ１＝Ｓ２を有するかどうかをテストする。そうである場合には、銀行は、（Ｃ１，Ｃ２）に対してＩｄｅｎｔｉｆｙＶｉｏｌａｔｏｒ（１）アルゴリズムを実行し、違反者の公開鍵ｐｋおよび有罪の証明Πを入手する。誰もが、公開鍵ｐｋを有するユーザが通し番号Ｓ１を有する硬貨を二重に使ったことを確信するために、（ｐｋ，Ｓ１，Ｖ１，Π）に対してＶｅｒｉｆｙＶｉｏｌａｔｉｏｎ（１）を実行することができる。
【００６４】
違反２（マネー・ロンダリング）：ＤｅｔｅｃｔＶｉｏｌａｔｉｏｎ（２）で、銀行が、Ｌ内の２つの硬貨Ｃ１＝（Ｓ１，Ｖ１，π１）およびＣ２＝（Ｓ２，Ｖ２，π２）が、同一の商店レコード・ロケータすなわちマネー・ロンダリング検査値Ｖ１＝Ｖ２を有するかどうかをテストする。そうである場合には、銀行は、（Ｃ１，Ｃ２）に対してＩｄｅｎｔｉｆｙＶｉｏｌａｔｏｒ（２）アルゴリズムを実行し、違反者の公開鍵ｐｋおよび有罪の証明Πを入手する。誰もが、公開鍵ｐｋを有するユーザが商店レコード・ロケータすなわちマネー・ロンダリング検査値Ｖ１を有する硬貨に関する限界のある匿名性ビジネス限度を超えたことを確信するために、（ｐｋ，Ｓ１，Ｖ１，Π）に対してＶｅｒｉｆｙＶｉｏｌａｔｉｏｎ（２）を実行することができる。
【００６５】
任意選択として、すべての違反の後に、銀行は、有効な有罪の証明Πに対してＴｒａｃｅアルゴリズムを実行して、所有権の証明Γと一緒に、公開鍵ｐｋを有する不正を働くユーザによってこれまでに使われたすべての通し番号Ｓｉのリストを入手することもできる。誰もが、公開鍵ｐｋを有するユーザが通し番号Ｓｉを有する硬貨の所有者であったことを確信するために、（ｐｋ，Ｓｉ，Γ）に対してＶｅｒｉｆｙＯｗｎｅｒｓｈｉｐを実行することができる。
【００６６】
さらに、ＣＨＬシステムのセキュリティ定義は、電子マネー用に一般化される。正しさ、バランス、およびユーザの匿名性の、ＣＨＬシステムの形式化は、変更されないままである。おおまかに言って、バランスは、正直な銀行が、ユーザが引き出したものより多くの硬貨の預け入れを受け入れる必要が絶対になくなることを保証し、ユーザの匿名性は、ユーザが、既知のシステム条件の１つに違反しない限り、完全に匿名のままであることをユーザに保証する。次では、３つの追加のプロパティを説明する。これらのプロパティは、任意の指定された違反、具体的には上記の違反に適用するための、二重使用者およびその無罪証明可能性（ｅｘｃｕｌｐａｂｉｌｉｔｙ）のＣＨＬの識別およびトレーシングの一般化である。ｐａｒａｍｓは、ウォレットあたりの硬貨の個数および商店ごとの使用限度を含む、グローバル・パラメータであるものとする。
【００６７】
違反者の識別：正直な商店（または、おそらくは複数の正直な商店）が、敵対者と共にＳｐｅｎｄプロトコルを２回実行し、出力がＣ１＝（Ｓ１，Ｖ１，π１）およびＣ２＝（Ｓ２，Ｖ２，π２）であったと仮定する。このプロパティは、あるｉについてＤｅｔｅｃｔＶｉｏｌａｔｉｏｎ（ｉ）（ｐａｒａｍｓ，Ｃ１，Ｃ２）が受け入れる場合に、ＩｄｅｎｔｉｆｙＶｉｏｌａｔｏｒ（ｉ）（ｐａｒａｍｓ，Ｃ１，Ｃ２）が、鍵ｐｋおよび証明Πを出力し、ＶｅｒｉｆｙＶｉｏｌａｔｉｏｎ（ｉ）（ｐａｒａｍｓ，ｐｋ，Ｓ１，Ｖ１，Π）が受け入れることを、高い確率で保証する。
【００６８】
違反者のトレース：ＶｅｒｉｆｙＶｉｏｌａｔｉｏｎ（ｉ）（ｐａｒａｍｓ，ｐｋ，Ｓ，Ｖ，Π）が、硬貨Ｃ１，Ｃ２から導出されたある違反ｉについて受け入れると仮定する。このプロパティは、Ｔｒａｃｅ（ｐａｒａｍｓ，ｐｋ，Ｃ１，Ｃ２，Π，Ｄ）が、所有権の証明Γ１，…，Γｍと一緒にｐｋのユーザに属するすべての硬貨の通し番号Ｓ１，…，Ｓｍを出力し、すべてのｊについて、ＶｅｒｉｆｙＯｗｎｅｒｓｈｉｐ（ｐａｒａｍｓ，ｐｋ，Ｓｊ，Γｊ）が受け入れることを、高い確率で保証する。
【００６９】
無罪証明可能性：敵対者が、鍵ｐｋを有する正直なユーザと共にＷｉｔｈｄｒａｗプロトコルに任意の回数だけ参加し、その後、その同一ユーザと共に違反しないＳｐｅｎｄプロトコルに任意の回数だけ参加すると仮定する。次に、この敵対者は、整数ｉと、硬貨通し番号Ｓと、鍵ｐｋを有するユーザが違反ｉを犯し、硬貨Ｓを所有すると主張する証明Γとを出力する。弱い無罪証明可能性プロパティは、すべての敵対者について、ＶｅｒｉｆｙＯ（ｐａｒａｍｓ，ｐｋ，Ｓ，Γ）が受け入れる確率を無視できることを述べる。
【００７０】
さらに、敵対者は、このユーザをＳｐｅｎｄプロトコルにかかわらせ続け、このユーザにシステム条件を違反することを強制することができる。次に、この敵対者は、（ｉ，Ｓ，Ｖ，Π）を出力する。強い無罪証明可能性プロパティは、すべての敵対者について、（１）Ｓが、ｐｋのユーザに属さない硬貨通し番号であるときに、弱い無罪証明可能性が成り立ち、（２）ｐｋのユーザが違反ｉを犯さなかったときに、ＶｅｒｉｆｙＶｉｏｌａｔｉｏｎ（ｉ）（ｐａｒａｍｓ，ｐｋ，Ｓ，Ｖ，Π）が受け入れる確率は、無視できることを述べる。
【００７１】
技術的予備行為
電子マネー・システムは、さまざまな既知のプロトコルを基本構成要素として使用するが、これらのプロトコルをこれから短く再検討する。これらのプロトコルの多くは、複数の異なる複雑さの仮定の下でセキュアであることを示すことができ、これが、本発明人の電子マネー・システムに拡張される柔軟性である。表記：本明細書では、ｇが群Ｇを生成することを示すために、Ｇ＝〈ｇ〉と書く。
【００７２】
双一次写像
Ｂｉｌｉｎｅａｒ＿Ｓｅｔｕｐが、セキュリティ・パラメータｌｋの入力時に、双一次写像のパラメータを、γ＝（ｑ，ｇ１，ｈ１，Ｇ１，ｇ２，ｈ２，Ｇ２，ＧＴ，ｅ）として出力するアルゴリズムであるものとする。各群Ｇ１＝〈ｇ１〉＝〈ｈ１〉、Ｇ２＝〈ｇ２〉＝〈ｈ２〉、およびＧＴは、素数位数ｑ＝Θ（２ｋ）の群である。効率的に計算可能な写像ｅ：Ｇ１×Ｇ２→ＧＴは、（双一次）すべてのｇ１∈Ｇ１、ｇ２∈Ｇ２、およびａ，ｂ∈Ｚｑについて、
【００７３】
【数１】
【００７４】
であり、（非縮重）ｇ１がＧ１の生成元であり、ｇ２がＧ２の生成元である場合に、ｅ（ｇ１，ｇ２）はＧＴを生成する、の両方である。
【００７５】
複雑さの仮定
本方式のセキュリティは、次の、ＣＨＬと同一の仮定に頼る。
【００７６】
強いＲＳＡ仮定：ＲＳＡの法ｎおよびランダム要素
【００７７】
【数２】
【００７８】
を与えられて、ｈｅ≡ｇ ｍｏｄ ｎになる
【００７９】
【数３】
【００８０】
および整数ｅ＞１を計算することは困難である。法ｎは、特殊な形ｐｑであり、ここで、ｐ＝２ｐ’＋１およびｑ＝２ｑ’＋１は、安全な素数である。
【００８１】
ｙ−Ｄｅｃｉｓｉｏｎａｌ Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ Ｉｎｖｅｒｓｉｏｎ仮定（ｙ−ＤＤＨＩ）：ランダムな生成元ｇ∈Ｇ（ただし、Ｇは素数位数ｑを有する）と、ランダムなｘ∈Ｚｑの値
【００８２】
【数４】
【００８３】
と、値Ｒ∈Ｇとを与えられて、Ｒ＝ｇ１／ｘであるか否かを判断することは困難である。
【００８４】
Ｅｘｔｅｒｎａｌ Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ仮定（ＸＤＨ）：Ｂｉｌｉｎｅａｒ＿Ｓｅｔｕｐ（ｌｋ）が、双一次写像ｅ：Ｇ１×Ｇ２→ＧＴのパラメータを作ると仮定する。ＸＤＨ仮定は、Ｄｅｃｉｓｉｏｎａｌ Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ＤＤＨ）問題がＧ１で困難であることを述べる。これは、効率的に計算可能な同形写像ψ’：Ｇ１→Ｇ２が存在しないことを暗示する。
【００８５】
Ｓｕｍ−Ｆｒｅｅ Ｄｅｃｉｓｉｏｎａｌ Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ仮定（ＳＦ−ＤＤＨ）：ｇ∈Ｇが、位数ｑのランダム生成元であると仮定する。Ｌが、｜ｑ｜の任意の多項式関数であるものとする。
【００８６】
【数５】
【００８７】
が、部分集合Ｉ⊂ｅｑ｛１，…，Ｌ｝の入力時に、値
【００８８】
【数６】
【００８９】
を出力するオラクルであるものとするが、ここで、いくつかの
【００９０】
【数７】
【００９１】
について
【００９２】
【数８】
【００９３】
である。さらに、Ｒは、Ｊ⊆｛１，…，Ｌ｝がＩｉからＤＤＨ独立である場合に限ってＲ（Ｊ，Ｉ１，…，Ｉｔ）＝１になる述部であるものとする。すなわち、ｖ（Ｉｉ）が、ｊ∈Ｉｉの場合に限って位置ｊに１を有し、それ以外の場合に０を有する長さＬのベクトルであるときに、ｖ（Ｊ）＋ｖ（Ｉａ）＝ｖ（Ｉｂ）＋ｖ（Ｉｃ）（加算は整数に対してビット単位である）になる３つの集合Ｉａ、Ｉｂ、およびＩｃはない。
【００９４】
次に、すべての確率的多項式時間敵対者Ａ（・）について、
【００９５】
【数９】
【００９６】
である。ただし、Ｑは、Ａが
【００９７】
【数１０】
【００９８】
に対して行ったクエリの集合である。
【００９９】
鍵作成ブロック
１）既知の離散対数ベースのゼロ知識証明
一般的なパラメータ・モデルでは、（１）素数または合成数による離散対数の剰余の知識の証明、（２）２つの（おそらくは異なる）素数または合成数を法とする表現剰余の同等性の知識の証明、（３）あるコミットメントが２つの他のコミットされた値の積を表すことの証明、（４）コミットされた値が所与の整数区間内にあることの証明、および（５）前の４つのうちのいずれか２つの論理和または論理積の証明など、離散対数に関するステートメントを提供する複数の前から既知の結果が使用される。これらのプロトコルでは、合成数による剰余は、強いＲＳＡ仮定の下でセキュアであり、素数による剰余は、離散対数仮定の下でセキュアである。Ｆｉａｔ−Ｓｈａｍｉｒヒューリスティックを適用して、そのような知識の証明を、あるメッセージｍに対するｓｉｇｎａｔｕｒｅ ｐｒｏｏｆ ｏｆ ｋｎｏｗｌｅｄｇｅにすることができる。
【０１００】
２）ＣＬ署名
Ｐｅｄｅｒｓｅｎコミットメント方式によれば、公開パラメータは、素数位数ｑおよび生成元（ｇ０，…，ｇｍ）の群Ｇである。値（ｖ１，…，ｖｍ）∈ｑｍをコミットするために、ランダムなｒ∈ｑを選択し、
【０１０１】
【数１１】
【０１０２】
をセットする。
【０１０３】
次の２つのプロトコルを有するセキュアな署名方式が存在する。（１）ユーザと鍵（ｐｋｓ，ｓｋｓ）を有する署名者との間の効率的なプロトコル。共通の入力は、ｐｋｓおよびＣすなわちＰｅｄｅｒｓｅｎコミットメントからなる。ユーザの秘密入力は、Ｃ＝ＰｅｄＣｏｍ（ｖ１，…，ｖｌ；ｒ）になる値（ｖ１，…，ｖｌ，ｒ）の集合である。このプロトコルの結果として、ユーザは、そのユーザがコミットした値に対する署名
【０１０４】
【数１２】
【０１０５】
を入手するが、署名者は、それらについて何も知るようにならない。署名は、サイズＯ（ｌ ｌｏｇ ｑ）を有する。（２）ユーザと検証者との間の署名プロトコルの効率的な知識の証明。共通の入力は、ｐｋｓおよびコミットメントＣである。ユーザの秘密入力は、Ｃ＝ＰｅｄＣｏｍ（ｖ１，…，ｖｌ；ｒ）になる値（ｖ１，…，ｖｌ，ｒ）および
【０１０６】
【数１３】
【０１０７】
である。これらの署名は、強いＲＳＡ仮定の下でセキュアである。この説明において、ＣＬ署名が実際にどのように働くかは問題ではない。
【０１０８】
後続の電子マネー・システムは、ＣＬ署名と独立に、強いＲＳＡ仮定を使用する。双一次写像を使用することによって、実際により短い署名を作るために他の署名方式を使用することができる。
【０１０９】
３）検証可能な暗号化
検証可能な暗号化方式では、暗号化する側／証明する側は、既知の公開鍵の下での暗号化の平文が、Ｐｅｄｅｒｓｅｎコミットメントで隠される値と同等であることを検証者に確信させる。"Jan Camenisch and Ivan Damgard. Verifable encryption, groupencryption, and their applications to group signatures and signature sharingschemes. In Tatsuaki Okamoto, editor, Advances in Cryptology | ASIACRYPT '00,volume 1976 of LNCS, pages 331-345. Springer Verlag, 2000"に、すべての意味論的にセキュアな暗号化方式を検証可能な暗号化方式にする技法が記載されている。
【０１１０】
この技法は、すべての意味論的にセキュアな暗号化方式を検証可能な暗号化方式にするのに使用することができる。検証可能な暗号化方式とは、証明する側兼暗号化する側Ｐと検証者兼受信側Ｖとの間の２当事者プロトコルである。
【０１１１】
おおまかに言って、ＰおよびＶの共通の入力は、公開暗号化鍵ｐｋおよびコミットメントＡである。このプロトコルの結果として、Ｖは、Ａの冒頭の暗号化ｃの拒否または入手のいずれかを行う。このプロトコルは、Ｖが、無視できる確率でのみ不正な暗号化を受け入れることと、ＶがＡの冒頭について意味のあることを何も知るようにならないこととを保証する。対応する秘密鍵ｓｋと一緒に、トランスクリプトｃは、Ａの冒頭を効率的に回復するのに十分な情報を含む。本発明人は、ここではいくつかの詳細を隠し、十分な議論についてはＣａｍｅｎｉｓｃｈおよびＤａｍｇａｒｄを参照する。
【０１１２】
４）双一次Ｅｌｇａｍａｌ暗号化
ｇｘが、暗号化解除に十分であり、公開鍵が、ある関数ｆについてｆ（ｇｘ）である暗号方式が、探されている。"Dan Boneh and Matthew Franklin. Identity-based encryption fromthe Weil pairing. In Joe Kilian, editor, Advances in Cryptology | CRYPTO '01,volume 2139 of LNCS, pages 213-229. Springer Verlag, 2001"で、アイデンティティベースのコンテキストでの１つの例が提供されている。ここでは、Ｓｕｍ−Ｆｒｅｅ ＤＤＨによって暗示される仮定の下で意味論的にセキュアであるＡｔｅｎｉｅｓｅ他の双一次Ｅｌｇａｍａｌ暗号化方式を使用する。
【０１１３】
具体的に言うと、Ｅｌｇａｍａｌ暗号化の次の双一次変形への上の検証可能な暗号化技法が、適用される。ｌｋに対してＢｉｌｉｎｅａｒ＿Ｓｅｔｕｐを実行してγ＝（ｑ，ｇ１，ｈ１，Ｇ１，ｇ２，ｈ２，Ｇ２，ＧＴ，ｅ）を入手し、ここで、双一次写像ｅ：Ｇ１×Ｇ２→ＧＴを有すると仮定する。（Ｇ，Ｅ，Ｄ）が、標準的な鍵生成アルゴリズム、暗号化アルゴリズム、および暗号化解除アルゴリズムを表すものとする。（ｌｋ，γ）の入力の際に、鍵生成アルゴリズムＧは、ランダムなｕ∈Ｚｑについて鍵対
【０１１４】
【数１４】
【０１１５】
を出力する。主な発想は、値
【０１１６】
【数１５】
【０１１７】
が、暗号化解除に十分であるということである。
【０１１８】
ｐｋの下でメッセージｍ∈ＧＴを暗号化するためには、ランダムなｋ∈Ｚｑを選択し、暗号文
【０１１９】
【数１６】
【０１２０】
を出力する。次に、値
【０１２１】
【数１７】
【０１２２】
を用いてｃ＝（ｃ１，ｃ２）を暗号化解除するためには、単純に
【０１２３】
【数１８】
【０１２４】
を計算する。この暗号化方式は、Ｄｅｃｉｓｉｏｎａｌ Ｂｉｌｉｎｅａｒ Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ＤＢＤＨ）仮定の下で意味論的にセキュアであることがわかっている、すなわち、ランダムなａ，ｂ，ｃ∈ＺｑおよびＸ∈ＧＴについて
【０１２５】
【数１９】
【０１２６】
を与えられて、Ｘ＝ｅ（ｇ１，ｇ２）ａｂｃであるかどうかを判断することは困難である。
【０１２７】
５）ＤＹ擬似ランダム関数（ＰＲＦ）
Ｇ＝〈ｇ〉が、素数位数ｑの群であるものとする。ｓが、Ｚｑのランダムな要素であるものとする。ＤｏｄｉｓおよびＹａｍｐｏｌｓｋｉｙは、最近、入力
【０１２８】
【数２０】
【０１２９】
に関する擬似ランダム関数
【０１３０】
【数２１】
【０１３１】
を提案した。この構成は、ｙ−ＤＤＨＩの下でセキュアである。上で説明した構成では、本発明のウォレットをＯ（ｌ＋ｋ）ビットからＯ（ｌ・ｋ）ビットに大きくするという犠牲を払って、ＤＹ ＰＲＦをＮａｏｒ−Ｒｅｉｎｇｏｌｄ ＰＲＦに置換し、ｙ−ＤＤＨＩ仮定をより標準的なＤＤＨ仮定に置換することができる。
【０１３２】
限界のある匿名性モデルでのコンパクト電子マネー
ＣＨＬコンパクト電子マネー方式と同様に、ユーザは、銀行から２ｌ個の硬貨のウォレットを引き出し、これらを１つずつ使う。また、ＣＨＬ方式と同様に、擬似ランダム関数Ｆ（・）（・）が使用され、この関数の範囲は、大きい素数位数ｑの、ある群Ｇである。
【０１３３】
高水準で、ユーザは、後で説明する適当な領域から５つの値（ｘ，ｓ，ｔ，ｖ，ｗ）を選択することと、これらの値に対する銀行の署名σを入手するために銀行と共に適当なセキュア・プロトコルを実行することによって、２ｌ＝Ｎ個の硬貨のウォレットを形成する。
【０１３４】
次では、ユーザが、商店Ｍから商品を買うことによって硬貨番号ｉを使うことを望み、この商店とのＫ回までの取引だけを匿名にすることができると仮定する。さらに、これが、このユーザのＭとのｊ回目の取引であり、ｊ≦Ｋであると仮定する。ウォレット内のｉ番目の硬貨に関連するのが、その通し番号Ｓ＝Ｆｓ（ｉ）である。商店Ｍとのｊ番目の取引に関連するのが、その商店のレコード・ロケータＶ＝Ｆｖ（Ｍ，ｊ）である。
【０１３５】
本発明の実施形態によれば、Ｓｐｅｎｄプロトコルで、ユーザが、値（Ｓ，Ｖ）を、これらの値が（ｓ，ｉ，ｖ，Ｍ，ｊ）の関数として計算されることの（非対話的ゼロ知識）証明と一緒に商店に与えなければならないことが規定され、ここで、１≦ｉ≦Ｎであり、１≦ｊ≦Ｋであり、（ｓ，ｖ）は、銀行によって署名されたウォレットに対応する。ＳおよびＶは、擬似ランダムであり、したがって、計算的に情報を漏らさず、証明は、ゼロ知識なので情報を漏らさない。あるユーザが、Ｎ個を超える硬貨を使うと仮定する。その場合に、このユーザは、いくつかの通し番号を複数回使用している。というのは、形Ｆｓ（ｉ）、ただし１≦ｉ≦Ｎの可能な値ＳがＮ個しかないからである。同様に、あるユーザが、ＭとのＫ回を超える取引を行ったと仮定する。その場合に、このユーザは、いくつかの商店レコード・ロケータを複数回使用している。というのは、固定されたＭについて、異なる値Ｖ＝Ｆｖ（Ｍ，ｊ）、ただし１≦ｊ≦ＫがＫ個しかないからである。したがって、二重使用および限界のある匿名性ビジネス・モデルの違反を検出することができる。
【０１３６】
次では、任意のＳまたはＶの複数回の使用が識別につながることをどのように提供するかを説明する。ｓおよびｖの他に、ウォレットには、ｘ、ｔ、およびｗも含まれる。値ｘ∈ｑは、ｇｘが、ユーザのアイデンティティに公開してリンクできる値になるような値である（ただし、ｇは、群Ｇの生成元である）。たとえば、ある計算可能関数ｆについて、ｆ（ｇｘ）をユーザの公開鍵とすることができる。取引の一部として、商店が、ランダム値ｒ≠０を与え、ユーザが、Ｔ＝ｇｘＦｔ（ｉ）ｒおよびＷ＝ｇｘＦｗ（Ｍ，ｊ）ｒを、ＴおよびＷがまさに同一のウォレットならびに同一のｉおよびｊに対応する（ｒ，ｘ，ｔ，ｉ，ｗ，Ｍ，ｊ）の関数として適当に計算されることの証明と一緒に明らかにすると仮定する。やはり、ＴおよびＷは、擬似ランダムであり、したがって、情報を一切漏らさない。
【０１３７】
ユーザが、同一の通し番号Ｓ＝Ｆｓ（ｉ）を２回使用し、ｑが適度に大きい場合に、高い確率で、２つの異なる取引で、そのユーザは、異なるｒを受け取り、これらをｒ１およびｒ２と呼び、したがって、
【０１３８】
【数２２】
【０１３９】
を用いて応答しなければならない。値ｇｘを、その後に次にように計算できることは、簡単にわかる。
【０１４０】
【数２３】
【０１４１】
ユーザが、同一の商店のレコード・ロケータ番号Ｖを２回使用する場合に、ｇｘを正確に同一の形で見つけることができることも、そうであることが示される。この２つの取引で、商店が同一のｒを使用すると仮定する。その場合に、銀行は、単純にこのｅ−ｃｏｉｎの預け入れを拒否することができる（商店が同一なので、この商店が、適当なランダム化のその商店自体の欠如の責任を負う）。この商店が２つの異なるｒすなわちｒ１およびｒ２を使用し、Ｗ１およびＷ２を生じたと推定される場合に、
【０１４２】
【数２４】
【０１４３】
であることがわかる。
【０１４４】
したがって、二重使用または限界のあるビジネス・モデルの違反は、識別につながる。唯一の残っている疑問は、同一ユーザの他の取引をトレースするために、これをどのように適合させることができるかである。ｇｘは、必ずしも公開値ではなく、ｆ（ｇｘ）だけが公開される場合もありえるが、ｇｘの知識は、ｓを検証可能に暗号化することによって形成された暗号文を暗号化解除する能力を与える（たとえば、ＢｏｎｅｈおよびＦｒａｎｋｌｉｎの暗号方式は、ｇｘが暗号化解除に十分であるというプロパティを有する）。ウォレットを引き出すときに、ユーザは、そのような暗号文を銀行に与える。ｓの知識は、このウォレットからのすべての硬貨の通し番号を発見することを可能にし、それらがどのように使われたかを調べることを可能にする。
【０１４５】
最後に、値（ｘ，ｖ，ｗ）は、特定のウォレットではなく、ユーザのアイデンティティに結び付けられなければならない。この形では、ユーザが特定の商店で異なるウォレットから多すぎる金銭を使うことを試みる場合であっても、それが検出および識別につながる。
【０１４６】
本プロトコルの詳細な説明
本方式は、ＣＨＬ電子マネー方式の拡張なので、Ｄｏｄｉｓ−Ｙａｍｐｏｌｓｋｉｙ擬似ランダム関数すなわち、
【０１４７】
【数２５】
【０１４８】
が使用され、ここで、ｇは、適切な群の生成元であり、ＣＬ署名および関連するプロトコルが、署名を発行し、署名の知識を証明するのに使用され、双一次Ｅｌｇａｍａｌ暗号方式が、Ｃａｍｅｎｉｓｃｈ−Ｄａｍｇａｒｄ検証可能暗号化技法と共に使用される。
【０１４９】
表記：
【０１５０】
【数２６】
【０１５１】
であるものとし、Ｈが、その範囲が適当な群であるハッシュ関数であるときに、
【０１５２】
【数２７】
【０１５３】
であるものとする。
【０１５４】
これから、本システムのプロトコルすなわち、Ｓｅｔｕｐ、Ｗｉｔｈｄｒａｗ、Ｓｐｅｎｄ、およびＤｅｐｏｓｉｔ（違反に応答するプロトコルを含む）を説明する。
【０１５５】
Ｓｅｔｕｐプロトコル
ｋが、セキュリティ・パラメータであると仮定する。共通のシステム・パラメータは、Ｂｉｌｉｎｅａｒ＿Ｓｅｔｕｐ（ｌｋ）→（ｑ，ｇ１，Ｇ１，ｇ２，ｈ２，Ｇ２，ＧＴ，ｅ）、ウォレット・サイズｌ、ならびに２つのハッシュ関数Ｈ１：｛０，１｝＊→ＧｔおよびＨ２：｛０，１｝＊→Ｇ１である。銀行は、ＣＬ署名鍵（ｐｋＢ，ｓｋＢ）を生成する。
【０１５６】
各ユーザは、形ｓｋＵ＝（ｘ，ｖ，ｗ）およびｐｋＵ＝（ｅ（ｇ１，ｈ２）ｘ，ｅ（ｇ１，ｈ２）ｖ，ｅ（ｇ１，ｈ２）ｗ）の鍵対を生成し、ここで、ｘ、ｖ、およびｗは、Ｚｑからランダムに選択される。各ユーザは、任意のセキュア署名方式用の署名鍵も生成する。各商店は、一意のアイデンティティ・ストリングｉｄＭも公開する。また、各ユーザが商店ｉｄＭで使うことのできる硬貨の個数の上限ＮＭが決定される。
【０１５７】
Ｗｉｔｈｄｒａｗプロトコル
ユーザＵは、次のように銀行Ｂから２ｌ個の硬貨を引き出す。このユーザおよび銀行は、対話型プロトコルにかかわり、両方がエラーを報告しない場合に、最後に、
１．Ｕは、（ｓ，ｔ，σ）を入手し、ここで、ｓ、ｔは、Ｚｑ内のランダムな値であり、σは、（ｓｋＵ，ｓ，ｔ）に対する銀行の署名すなわち（ｘ，ｖ，ｗ，ｓ，ｔ）である。
２．Ｂは、ｅ（ｇ１，ｈ２）ｘの下でのｓの検証可能な暗号化すなわち、ユーザの公開鍵ｐｋＵの最初の要素を、この暗号化に対するユーザの署名と一緒に入手する。
３．Ｂは、ｓｋＵ、ｓ、またはｔに関して何も知るようにならない。
【０１５８】
ステップ１は、文献"Jan Camenisch and AnnaLysyanskaya. A signature scheme with ecient protocols. In Stelvio Cimato,Clemente Galdi, and Giuseppe Persiano, editors, Security in Communication Networks'02, volume 2576 of LNCS, pages 268{289. Springer Verlag, 2002"に記載のように、署名および関連するプロトコルを使用して実現することができる。ステップ２は、Ｃａｍｅｎｉｓｃｈ−Ｄａｍｇａｒｄ検証可能暗号化技法を双一次Ｅｌｇａｍａｌ暗号方式に適用することによって実現することができる。ステップ３は、他の２つから得られる。これらのステップのすべてが、本質的にＣＨＬ電子マネー方式と同一であり、例外は、ここではｘのほかにｖおよびｗをも含む署名された秘密鍵である。
【０１５９】
Ｓｐｅｎｄプロトコル
ユーザＵは、次のように、ＮＭ個の硬貨という使用限度を伴って、商店Ｍで１つの硬貨を使う。ＣＨＬと同様に、このユーザは、このユーザのウォレット内で使われる硬貨の個数の、１から２ｌまでの秘密カウンタｉを保持する。さらに、このユーザは、現在、このユーザが各商店で使った硬貨の個数を表す、商店ＭごとのカウンタｊＭも保持する。
１．Ｕは、商店Ｍに関するＵの使用限度未満である、すなわち、ｊＭ＜ＮＭであることを検査する。そうでない場合には、Ｕは、打ち切る。
２．Ｍは、ランダムな
【０１６０】
【数２８】
【０１６１】
をＵに送信する。
３．Ｕは、ＭとのｊＭ番目の取引で、Ｕのウォレット内のｉ番目の硬貨をＭに送信する。ｓｋＵ＝（ｘ，ｖ，ｗ）であることを想起されたい。この硬貨は、通し番号Ｓおよびウォレット検査Ｔ、ただし
【０１６２】
【数２９】
【０１６３】
と、２つのマネー・ロンダリング検査値ＶおよびＷ、ただし
【０１６４】
【数３０】
【０１６５】
と、（ｉ，ｊＭ，ｓｋＵ＝（ｘ，ｖ，ｗ），ｓ，ｔ，σ）の知識のゼロ知識証明（ＺＫＰＯＫ）πとからなり、
（ａ）１≦ｉ≦２ｌ
（ｂ）１≦ｊＭ≦ＮＭ
（ｃ）
【０１６６】
【数３１】
【０１６７】
、すなわち、Ｓ＝ｅ（ｇ１，ｈ２）１／（Ｓ＋ｉ）
（ｄ）
【０１６８】
【数３２】
【０１６９】
（ｅ）
【０１７０】
【数３３】
【０１７１】
（ｆ）
【０１７２】
【数３４】
【０１７３】
（ｇ） ＶｅｒｉｆｙＳｉｇ（ｐｋＢ，（ｓｋＵ＝（ｘ，ｖ，ｗ），ｓ，ｔ），σ）＝ｔｒｕｅ
になる。証明πは、Ｆｉａｔ−Ｓｈａｍｉｒヒューリスティックを使用して非対話的にすることができる。
４．πが検証され、値Ｖｊが前にＭによって一度も見られていない場合に、Ｍは、硬貨（ｒ１，ｒ２，Ｓ，Ｔ，Ｖ，Ｗ，π）を受け入れ、保存する。値Ｖｊが、前に硬貨（ｒ１，ｒ２，Ｓ’，Ｔ’，Ｖ，Ｗ’，π’）で以前に見られた場合に、Ｍは、Ｏｐｅｎ（Ｗ’，Ｗ，ｒ２，ｒ２）を返す。Ｍが、Ｓｐｅｎｄプロトコルを正直に実行する（すなわち、各プロトコルの始めに新しいランダムな値を選択する）場合に、高い確率で、ｒ２≠ｒ２であり、
【０１７４】
【数３５】
【０１７５】
である。したがって、この商店は、Ｕの公開鍵の一部である
【０１７６】
【数３６】
【０１７７】
を計算することによって、このユーザを識別することができる。これは、正直な商店が、その商店で超過して使うことを試みる顧客からその商店自体を保護することを可能にする（その商店が正直でない場合には、銀行が、預け入れの時に超過使用を把握する）。
【０１７８】
ステップ３（ａ）、３（ｃ）、および３（ｄ）は、ＣＨＬ方式と同一であるが、ステップ３（ｂ）、３（ｅ）、および３（ｆ）は、新規であるがステップ３（ａ）、３（ｃ）、および３（ｄ）に類似する。最後に、ステップ３（ｇ）は、正しく適合される必要がある。その結果、ステップ３（ａ）および３（ｂ）は、標準技法を使用して行うことができる。ステップ３（ｃ）から３（ｆ）は、"Jan Camenisch, Susan Hohenberger, and Anna Lysyanskaya.Compact E-Cash. In Ronald Cramer, editor, Advances in Cryptology { EUROCRYPT'05, volume 3494 of LNCS, pages 302-321, 2005"に記載のＣａｍｅｎｉｓｃｈ、Ｈｏｈｅｎｂｅｒｇｅｒ、およびＬｙｓｙａｎｓｋａｙａの技法を使用して行うことができる。ステップ３（ｇ）は、Ｃａｍｅｎｉｓｃｈ署名およびＬｙｓｙａｎｓｋａｙａ署名を使用して行うことができる。
【０１７９】
Ｄｅｐｏｓｉｔプロトコル
商店Ｍは、硬貨（ｒ１，ｒ２，Ｓ，Ｔ，Ｖ，Ｗ，π）をサブミットすることによって、銀行Ｂに硬貨を預ける。銀行は、証明πを検査し、これが検証されない場合には、銀行は、即座に拒否する。ここで、銀行は、２つの追加検査を行う。
【０１８０】
第１に、Ｂは、硬貨の使用者がその使用者のウォレットを超過して使っていないことを検査する、すなわち、銀行は、同一の通し番号Ｓを有する前に受け入れられたすべての硬貨を検索する。そのような硬貨（ｒ１，ｒ２，Ｓ，Ｔ’，Ｖ’，Ｗ’，π’）が見つかると仮定する。ｒ１＝ｒ１である場合には、Ｂは、その硬貨を受け入れることを拒否する。そうでない場合には、Ｂは、商店からの硬貨を受け入れるが、ここで、二重に使ったユーザを罰しなければならない。
１．Ｂは、
【０１８１】
【数３７】
【０１８２】
を実行する。
２．Ｂは、
【０１８３】
【数３８】
【０１８４】
を含む公開鍵を有する人としてユーザを識別する。
３．Ｂは、
【０１８５】
【数３９】
【０１８６】
を使用して、引き出しプロトコル中に銀行に渡されたｓの暗号化を暗号化解除する。次に、Ｂは、ｓを使用して、そのユーザのウォレット内のすべての硬貨の各硬貨ｊ＝１ ｔｏ ２ｌの通し番号
【０１８７】
【数４０】
【０１８８】
を計算する。実際に、銀行は、
【０１８９】
【数４１】
【０１９０】
を使用して、同一の形ですべてのユーザのウォレットの秘密を暗号化解除し、これらの取引をトレースすることができる。
【０１９１】
第２に、Ｂは、硬貨の使用者が、商店Ｍに関する使用限度を超えていないことを検査する。すなわち、この銀行は、同一のマネー・ロンダリング検査値Ｖｊを有する、以前に受け入れられたすべての硬貨を検索する。そのような硬貨（ｒ１，ｒ２，Ｓ’，Ｔ’，Ｖ，Ｗ’，π’）が見つかると仮定する。この銀行は、預け入れを受け入れるのを拒否し、その商店を罰する。この銀行は、ここで、使用者に責任があるかどうかを判定する。ｒ２＝ｒ２である場合に、Ｂは、商店だけを罰する。そうでない場合には、Ｂは、マネー・ロンダリングを試みたユーザも罰する。
１．Ｂは、
【０１９２】
【数４２】
【０１９３】
を実行する。
２．Ｂは、
【０１９４】
【数４３】
【０１９５】
を含む公開鍵を有する人としてユーザを識別する。
３．Ｂは、
【０１９６】
【数４４】
【０１９７】
を使用して、引き出しプロトコル中に銀行に渡されたｓの暗号化を暗号化解除する。次に、Ｂは、ｓを使用して、そのユーザのウォレット内のすべての硬貨の各硬貨ｊ＝１ ｔｏ ２ｌの通し番号
【０１９８】
【数４５】
【０１９９】
を計算する（実際に、銀行は、
【０２００】
【数４６】
【０２０１】
を使用して、同一の形ですべてのユーザのウォレットの秘密を暗号化解除し、これらの取引をトレースすることができる。
すべての検査に合格する場合に、Ｂは、Ｍの口座内の預け入れに関してこの硬貨を受け入れる。
【０２０２】
預け入れプロトコルは、ＣＨＬ方式の預け入れプロトコルに類似する、すなわち、二重使用の検査だけではなく、銀行は、現在、マネー・ロンダリングについても検査する。したがって、ユーザが正直である場合に、銀行は、前のように１つではなく、２つのデータベース・ルックアップを実行する。
【０２０３】
次では、Ｏｐｅｎ（）アルゴリズムを説明するが、これは、ＣＨＬシステムと同一である。
【０２０４】
【数４７】
【０２０５】
したがって、いくつかの要素ｈ∈Ｇ１および
【０２０６】
【数４８】
【０２０７】
について
【０２０８】
【数４９】
【０２０９】
である場合に、Ｏｐｅｎ（Ｗ１，Ｗ２，ｒ１，ｒ２）＝ｇｘが得られる。
【０２１０】
次では、違反関連プロトコルがどのように働くかを説明する。Ｃ１＝（ｒ１，ｒ２，Ｓ，Ｔ，Ｖ，Ｗ，π）およびＣ２＝（ｒ１，ｒ２，Ｓ’，Ｔ’，Ｖ’，Ｗ’，π’）が、一方は既存の通貨であり、他方は新に預けられる硬貨であるものとする。二重検出またはマネー・ロンダリングの検出には、それぞれＳ１＝Ｓ２またはＶ１＝Ｖ２の検査が用いられる。識別アルゴリズムは、適当な入力に対してＯｐｅｎを実行し、結果の有罪の証明は、Π＝（Ｃ１，Ｃ２）である。違反の検証は、硬貨の妥当性を成功して検査することと、損害賠償を請求された違反を検出することと、Ｏｐｅｎを実行して
【０２１１】
【数５０】
【０２１２】
を入手することと、そのｐｋに対する関係を検査することとが含まれる。１つの違反の漏洩を使用して、そのユーザの硬貨を使うことまたは別の違反を捏造することはできない）。トレース・アルゴリズムには、Ｗｉｔｈｄｒａｗ中にユーザによって署名された暗号化Ｅからｓを回復することと、すべての通し番号を計算することとが含まれる。所有権の証明は、
【０２１３】
【数５１】
【０２１４】
であり、ここで、σは、Ｅに対するユーザの署名である。ある通し番号Ｓに関する所有権の検証は、署名σを検証することと、
【０２１５】
【数５２】
【０２１６】
であることを検査することと、ｓを回復するためにＥを暗号化解除することと、すべての通し番号Ｓｉを計算することと、すべてのｉについてＳ＝Ｓｉであるかどうかをテストすることとが含まれる。
【０２１７】
システム違反者に関する処罰の軽減
システム違反者に関する処罰をより寛大にするために、または単にシステムをより効率的にするために、２つの他のオプションが使用可能である。
オプション（１）：違反が検出され、ユーザのアイデンティティが明らかにされる。このシステムは、Ｗｉｔｈｄｒａｗプロトコル中に、ユーザがウォレット秘密ｓの検証可能な暗号化を銀行に与えないことを除いて、上と同様に動作する。次に、後に、Ｄｅｐｏｓｉｔプロトコル中に、銀行は、それでも、違反を検出し、ユーザを識別することができるが、このユーザを含む他の取引の通し番号を計算することはできない。
オプション（２）：違反が検出される。このシステムは、Ｓｐｅｎｄプロトコル中に、ユーザが商店にマネー・ロンダリング検査値Ｖｊを与えないことを除いて、オプション（１）のシステムと同様に動作する。次に、後に、Ｄｅｐｏｓｉｔプロトコル中に、銀行は、それでも、違反を検出することができるが、ユーザを識別することはできない。
【０２１８】
効率の考慮事項
プロトコル効率の表示として、いくつかの数字を述べる。たとえば、ユーザが、コミットメントを作るために１４回の複数の底の指数を計算しなければならず、証明のためにさらに２０回計算しなければならなくなるようにＳｐｅｎｄを構成することができる。この例では、商店および銀行は、硬貨が有効であることを検査するために、２０回の複数の底の指数を行う必要がある。本プロトコルは、ユーザと商店との間の２ラウンドの通信、ならびに銀行と商店との間の１ラウンドの通信をもたらす。上のオプション（２）を採用する場合に、コミットメントを作るために１３回の複数の底の指数と、証明のためにさらに１８回になる。銀行および商店による検証は、８回の複数の底の指数を要する。
【０２１９】
セキュリティの証明
限界のある匿名性ビジネス・モデルでは、本方式は、ランダム・オラクル・モデルでの強いＲＳＡ仮定、ｙ−ＤＤＨＩ仮定、およびＸＤＨ仮定またはＳｕｍ−Ｆｒｅｅ ＤＤＨ仮定のいずれかの下で、正しさ、バランス、ユーザの匿名性、違反者の識別、違反者のトレース、および強い無罪証明可能性を達成する。
【０２２０】
スペースの制限に起因して、いくつかの高水準直観を、証明の梗概と一緒に提供する。ＣＨＬの３つの主な観察がある。これらは、二重使用を超えた違反を防ぐために、特にＰＲＦの出力を商店にリンクするためのＰＲＦの注意深い使用を介して拡張することができる。
【０２２１】
バランス：ウォレットごとに、ｓは、硬貨の有効な通し番号とすることができる正確にＮ個の値を決定論的に定義する。ウォレットを超過して使うために、ユーザは、１つの通し番号を２回使用することができるが、その場合に、このユーザは、識別可能であり、あるいは、ユーザは、ＣＬ署名を偽造するか、ＺＫ証明を捏造することができる。
【０２２２】
ユーザの匿名性：硬貨は、ゼロ知識なので何も漏らさない妥当性の（非対話的ゼロ知識）証明と一緒に、擬似ランダムであり、したがって、やはりユーザに関する情報を漏らさない４つの値（Ｓ、Ｔ、Ｖ、Ｗ）からなる。
【０２２３】
ここでの唯一の異常は、ＶおよびＷを計算する時に、ＰＲＦに使用される底が、商店のアイデンティティのハッシュである（ＳおよびＴの計算に使用される固定された底ではなく）ことである。ハッシュＨをランダム・オラクルとして扱うことによって、
【０２２４】
【数５３】
【０２２５】
を与えられれば、すべての他の入力に対する
【０２２６】
【数５４】
【０２２７】
、特にｉｄＭ≠ｉｄＭの
【０２２８】
【数５５】
【０２２９】
の出力が、ランダムから区別不能であることがわかる。具体的に言うと、
【０２３０】
【数５６】
【０２３１】
を与えられた敵対者が、Ｈ（ｉｄＭ）１／（ｖ＋ｊ）を、あるランダムな固定されたＨ（ｉｄＭ）およびＨ（ｉｄＭ）についてランダムから区別できる場合に、これは、ＤＤＨを解いている。
【０２３２】
無罪証明可能性：第１に、正直なユーザを、そのユーザが犯していない犯罪について有罪と証明することはできない。というのは、有罪の証明に、ユーザの秘密値
【０２３３】
【数５７】
【０２３４】
が含まれるからである。ユーザが正直である場合には、そのユーザだけがこの値を知っている。第２に、不正を働くユーザであっても、そのユーザが犯していない犯罪について有罪と証明することはできない。たとえば、１つの硬貨の二重使用は、２０個の硬貨のマネー・ロンダリングの偽の証明を可能にしない。というのは、（１）罪が、硬貨自体から公に検証可能であり、（２）ｘの知識が硬貨を作成するためのｄであるからである。違反によって漏らされる値
【０２３５】
【数５８】
【０２３６】
の値は、そのユーザのウォレットから硬貨を使うのには十分でない。
【０２３７】
下では、証明の概要を、上で輪郭を示した定義に基づいて示す。
【０２３８】
正しさ：正直な当事者が本プロトコルに従う場合に、誰もエラー・メッセージを出力しないことを検証することができる。
【０２３９】
バランス：Ａが、銀行として働くエクストラクタＥとのｎ回のＷｉｔｈｄｒａｗプロトコルを実行する敵対者であるものとする。各Ｗｉｔｈｄｒａｗ中に、Ｅは、Ａが（ｘ，ｓ，ｔ，ｖ，ｗ）の知識の証明を与える時にＥがこれらの値を抽出することを除いて、正確に、正直な銀行が行う通りに動作する。ｓから、Ｅは、Ａがそのウォレットについて計算できるすべての正当な通し番号を特定の確率で計算することができる。Ｌが、すべてのウォレットからのすべての通し番号の集合を表すものとする。ここで、Ａが、通し番号
【０２４０】
【数５９】
【０２４１】
を有する硬貨を正直な銀行に受け入れさせることができると仮定する。その場合に、Ａは、妥当性の偽の証明をでっち上げたことになるが、これは、無視できる確率で発生する。
【０２４２】
ユーザの匿名性：匿名性のＣＨＬ定義は、ユーザのウォレット、秘密鍵、またはユーザの公開鍵にさえアクセスせずにＳｐｅｎｄプロトコルのユーザの側を成功して実行できるシミュレータＳをもたらす。Ｓが商店Ｍで硬貨を使うことを望み、ウォレット・サイズがＮであり、Ｍの匿名使用限度がＭであると仮定する。Ｓは、ランダムな値（ｘ，ｓ，ｔ，ｖ，ｗ）を選択し、１≦ｉ≦Ｎであり、１≦ｊＭ≦Ｍである。次に、Ｓは、正直なユーザが行うのと正確に同一に、硬貨通し番号
【０２４３】
【数６０】
【０２４４】
と、商店レコード・ロケータ
【０２４５】
【数６１】
【０２４６】
と、検査値
【０２４７】
【数６２】
【０２４８】
とを作成する。これらの値は、擬似ランダムなので、実際の通貨から区別不能である。Ｓは、（Ｓ、Ｔ、Ｖ、Ｗ）がきちんと形成されていることと、ｉおよびｊＭが適当な範囲内にあることを証明することができる。Ｓが捏造する可能性がある証明の唯一の部分は、Ｓが（ｘ，ｓ，ｔ，ｖ，ｗ）に対する銀行からの署名を有することである。ここで、Ｓは、このステップに関する適当なＣＬシミュレータを呼び出し、このＣＬシミュレータは、ランダム・オラクルの制御を要求する。
【０２４９】
違反者の識別：バランスで説明したように、エクストラクタＥは、敵対者Ａと複数回のＳｐｅｎｄプロトコルを実行し、高い確率で（ｘ，ｓ，ｔ，ｖ，ｗ）を抽出する。ウォレットごとに、Ｅは、１≦ｉ≦Ｎのすべての有効な硬貨通し番号
【０２５０】
【数６３】
【０２５１】
と、１≦ｊＭ≦Ｍおよびいくつかの商店Ｍについてすべての有効な商店レコード・ロケータ
【０２５２】
【数６４】
【０２５３】
とを計算することができる。ここで、Ａが、同一の通し番号Ｓ１＝Ｓ２を有する２つの硬貨Ｃ１＝（Ｓ１，Ｔ１，Ｖ１，Ｗ１，π１，ｒ１，ｒ１）およびＣ２＝（Ｓ２，Ｔ２，Ｖ２，Ｗ２，π２，ｒ２，ｒ２）または同一の商店レコード・ロケータＶ１＝Ｖ２を有する２つの硬貨を正直な銀行に受け入れさせることができると仮定する。これらの衝突が発生するために、硬貨は、同一のウォレット（ｘ，ｓ，ｔ，ｖ，ｗ）から発し、同一のｉまたは同一の（ｉｄＭ，ｊＭ）のいずれかを有し、きちんと形成される。そうでなければ、ユーザが、妥当性の証明を偽造している。その場合に、特定の確率で
【０２５４】
【数６５】
【０２５５】
または
【０２５６】
【数６６】
【０２５７】
のいずれかであり、これによって、ユーザのアイデンティティが明らかにされる。
【０２５８】
違反ｉ＝１（二重使用）の有罪の証明Πは、有効な硬貨（Ｃ１，Ｃ２）である。誰もが、
【０２５９】
【数６７】
【０２６０】
であることと、ｐｋ
【０２６１】
【数６８】
【０２６２】
に対応する
【０２６３】
【数６９】
【０２６４】
とを検査することができる。同様に、違反ｉ＝２（特定の商店に関する匿名ビジネス限界を超えること）の有罪の証明は、Ｖ１＝Ｖ２であり、
【０２６５】
【数７０】
【０２６６】
であり、
【０２６７】
【数７１】
【０２６８】
がｐｋに対応する、有効な硬貨（Ｃ１，Ｃ２）である。
【０２６９】
１つの専門事項は、２つのウォレット種ｓ、ｓ’が、｜ｓ−ｓ’｜＜２ｌ＝Ｎになっており、したがって、これらのウォレットが、少なくとも１つの通し番号でオーバーラップする場合に何が起きるかである。同一の通し番号が、両方のウォレットから使われる場合に、銀行は、二重に使われたものとしてこれらにフラグを立てるが、それでも、識別アルゴリズムは動作しない。というのは、二重使用が実際には発生していないからである。これは銀行を混乱させる可能性があるので、この問題を、銀行にウォレットごとのｓの選択にランダムさを与えさせることによって回避することができる。ｓ、ｓ’がＺｑからランダムに引き出されるときに、それらがオーバーラップする可能性は、２ｌ＋１／ｑである。
【０２７０】
違反者のトレース：Ｗｉｔｈｄｒａｗ中に、各ユーザは、そのユーザ自身の鍵
【０２７１】
【数７２】
【０２７２】
が暗号化解除に十分になるように、そのユーザのウォレット秘密ｓの検証可能な暗号化Ｅを銀行に渡すように求められる。ユーザは、この暗号化に署名するようにも求められる。違反者の識別プロパティによって、システム違反は、銀行が
【０２７３】
【数７３】
【０２７４】
を回復することを可能にすると推論することができる。検証可能な暗号化の完全性によって、不正を働くユーザに属する各ウォレットを、
【０２７５】
【数７４】
【０２７６】
を使用して、高い確率で開いて、ウォレット種ｓを回復し、１≦ｉ≦Ｎのすべての通し番号
【０２７７】
【数７５】
【０２７８】
を計算することができる。
【０２７９】
通し番号Ｓを有するある硬貨の所有権の証明Γは、暗号化Ｅ、暗号化解除鍵
【０２８０】
【数７６】
【０２８１】
、およびＥに対する署名からなる。検証者は、まず、
【０２８２】
【数７７】
【０２８３】
がｐｋに対応することと、Ｅに対する署名が有効であることを検査しなければならない。次に、検証者は、Ｅを暗号化解除してｓを回復し、１≦ｉ≦Ｎのすべての通し番号
【０２８４】
【数７８】
【０２８５】
を計算し、いくつかのｉについてＳ＝Ｓｉであることをテストすることができる。
【０２８６】
強い無罪証明可能性：強い無罪証明可能性は、２つの部分を有する。第１に、正直なユーザと対話する敵対者は、ｐｋを有するユーザが違反ｉについて有罪でない限り、ＶｅｒｉｆｙＶｉｏｌａｔｉｏｎ（ｉ）（ｐａｒａｍｓ，Ｓ，Ｖ，Π）が受け入れるように値（ｉ，Ｓ，Ｖ，Π）を作ることはできない。
【０２８７】
証明Πは、
【０２８８】
【数７９】
【０２８９】
を明らかにする２つの有効な硬貨（Ｃ１，Ｃ２）からなる。
【０２９０】
【数８０】
【０２９１】
は秘密情報なので、これを公開することは、そのユーザがある違反を犯したことを知らせる。そのユーザが間近な特定の違反（以前の違反ではなく）の責任がある理由は、ｘ（単純に
【０２９２】
【数８１】
【０２９３】
ではなく）の知識が、有効な硬貨を作成するのに必要になることである。
【０２９４】
第２部分は、敵対者が、ユーザにシステム条件を違反することを強制した後であっても、通し番号Ｓを有する通貨がｐｋを有するユーザに実際に属さない限り、ＶｅｒｉｆｙＯｗｎｅｒｓｈｉｐ（ｐａｒａｍｓ，ｐｋ，Ｓ，Γ）が受け入れるように（ｉ，Ｓ，Γ）を作ることができないことである。証明Γは、暗号化Ｅ、ユーザの署名σ、および暗号化解除鍵
【０２９５】
【数８２】
【０２９６】
からなる。ユーザによって署名されたすべての暗号化は、ある平文ｓに高い確率で対応し、この平文ｓは、そのユーザに属するすべての通し番号を計算することを可能にする。したがって、敵対者は、勝つためにはある新しい暗号化に対するユーザの署名を偽造しなければならないはずであり、これは、無視できる確率で発生すると考えられる。
【０２９７】
上で提示した詳細な説明は、電子決済システムに言及するが、限界のある匿名性に関連する類似する問題は、本発明的方法によって対処し、解決することができる。具体的に言うと、エミッタに、証明書ベースのシステム上の異なるアクセプタへの限られた回数の匿名アクセスを許可するすべてのシステムを、本発明的方法に基づいて実施することができる。そのようなシステムの例に、プリンタ・クォータ・システム、電子投票システム、および他の電子政府サービスを含めることができるが、これらに限定はされない。
【０２９８】
ＣＨＬシステムのほかに、電子マネー・ロンダリングを防ぐために、他の基礎になる電子決済システムを機能強化することができる。類似する形で拡張できるもう１つの電子決済システムの例が、Stefan Brandsによる論文、"Untraceable Off-Line Cash in Wallets withObservers", published in CRYPTO '93, Vol. 773 of LNCS, page 302, 1994に記載されている。
【図面の簡単な説明】
【０２９９】
【図１】本発明の実施形態による、組み合わされた銀行およびバリデータ・コンピュータ・システムと、ユーザ・コンピュータ・システムと、商店コンピュータ・システムとを含む電子決済システムを示す図である。
【図２】本発明の実施形態による方法を示す流れ図の一部である。
【図３】本発明の実施形態による方法を示す流れ図の一部である。
【図４】本発明の実施形態による方法を示す流れ図の一部である。
【図５】本発明の実施形態による方法を示す流れ図の一部である。
【符号の説明】
【０３００】
１００ 電子決済システム
１０１ 組み合わされた銀行およびバリデータ・コンピュータ・システム
１０２ ユーザ・コンピュータ・システム
１０３ 商店コンピュータ・システム
１０４ データ・ネットワーク
２００ 第１の２当事者プロトコル
２０１ パラメータをセット・アップするステップ
２０２ 発行者鍵（ｐｋＢ，ｓｋＢ）を生成するステップ
２０３ エミッタ鍵（ｐｋＵ，ｓｋＵ）を生成するステップ
２０４ ランダムな値ｓ、ｔを生成するステップ
２０５ （ｓｋＵ，ｓ，ｔ）に対する署名σを生成するステップ
２０６ 証明書Ｓ（ｓ，ｔ，ｓ）を保管するステップ
２１０ 第２の２当事者プロトコル
２１１ 取引限度ＮＭを検査し、ｉ，ｊを判定するステップ
２１２ 取引チャレンジ値（ｒ１，ｒ２）を生成するステップ
２１３ ウォレット検査Ｔｉおよび検査値Ｖｊを計算するステップ
２１４ 証明書Ｓｉおよび検査値Ｔｉ，Ｖｊを送信するステップ
２１５ （ｉ，ｊ，ｓｋＵ，ｓ，σ）の知識の証明πを生成するステップ
２１６ 証明πを検証するステップ
２２０ 妥当性検査手順の第１部分
２２１ 証明書ｒ１，ｒ２，Ｓｉ，Ｔｉ，Ｖｊ、および証明πをサブミットするステップ
２２２ 証明πを検証するステップ
２２３ Ｓｉが一意であるかどうかを判定するステップ
２２５ 証明書Ｓを拒否するステップ
２２６ エミッタｐｋＵを識別するステップ
２２７ エミッタｐｋＵのウォレット秘密ｓを暗号化解除するステップ
２２８ ｓに基づいて他のＳを計算するステップ
２３０ 第２部分
２３１ 検査値Ｖｊを検証するステップ
２３２ Ｖｊが一意かどうかを判定するステップ
２３３ 証明書Ｓを受け入れるステップ
２３４ ｒ２＝ｒ２’かどうかを判定するステップ
２３５ 証明書Ｓを拒否するステップ
２３６ エミッタｐｋＵを識別するステップ
２３７ エミッタｐｋＵのウォレット秘密ｓを暗号化解除するステップ
２３８ ｓに基づいて他のＳを計算するステップ
Ｂ 銀行
Ｄ データベース
ｅ 双一次写像
Ｈ１ ハッシュ関数
Ｈ２ ハッシュ関数
ｉｄＭ 一意のアイデンティティ
ｋ セキュリティ・パラメータ
ｌ ウォレット・サイズ
Ｌ データベース
Ｍ 商店
ＮＭ 取引に対する限度
ｐｋＢ 署名鍵
ｐｋＵ エミッタ鍵
ｒ１ 取引チャレンジ値
ｒ２ 取引チャレンジ値
Ｓ 証明書
Ｓｉ 通し番号
ｓｋＵ エミッタ鍵
ｓｋＢ 署名鍵
ｓ ウォレット秘密
ｔ ウォレット秘密
Ｕ ユーザ
Ｖｊ マネー・ロンダリング検査値
Ｔｉ ウォレット検査値
σ 署名
π 証明
【技術分野】
【０００１】
本発明は、署名鍵を有する発行者と、エミッタ（ｅｍｉｔｔｅｒ）鍵を有するエミッタと、一意のアイデンティティおよび取引に対する限度を有するアクセプタと、バリデータとの間の取引を自動的に妥当性検査する方法に関する。本発明は、さらに、銀行コンピュータ・システムと、ユーザ・コンピュータ・システムと、商店コンピュータ・システムと、バリデータ・コンピュータ・システムとを含む電子決済システム、コンピュータ・プログラム、ならびにコンピュータ・プログラム製品に関する。
【背景技術】
【０００２】
取引を実行し、妥当性検査する方法およびシステムは、さまざまな競合する目的に直面する。一方では、これらの方法およびシステムは、ある取引に参加する誰もが、たとえば偽のアイデンティティを装うことまたは故意に取引額を変更することによって不相応な利益を得ることができなくなるように、証明可能に正しく、セキュアであらねばならないが、他方では、参加者のアイデンティティおよび参加者の正確な対話は、しばしば、匿名のままにならなければならない。それと同時に、取引プロトコルを実施する動作ｄは、計算的に効率的であり、標準的な手順に従わなければならない。
【０００３】
商品およびサービスについてオンラインで、特にインターネットを介して支払うための電子決済システムは、電子商取引システムの特に重要な例である。高速、セキュア、匿名、かつ実施しやすい電子決済システムがなければ、電子商取引の成長が危険にさらされる可能性がある。その結果、複数の電子決済システムが、研究者と金融機関の両方によって開発されてきた。そのようなシステムの一例が、参照によって本明細書に組み込まれ、ＣＨＬシステムと呼ばれる、J. Camenisch, S. Hohenberger and A. Lysyanskayaによる論文"CompactE-Cash" published in EUROCRYPT, Vol. 3494 of LNCS, pages 302-321, 2005に記載されている。ＣＨＬシステムは、証明可能にセキュアかつ匿名である、すなわち、硬貨をこのシステム内で再利用することはできないが、銀行または硬貨発行者は、硬貨が銀行にもう一度預けられる時に、商店またはアクセプタでその硬貨を使ったユーザまたはエミッタのアイデンティティを回復することができない。
【０００４】
しかし、このシステムおよび類似するシステムは、１つの不利益を有する。これらは、電子マネー・ロンダリングを受けやすい。さまざまなシナリオで、たとえば任意の２つの当事者の間の大量のキャッシュ・フローを含み、表す大量の取引が、検出されるか、防がれるか、報告されなければならない。応用例に、たとえば脱税、汚職、および大がかりな詐欺の防止が含まれる。M. Stadler, J.-M. Piveteau and J. Camenischによる論文"Fair BlindSignatures" at EUROCRYPT '95, Vol. 921 of LNCS, pages 209-219, 1995に記載のシステムでは、ｓが、マネー・ロンダリングを防ぐためにいつでもユーザの匿名性を取り消すことができる信頼のおける第三者機関を有する。しかし、第三者を有することは、電子決済システムに関する主要な欠点である。というのは、このシステムのユーザが、どの情況の下でも、彼らの匿名性が取り消され得ることを絶対に確信できないからである。他のシステム、たとえば、T.Okamoto and K. Ohtaによる論文"Disposable Zero-Knowledge Authentications andtheir Applications to Untraceable Electronic Cash" in CRYPTO, Vol. 435 ofLNCS, pages 481-496, 1990に記載の電子決済システムは、不正使用を防ぐために、限られた形の匿名性だけをユーザに提供する。このシステムでは、ユーザの硬貨は、匿名であるが、互いにリンクされ得る。これは、電子決済システムの匿名性を厳しく制限する。
【非特許文献１】J. Camenisch, S. Hohenberger and A.Lysyanskayaによる論文"Compact E-Cash" published in EUROCRYPT, Vol. 3494 ofLNCS, pages 302-321, 2005
【非特許文献２】M. Stadler, J.-M. Piveteau and J.Camenischによる論文"Fair Blind Signatures" at EUROCRYPT '95, Vol. 921 ofLNCS, pages 209-219, 1995
【非特許文献３】T. Okamoto and K. Ohtaによる論文"DisposableZero-Knowledge Authentications and their Applications to Untraceable ElectronicCash" in CRYPTO, Vol. 435 of LNCS, pages 481-496, 1990
【非特許文献４】"Jan Camenisch and IvanDamgard. Verifable encryption, group encryption, and their applications togroup signatures and signature sharing schemes. In Tatsuaki Okamoto, editor,Advances in Cryptology | ASIACRYPT '00, volume 1976 of LNCS, pages 331-345.Springer Verlag, 2000"
【非特許文献５】"Dan Boneh and MatthewFranklin. Identity-based encryption from the Weil pairing. In Joe Kilian,editor, Advances in Cryptology | CRYPTO '01, volume 2139 of LNCS, pages213-229. Springer Verlag, 2001"
【非特許文献６】"Jan Camenisch and AnnaLysyanskaya. A signature scheme with ecient protocols. In Stelvio Cimato,Clemente Galdi, and Giuseppe Persiano, editors, Security in CommunicationNetworks '02, volume 2576 of LNCS, pages 268{289. Springer Verlag, 2002"
【非特許文献７】"Jan Camenisch, SusanHohenberger, and Anna Lysyanskaya. Compact E-Cash. In Ronald Cramer, editor,Advances in Cryptology { EUROCRYPT '05, volume 3494 of LNCS, pages 302-321,2005"
【非特許文献８】Stefan Brandsによる論文、"UntraceableOff-Line Cash in Wallets with Observers", published in CRYPTO '93, Vol.773 of LNCS, page 302, 1994
【発明の開示】
【発明が解決しようとする課題】
【０００５】
その結果、改善されたセキュアで匿名の取引システムおよび取引方法の必要が存在する。電子マネー・ロンダリングを防ぐのを助けることができる電子決済システムを考案することが、特定の課題である。
【課題を解決するための手段】
【０００６】
本発明の一態様によれば、署名鍵を有する発行者と、エミッタ鍵を有するエミッタと、一意のアイデンティティおよび取引に対する限度を有するアクセプタと、バリデータとの間の取引を自動的に妥当性検査する方法が提供される。この方法は、
−エミッタによって発行者から証明書を回収するステップであって、証明書が、発行者の署名鍵およびエミッタのエミッタ鍵に基づいて発行者とエミッタとの間の第１の２当事者プロトコルを使用して計算される、ステップと、
−エミッタによってアクセプタで証明書を使うステップであって、マネー・ロンダリング検査値が、証明書、エミッタとアクセプタとの間の取引番号、アクセプタによって生成される取引チャレンジ値、およびアクセプタの一意のアイデンティティに基づいてエミッタとアクセプタとの間の第２の２当事者プロトコルを使用して計算される、ステップと、
−アクセプタによってバリデータに証明書、取引チャレンジ値、およびマネー・ロンダリング検査値を預けるステップと、
−マネー・ロンダリング検査値をより以前の取引でバリデータに既に預けられたマネー・ロンダリング検査値と比較することによって、エミッタとアクセプタとの間の取引の回数がアクセプタの取引に対する限度未満であることを検証することによって、バリデータによって取引を妥当性検査するステップと、
を含む。
【０００７】
エミッタとアクセプタとの間の取引の回数がアクセプタの取引に対する限度未満であることを検証することによって、任意の１つのエミッタとアクセプタとの間の異常に大量の取引を検出することができる。
【０００８】
第１の態様の改善された実施形態によれば、使うステップで、知識の証明が、エミッタによって計算され、アクセプタに送信され、預けるステップで、証明が、バリデータに預けられ、妥当性検査するステップが、さらに、証明が、アクセプタの一意のアイデンティティ、証明書、およびマネー・ロンダリング検査値に関して有効であることを検証するステップを含む。知識の証明を計算し、検証することによって、この方法の完全性を実施することができる。
【０００９】
第１の態様のさらなる改善された実施形態によれば、妥当性検査するステップで、バリデータが、証明がアクセプタの取引に対する限度に基づいて計算されたことを検証する。証明がアクセプタの取引に対する限度に基づいて計算されたことを検証することによって、バリデータは、アクセプタが証明の計算中に取引に対する偽の限度を使用することを試みていたかどうかを検出することができる。
【００１０】
第１の態様のさらなる改善された実施形態によれば、バリデータが、より以前の取引でバリデータに預けられたマネー・ロンダリング検査値が現在の取引のマネー・ロンダリング検査値と等しいことを検出する場合に、妥当性検査するステップが、さらに、証明書を拒否するステップと、より以前の取引で使用された取引チャレンジ値および証明書を取り出すステップとを含み、より以前の取引で使用された取引チャレンジ値と取引チャレンジ値とが異なる場合に、エミッタのアイデンティティが、より以前の取引および現在の取引で使用される証明書に基づいてバリデータによって計算される。マネー・ロンダリング検査値および取引チャレンジ値を、以前の取引のこれらの値を用いて検証することによって、取引に対する限度を超えることを試みる当事者を、識別し、罰することができる。
【００１１】
第１の態様のさらなる改善された実施形態によれば、妥当性検査するステップで、バリデータが、証明書をより以前の取引で預けられた証明書と比較し、バリデータが、より以前の取引でバリデータに預けられた証明書が現在の取引の証明書と等しいことを検出する場合に、妥当性検査するステップが、さらに、より以前の取引で使用された取引チャレンジ値を取り出すステップと、より以前の取引で使用された取引チャレンジ値と取引チャレンジ値とが等しい場合に、証明書がバリデータによって拒否されるステップと、より以前の取引で使用された取引チャレンジ値と取引チャレンジ値とが異なる場合に、エミッタのアイデンティティが、より以前の取引および現在の取引で使用される証明書に基づいてバリデータによって計算されるステップとを含む。証明書および取引チャレンジ値を、より以前の取引のこれらの値を用いて検証することによって、超過して使うことを試みる当事者を、識別し、罰することができる。
【００１２】
第１の態様のさらなる改善された実施形態によれば、回収するステップで、エミッタが、ウォレット秘密の知識の証明を発行者に提供し、証明書が、ウォレット秘密に基づき、使うステップで、ウォレット検査値が、計算され、アクセプタに転送され、預けるステップで、ウォレット検査値が、バリデータに預けられ、妥当性検査するステップで、証明書またはマネー・ロンダリング検査値がより以前の取引でバリデータに預けられ、現在の取引の取引チャレンジ値がより以前の取引で使用された取引チャレンジ値と等しいことをバリデータが検出する場合に、現在の取引およびより以前の取引のウォレット検査値に基づいて、エミッタのウォレット秘密が、バリデータによって計算される。エミッタのウォレットが超過して使われるか取引の限度を超える場合にエミッタのウォレット秘密を計算することによって、エミッタのすべての証明書を識別することができる。
【００１３】
第１の態様のさらなる改善された実施形態によれば、使うステップで、アクセプタが、取引番号が取引に対する限度未満であることを検証し、取引番号が取引に対する限度を超える場合に取引を中止する。特定の取引の取引番号がアクセプタの取引に対する限度未満であることを検証することによって、アクセプタ自体が、その所定の取引限度を超える取引を防ぐことができる。
【００１４】
本発明の第２の態様によれば、電子決済システムが開示される。この電子決済システムは、硬貨を妥当性検査するために、所定の額面金額の硬貨を発行する銀行コンピュータ・システムと、硬貨を発するユーザ・コンピュータ・システムと、硬貨を受け入れる商店コンピュータ・システムと、バリデータ・コンピュータ・システムとを含み、銀行コンピュータ・システムと、ユーザ・コンピュータ・システムと、商店コンピュータ・システムと、バリデータ・コンピュータ・システムとが、データ・ネットワークによって機能的に接続される。硬貨は、第１の態様による方法に従って引き出され、発せられ、預けられ、妥当性検査される。銀行コンピュータ・システム、ユーザ・コンピュータ・システム、商店コンピュータ・システム、およびバリデータ・コンピュータ・システムを有する電子決済システムを提供することによって、これらの実体の間の取引を、電子マネー・ロンダリングの危険を導入せずに、セキュアに、匿名で、効率的にオンラインで実行することができる。
【００１５】
本発明の第３および第４の態様によれば、コンピュータ・プログラムおよびコンピュータ・プログラム製品が開示される。これらは、コンピュータ・システムの少なくとも１つのプロセッサによって実行可能なプログラム命令を含み、少なくとも１つのプロセッサによるプログラム命令の実行時に、本発明の第１の態様による発行者、エミッタ、アクセプタ、またはバリデータのすべてのステップが実行される。コンピュータ・プログラムまたはコンピュータ・プログラム製品を提供することによって、第１の態様による方法による動作を、簡単に提供し、コンピュータ・システムに配布することができる。
【００１６】
本発明およびその実施形態は、添付図面と共に解釈される時に、本発明による現在好ましいがそれでも例示的な実施形態の次の詳細な説明を参照することによってより十分に諒解されるであろう。
【発明を実施するための最良の形態】
【００１７】
図１に、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１と、ユーザ・コンピュータ・システム１０２と、商店コンピュータ・システム１０３とを含む電子決済システム１００を示す。組み合わされた銀行およびバリデータ・コンピュータ・システム１０１と、ユーザ・コンピュータ・システム１０２と、商店コンピュータ・システム１０３とは、データ・ネットワーク１０４によって接続される。
【００１８】
組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、次で発行者またはバリデータとも称する銀行Ｂに属する。電子決済システムの規約に従って、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１が、電子決済システム１００の硬貨の発行と受入の両方の責任を負うと仮定する。その結果、単一の実体だけが、図１に示され、次で説明される。しかし、両方の役割すなわち、下でさらに説明する、硬貨を発行する役割および硬貨を妥当性検査する役割を、別々の実体すなわち、別々の発行者およびバリデータによって実行できることは、当業者に明白であろう。
【００１９】
銀行Ｂは、次で証明書Ｓとも称する所定の額面金額の硬貨を、次でエミッタとも称するユーザＵに、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１とユーザ・コンピュータ・システム１０２との間の第１の２当事者プロトコルによって発行することができる。組み合わされた銀行およびバリデータ・コンピュータ・システム１０１によって発行された証明書Ｓを認証するために、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、署名鍵（ｐｋＢ，ｓｋＢ）を含む。署名鍵（ｐｋＢ，ｓｋＢ）は、２部分非対称署名鍵であり、その第１部分は、公開鍵ｐｋＢであり、その第２部分は、セキュア鍵または秘密鍵ｓｋＢである。
【００２０】
署名鍵（ｐｋＢ，ｓｋＢ）は、証明書Ｓの生成中に組み合わされた銀行およびバリデータ・コンピュータ・システム１０１によって使用される。これは、署名アルゴリズムを使用して、ユーザ・コンピュータ・システム１０２によって供給される値に署名することによって行うことができる。代替案では、署名鍵（ｐｋＢ，ｓｋＢ）を、証明書Ｓを計算するために第１の２当事者プロトコルでの組み合わされた銀行およびバリデータ・コンピュータ・システム１０１の入力として使用することができ、ここで、署名鍵（ｐｋＢ，ｓｋＢ）の秘密鍵ｓｋＢは、明らかにされない。
【００２１】
ユーザ・コンピュータ・システム１０２は、エミッタ鍵（ｐｋＵ，ｓｋＵ）を含み、このエミッタ鍵（ｐｋＵ，ｓｋＵ）も、公開鍵ｐｋＵおよび秘密鍵ｓｋＵを有する２部分鍵である。さらに、ユーザ・コンピュータ・システム１０２は、ウォレット秘密ｓを含み、このウォレット秘密ｓは、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１によって発行された証明書Ｓを表す通し番号Ｓｉを生成するのに使用される。やはり、エミッタ鍵の秘密鍵ｓｋＵ、ウォレット秘密ｓ、および導出される通し番号Ｓｉは、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１に開示されない。その代わりに、ユーザ・コンピュータ・システム１０２だけが、これらおよびさらなるパラメータの知識を、第１の２当事者プロトコルで組み合わされた銀行およびバリデータ・コンピュータ・システム１０１に証明する。
【００２２】
商店コンピュータ・システム１０３は、一意のアイデンティティｉｄＭによって識別される。さらに、商店コンピュータ・システム１０３は、取引に対する限度ＮＭに関連し、取引に対する限度ＮＭは、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１とユーザ・コンピュータ・システム１０２の両方に既知である。取引に対する限度ＮＭは、たとえば、任意の単一のユーザ・コンピュータ・システム１０２と商店コンピュータ・システム１０３との間で所与のコンテキストで実行されることを許可される取引の回数を制限することができる。
【００２３】
証明書Ｓの性質に応じて、証明書Ｓは、取引額に対する限度を表すこともできる。たとえば、各証明書Ｓが、１ドルという所定の額を有する場合に、取引に対する限度ＮＭに１００がセットされているならば、ユーザは、商店コンピュータ・システム１０３に関連する商店Ｍで１００ドルだけを使うことができる。取引に対する限度ＮＭおよび証明書Ｓの他の定義を設け、電子決済システム１００または他の証明書発行システムおよび証明書償還システムと共に使用することができる。電子決済システム１００には、たとえば、異なる額を有する証明書Ｓ、たとえば、１セント、１０セント、１ドル、１０ドル、および１００ドルの関連する額を有する証明書が存在することができる。同様に、取引に対する限度ＮＭは、単一の購入について、固定された時間期間、たとえば１週間、１ヵ月、または１年について有効とすることができ、あるいは、証明書Ｓ、署名鍵（ｐｋＢ，ｓｋＢ）、エミッタ鍵（ｐｋＵ，ｓｋＵ）、または商店コンピュータ・システム１０３の一意のアイデンティティｉｄＭの寿命全体にわたって有効とすることができる。
【００２４】
第２の２当事者プロトコルでは、ユーザ・コンピュータ・システム１０２は、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１によって前に発行された証明書Ｓをそのユーザ・コンピュータ・システム１０２が所有することを商店コンピュータ・システム１０３に証明する。このために、証明πが、ユーザ・コンピュータ・システム１０２によって計算される。さらに、ユーザ・コンピュータ・システム１０２は、商店コンピュータ１０３によって生成された取引チャレンジ値ｒ１に基づいて、マネー・ロンダリング検査値Ｖｊを計算する。マネー・ロンダリング検査値Ｖｊは、商店ＭとユーザＵとの間の取引に対する限度ＮＭを超えないことを実施する。
【００２５】
ユーザ・コンピュータ・システム１０２が、商店コンピュータ・システム１０３と共に第２の２当事者プロトコルを使用する取引にかかわる前に、ユーザ・コンピュータ・システム１０２は、その商店コンピュータ・システム１０３と共に既に実行された取引の回数を検査する。正直なユーザ・コンピュータ・システム１０２は、取引に対する限度ＮＭを超えている場合には取引にかかわらない。同様に、商店コンピュータ・システム１０３は、取引に対する限度ＮＭを超えている場合には取引にかかわらない。この正直を実施するために、基礎になる数学的プロパティは、商店コンピュータ・システム１０３が、公開鍵ｐｋＵごとに、取引に対する限度ＮＭが許容するのと同一の個数の異なる取引チャレンジ値ｒ１だけを生成することができる。その結果、両方の当事者が、特定のユーザ・コンピュータ・システム１０２との取引に対する限度ＮＭを超える回数の取引が行われることを許可しない。しかし、ユーザ・コンピュータ・システム１０２と商店コンピュータ・システム１０３の両方が不正直である場合には、これらは、前に、より以前の取引で使用された取引チャレンジ値ｒ１を再利用するか、偽の証明πを生成することを強いられる。
【００２６】
第３の２当事者プロトコルでは、商店コンピュータ・システム１０３は、ユーザ・コンピュータ・システム１０２から入手した証明書Ｓを、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１に預ける。証明書Ｓの他に、商店コンピュータ・システム１０３は、ユーザ・コンピュータ・システム１０２との第２の２当事者プロトコルで計算された取引チャレンジ値ｒ１、マネー・ロンダリング検査値Ｖｊ、および証明πも預ける。次に、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、証明πが、証明書Ｓを預けることを試みている商店コンピュータ・システム１０３の証明書Ｓ、取引チャレンジ値ｒ１、一意のアイデンティティｉｄＭ、および取引に対する限度ＮＭに関して実際に有効であることを検証する。証明πが無効である場合には、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、預かりを拒否する。これは、特に、証明書Ｓに関連する額が、商店Ｍの貸方に記入されないことを意味する。
【００２７】
さらに、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、証明書Ｓが、より以前の取引で預けられたかどうかを検査する。そうである場合には、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、違反者を識別するために取引チャレンジ値ｒ１を調査する。同一の取引チャレンジ値ｒ１’がより以前の取引で使用されたことが検出される場合には、商店Ｍに、証明書Ｓを２回預けることを試みたことの責任がある。その結果、証明書Ｓは、拒否され、任意選択として、商店Ｍの一意のアイデンティティｉｄＭを、公表することができる。取引チャレンジ値ｒ１とｒ１’とが異なる場合には、ユーザＵに責任がある。この場合に、現在の取引および前の取引に基づいて、ユーザＵの公開鍵ｐｋＵを判定することができる。その結果、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、詐欺的なユーザ・コンピュータ・システム１０２のアイデンティティを暴露することができ、あるいは、エミッタ鍵（ｐｋＵ，ｓｋＵ）に関連するウォレット秘密ｓを暴露することができる。この場合に、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、ユーザ・コンピュータ・システム１０２に発行されたすべての証明書Ｓを識別でき、したがって、そのユーザ・コンピュータ・システム１０２を含む取引を識別することができる。
【００２８】
もう１つのステップで、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、マネー・ロンダリング検査値Ｖｊをより以前の取引のマネー・ロンダリング検査値と比較することによって、取引の限度を超えていないことをも検証する。組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、商店コンピュータ・システム１０３が、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１に前に預けられたマネー・ロンダリング検査値Ｖｊを預けることを試みていることを検出する場合に、１つまたは複数の違反者を識別するために、取引チャレンジ値ｒ１をも調査する。より以前の取引が、現在の取引と同一の取引チャレンジ値ｒ１に基づく場合には、商店コンピュータ・システム１０３だけに責任がある。電子決済システム１００のセキュリティ・セッティングに応じて、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、証明書Ｓの預かりを拒否するか、詐欺的な商店Ｍの一意のアイデンティティｉｄＭを公表するか、その両方を行うことができる。取引チャレンジ値が異なる場合には、ユーザ・コンピュータ・システムも、故意に取引に対する限度ＮＭを超えており、上で説明したようにこれを罰することができる。
【００２９】
発行者兼バリデータである銀行Ｂの役割、エミッタであるユーザＵの役割、およびアクセプタである商店Ｍの役割は、たとえば専用のコンピュータ・システムである組み合わされた銀行およびバリデータ・コンピュータ・システム１０１、ユーザ・コンピュータ・システム１０２、ならびに商店コンピュータ・システム１０３による、または汎用コンピュータ・システムである組み合わされた銀行およびバリデータ・コンピュータ・システム１０１、ユーザ・コンピュータ・システム１０２、ならびに商店コンピュータ・システム１０３で稼動するソフトウェア・モジュールによる、あるいはその組合せによるなど、ハードまたはソフトウェアで実施することができる。コンピュータ可読媒体を、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１、ユーザ・コンピュータ・システム１０２、または商店コンピュータ・システム１０３に含め、たとえば組み合わされた銀行およびバリデータ・コンピュータ・システム１０１、ユーザ・コンピュータ・システム１０２、または商店コンピュータ・システム１０３に含まれるプロセッサによって実行可能なプログラムのプログラム命令を実施することができる。コンピュータ可読媒体は、たとえば、ＣＤ−ＲＯＭ、フラッシュ・メモリ・カード、ハード・ディスク、または任意の他の適切なコンピュータ可読媒体とすることができる。
【００３０】
図２から図５に、本発明の実施形態による方法の流れ図を示す。
【００３１】
図２に、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１とユーザ・コンピュータ・システム１０２との間で実行される第１の２当事者プロトコル２００を示す。第１の２当事者プロトコル２００は、電子決済システム１００内で取引を実行するためのシステム・パラメータと、ユーザ・コンピュータ・システム１０２によって組み合わされた銀行およびバリデータ・コンピュータ・システム１０１から硬貨を引き出すためのシステム・パラメータとをセット・アップするように働く。
【００３２】
ステップ２０１で、電子決済システム１００の重要なシステム・パラメータをセット・アップする。具体的に言うと、セキュリティ・パラメータｋ、双一次写像ｅ、ウォレット・サイズｌ、および双一次写像ｅ上のハッシュ関数Ｈ１およびＨ２が、定義される。これらのパラメータは、ユーザ・コンピュータ・システム１０２がそのウォレットに保管できる証明書Ｓの個数のシステム境界をセットする。
【００３３】
ステップ２０２で、発行者である銀行Ｂは、公開鍵ｐｋＢおよび秘密鍵ｓｋＢを含む非対称の署名鍵（ｐｋＢ，ｓｋＢ）を生成する。
【００３４】
ステップ２０３で、エミッタであるユーザＵも、ユーザ・コンピュータ・システム１０２の公開鍵ｐｋＵおよび秘密鍵ｓｋＵを含む非対称のエミッタ鍵（ｐｋＵ，ｓｋＵ）を生成する。
【００３５】
ステップ２０４で、ユーザ・コンピュータ・システム１０２は、ランダムな値、具体的にはウォレット秘密ｓおよびｔを生成し、このウォレット秘密ｓおよびｔは、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１から引き出される証明書Ｓまたは硬貨のそれぞれの一意の通し番号Ｓｉを生成するのに使用される。生成されたランダムな値すなわちウォレット秘密ｓおよびｔは、ユーザ・コンピュータ・システム１０２によって秘密に保たれる。
【００３６】
ステップ２０５で、ユーザ・コンピュータ・システム１０２は、秘密鍵ｓｋＵとランダムな値すなわちウォレット秘密ｓおよびｔとの知識を組み合わされた銀行およびバリデータ・コンピュータ・システム１０１に証明する。さらに、ユーザ・コンピュータ・システム１０２は、その秘密鍵ｓｋＵとウォレット秘密ｓに対する署名σを入手する。その結果、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、ウォレット秘密ｓの検証可能な暗号化を、この暗号化に対するユーザ署名と共に入手する。組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、エミッタ鍵の秘密鍵ｓｋＵまたはウォレット秘密ｓに関して何も知るようにならない。
【００３７】
ステップ２０６で、ユーザ・コンピュータ・システム１０２は、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１から引き出された証明書Ｓを保管する。実際には、２ｌ個の証明書を含む証明書の組全体を、一緒に引き出し、保管することができ、各証明書Ｓは、通し番号Ｓｉによって表される。証明書は、ＣＨＬシステムによれば、サイズＯ（ｌ＋ｋ）の特にコンパクトな形で保管することができ、ここで、ｋは、システムのセキュリティ・パラメータである。
【００３８】
図３に、ユーザ・コンピュータ・システム１０２に発行された証明書Ｓを使うためにユーザ・コンピュータ・システム１０２と商店コンピュータ・システム１０３との間で実行される第２の２当事者プロトコル２１０を示す。
【００３９】
ステップ２１１で、ユーザ・コンピュータ・システム１０２は、特定の商店コンピュータ・システム１０３との取引に対する限度ＮＭを検査する。正直なユーザ・コンピュータ・システム１０２は、取引に対する限度ＮＭに既に達している場合には、商店コンピュータ・システム１０３との取引にかかわらない。この検査に基づいて、ユーザ・コンピュータ・システム１０２は、ユーザ・コンピュータ・システム１０２と商店コンピュータ・システム１０３との間の前の取引の番号ｊをも計算する。ユーザ・コンピュータ・システム１０２は、通常は次の未使用の証明書Ｓに関連する、現在の取引に使用される通し番号Ｓｉのインデックスｉをも判定する。同様に、商店コンピュータ・システム１０３は、ユーザ・コンピュータ・システム１０２との取引に対する限度ＮＭ未満であるかどうかを判定する。
【００４０】
ステップ２１２で、商店コンピュータ・システム１０３は、たとえば取引チャレンジ値ｒ１およびｒ２を含む、取引チャレンジ値を生成する。次に、取引チャレンジ値ｒ１およびｒ２は、ユーザ・コンピュータ・システム１０２に転送される。
【００４１】
ステップ２１３で、ユーザ・コンピュータ・システム１０２は、通し番号Ｓｉを有する証明書Ｓと取引チャレンジ値ｒ１およびｒ２とに基づいて、ウォレット検査値Ｔｉを計算する。ユーザ・コンピュータ・システム１０２は、ユーザ・コンピュータ・システム１０２と商店コンピュータ・システム１０３との間のｊ番目の取引のマネー・ロンダリング検査値Ｖｊをも計算する。
【００４２】
ステップ２１４で、使用される証明書Ｓが、ｉ番目の通し番号Ｓｉとそれに関連するウォレット検査値Ｔｉおよびマネー・ロンダリング検査値Ｖｊとを商店コンピュータ・システム１０３に送信することによって、商店コンピュータ・システム１０３に送られる。
【００４３】
ステップ２１５で、値ｉ、ｊ、ｓｋＵ、ｓ、およびσの知識の証明πが、商店コンピュータ・システム１０３のためにユーザ・コンピュータ・システム１０２によって生成される。この証明πは、ユーザ・コンピュータ・システム１０２と商店コンピュータ・システム１０３との間で対話的にまたはＦｉａｔ−Ｓｈａｍｉｒヒューリスティックを使用して非対話的に実行することができる。
【００４４】
ステップ２１６で、商店コンピュータ・システム１０３が、証明πを検証する。証明πが、この取引で使用される通し番号Ｓｉに関して有効である場合には、商店コンピュータ・システム１０３は、たとえば支払いに関して、通し番号Ｓｉおよび証明πに関連する証明書Ｓを受け入れる。
【００４５】
図４に、証明書Ｓがより以前の取引で既に使われているかどうかを判定するのに使用される、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１によって実行される妥当性検査手順の第１部分２２０を示す。
【００４６】
ステップ２２１で、商店コンピュータ・システム１０３は、取引チャレンジ値ｒ１およびｒ２と、証明書Ｓの通し番号Ｓｉと、ウォレット検査値Ｔｉと、マネー・ロンダリング検査値Ｖｊとを含む証明書Ｓ、ならびに証明πをサブミットする。この形で、商店コンピュータ・システム１０３は、たとえば関連する金額が組み合わされた銀行およびバリデータ・コンピュータ・システム１０１によって貸方記入されることを要求することによって、証明書Ｓに関連する額を償還することを試みる。
【００４７】
ステップ２２２で、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、証明πが通し番号Ｓｉと取引チャレンジ値ｒ１およびｒ２とに関して有効であることを検証する。証明πが有効でない場合には、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、即座にその取引の受入を拒否する。
【００４８】
ステップ２２３で、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、通し番号Ｓｉに関連する証明書Ｓが、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１に前に預けられたことがないことを検証する。
【００４９】
証明書Ｓが、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１に前に預けられたことがある場合には、ステップ２２４で、さらなる検査を実行し、同一の取引チャレンジ値ｒ１がより以前の取引で使用されたかどうかを検証する。
【００５０】
そうである場合には、商店コンピュータ・システム１０３が、証明書Ｓの２回目の預け入れを試みている。その結果、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、ステップ２２５でこの証明書を拒否する。
【００５１】
そうでない場合には、ユーザが、二重に使っており、銀行Ｂによって罰せられなければならない。この場合に、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、商店コンピュータ・システム１０３からの証明書を受け入れるが、ステップ２２６で、公開鍵ｐｋＵに関連するユーザ・コンピュータ・システム１０２を識別する。
【００５２】
任意選択のステップ２２７では、図２に示された引出プロトコル中に使用される電子決済システム１００のセキュリティ・セッティングに応じて、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１が、現在の取引と、同一の通し番号Ｓｉが使用されたより以前の取引とに基づいて、ユーザ・コンピュータ・システム１０２のウォレット秘密ｓを計算することができる。
【００５３】
その結果、ステップ２２８で、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、ウォレット秘密ｓまたは公開鍵ｐｋＵに基づいて、ユーザ・コンピュータ・システム１０２に発行された証明書Ｓの他のすべての通し番号Ｓｉを識別することができる。
【００５４】
ステップ２２３でテストされた通し番号Ｓｉが一意である場合には、妥当性検査は、図５に示された第２部分２３０で継続され、この第２部分２３０は、現在の取引が取引に対する限度ＮＭを超えないことを検証するのに使用される。
【００５５】
ステップ２３１で、この取引について計算されたマネー・ロンダリング検査値Ｖｊを検証する。これは、現在のマネー・ロンダリング検査値Ｖｊを、より以前の取引でステップ２３２で組み合わされた銀行およびバリデータ・コンピュータ・システム１０１に既にサブミットされている以前のマネー・ロンダリング検査値Ｖｊと比較することによって行われる。
【００５６】
マネー・ロンダリング検査値Ｖｊが一意である場合には、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、ステップ２３３で、サブミットされた証明書Ｓを受け入れ、この方法は終了する。
【００５７】
そうでない場合には、さらなるステップ２３４で、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１は、同一の取引チャレンジ値ｒ２が現在の取引およびより以前の取引で使用されたかどうかを検証する。
【００５８】
同一の取引チャレンジ値ｒ２が使用された場合には、商店コンピュータ・システム１０３だけに責任がある。この場合には、ステップ２３５で、証明書を拒否し、この取引に関連する額は、商店コンピュータ・システム１０３に貸方記入されなくなる。
【００５９】
そうでない場合には、ユーザにも責任がある。その結果、ステップ２３６、２３７、および２３８で、上で説明したように、組み合わされた銀行およびバリデータ・コンピュータ・システム１０１によって、公開鍵ｐｋＵに関連するユーザ・コンピュータ・システム１０２が識別され、そのウォレット秘密ｓが暗号化解除され、この情報に基づいて、このユーザの証明書Ｓの他の通し番号Ｓｉが、計算される。さらに、商店Ｍも、ステップ２３５で現在の証明書を拒否することによって罰せられる。
【００６０】
基礎になる問題の数学的複雑さに起因して、図２から図５に提示された流れ図は、電子決済システム１００の情報フローの高水準の概要を提示することしかできない。組み合わされた銀行およびバリデータ・コンピュータ・システム１０１と、ユーザ・コンピュータ・システム１０２と、商店コンピュータ・システム１０３との間のプロトコルを実施するために行われる詳細な動作は、次の数学的説明で詳細に示す。
【００６１】
セキュリティの定義
ＣＨＬシステムの定義は、二重使用を超える違反を処理するために一般化される。本明細書のオフライン電子マネー・シナリオは、アルゴリズムＢＫｅｙｇｅｎ、ＵＫｅｙｇｅｎ、Ｗｉｔｈｄｒａｗ、Ｓｐｅｎｄ、Ｄｅｐｏｓｉｔ、｛ＤｅｔｅｃｔＶｉｏｌａｔｉｏｎ（ｉ）、ＩｄｅｎｔｉｆｙＶｉｏｌａｔｏｒ（ｉ）、ＶｅｒｉｆｙＶｉｏｌａｔｉｏｎ（ｉ）｝、Ｔｒａｃｅ、およびＶｅｒｉｆｙＯｗｎｅｒｓｈｉｐと一緒に、３つの通常のプレイヤすなわち、ユーザ、銀行、および商店からなる。形式ばらずに言うと、ＢＫｅｙｇｅｎおよびＵＫｅｙｇｅｎは、それぞれ銀行およびユーザの鍵生成アルゴリズムである。ユーザは、２ｌ個の硬貨のウォレットを入手するためにＷｉｔｈｄｒａｗ中に銀行と対話し、銀行は、任意選択のトレーシング情報をデータベースＤに保管する。Ｓｐｅｎｄでは、ユーザは、そのユーザのウォレットからの１つの硬貨を商店で使い、その結果、この商店は、その硬貨の通し番号Ｓを入手し、商店Ｍは、硬貨のロケータすなわちマネー・ロンダリング検査値Ｖおよび有効性の証明πを記録する。Ｄｅｐｏｓｉｔでは、正直な商店Ｍがユーザから硬貨Ｃ＝（Ｓ，Ｖ，π）を受け入れる時に、必ず、銀行が預け入れについてこの硬貨を受け入れることの保証がある。銀行は、Ｃ＝（Ｓ，Ｖ，π）をデータベースＬに保管する。しかし、この点で、銀行は、Ｃがシステム条件のいずれかに違反するかどうかを判定する必要がある。
【００６２】
違反ｉのそれぞれについて、アルゴリズムのタプル｛ＤｅｔｅｃｔＶｉｏｌａｔｉｏｎ（ｉ），ＩｄｅｎｔｉｆｙＶｉｏｌａｔｏｒ（ｉ），ＶｅｒｉｆｙＶｉｏｌａｔｉｏｎ（ｉ）｝が定義される。ここでは、２つの違反がある。
【００６３】
違反１（二重使用）：ＤｅｔｅｃｔＶｉｏｌａｔｉｏｎ（１）で、銀行が、Ｌ内の２つの硬貨Ｃ１＝（Ｓ１，Ｖ１，π１）およびＣ２＝（Ｓ２，Ｖ２，π２）が、同一の通し番号Ｓ１＝Ｓ２を有するかどうかをテストする。そうである場合には、銀行は、（Ｃ１，Ｃ２）に対してＩｄｅｎｔｉｆｙＶｉｏｌａｔｏｒ（１）アルゴリズムを実行し、違反者の公開鍵ｐｋおよび有罪の証明Πを入手する。誰もが、公開鍵ｐｋを有するユーザが通し番号Ｓ１を有する硬貨を二重に使ったことを確信するために、（ｐｋ，Ｓ１，Ｖ１，Π）に対してＶｅｒｉｆｙＶｉｏｌａｔｉｏｎ（１）を実行することができる。
【００６４】
違反２（マネー・ロンダリング）：ＤｅｔｅｃｔＶｉｏｌａｔｉｏｎ（２）で、銀行が、Ｌ内の２つの硬貨Ｃ１＝（Ｓ１，Ｖ１，π１）およびＣ２＝（Ｓ２，Ｖ２，π２）が、同一の商店レコード・ロケータすなわちマネー・ロンダリング検査値Ｖ１＝Ｖ２を有するかどうかをテストする。そうである場合には、銀行は、（Ｃ１，Ｃ２）に対してＩｄｅｎｔｉｆｙＶｉｏｌａｔｏｒ（２）アルゴリズムを実行し、違反者の公開鍵ｐｋおよび有罪の証明Πを入手する。誰もが、公開鍵ｐｋを有するユーザが商店レコード・ロケータすなわちマネー・ロンダリング検査値Ｖ１を有する硬貨に関する限界のある匿名性ビジネス限度を超えたことを確信するために、（ｐｋ，Ｓ１，Ｖ１，Π）に対してＶｅｒｉｆｙＶｉｏｌａｔｉｏｎ（２）を実行することができる。
【００６５】
任意選択として、すべての違反の後に、銀行は、有効な有罪の証明Πに対してＴｒａｃｅアルゴリズムを実行して、所有権の証明Γと一緒に、公開鍵ｐｋを有する不正を働くユーザによってこれまでに使われたすべての通し番号Ｓｉのリストを入手することもできる。誰もが、公開鍵ｐｋを有するユーザが通し番号Ｓｉを有する硬貨の所有者であったことを確信するために、（ｐｋ，Ｓｉ，Γ）に対してＶｅｒｉｆｙＯｗｎｅｒｓｈｉｐを実行することができる。
【００６６】
さらに、ＣＨＬシステムのセキュリティ定義は、電子マネー用に一般化される。正しさ、バランス、およびユーザの匿名性の、ＣＨＬシステムの形式化は、変更されないままである。おおまかに言って、バランスは、正直な銀行が、ユーザが引き出したものより多くの硬貨の預け入れを受け入れる必要が絶対になくなることを保証し、ユーザの匿名性は、ユーザが、既知のシステム条件の１つに違反しない限り、完全に匿名のままであることをユーザに保証する。次では、３つの追加のプロパティを説明する。これらのプロパティは、任意の指定された違反、具体的には上記の違反に適用するための、二重使用者およびその無罪証明可能性（ｅｘｃｕｌｐａｂｉｌｉｔｙ）のＣＨＬの識別およびトレーシングの一般化である。ｐａｒａｍｓは、ウォレットあたりの硬貨の個数および商店ごとの使用限度を含む、グローバル・パラメータであるものとする。
【００６７】
違反者の識別：正直な商店（または、おそらくは複数の正直な商店）が、敵対者と共にＳｐｅｎｄプロトコルを２回実行し、出力がＣ１＝（Ｓ１，Ｖ１，π１）およびＣ２＝（Ｓ２，Ｖ２，π２）であったと仮定する。このプロパティは、あるｉについてＤｅｔｅｃｔＶｉｏｌａｔｉｏｎ（ｉ）（ｐａｒａｍｓ，Ｃ１，Ｃ２）が受け入れる場合に、ＩｄｅｎｔｉｆｙＶｉｏｌａｔｏｒ（ｉ）（ｐａｒａｍｓ，Ｃ１，Ｃ２）が、鍵ｐｋおよび証明Πを出力し、ＶｅｒｉｆｙＶｉｏｌａｔｉｏｎ（ｉ）（ｐａｒａｍｓ，ｐｋ，Ｓ１，Ｖ１，Π）が受け入れることを、高い確率で保証する。
【００６８】
違反者のトレース：ＶｅｒｉｆｙＶｉｏｌａｔｉｏｎ（ｉ）（ｐａｒａｍｓ，ｐｋ，Ｓ，Ｖ，Π）が、硬貨Ｃ１，Ｃ２から導出されたある違反ｉについて受け入れると仮定する。このプロパティは、Ｔｒａｃｅ（ｐａｒａｍｓ，ｐｋ，Ｃ１，Ｃ２，Π，Ｄ）が、所有権の証明Γ１，…，Γｍと一緒にｐｋのユーザに属するすべての硬貨の通し番号Ｓ１，…，Ｓｍを出力し、すべてのｊについて、ＶｅｒｉｆｙＯｗｎｅｒｓｈｉｐ（ｐａｒａｍｓ，ｐｋ，Ｓｊ，Γｊ）が受け入れることを、高い確率で保証する。
【００６９】
無罪証明可能性：敵対者が、鍵ｐｋを有する正直なユーザと共にＷｉｔｈｄｒａｗプロトコルに任意の回数だけ参加し、その後、その同一ユーザと共に違反しないＳｐｅｎｄプロトコルに任意の回数だけ参加すると仮定する。次に、この敵対者は、整数ｉと、硬貨通し番号Ｓと、鍵ｐｋを有するユーザが違反ｉを犯し、硬貨Ｓを所有すると主張する証明Γとを出力する。弱い無罪証明可能性プロパティは、すべての敵対者について、ＶｅｒｉｆｙＯ（ｐａｒａｍｓ，ｐｋ，Ｓ，Γ）が受け入れる確率を無視できることを述べる。
【００７０】
さらに、敵対者は、このユーザをＳｐｅｎｄプロトコルにかかわらせ続け、このユーザにシステム条件を違反することを強制することができる。次に、この敵対者は、（ｉ，Ｓ，Ｖ，Π）を出力する。強い無罪証明可能性プロパティは、すべての敵対者について、（１）Ｓが、ｐｋのユーザに属さない硬貨通し番号であるときに、弱い無罪証明可能性が成り立ち、（２）ｐｋのユーザが違反ｉを犯さなかったときに、ＶｅｒｉｆｙＶｉｏｌａｔｉｏｎ（ｉ）（ｐａｒａｍｓ，ｐｋ，Ｓ，Ｖ，Π）が受け入れる確率は、無視できることを述べる。
【００７１】
技術的予備行為
電子マネー・システムは、さまざまな既知のプロトコルを基本構成要素として使用するが、これらのプロトコルをこれから短く再検討する。これらのプロトコルの多くは、複数の異なる複雑さの仮定の下でセキュアであることを示すことができ、これが、本発明人の電子マネー・システムに拡張される柔軟性である。表記：本明細書では、ｇが群Ｇを生成することを示すために、Ｇ＝〈ｇ〉と書く。
【００７２】
双一次写像
Ｂｉｌｉｎｅａｒ＿Ｓｅｔｕｐが、セキュリティ・パラメータｌｋの入力時に、双一次写像のパラメータを、γ＝（ｑ，ｇ１，ｈ１，Ｇ１，ｇ２，ｈ２，Ｇ２，ＧＴ，ｅ）として出力するアルゴリズムであるものとする。各群Ｇ１＝〈ｇ１〉＝〈ｈ１〉、Ｇ２＝〈ｇ２〉＝〈ｈ２〉、およびＧＴは、素数位数ｑ＝Θ（２ｋ）の群である。効率的に計算可能な写像ｅ：Ｇ１×Ｇ２→ＧＴは、（双一次）すべてのｇ１∈Ｇ１、ｇ２∈Ｇ２、およびａ，ｂ∈Ｚｑについて、
【００７３】
【数１】
【００７４】
であり、（非縮重）ｇ１がＧ１の生成元であり、ｇ２がＧ２の生成元である場合に、ｅ（ｇ１，ｇ２）はＧＴを生成する、の両方である。
【００７５】
複雑さの仮定
本方式のセキュリティは、次の、ＣＨＬと同一の仮定に頼る。
【００７６】
強いＲＳＡ仮定：ＲＳＡの法ｎおよびランダム要素
【００７７】
【数２】
【００７８】
を与えられて、ｈｅ≡ｇ ｍｏｄ ｎになる
【００７９】
【数３】
【００８０】
および整数ｅ＞１を計算することは困難である。法ｎは、特殊な形ｐｑであり、ここで、ｐ＝２ｐ’＋１およびｑ＝２ｑ’＋１は、安全な素数である。
【００８１】
ｙ−Ｄｅｃｉｓｉｏｎａｌ Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ Ｉｎｖｅｒｓｉｏｎ仮定（ｙ−ＤＤＨＩ）：ランダムな生成元ｇ∈Ｇ（ただし、Ｇは素数位数ｑを有する）と、ランダムなｘ∈Ｚｑの値
【００８２】
【数４】
【００８３】
と、値Ｒ∈Ｇとを与えられて、Ｒ＝ｇ１／ｘであるか否かを判断することは困難である。
【００８４】
Ｅｘｔｅｒｎａｌ Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ仮定（ＸＤＨ）：Ｂｉｌｉｎｅａｒ＿Ｓｅｔｕｐ（ｌｋ）が、双一次写像ｅ：Ｇ１×Ｇ２→ＧＴのパラメータを作ると仮定する。ＸＤＨ仮定は、Ｄｅｃｉｓｉｏｎａｌ Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ＤＤＨ）問題がＧ１で困難であることを述べる。これは、効率的に計算可能な同形写像ψ’：Ｇ１→Ｇ２が存在しないことを暗示する。
【００８５】
Ｓｕｍ−Ｆｒｅｅ Ｄｅｃｉｓｉｏｎａｌ Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ仮定（ＳＦ−ＤＤＨ）：ｇ∈Ｇが、位数ｑのランダム生成元であると仮定する。Ｌが、｜ｑ｜の任意の多項式関数であるものとする。
【００８６】
【数５】
【００８７】
が、部分集合Ｉ⊂ｅｑ｛１，…，Ｌ｝の入力時に、値
【００８８】
【数６】
【００８９】
を出力するオラクルであるものとするが、ここで、いくつかの
【００９０】
【数７】
【００９１】
について
【００９２】
【数８】
【００９３】
である。さらに、Ｒは、Ｊ⊆｛１，…，Ｌ｝がＩｉからＤＤＨ独立である場合に限ってＲ（Ｊ，Ｉ１，…，Ｉｔ）＝１になる述部であるものとする。すなわち、ｖ（Ｉｉ）が、ｊ∈Ｉｉの場合に限って位置ｊに１を有し、それ以外の場合に０を有する長さＬのベクトルであるときに、ｖ（Ｊ）＋ｖ（Ｉａ）＝ｖ（Ｉｂ）＋ｖ（Ｉｃ）（加算は整数に対してビット単位である）になる３つの集合Ｉａ、Ｉｂ、およびＩｃはない。
【００９４】
次に、すべての確率的多項式時間敵対者Ａ（・）について、
【００９５】
【数９】
【００９６】
である。ただし、Ｑは、Ａが
【００９７】
【数１０】
【００９８】
に対して行ったクエリの集合である。
【００９９】
鍵作成ブロック
１）既知の離散対数ベースのゼロ知識証明
一般的なパラメータ・モデルでは、（１）素数または合成数による離散対数の剰余の知識の証明、（２）２つの（おそらくは異なる）素数または合成数を法とする表現剰余の同等性の知識の証明、（３）あるコミットメントが２つの他のコミットされた値の積を表すことの証明、（４）コミットされた値が所与の整数区間内にあることの証明、および（５）前の４つのうちのいずれか２つの論理和または論理積の証明など、離散対数に関するステートメントを提供する複数の前から既知の結果が使用される。これらのプロトコルでは、合成数による剰余は、強いＲＳＡ仮定の下でセキュアであり、素数による剰余は、離散対数仮定の下でセキュアである。Ｆｉａｔ−Ｓｈａｍｉｒヒューリスティックを適用して、そのような知識の証明を、あるメッセージｍに対するｓｉｇｎａｔｕｒｅ ｐｒｏｏｆ ｏｆ ｋｎｏｗｌｅｄｇｅにすることができる。
【０１００】
２）ＣＬ署名
Ｐｅｄｅｒｓｅｎコミットメント方式によれば、公開パラメータは、素数位数ｑおよび生成元（ｇ０，…，ｇｍ）の群Ｇである。値（ｖ１，…，ｖｍ）∈ｑｍをコミットするために、ランダムなｒ∈ｑを選択し、
【０１０１】
【数１１】
【０１０２】
をセットする。
【０１０３】
次の２つのプロトコルを有するセキュアな署名方式が存在する。（１）ユーザと鍵（ｐｋｓ，ｓｋｓ）を有する署名者との間の効率的なプロトコル。共通の入力は、ｐｋｓおよびＣすなわちＰｅｄｅｒｓｅｎコミットメントからなる。ユーザの秘密入力は、Ｃ＝ＰｅｄＣｏｍ（ｖ１，…，ｖｌ；ｒ）になる値（ｖ１，…，ｖｌ，ｒ）の集合である。このプロトコルの結果として、ユーザは、そのユーザがコミットした値に対する署名
【０１０４】
【数１２】
【０１０５】
を入手するが、署名者は、それらについて何も知るようにならない。署名は、サイズＯ（ｌ ｌｏｇ ｑ）を有する。（２）ユーザと検証者との間の署名プロトコルの効率的な知識の証明。共通の入力は、ｐｋｓおよびコミットメントＣである。ユーザの秘密入力は、Ｃ＝ＰｅｄＣｏｍ（ｖ１，…，ｖｌ；ｒ）になる値（ｖ１，…，ｖｌ，ｒ）および
【０１０６】
【数１３】
【０１０７】
である。これらの署名は、強いＲＳＡ仮定の下でセキュアである。この説明において、ＣＬ署名が実際にどのように働くかは問題ではない。
【０１０８】
後続の電子マネー・システムは、ＣＬ署名と独立に、強いＲＳＡ仮定を使用する。双一次写像を使用することによって、実際により短い署名を作るために他の署名方式を使用することができる。
【０１０９】
３）検証可能な暗号化
検証可能な暗号化方式では、暗号化する側／証明する側は、既知の公開鍵の下での暗号化の平文が、Ｐｅｄｅｒｓｅｎコミットメントで隠される値と同等であることを検証者に確信させる。"Jan Camenisch and Ivan Damgard. Verifable encryption, groupencryption, and their applications to group signatures and signature sharingschemes. In Tatsuaki Okamoto, editor, Advances in Cryptology | ASIACRYPT '00,volume 1976 of LNCS, pages 331-345. Springer Verlag, 2000"に、すべての意味論的にセキュアな暗号化方式を検証可能な暗号化方式にする技法が記載されている。
【０１１０】
この技法は、すべての意味論的にセキュアな暗号化方式を検証可能な暗号化方式にするのに使用することができる。検証可能な暗号化方式とは、証明する側兼暗号化する側Ｐと検証者兼受信側Ｖとの間の２当事者プロトコルである。
【０１１１】
おおまかに言って、ＰおよびＶの共通の入力は、公開暗号化鍵ｐｋおよびコミットメントＡである。このプロトコルの結果として、Ｖは、Ａの冒頭の暗号化ｃの拒否または入手のいずれかを行う。このプロトコルは、Ｖが、無視できる確率でのみ不正な暗号化を受け入れることと、ＶがＡの冒頭について意味のあることを何も知るようにならないこととを保証する。対応する秘密鍵ｓｋと一緒に、トランスクリプトｃは、Ａの冒頭を効率的に回復するのに十分な情報を含む。本発明人は、ここではいくつかの詳細を隠し、十分な議論についてはＣａｍｅｎｉｓｃｈおよびＤａｍｇａｒｄを参照する。
【０１１２】
４）双一次Ｅｌｇａｍａｌ暗号化
ｇｘが、暗号化解除に十分であり、公開鍵が、ある関数ｆについてｆ（ｇｘ）である暗号方式が、探されている。"Dan Boneh and Matthew Franklin. Identity-based encryption fromthe Weil pairing. In Joe Kilian, editor, Advances in Cryptology | CRYPTO '01,volume 2139 of LNCS, pages 213-229. Springer Verlag, 2001"で、アイデンティティベースのコンテキストでの１つの例が提供されている。ここでは、Ｓｕｍ−Ｆｒｅｅ ＤＤＨによって暗示される仮定の下で意味論的にセキュアであるＡｔｅｎｉｅｓｅ他の双一次Ｅｌｇａｍａｌ暗号化方式を使用する。
【０１１３】
具体的に言うと、Ｅｌｇａｍａｌ暗号化の次の双一次変形への上の検証可能な暗号化技法が、適用される。ｌｋに対してＢｉｌｉｎｅａｒ＿Ｓｅｔｕｐを実行してγ＝（ｑ，ｇ１，ｈ１，Ｇ１，ｇ２，ｈ２，Ｇ２，ＧＴ，ｅ）を入手し、ここで、双一次写像ｅ：Ｇ１×Ｇ２→ＧＴを有すると仮定する。（Ｇ，Ｅ，Ｄ）が、標準的な鍵生成アルゴリズム、暗号化アルゴリズム、および暗号化解除アルゴリズムを表すものとする。（ｌｋ，γ）の入力の際に、鍵生成アルゴリズムＧは、ランダムなｕ∈Ｚｑについて鍵対
【０１１４】
【数１４】
【０１１５】
を出力する。主な発想は、値
【０１１６】
【数１５】
【０１１７】
が、暗号化解除に十分であるということである。
【０１１８】
ｐｋの下でメッセージｍ∈ＧＴを暗号化するためには、ランダムなｋ∈Ｚｑを選択し、暗号文
【０１１９】
【数１６】
【０１２０】
を出力する。次に、値
【０１２１】
【数１７】
【０１２２】
を用いてｃ＝（ｃ１，ｃ２）を暗号化解除するためには、単純に
【０１２３】
【数１８】
【０１２４】
を計算する。この暗号化方式は、Ｄｅｃｉｓｉｏｎａｌ Ｂｉｌｉｎｅａｒ Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ＤＢＤＨ）仮定の下で意味論的にセキュアであることがわかっている、すなわち、ランダムなａ，ｂ，ｃ∈ＺｑおよびＸ∈ＧＴについて
【０１２５】
【数１９】
【０１２６】
を与えられて、Ｘ＝ｅ（ｇ１，ｇ２）ａｂｃであるかどうかを判断することは困難である。
【０１２７】
５）ＤＹ擬似ランダム関数（ＰＲＦ）
Ｇ＝〈ｇ〉が、素数位数ｑの群であるものとする。ｓが、Ｚｑのランダムな要素であるものとする。ＤｏｄｉｓおよびＹａｍｐｏｌｓｋｉｙは、最近、入力
【０１２８】
【数２０】
【０１２９】
に関する擬似ランダム関数
【０１３０】
【数２１】
【０１３１】
を提案した。この構成は、ｙ−ＤＤＨＩの下でセキュアである。上で説明した構成では、本発明のウォレットをＯ（ｌ＋ｋ）ビットからＯ（ｌ・ｋ）ビットに大きくするという犠牲を払って、ＤＹ ＰＲＦをＮａｏｒ−Ｒｅｉｎｇｏｌｄ ＰＲＦに置換し、ｙ−ＤＤＨＩ仮定をより標準的なＤＤＨ仮定に置換することができる。
【０１３２】
限界のある匿名性モデルでのコンパクト電子マネー
ＣＨＬコンパクト電子マネー方式と同様に、ユーザは、銀行から２ｌ個の硬貨のウォレットを引き出し、これらを１つずつ使う。また、ＣＨＬ方式と同様に、擬似ランダム関数Ｆ（・）（・）が使用され、この関数の範囲は、大きい素数位数ｑの、ある群Ｇである。
【０１３３】
高水準で、ユーザは、後で説明する適当な領域から５つの値（ｘ，ｓ，ｔ，ｖ，ｗ）を選択することと、これらの値に対する銀行の署名σを入手するために銀行と共に適当なセキュア・プロトコルを実行することによって、２ｌ＝Ｎ個の硬貨のウォレットを形成する。
【０１３４】
次では、ユーザが、商店Ｍから商品を買うことによって硬貨番号ｉを使うことを望み、この商店とのＫ回までの取引だけを匿名にすることができると仮定する。さらに、これが、このユーザのＭとのｊ回目の取引であり、ｊ≦Ｋであると仮定する。ウォレット内のｉ番目の硬貨に関連するのが、その通し番号Ｓ＝Ｆｓ（ｉ）である。商店Ｍとのｊ番目の取引に関連するのが、その商店のレコード・ロケータＶ＝Ｆｖ（Ｍ，ｊ）である。
【０１３５】
本発明の実施形態によれば、Ｓｐｅｎｄプロトコルで、ユーザが、値（Ｓ，Ｖ）を、これらの値が（ｓ，ｉ，ｖ，Ｍ，ｊ）の関数として計算されることの（非対話的ゼロ知識）証明と一緒に商店に与えなければならないことが規定され、ここで、１≦ｉ≦Ｎであり、１≦ｊ≦Ｋであり、（ｓ，ｖ）は、銀行によって署名されたウォレットに対応する。ＳおよびＶは、擬似ランダムであり、したがって、計算的に情報を漏らさず、証明は、ゼロ知識なので情報を漏らさない。あるユーザが、Ｎ個を超える硬貨を使うと仮定する。その場合に、このユーザは、いくつかの通し番号を複数回使用している。というのは、形Ｆｓ（ｉ）、ただし１≦ｉ≦Ｎの可能な値ＳがＮ個しかないからである。同様に、あるユーザが、ＭとのＫ回を超える取引を行ったと仮定する。その場合に、このユーザは、いくつかの商店レコード・ロケータを複数回使用している。というのは、固定されたＭについて、異なる値Ｖ＝Ｆｖ（Ｍ，ｊ）、ただし１≦ｊ≦ＫがＫ個しかないからである。したがって、二重使用および限界のある匿名性ビジネス・モデルの違反を検出することができる。
【０１３６】
次では、任意のＳまたはＶの複数回の使用が識別につながることをどのように提供するかを説明する。ｓおよびｖの他に、ウォレットには、ｘ、ｔ、およびｗも含まれる。値ｘ∈ｑは、ｇｘが、ユーザのアイデンティティに公開してリンクできる値になるような値である（ただし、ｇは、群Ｇの生成元である）。たとえば、ある計算可能関数ｆについて、ｆ（ｇｘ）をユーザの公開鍵とすることができる。取引の一部として、商店が、ランダム値ｒ≠０を与え、ユーザが、Ｔ＝ｇｘＦｔ（ｉ）ｒおよびＷ＝ｇｘＦｗ（Ｍ，ｊ）ｒを、ＴおよびＷがまさに同一のウォレットならびに同一のｉおよびｊに対応する（ｒ，ｘ，ｔ，ｉ，ｗ，Ｍ，ｊ）の関数として適当に計算されることの証明と一緒に明らかにすると仮定する。やはり、ＴおよびＷは、擬似ランダムであり、したがって、情報を一切漏らさない。
【０１３７】
ユーザが、同一の通し番号Ｓ＝Ｆｓ（ｉ）を２回使用し、ｑが適度に大きい場合に、高い確率で、２つの異なる取引で、そのユーザは、異なるｒを受け取り、これらをｒ１およびｒ２と呼び、したがって、
【０１３８】
【数２２】
【０１３９】
を用いて応答しなければならない。値ｇｘを、その後に次にように計算できることは、簡単にわかる。
【０１４０】
【数２３】
【０１４１】
ユーザが、同一の商店のレコード・ロケータ番号Ｖを２回使用する場合に、ｇｘを正確に同一の形で見つけることができることも、そうであることが示される。この２つの取引で、商店が同一のｒを使用すると仮定する。その場合に、銀行は、単純にこのｅ−ｃｏｉｎの預け入れを拒否することができる（商店が同一なので、この商店が、適当なランダム化のその商店自体の欠如の責任を負う）。この商店が２つの異なるｒすなわちｒ１およびｒ２を使用し、Ｗ１およびＷ２を生じたと推定される場合に、
【０１４２】
【数２４】
【０１４３】
であることがわかる。
【０１４４】
したがって、二重使用または限界のあるビジネス・モデルの違反は、識別につながる。唯一の残っている疑問は、同一ユーザの他の取引をトレースするために、これをどのように適合させることができるかである。ｇｘは、必ずしも公開値ではなく、ｆ（ｇｘ）だけが公開される場合もありえるが、ｇｘの知識は、ｓを検証可能に暗号化することによって形成された暗号文を暗号化解除する能力を与える（たとえば、ＢｏｎｅｈおよびＦｒａｎｋｌｉｎの暗号方式は、ｇｘが暗号化解除に十分であるというプロパティを有する）。ウォレットを引き出すときに、ユーザは、そのような暗号文を銀行に与える。ｓの知識は、このウォレットからのすべての硬貨の通し番号を発見することを可能にし、それらがどのように使われたかを調べることを可能にする。
【０１４５】
最後に、値（ｘ，ｖ，ｗ）は、特定のウォレットではなく、ユーザのアイデンティティに結び付けられなければならない。この形では、ユーザが特定の商店で異なるウォレットから多すぎる金銭を使うことを試みる場合であっても、それが検出および識別につながる。
【０１４６】
本プロトコルの詳細な説明
本方式は、ＣＨＬ電子マネー方式の拡張なので、Ｄｏｄｉｓ−Ｙａｍｐｏｌｓｋｉｙ擬似ランダム関数すなわち、
【０１４７】
【数２５】
【０１４８】
が使用され、ここで、ｇは、適切な群の生成元であり、ＣＬ署名および関連するプロトコルが、署名を発行し、署名の知識を証明するのに使用され、双一次Ｅｌｇａｍａｌ暗号方式が、Ｃａｍｅｎｉｓｃｈ−Ｄａｍｇａｒｄ検証可能暗号化技法と共に使用される。
【０１４９】
表記：
【０１５０】
【数２６】
【０１５１】
であるものとし、Ｈが、その範囲が適当な群であるハッシュ関数であるときに、
【０１５２】
【数２７】
【０１５３】
であるものとする。
【０１５４】
これから、本システムのプロトコルすなわち、Ｓｅｔｕｐ、Ｗｉｔｈｄｒａｗ、Ｓｐｅｎｄ、およびＤｅｐｏｓｉｔ（違反に応答するプロトコルを含む）を説明する。
【０１５５】
Ｓｅｔｕｐプロトコル
ｋが、セキュリティ・パラメータであると仮定する。共通のシステム・パラメータは、Ｂｉｌｉｎｅａｒ＿Ｓｅｔｕｐ（ｌｋ）→（ｑ，ｇ１，Ｇ１，ｇ２，ｈ２，Ｇ２，ＧＴ，ｅ）、ウォレット・サイズｌ、ならびに２つのハッシュ関数Ｈ１：｛０，１｝＊→ＧｔおよびＨ２：｛０，１｝＊→Ｇ１である。銀行は、ＣＬ署名鍵（ｐｋＢ，ｓｋＢ）を生成する。
【０１５６】
各ユーザは、形ｓｋＵ＝（ｘ，ｖ，ｗ）およびｐｋＵ＝（ｅ（ｇ１，ｈ２）ｘ，ｅ（ｇ１，ｈ２）ｖ，ｅ（ｇ１，ｈ２）ｗ）の鍵対を生成し、ここで、ｘ、ｖ、およびｗは、Ｚｑからランダムに選択される。各ユーザは、任意のセキュア署名方式用の署名鍵も生成する。各商店は、一意のアイデンティティ・ストリングｉｄＭも公開する。また、各ユーザが商店ｉｄＭで使うことのできる硬貨の個数の上限ＮＭが決定される。
【０１５７】
Ｗｉｔｈｄｒａｗプロトコル
ユーザＵは、次のように銀行Ｂから２ｌ個の硬貨を引き出す。このユーザおよび銀行は、対話型プロトコルにかかわり、両方がエラーを報告しない場合に、最後に、
１．Ｕは、（ｓ，ｔ，σ）を入手し、ここで、ｓ、ｔは、Ｚｑ内のランダムな値であり、σは、（ｓｋＵ，ｓ，ｔ）に対する銀行の署名すなわち（ｘ，ｖ，ｗ，ｓ，ｔ）である。
２．Ｂは、ｅ（ｇ１，ｈ２）ｘの下でのｓの検証可能な暗号化すなわち、ユーザの公開鍵ｐｋＵの最初の要素を、この暗号化に対するユーザの署名と一緒に入手する。
３．Ｂは、ｓｋＵ、ｓ、またはｔに関して何も知るようにならない。
【０１５８】
ステップ１は、文献"Jan Camenisch and AnnaLysyanskaya. A signature scheme with ecient protocols. In Stelvio Cimato,Clemente Galdi, and Giuseppe Persiano, editors, Security in Communication Networks'02, volume 2576 of LNCS, pages 268{289. Springer Verlag, 2002"に記載のように、署名および関連するプロトコルを使用して実現することができる。ステップ２は、Ｃａｍｅｎｉｓｃｈ−Ｄａｍｇａｒｄ検証可能暗号化技法を双一次Ｅｌｇａｍａｌ暗号方式に適用することによって実現することができる。ステップ３は、他の２つから得られる。これらのステップのすべてが、本質的にＣＨＬ電子マネー方式と同一であり、例外は、ここではｘのほかにｖおよびｗをも含む署名された秘密鍵である。
【０１５９】
Ｓｐｅｎｄプロトコル
ユーザＵは、次のように、ＮＭ個の硬貨という使用限度を伴って、商店Ｍで１つの硬貨を使う。ＣＨＬと同様に、このユーザは、このユーザのウォレット内で使われる硬貨の個数の、１から２ｌまでの秘密カウンタｉを保持する。さらに、このユーザは、現在、このユーザが各商店で使った硬貨の個数を表す、商店ＭごとのカウンタｊＭも保持する。
１．Ｕは、商店Ｍに関するＵの使用限度未満である、すなわち、ｊＭ＜ＮＭであることを検査する。そうでない場合には、Ｕは、打ち切る。
２．Ｍは、ランダムな
【０１６０】
【数２８】
【０１６１】
をＵに送信する。
３．Ｕは、ＭとのｊＭ番目の取引で、Ｕのウォレット内のｉ番目の硬貨をＭに送信する。ｓｋＵ＝（ｘ，ｖ，ｗ）であることを想起されたい。この硬貨は、通し番号Ｓおよびウォレット検査Ｔ、ただし
【０１６２】
【数２９】
【０１６３】
と、２つのマネー・ロンダリング検査値ＶおよびＷ、ただし
【０１６４】
【数３０】
【０１６５】
と、（ｉ，ｊＭ，ｓｋＵ＝（ｘ，ｖ，ｗ），ｓ，ｔ，σ）の知識のゼロ知識証明（ＺＫＰＯＫ）πとからなり、
（ａ）１≦ｉ≦２ｌ
（ｂ）１≦ｊＭ≦ＮＭ
（ｃ）
【０１６６】
【数３１】
【０１６７】
、すなわち、Ｓ＝ｅ（ｇ１，ｈ２）１／（Ｓ＋ｉ）
（ｄ）
【０１６８】
【数３２】
【０１６９】
（ｅ）
【０１７０】
【数３３】
【０１７１】
（ｆ）
【０１７２】
【数３４】
【０１７３】
（ｇ） ＶｅｒｉｆｙＳｉｇ（ｐｋＢ，（ｓｋＵ＝（ｘ，ｖ，ｗ），ｓ，ｔ），σ）＝ｔｒｕｅ
になる。証明πは、Ｆｉａｔ−Ｓｈａｍｉｒヒューリスティックを使用して非対話的にすることができる。
４．πが検証され、値Ｖｊが前にＭによって一度も見られていない場合に、Ｍは、硬貨（ｒ１，ｒ２，Ｓ，Ｔ，Ｖ，Ｗ，π）を受け入れ、保存する。値Ｖｊが、前に硬貨（ｒ１，ｒ２，Ｓ’，Ｔ’，Ｖ，Ｗ’，π’）で以前に見られた場合に、Ｍは、Ｏｐｅｎ（Ｗ’，Ｗ，ｒ２，ｒ２）を返す。Ｍが、Ｓｐｅｎｄプロトコルを正直に実行する（すなわち、各プロトコルの始めに新しいランダムな値を選択する）場合に、高い確率で、ｒ２≠ｒ２であり、
【０１７４】
【数３５】
【０１７５】
である。したがって、この商店は、Ｕの公開鍵の一部である
【０１７６】
【数３６】
【０１７７】
を計算することによって、このユーザを識別することができる。これは、正直な商店が、その商店で超過して使うことを試みる顧客からその商店自体を保護することを可能にする（その商店が正直でない場合には、銀行が、預け入れの時に超過使用を把握する）。
【０１７８】
ステップ３（ａ）、３（ｃ）、および３（ｄ）は、ＣＨＬ方式と同一であるが、ステップ３（ｂ）、３（ｅ）、および３（ｆ）は、新規であるがステップ３（ａ）、３（ｃ）、および３（ｄ）に類似する。最後に、ステップ３（ｇ）は、正しく適合される必要がある。その結果、ステップ３（ａ）および３（ｂ）は、標準技法を使用して行うことができる。ステップ３（ｃ）から３（ｆ）は、"Jan Camenisch, Susan Hohenberger, and Anna Lysyanskaya.Compact E-Cash. In Ronald Cramer, editor, Advances in Cryptology { EUROCRYPT'05, volume 3494 of LNCS, pages 302-321, 2005"に記載のＣａｍｅｎｉｓｃｈ、Ｈｏｈｅｎｂｅｒｇｅｒ、およびＬｙｓｙａｎｓｋａｙａの技法を使用して行うことができる。ステップ３（ｇ）は、Ｃａｍｅｎｉｓｃｈ署名およびＬｙｓｙａｎｓｋａｙａ署名を使用して行うことができる。
【０１７９】
Ｄｅｐｏｓｉｔプロトコル
商店Ｍは、硬貨（ｒ１，ｒ２，Ｓ，Ｔ，Ｖ，Ｗ，π）をサブミットすることによって、銀行Ｂに硬貨を預ける。銀行は、証明πを検査し、これが検証されない場合には、銀行は、即座に拒否する。ここで、銀行は、２つの追加検査を行う。
【０１８０】
第１に、Ｂは、硬貨の使用者がその使用者のウォレットを超過して使っていないことを検査する、すなわち、銀行は、同一の通し番号Ｓを有する前に受け入れられたすべての硬貨を検索する。そのような硬貨（ｒ１，ｒ２，Ｓ，Ｔ’，Ｖ’，Ｗ’，π’）が見つかると仮定する。ｒ１＝ｒ１である場合には、Ｂは、その硬貨を受け入れることを拒否する。そうでない場合には、Ｂは、商店からの硬貨を受け入れるが、ここで、二重に使ったユーザを罰しなければならない。
１．Ｂは、
【０１８１】
【数３７】
【０１８２】
を実行する。
２．Ｂは、
【０１８３】
【数３８】
【０１８４】
を含む公開鍵を有する人としてユーザを識別する。
３．Ｂは、
【０１８５】
【数３９】
【０１８６】
を使用して、引き出しプロトコル中に銀行に渡されたｓの暗号化を暗号化解除する。次に、Ｂは、ｓを使用して、そのユーザのウォレット内のすべての硬貨の各硬貨ｊ＝１ ｔｏ ２ｌの通し番号
【０１８７】
【数４０】
【０１８８】
を計算する。実際に、銀行は、
【０１８９】
【数４１】
【０１９０】
を使用して、同一の形ですべてのユーザのウォレットの秘密を暗号化解除し、これらの取引をトレースすることができる。
【０１９１】
第２に、Ｂは、硬貨の使用者が、商店Ｍに関する使用限度を超えていないことを検査する。すなわち、この銀行は、同一のマネー・ロンダリング検査値Ｖｊを有する、以前に受け入れられたすべての硬貨を検索する。そのような硬貨（ｒ１，ｒ２，Ｓ’，Ｔ’，Ｖ，Ｗ’，π’）が見つかると仮定する。この銀行は、預け入れを受け入れるのを拒否し、その商店を罰する。この銀行は、ここで、使用者に責任があるかどうかを判定する。ｒ２＝ｒ２である場合に、Ｂは、商店だけを罰する。そうでない場合には、Ｂは、マネー・ロンダリングを試みたユーザも罰する。
１．Ｂは、
【０１９２】
【数４２】
【０１９３】
を実行する。
２．Ｂは、
【０１９４】
【数４３】
【０１９５】
を含む公開鍵を有する人としてユーザを識別する。
３．Ｂは、
【０１９６】
【数４４】
【０１９７】
を使用して、引き出しプロトコル中に銀行に渡されたｓの暗号化を暗号化解除する。次に、Ｂは、ｓを使用して、そのユーザのウォレット内のすべての硬貨の各硬貨ｊ＝１ ｔｏ ２ｌの通し番号
【０１９８】
【数４５】
【０１９９】
を計算する（実際に、銀行は、
【０２００】
【数４６】
【０２０１】
を使用して、同一の形ですべてのユーザのウォレットの秘密を暗号化解除し、これらの取引をトレースすることができる。
すべての検査に合格する場合に、Ｂは、Ｍの口座内の預け入れに関してこの硬貨を受け入れる。
【０２０２】
預け入れプロトコルは、ＣＨＬ方式の預け入れプロトコルに類似する、すなわち、二重使用の検査だけではなく、銀行は、現在、マネー・ロンダリングについても検査する。したがって、ユーザが正直である場合に、銀行は、前のように１つではなく、２つのデータベース・ルックアップを実行する。
【０２０３】
次では、Ｏｐｅｎ（）アルゴリズムを説明するが、これは、ＣＨＬシステムと同一である。
【０２０４】
【数４７】
【０２０５】
したがって、いくつかの要素ｈ∈Ｇ１および
【０２０６】
【数４８】
【０２０７】
について
【０２０８】
【数４９】
【０２０９】
である場合に、Ｏｐｅｎ（Ｗ１，Ｗ２，ｒ１，ｒ２）＝ｇｘが得られる。
【０２１０】
次では、違反関連プロトコルがどのように働くかを説明する。Ｃ１＝（ｒ１，ｒ２，Ｓ，Ｔ，Ｖ，Ｗ，π）およびＣ２＝（ｒ１，ｒ２，Ｓ’，Ｔ’，Ｖ’，Ｗ’，π’）が、一方は既存の通貨であり、他方は新に預けられる硬貨であるものとする。二重検出またはマネー・ロンダリングの検出には、それぞれＳ１＝Ｓ２またはＶ１＝Ｖ２の検査が用いられる。識別アルゴリズムは、適当な入力に対してＯｐｅｎを実行し、結果の有罪の証明は、Π＝（Ｃ１，Ｃ２）である。違反の検証は、硬貨の妥当性を成功して検査することと、損害賠償を請求された違反を検出することと、Ｏｐｅｎを実行して
【０２１１】
【数５０】
【０２１２】
を入手することと、そのｐｋに対する関係を検査することとが含まれる。１つの違反の漏洩を使用して、そのユーザの硬貨を使うことまたは別の違反を捏造することはできない）。トレース・アルゴリズムには、Ｗｉｔｈｄｒａｗ中にユーザによって署名された暗号化Ｅからｓを回復することと、すべての通し番号を計算することとが含まれる。所有権の証明は、
【０２１３】
【数５１】
【０２１４】
であり、ここで、σは、Ｅに対するユーザの署名である。ある通し番号Ｓに関する所有権の検証は、署名σを検証することと、
【０２１５】
【数５２】
【０２１６】
であることを検査することと、ｓを回復するためにＥを暗号化解除することと、すべての通し番号Ｓｉを計算することと、すべてのｉについてＳ＝Ｓｉであるかどうかをテストすることとが含まれる。
【０２１７】
システム違反者に関する処罰の軽減
システム違反者に関する処罰をより寛大にするために、または単にシステムをより効率的にするために、２つの他のオプションが使用可能である。
オプション（１）：違反が検出され、ユーザのアイデンティティが明らかにされる。このシステムは、Ｗｉｔｈｄｒａｗプロトコル中に、ユーザがウォレット秘密ｓの検証可能な暗号化を銀行に与えないことを除いて、上と同様に動作する。次に、後に、Ｄｅｐｏｓｉｔプロトコル中に、銀行は、それでも、違反を検出し、ユーザを識別することができるが、このユーザを含む他の取引の通し番号を計算することはできない。
オプション（２）：違反が検出される。このシステムは、Ｓｐｅｎｄプロトコル中に、ユーザが商店にマネー・ロンダリング検査値Ｖｊを与えないことを除いて、オプション（１）のシステムと同様に動作する。次に、後に、Ｄｅｐｏｓｉｔプロトコル中に、銀行は、それでも、違反を検出することができるが、ユーザを識別することはできない。
【０２１８】
効率の考慮事項
プロトコル効率の表示として、いくつかの数字を述べる。たとえば、ユーザが、コミットメントを作るために１４回の複数の底の指数を計算しなければならず、証明のためにさらに２０回計算しなければならなくなるようにＳｐｅｎｄを構成することができる。この例では、商店および銀行は、硬貨が有効であることを検査するために、２０回の複数の底の指数を行う必要がある。本プロトコルは、ユーザと商店との間の２ラウンドの通信、ならびに銀行と商店との間の１ラウンドの通信をもたらす。上のオプション（２）を採用する場合に、コミットメントを作るために１３回の複数の底の指数と、証明のためにさらに１８回になる。銀行および商店による検証は、８回の複数の底の指数を要する。
【０２１９】
セキュリティの証明
限界のある匿名性ビジネス・モデルでは、本方式は、ランダム・オラクル・モデルでの強いＲＳＡ仮定、ｙ−ＤＤＨＩ仮定、およびＸＤＨ仮定またはＳｕｍ−Ｆｒｅｅ ＤＤＨ仮定のいずれかの下で、正しさ、バランス、ユーザの匿名性、違反者の識別、違反者のトレース、および強い無罪証明可能性を達成する。
【０２２０】
スペースの制限に起因して、いくつかの高水準直観を、証明の梗概と一緒に提供する。ＣＨＬの３つの主な観察がある。これらは、二重使用を超えた違反を防ぐために、特にＰＲＦの出力を商店にリンクするためのＰＲＦの注意深い使用を介して拡張することができる。
【０２２１】
バランス：ウォレットごとに、ｓは、硬貨の有効な通し番号とすることができる正確にＮ個の値を決定論的に定義する。ウォレットを超過して使うために、ユーザは、１つの通し番号を２回使用することができるが、その場合に、このユーザは、識別可能であり、あるいは、ユーザは、ＣＬ署名を偽造するか、ＺＫ証明を捏造することができる。
【０２２２】
ユーザの匿名性：硬貨は、ゼロ知識なので何も漏らさない妥当性の（非対話的ゼロ知識）証明と一緒に、擬似ランダムであり、したがって、やはりユーザに関する情報を漏らさない４つの値（Ｓ、Ｔ、Ｖ、Ｗ）からなる。
【０２２３】
ここでの唯一の異常は、ＶおよびＷを計算する時に、ＰＲＦに使用される底が、商店のアイデンティティのハッシュである（ＳおよびＴの計算に使用される固定された底ではなく）ことである。ハッシュＨをランダム・オラクルとして扱うことによって、
【０２２４】
【数５３】
【０２２５】
を与えられれば、すべての他の入力に対する
【０２２６】
【数５４】
【０２２７】
、特にｉｄＭ≠ｉｄＭの
【０２２８】
【数５５】
【０２２９】
の出力が、ランダムから区別不能であることがわかる。具体的に言うと、
【０２３０】
【数５６】
【０２３１】
を与えられた敵対者が、Ｈ（ｉｄＭ）１／（ｖ＋ｊ）を、あるランダムな固定されたＨ（ｉｄＭ）およびＨ（ｉｄＭ）についてランダムから区別できる場合に、これは、ＤＤＨを解いている。
【０２３２】
無罪証明可能性：第１に、正直なユーザを、そのユーザが犯していない犯罪について有罪と証明することはできない。というのは、有罪の証明に、ユーザの秘密値
【０２３３】
【数５７】
【０２３４】
が含まれるからである。ユーザが正直である場合には、そのユーザだけがこの値を知っている。第２に、不正を働くユーザであっても、そのユーザが犯していない犯罪について有罪と証明することはできない。たとえば、１つの硬貨の二重使用は、２０個の硬貨のマネー・ロンダリングの偽の証明を可能にしない。というのは、（１）罪が、硬貨自体から公に検証可能であり、（２）ｘの知識が硬貨を作成するためのｄであるからである。違反によって漏らされる値
【０２３５】
【数５８】
【０２３６】
の値は、そのユーザのウォレットから硬貨を使うのには十分でない。
【０２３７】
下では、証明の概要を、上で輪郭を示した定義に基づいて示す。
【０２３８】
正しさ：正直な当事者が本プロトコルに従う場合に、誰もエラー・メッセージを出力しないことを検証することができる。
【０２３９】
バランス：Ａが、銀行として働くエクストラクタＥとのｎ回のＷｉｔｈｄｒａｗプロトコルを実行する敵対者であるものとする。各Ｗｉｔｈｄｒａｗ中に、Ｅは、Ａが（ｘ，ｓ，ｔ，ｖ，ｗ）の知識の証明を与える時にＥがこれらの値を抽出することを除いて、正確に、正直な銀行が行う通りに動作する。ｓから、Ｅは、Ａがそのウォレットについて計算できるすべての正当な通し番号を特定の確率で計算することができる。Ｌが、すべてのウォレットからのすべての通し番号の集合を表すものとする。ここで、Ａが、通し番号
【０２４０】
【数５９】
【０２４１】
を有する硬貨を正直な銀行に受け入れさせることができると仮定する。その場合に、Ａは、妥当性の偽の証明をでっち上げたことになるが、これは、無視できる確率で発生する。
【０２４２】
ユーザの匿名性：匿名性のＣＨＬ定義は、ユーザのウォレット、秘密鍵、またはユーザの公開鍵にさえアクセスせずにＳｐｅｎｄプロトコルのユーザの側を成功して実行できるシミュレータＳをもたらす。Ｓが商店Ｍで硬貨を使うことを望み、ウォレット・サイズがＮであり、Ｍの匿名使用限度がＭであると仮定する。Ｓは、ランダムな値（ｘ，ｓ，ｔ，ｖ，ｗ）を選択し、１≦ｉ≦Ｎであり、１≦ｊＭ≦Ｍである。次に、Ｓは、正直なユーザが行うのと正確に同一に、硬貨通し番号
【０２４３】
【数６０】
【０２４４】
と、商店レコード・ロケータ
【０２４５】
【数６１】
【０２４６】
と、検査値
【０２４７】
【数６２】
【０２４８】
とを作成する。これらの値は、擬似ランダムなので、実際の通貨から区別不能である。Ｓは、（Ｓ、Ｔ、Ｖ、Ｗ）がきちんと形成されていることと、ｉおよびｊＭが適当な範囲内にあることを証明することができる。Ｓが捏造する可能性がある証明の唯一の部分は、Ｓが（ｘ，ｓ，ｔ，ｖ，ｗ）に対する銀行からの署名を有することである。ここで、Ｓは、このステップに関する適当なＣＬシミュレータを呼び出し、このＣＬシミュレータは、ランダム・オラクルの制御を要求する。
【０２４９】
違反者の識別：バランスで説明したように、エクストラクタＥは、敵対者Ａと複数回のＳｐｅｎｄプロトコルを実行し、高い確率で（ｘ，ｓ，ｔ，ｖ，ｗ）を抽出する。ウォレットごとに、Ｅは、１≦ｉ≦Ｎのすべての有効な硬貨通し番号
【０２５０】
【数６３】
【０２５１】
と、１≦ｊＭ≦Ｍおよびいくつかの商店Ｍについてすべての有効な商店レコード・ロケータ
【０２５２】
【数６４】
【０２５３】
とを計算することができる。ここで、Ａが、同一の通し番号Ｓ１＝Ｓ２を有する２つの硬貨Ｃ１＝（Ｓ１，Ｔ１，Ｖ１，Ｗ１，π１，ｒ１，ｒ１）およびＣ２＝（Ｓ２，Ｔ２，Ｖ２，Ｗ２，π２，ｒ２，ｒ２）または同一の商店レコード・ロケータＶ１＝Ｖ２を有する２つの硬貨を正直な銀行に受け入れさせることができると仮定する。これらの衝突が発生するために、硬貨は、同一のウォレット（ｘ，ｓ，ｔ，ｖ，ｗ）から発し、同一のｉまたは同一の（ｉｄＭ，ｊＭ）のいずれかを有し、きちんと形成される。そうでなければ、ユーザが、妥当性の証明を偽造している。その場合に、特定の確率で
【０２５４】
【数６５】
【０２５５】
または
【０２５６】
【数６６】
【０２５７】
のいずれかであり、これによって、ユーザのアイデンティティが明らかにされる。
【０２５８】
違反ｉ＝１（二重使用）の有罪の証明Πは、有効な硬貨（Ｃ１，Ｃ２）である。誰もが、
【０２５９】
【数６７】
【０２６０】
であることと、ｐｋ
【０２６１】
【数６８】
【０２６２】
に対応する
【０２６３】
【数６９】
【０２６４】
とを検査することができる。同様に、違反ｉ＝２（特定の商店に関する匿名ビジネス限界を超えること）の有罪の証明は、Ｖ１＝Ｖ２であり、
【０２６５】
【数７０】
【０２６６】
であり、
【０２６７】
【数７１】
【０２６８】
がｐｋに対応する、有効な硬貨（Ｃ１，Ｃ２）である。
【０２６９】
１つの専門事項は、２つのウォレット種ｓ、ｓ’が、｜ｓ−ｓ’｜＜２ｌ＝Ｎになっており、したがって、これらのウォレットが、少なくとも１つの通し番号でオーバーラップする場合に何が起きるかである。同一の通し番号が、両方のウォレットから使われる場合に、銀行は、二重に使われたものとしてこれらにフラグを立てるが、それでも、識別アルゴリズムは動作しない。というのは、二重使用が実際には発生していないからである。これは銀行を混乱させる可能性があるので、この問題を、銀行にウォレットごとのｓの選択にランダムさを与えさせることによって回避することができる。ｓ、ｓ’がＺｑからランダムに引き出されるときに、それらがオーバーラップする可能性は、２ｌ＋１／ｑである。
【０２７０】
違反者のトレース：Ｗｉｔｈｄｒａｗ中に、各ユーザは、そのユーザ自身の鍵
【０２７１】
【数７２】
【０２７２】
が暗号化解除に十分になるように、そのユーザのウォレット秘密ｓの検証可能な暗号化Ｅを銀行に渡すように求められる。ユーザは、この暗号化に署名するようにも求められる。違反者の識別プロパティによって、システム違反は、銀行が
【０２７３】
【数７３】
【０２７４】
を回復することを可能にすると推論することができる。検証可能な暗号化の完全性によって、不正を働くユーザに属する各ウォレットを、
【０２７５】
【数７４】
【０２７６】
を使用して、高い確率で開いて、ウォレット種ｓを回復し、１≦ｉ≦Ｎのすべての通し番号
【０２７７】
【数７５】
【０２７８】
を計算することができる。
【０２７９】
通し番号Ｓを有するある硬貨の所有権の証明Γは、暗号化Ｅ、暗号化解除鍵
【０２８０】
【数７６】
【０２８１】
、およびＥに対する署名からなる。検証者は、まず、
【０２８２】
【数７７】
【０２８３】
がｐｋに対応することと、Ｅに対する署名が有効であることを検査しなければならない。次に、検証者は、Ｅを暗号化解除してｓを回復し、１≦ｉ≦Ｎのすべての通し番号
【０２８４】
【数７８】
【０２８５】
を計算し、いくつかのｉについてＳ＝Ｓｉであることをテストすることができる。
【０２８６】
強い無罪証明可能性：強い無罪証明可能性は、２つの部分を有する。第１に、正直なユーザと対話する敵対者は、ｐｋを有するユーザが違反ｉについて有罪でない限り、ＶｅｒｉｆｙＶｉｏｌａｔｉｏｎ（ｉ）（ｐａｒａｍｓ，Ｓ，Ｖ，Π）が受け入れるように値（ｉ，Ｓ，Ｖ，Π）を作ることはできない。
【０２８７】
証明Πは、
【０２８８】
【数７９】
【０２８９】
を明らかにする２つの有効な硬貨（Ｃ１，Ｃ２）からなる。
【０２９０】
【数８０】
【０２９１】
は秘密情報なので、これを公開することは、そのユーザがある違反を犯したことを知らせる。そのユーザが間近な特定の違反（以前の違反ではなく）の責任がある理由は、ｘ（単純に
【０２９２】
【数８１】
【０２９３】
ではなく）の知識が、有効な硬貨を作成するのに必要になることである。
【０２９４】
第２部分は、敵対者が、ユーザにシステム条件を違反することを強制した後であっても、通し番号Ｓを有する通貨がｐｋを有するユーザに実際に属さない限り、ＶｅｒｉｆｙＯｗｎｅｒｓｈｉｐ（ｐａｒａｍｓ，ｐｋ，Ｓ，Γ）が受け入れるように（ｉ，Ｓ，Γ）を作ることができないことである。証明Γは、暗号化Ｅ、ユーザの署名σ、および暗号化解除鍵
【０２９５】
【数８２】
【０２９６】
からなる。ユーザによって署名されたすべての暗号化は、ある平文ｓに高い確率で対応し、この平文ｓは、そのユーザに属するすべての通し番号を計算することを可能にする。したがって、敵対者は、勝つためにはある新しい暗号化に対するユーザの署名を偽造しなければならないはずであり、これは、無視できる確率で発生すると考えられる。
【０２９７】
上で提示した詳細な説明は、電子決済システムに言及するが、限界のある匿名性に関連する類似する問題は、本発明的方法によって対処し、解決することができる。具体的に言うと、エミッタに、証明書ベースのシステム上の異なるアクセプタへの限られた回数の匿名アクセスを許可するすべてのシステムを、本発明的方法に基づいて実施することができる。そのようなシステムの例に、プリンタ・クォータ・システム、電子投票システム、および他の電子政府サービスを含めることができるが、これらに限定はされない。
【０２９８】
ＣＨＬシステムのほかに、電子マネー・ロンダリングを防ぐために、他の基礎になる電子決済システムを機能強化することができる。類似する形で拡張できるもう１つの電子決済システムの例が、Stefan Brandsによる論文、"Untraceable Off-Line Cash in Wallets withObservers", published in CRYPTO '93, Vol. 773 of LNCS, page 302, 1994に記載されている。
【図面の簡単な説明】
【０２９９】
【図１】本発明の実施形態による、組み合わされた銀行およびバリデータ・コンピュータ・システムと、ユーザ・コンピュータ・システムと、商店コンピュータ・システムとを含む電子決済システムを示す図である。
【図２】本発明の実施形態による方法を示す流れ図の一部である。
【図３】本発明の実施形態による方法を示す流れ図の一部である。
【図４】本発明の実施形態による方法を示す流れ図の一部である。
【図５】本発明の実施形態による方法を示す流れ図の一部である。
【符号の説明】
【０３００】
１００ 電子決済システム
１０１ 組み合わされた銀行およびバリデータ・コンピュータ・システム
１０２ ユーザ・コンピュータ・システム
１０３ 商店コンピュータ・システム
１０４ データ・ネットワーク
２００ 第１の２当事者プロトコル
２０１ パラメータをセット・アップするステップ
２０２ 発行者鍵（ｐｋＢ，ｓｋＢ）を生成するステップ
２０３ エミッタ鍵（ｐｋＵ，ｓｋＵ）を生成するステップ
２０４ ランダムな値ｓ、ｔを生成するステップ
２０５ （ｓｋＵ，ｓ，ｔ）に対する署名σを生成するステップ
２０６ 証明書Ｓ（ｓ，ｔ，ｓ）を保管するステップ
２１０ 第２の２当事者プロトコル
２１１ 取引限度ＮＭを検査し、ｉ，ｊを判定するステップ
２１２ 取引チャレンジ値（ｒ１，ｒ２）を生成するステップ
２１３ ウォレット検査Ｔｉおよび検査値Ｖｊを計算するステップ
２１４ 証明書Ｓｉおよび検査値Ｔｉ，Ｖｊを送信するステップ
２１５ （ｉ，ｊ，ｓｋＵ，ｓ，σ）の知識の証明πを生成するステップ
２１６ 証明πを検証するステップ
２２０ 妥当性検査手順の第１部分
２２１ 証明書ｒ１，ｒ２，Ｓｉ，Ｔｉ，Ｖｊ、および証明πをサブミットするステップ
２２２ 証明πを検証するステップ
２２３ Ｓｉが一意であるかどうかを判定するステップ
２２５ 証明書Ｓを拒否するステップ
２２６ エミッタｐｋＵを識別するステップ
２２７ エミッタｐｋＵのウォレット秘密ｓを暗号化解除するステップ
２２８ ｓに基づいて他のＳを計算するステップ
２３０ 第２部分
２３１ 検査値Ｖｊを検証するステップ
２３２ Ｖｊが一意かどうかを判定するステップ
２３３ 証明書Ｓを受け入れるステップ
２３４ ｒ２＝ｒ２’かどうかを判定するステップ
２３５ 証明書Ｓを拒否するステップ
２３６ エミッタｐｋＵを識別するステップ
２３７ エミッタｐｋＵのウォレット秘密ｓを暗号化解除するステップ
２３８ ｓに基づいて他のＳを計算するステップ
Ｂ 銀行
Ｄ データベース
ｅ 双一次写像
Ｈ１ ハッシュ関数
Ｈ２ ハッシュ関数
ｉｄＭ 一意のアイデンティティ
ｋ セキュリティ・パラメータ
ｌ ウォレット・サイズ
Ｌ データベース
Ｍ 商店
ＮＭ 取引に対する限度
ｐｋＢ 署名鍵
ｐｋＵ エミッタ鍵
ｒ１ 取引チャレンジ値
ｒ２ 取引チャレンジ値
Ｓ 証明書
Ｓｉ 通し番号
ｓｋＵ エミッタ鍵
ｓｋＢ 署名鍵
ｓ ウォレット秘密
ｔ ウォレット秘密
Ｕ ユーザ
Ｖｊ マネー・ロンダリング検査値
Ｔｉ ウォレット検査値
σ 署名
π 証明
【特許請求の範囲】
【請求項１】
署名鍵（ｐｋＢ，ｓｋＢ）を有する発行者と、エミッタ鍵（ｐｋＵ，ｓｋＵ）を有するエミッタと、一意のアイデンティティ（ｉｄＭ）および取引に対する限度（ＮＭ）を有するアクセプタと、バリデータとの間の取引を自動的に妥当性検査する方法であって、
前記エミッタによって前記発行者から証明書（Ｓ）を回収するステップであって、前記証明書（Ｓ）が、前記発行者の前記署名鍵（ｐｋＢ，ｓｋＢ）および前記エミッタの前記エミッタ鍵（ｐｋＵ，ｓｋＵ）に基づいて前記発行者と前記エミッタとの間の第１の２当事者プロトコルを使用して計算される、ステップと、
前記エミッタによって前記アクセプタで前記証明書（Ｓ）を使うステップであって、マネー・ロンダリング検査値（Ｖｊ）が、前記証明書（Ｓ）、前記エミッタと前記アクセプタとの間の取引番号（ｊ）、前記アクセプタによって生成される取引チャレンジ値（ｒ１，ｒ２）、および前記アクセプタの前記一意のアイデンティティ（ｉｄＭ）に基づいて前記エミッタと前記アクセプタとの間の第２の２当事者プロトコルを使用して計算される、ステップと、
前記アクセプタによって前記バリデータに前記証明書（Ｓ）、前記取引チャレンジ値（ｒ１，ｒ２）、および前記マネー・ロンダリング検査値（Ｖｊ）を預けるステップと、
前記マネー・ロンダリング検査値（Ｖｊ）をより以前の取引で前記バリデータに既に預けられたマネー・ロンダリング検査値（Ｖｊ’）と比較することによって、前記エミッタと前記アクセプタとの間の取引の回数が前記アクセプタの取引に対する前記限度（ＮＭ）未満であることを検証することによって、前記バリデータによって前記取引を妥当性検査するステップと、
を含む方法。
【請求項２】
使う前記ステップで、知識の証明（π）が、前記エミッタによって計算され、前記アクセプタに送信され、
預ける前記ステップで、前記証明（π）が、前記バリデータに預けられ、
妥当性検査する前記ステップが、さらに、前記証明（π）が、前記アクセプタの前記一意のアイデンティティ（ｉｄＭ）、前記証明書（Ｓ）、および前記マネー・ロンダリング検査値（Ｖｊ）に関して有効であることを検証するステップを含む
請求項１に記載の方法。
【請求項３】
妥当性検査する前記ステップで、前記バリデータが、証明（π）が前記アクセプタの取引に対する前記限度（ＮＭ）に基づいて計算されたことを検証する
請求項２に記載の方法。
【請求項４】
前記バリデータが、より以前の取引で前記バリデータに預けられたマネー・ロンダリング検査値（Ｖｊ’）が現在の取引の前記マネー・ロンダリング検査値（Ｖｊ）と等しいことを検出する場合に、妥当性検査する前記ステップが、さらに、
前記証明書（Ｓ）を拒否するステップと、
前記より以前の取引で使用された取引チャレンジ値（ｒ２’）および証明書（Ｓ’）を取り出すステップと
を含み、前記より以前の取引で使用された取引チャレンジ値（ｒ２’）と前記取引チャレンジ値（ｒ２）とが異なる場合に、前記エミッタのアイデンティティ（ｐｋＵ）が、前記より以前の取引および前記現在の取引で使用される前記証明書（Ｓ，Ｓ’）に基づいて前記バリデータによって計算される
請求項１ないし３のいずれか一項に記載の方法。
【請求項５】
妥当性検査する前記ステップで、前記バリデータが、前記証明書（Ｓ）をより以前の取引で預けられた証明書（Ｓ’）と比較し、
前記発行者が、より以前の取引で前記バリデータに預けられた証明書（Ｓ’）が現在の取引の前記証明書（Ｓ）と等しいことを検出する場合に、妥当性検査する前記ステップが、さらに、
前記より以前の取引で使用された取引チャレンジ値（ｒ１’）を取り出すステップと、
前記より以前の取引で使用された前記取引チャレンジ値（ｒ１’）と前記取引チャレンジ値（ｒ１）とが等しい場合に、前記証明書（Ｓ）が前記バリデータによって拒否されるステップと、
前記より以前の取引で使用された前記取引チャレンジ値（ｒ１’）と前記取引チャレンジ値（ｒ１）とが異なる場合に、前記エミッタのアイデンティティ（ｐｋＵ）が、前記より以前の取引および現在の取引で使用される証明書（Ｓ，Ｓ’）に基づいて前記バリデータによって計算されるステップと
を含む、請求項１ないし４のいずれか一項に記載の方法。
【請求項６】
回収する前記ステップで、前記エミッタが、ウォレット秘密（ｓ）の知識の証明を前記発行者に提供し、前記証明書（Ｓ）が、前記ウォレット秘密（ｓ）に基づき、
使う前記ステップで、ウォレット検査値（Ｔｉ）が、計算され、前記アクセプタに転送され、
預ける前記ステップで、ウォレット検査値（Ｔｉ）が、前記バリデータに預けられ、
妥当性検査する前記ステップで、前記証明書（Ｓ）または前記マネー・ロンダリング検査値（Ｖｊ）がより以前の取引で前記バリデータに預けられ、現在の取引の前記取引チャレンジ値（ｒ１，ｒ２）が前記より以前の取引で使用された前記取引チャレンジ値（ｒ１’，ｒ２’）と等しいことを前記発行者が検出する場合に、現在の取引およびより以前の取引のウォレット検査値（Ｔｉ，Ｔｉ’）に基づいて、前記エミッタの前記ウォレット秘密（ｓ）が、前記バリデータによって計算される
請求項４または５に記載の方法。
【請求項７】
使う前記ステップで、前記アクセプタが、前記取引番号（ｊ）が取引に対する前記限度（ＮＭ）未満であることを検証し、前記取引番号（ｊ）が取引に対する前記限度（ＮＭ）を超える場合に前記取引を中止する
請求項１ないし６のいずれか一項に記載の方法。
【請求項８】
所定の額面金額の硬貨を発行する銀行コンピュータ・システムと、前記硬貨を発するユーザ・コンピュータ・システムと、前記硬貨を受け入れる商店コンピュータ・システムと、バリデータ・コンピュータ・システムとを含む、前記硬貨を妥当性検査する電子決済システムであって、前記銀行コンピュータ・システムと、前記ユーザ・コンピュータ・システムと、前記商店コンピュータ・システムと、前記バリデータ・コンピュータ・システムとが、データ・ネットワークによって機能的に接続され、前記硬貨が、請求項１ないし７のいずれか一項に記載の方法に従って引き出され、発せられ、預けられ、妥当性検査される、電子決済システム。
【請求項９】
コンピュータ・システムの少なくとも１つのプロセッサによって実行可能なプログラム命令を含むコンピュータ・プログラムであって、前記少なくとも１つのプロセッサによる前記プログラム命令の実行時に、請求項１ないし７のいずれか一項に記載の方法による前記発行者、前記エミッタ、前記アクセプタ、または前記バリデータのすべてのステップが実行される、コンピュータ・プログラム。
【請求項１０】
コンピュータ・システムの少なくとも１つのプロセッサによって実行可能なプログラム命令を含むコンピュータ可読媒体を含むコンピュータ・プログラム製品であって、前記少なくとも１つのプロセッサによる前記プログラム命令の実行時に、請求項１ないし７のいずれか一項に記載の方法による前記発行者、前記エミッタ、前記アクセプタ、または前記バリデータのすべてのステップが実行される、コンピュータ・プログラム製品。
【請求項１１】
証明書（Ｓ）、具体的には硬貨をエミッタに発行する発行システムであって、
前記発行者の署名鍵（ｐｋＢ，ｓｋＢ）および前記エミッタのエミッタ鍵（ｐｋＵ，ｓｋＵ）に基づいて前記発行者と前記エミッタとの間の第１の２当事者プロトコルを使用して前記証明書（Ｓ）を計算する
ために提供される、発行システム。
【請求項１２】
証明書（Ｓ）、具体的には硬貨をエミッタから受け入れるアクセプタであって、前記証明書（Ｓ）が、発行者の署名鍵（ｐｋＢ，ｓｋＢ）および前記エミッタのエミッタ鍵（ｐｋＵ，ｓｋＵ）に基づいて前記発行者と前記エミッタとの間の第１の２当事者プロトコルを使用して計算され、
前記証明書（Ｓ）、前記エミッタと前記アクセプタとの間の取引番号（ｊ）、前記アクセプタによって生成される取引チャレンジ値（ｒ１，ｒ２）、および前記アクセプタの一意のアイデンティティ（ｉｄＭ）に基づいて、前記エミッタと前記アクセプタとの間の第２の２当事者プロトコルを使用してマネー・ロンダリング検査値（Ｖｊ）を計算し、
前記証明書（Ｓ）、前記取引チャレンジ値（ｒ１，ｒ２）、および前記マネー・ロンダリング検査値（Ｖｊ）をバリデータに預ける
ために設けられる、アクセプタ。
【請求項１３】
署名鍵（ｐｋＢ，ｓｋＢ）を有する発行者と、エミッタ鍵（ｐｋＵ，ｓｋＵ）を有するエミッタと、一意のアイデンティティ（ｉｄＭ）および取引に対する限度（ＮＭ）を有するアクセプタと、バリデータとの間の取引を妥当性検査するバリデータであって、
マネー・ロンダリング検査値（Ｖｊ）をより以前の取引で前記バリデータに既に預けられたマネー・ロンダリング検査値（Ｖｊ’）と比較することによって、前記エミッタと前記アクセプタとの間の取引の回数が前記アクセプタの取引に対する前記限度（ＮＭ）未満であることを検証する
ために設けられる、バリデータ。
【請求項１４】
エミッタであって、
−発行者から証明書（Ｓ）を回収するためであって、前記証明書（Ｓ）が、前記発行者の署名鍵（ｐｋＢ，ｓｋＢ）および前記エミッタのエミッタ鍵（ｐｋＵ，ｓｋＵ）に基づいて前記発行者と前記エミッタとの間の第１の２当事者プロトコルを使用して計算される、回収するため、および
アクセプタで前記証明書（Ｓ）を使うためであって、マネー・ロンダリング検査値（Ｖｊ）が、前記証明書（Ｓ）、前記エミッタと前記アクセプタとの間の取引番号（ｊ）、前記アクセプタによって生成される取引チャレンジ値（ｒ１，ｒ２）、およびアクセプタの一意のアイデンティティ（ｉｄＭ）に基づいてエミッタとアクセプタとの間の第２の２当事者プロトコルを使用して計算される、使うため
に設けられる、エミッタ。
【請求項１】
署名鍵（ｐｋＢ，ｓｋＢ）を有する発行者と、エミッタ鍵（ｐｋＵ，ｓｋＵ）を有するエミッタと、一意のアイデンティティ（ｉｄＭ）および取引に対する限度（ＮＭ）を有するアクセプタと、バリデータとの間の取引を自動的に妥当性検査する方法であって、
前記エミッタによって前記発行者から証明書（Ｓ）を回収するステップであって、前記証明書（Ｓ）が、前記発行者の前記署名鍵（ｐｋＢ，ｓｋＢ）および前記エミッタの前記エミッタ鍵（ｐｋＵ，ｓｋＵ）に基づいて前記発行者と前記エミッタとの間の第１の２当事者プロトコルを使用して計算される、ステップと、
前記エミッタによって前記アクセプタで前記証明書（Ｓ）を使うステップであって、マネー・ロンダリング検査値（Ｖｊ）が、前記証明書（Ｓ）、前記エミッタと前記アクセプタとの間の取引番号（ｊ）、前記アクセプタによって生成される取引チャレンジ値（ｒ１，ｒ２）、および前記アクセプタの前記一意のアイデンティティ（ｉｄＭ）に基づいて前記エミッタと前記アクセプタとの間の第２の２当事者プロトコルを使用して計算される、ステップと、
前記アクセプタによって前記バリデータに前記証明書（Ｓ）、前記取引チャレンジ値（ｒ１，ｒ２）、および前記マネー・ロンダリング検査値（Ｖｊ）を預けるステップと、
前記マネー・ロンダリング検査値（Ｖｊ）をより以前の取引で前記バリデータに既に預けられたマネー・ロンダリング検査値（Ｖｊ’）と比較することによって、前記エミッタと前記アクセプタとの間の取引の回数が前記アクセプタの取引に対する前記限度（ＮＭ）未満であることを検証することによって、前記バリデータによって前記取引を妥当性検査するステップと、
を含む方法。
【請求項２】
使う前記ステップで、知識の証明（π）が、前記エミッタによって計算され、前記アクセプタに送信され、
預ける前記ステップで、前記証明（π）が、前記バリデータに預けられ、
妥当性検査する前記ステップが、さらに、前記証明（π）が、前記アクセプタの前記一意のアイデンティティ（ｉｄＭ）、前記証明書（Ｓ）、および前記マネー・ロンダリング検査値（Ｖｊ）に関して有効であることを検証するステップを含む
請求項１に記載の方法。
【請求項３】
妥当性検査する前記ステップで、前記バリデータが、証明（π）が前記アクセプタの取引に対する前記限度（ＮＭ）に基づいて計算されたことを検証する
請求項２に記載の方法。
【請求項４】
前記バリデータが、より以前の取引で前記バリデータに預けられたマネー・ロンダリング検査値（Ｖｊ’）が現在の取引の前記マネー・ロンダリング検査値（Ｖｊ）と等しいことを検出する場合に、妥当性検査する前記ステップが、さらに、
前記証明書（Ｓ）を拒否するステップと、
前記より以前の取引で使用された取引チャレンジ値（ｒ２’）および証明書（Ｓ’）を取り出すステップと
を含み、前記より以前の取引で使用された取引チャレンジ値（ｒ２’）と前記取引チャレンジ値（ｒ２）とが異なる場合に、前記エミッタのアイデンティティ（ｐｋＵ）が、前記より以前の取引および前記現在の取引で使用される前記証明書（Ｓ，Ｓ’）に基づいて前記バリデータによって計算される
請求項１ないし３のいずれか一項に記載の方法。
【請求項５】
妥当性検査する前記ステップで、前記バリデータが、前記証明書（Ｓ）をより以前の取引で預けられた証明書（Ｓ’）と比較し、
前記発行者が、より以前の取引で前記バリデータに預けられた証明書（Ｓ’）が現在の取引の前記証明書（Ｓ）と等しいことを検出する場合に、妥当性検査する前記ステップが、さらに、
前記より以前の取引で使用された取引チャレンジ値（ｒ１’）を取り出すステップと、
前記より以前の取引で使用された前記取引チャレンジ値（ｒ１’）と前記取引チャレンジ値（ｒ１）とが等しい場合に、前記証明書（Ｓ）が前記バリデータによって拒否されるステップと、
前記より以前の取引で使用された前記取引チャレンジ値（ｒ１’）と前記取引チャレンジ値（ｒ１）とが異なる場合に、前記エミッタのアイデンティティ（ｐｋＵ）が、前記より以前の取引および現在の取引で使用される証明書（Ｓ，Ｓ’）に基づいて前記バリデータによって計算されるステップと
を含む、請求項１ないし４のいずれか一項に記載の方法。
【請求項６】
回収する前記ステップで、前記エミッタが、ウォレット秘密（ｓ）の知識の証明を前記発行者に提供し、前記証明書（Ｓ）が、前記ウォレット秘密（ｓ）に基づき、
使う前記ステップで、ウォレット検査値（Ｔｉ）が、計算され、前記アクセプタに転送され、
預ける前記ステップで、ウォレット検査値（Ｔｉ）が、前記バリデータに預けられ、
妥当性検査する前記ステップで、前記証明書（Ｓ）または前記マネー・ロンダリング検査値（Ｖｊ）がより以前の取引で前記バリデータに預けられ、現在の取引の前記取引チャレンジ値（ｒ１，ｒ２）が前記より以前の取引で使用された前記取引チャレンジ値（ｒ１’，ｒ２’）と等しいことを前記発行者が検出する場合に、現在の取引およびより以前の取引のウォレット検査値（Ｔｉ，Ｔｉ’）に基づいて、前記エミッタの前記ウォレット秘密（ｓ）が、前記バリデータによって計算される
請求項４または５に記載の方法。
【請求項７】
使う前記ステップで、前記アクセプタが、前記取引番号（ｊ）が取引に対する前記限度（ＮＭ）未満であることを検証し、前記取引番号（ｊ）が取引に対する前記限度（ＮＭ）を超える場合に前記取引を中止する
請求項１ないし６のいずれか一項に記載の方法。
【請求項８】
所定の額面金額の硬貨を発行する銀行コンピュータ・システムと、前記硬貨を発するユーザ・コンピュータ・システムと、前記硬貨を受け入れる商店コンピュータ・システムと、バリデータ・コンピュータ・システムとを含む、前記硬貨を妥当性検査する電子決済システムであって、前記銀行コンピュータ・システムと、前記ユーザ・コンピュータ・システムと、前記商店コンピュータ・システムと、前記バリデータ・コンピュータ・システムとが、データ・ネットワークによって機能的に接続され、前記硬貨が、請求項１ないし７のいずれか一項に記載の方法に従って引き出され、発せられ、預けられ、妥当性検査される、電子決済システム。
【請求項９】
コンピュータ・システムの少なくとも１つのプロセッサによって実行可能なプログラム命令を含むコンピュータ・プログラムであって、前記少なくとも１つのプロセッサによる前記プログラム命令の実行時に、請求項１ないし７のいずれか一項に記載の方法による前記発行者、前記エミッタ、前記アクセプタ、または前記バリデータのすべてのステップが実行される、コンピュータ・プログラム。
【請求項１０】
コンピュータ・システムの少なくとも１つのプロセッサによって実行可能なプログラム命令を含むコンピュータ可読媒体を含むコンピュータ・プログラム製品であって、前記少なくとも１つのプロセッサによる前記プログラム命令の実行時に、請求項１ないし７のいずれか一項に記載の方法による前記発行者、前記エミッタ、前記アクセプタ、または前記バリデータのすべてのステップが実行される、コンピュータ・プログラム製品。
【請求項１１】
証明書（Ｓ）、具体的には硬貨をエミッタに発行する発行システムであって、
前記発行者の署名鍵（ｐｋＢ，ｓｋＢ）および前記エミッタのエミッタ鍵（ｐｋＵ，ｓｋＵ）に基づいて前記発行者と前記エミッタとの間の第１の２当事者プロトコルを使用して前記証明書（Ｓ）を計算する
ために提供される、発行システム。
【請求項１２】
証明書（Ｓ）、具体的には硬貨をエミッタから受け入れるアクセプタであって、前記証明書（Ｓ）が、発行者の署名鍵（ｐｋＢ，ｓｋＢ）および前記エミッタのエミッタ鍵（ｐｋＵ，ｓｋＵ）に基づいて前記発行者と前記エミッタとの間の第１の２当事者プロトコルを使用して計算され、
前記証明書（Ｓ）、前記エミッタと前記アクセプタとの間の取引番号（ｊ）、前記アクセプタによって生成される取引チャレンジ値（ｒ１，ｒ２）、および前記アクセプタの一意のアイデンティティ（ｉｄＭ）に基づいて、前記エミッタと前記アクセプタとの間の第２の２当事者プロトコルを使用してマネー・ロンダリング検査値（Ｖｊ）を計算し、
前記証明書（Ｓ）、前記取引チャレンジ値（ｒ１，ｒ２）、および前記マネー・ロンダリング検査値（Ｖｊ）をバリデータに預ける
ために設けられる、アクセプタ。
【請求項１３】
署名鍵（ｐｋＢ，ｓｋＢ）を有する発行者と、エミッタ鍵（ｐｋＵ，ｓｋＵ）を有するエミッタと、一意のアイデンティティ（ｉｄＭ）および取引に対する限度（ＮＭ）を有するアクセプタと、バリデータとの間の取引を妥当性検査するバリデータであって、
マネー・ロンダリング検査値（Ｖｊ）をより以前の取引で前記バリデータに既に預けられたマネー・ロンダリング検査値（Ｖｊ’）と比較することによって、前記エミッタと前記アクセプタとの間の取引の回数が前記アクセプタの取引に対する前記限度（ＮＭ）未満であることを検証する
ために設けられる、バリデータ。
【請求項１４】
エミッタであって、
−発行者から証明書（Ｓ）を回収するためであって、前記証明書（Ｓ）が、前記発行者の署名鍵（ｐｋＢ，ｓｋＢ）および前記エミッタのエミッタ鍵（ｐｋＵ，ｓｋＵ）に基づいて前記発行者と前記エミッタとの間の第１の２当事者プロトコルを使用して計算される、回収するため、および
アクセプタで前記証明書（Ｓ）を使うためであって、マネー・ロンダリング検査値（Ｖｊ）が、前記証明書（Ｓ）、前記エミッタと前記アクセプタとの間の取引番号（ｊ）、前記アクセプタによって生成される取引チャレンジ値（ｒ１，ｒ２）、およびアクセプタの一意のアイデンティティ（ｉｄＭ）に基づいてエミッタとアクセプタとの間の第２の２当事者プロトコルを使用して計算される、使うため
に設けられる、エミッタ。
【図１】
【図２】
【図３】
【図４】
【図５】
【図２】
【図３】
【図４】
【図５】
【公開番号】特開２００７−３１７２００（Ｐ２００７−３１７２００Ａ）
【公開日】平成１９年１２月６日（２００７．１２．６）
【国際特許分類】
【出願番号】特願２００７−１３７２７９（Ｐ２００７−１３７２７９）
【出願日】平成１９年５月２３日（２００７．５．２３）
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＳＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
【Ｆターム（参考）】
【公開日】平成１９年１２月６日（２００７．１２．６）
【国際特許分類】
【出願日】平成１９年５月２３日（２００７．５．２３）
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＳＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
【Ｆターム（参考）】
[ Back to top ]