(57)【要約】【課題】新しいフェア・ブラインド署名プロセスを提供すること。【解決手段】フェア・ブラインド署名プロセスで、ユーザは、Ａe＝ａ0ａx1ａm2ａxu3ａt4ａs5（ｍｏｄ  ｎ）になるように７タプル（Ａ，ｅ，ｓ，ｔ，ｘu，ｘ，ｍ）を完成するために署名者と対話する。ここで、ａ0，ａ1，ａ2，ａ3，ａ4、ａ5、およびｎは、署名者の公開鍵（ＰＵＢＫS）の要素である。署名発行フェーズ中に、ユーザ（Ｕ）は、署名者（Ｓ）に、信頼される機関（ＴＡ）に既知の鍵（ｆ）に従って暗号化されたデータ要素（ａ1x）を供給し、このデータ要素（ａ1x）が、署名されたメッセージの送信中に開示される。同様に、署名されたメッセージは、信頼される機関（ＴＡ）に既知の鍵（ｆ）に従って暗号化された第２データ要素ａxu3を含む第２の暗号化されたデータに関連して送信され、この第２データ要素ａxu3が、署名発行フェーズ中に署名者に開示される。【選択図】        図１
2005253083.tif 000002
【特許請求の範囲】
【請求項１】
メッセージに対するフェア・ブラインド・デジタル署名を入手するためにユーザが署名発行フェーズで署名者と対話するフェア・ブラインド署名方式であって、
前記署名者が、公開鍵を有し、信頼される機関が、前記デジタル署名の匿名性を取り消すことができるフェア・ブラインド署名方式において、
前記ユーザが、以下の式（１）を満足するように第１から第７の項目Ａ、ｅ、ｓ、ｔ、ｘu、ｘ、およびｍからなる７タプルを完成するために前記署名者からデータを入手し、
【数１】
2005253083.tif 000018
ａ0、ａ1、ａ2、ａ3、ａ4、ａ5、およびｎが、前記署名者の公開鍵の要素であり、前記署名者によって生成され、
ｍが、署名される前記メッセージであり、
ｅおよびｓが、前記署名者によって一様にランダムに選択されるパラメータであり、
ｔおよびｘuが、前記ユーザによって一様にランダムに選択されるパラメータであり、
ｘが、前記ユーによって一様にランダムに選択されるパラメータおよび前記署名者によって一様にランダムに選択されるパラメータに基づいて前記ユーザによって計算される中間値であり、
Ａが、以下の式（２）に従って計算されるパラメータであり、
【数２】
2005253083.tif 000019
Ｃ2が、以下の式（３）に従って前記ユーザによって計算されるパラメータであり、
【数３】
2005253083.tif 000020
ＩｄUが、前記ユーザを識別するために前記ユーザによって計算されるコードであることを特徴とする、
フェア・ブラインド署名方式。
【請求項２】
前記ユーザが前記フェア・ブラインド署名方式に従って署名されたメッセージｍを第三者にサブミットする署名サブミット・フェーズを含み、前記署名サブミット・フェーズで、前記ユーザが、前記第三者に、
少なくとも１つの第１データ要素ａxu3を暗号化された形で含む暗号化されたデータＥ3およびＥ4と、
Ａに対するコミットメントと、以下の式（４）で定義される知識の署名Ｐと、
【数４】
2005253083.tif 000021
をサブミットし、
Ｉsigが、Ｉsig＝ａ1x（ｍｏｄ  ｎ）に従って前記ユーザによって計算されるパラメータであり、
ｆが、前記信頼される機関の公開鍵であり、
ｇおよびｈが、前記署名者の公開鍵のさらなる要素であり、
Ｄ1が、Ｄ1＝Ａｈw1（ｍｏｄ  ｎ）に従って定義されるパラメータであり、ｗ1は、ユーザによって一様にランダムに選択されるパラメータであり、
Ｄ2が、Ｄ2＝ｇw1ｈw2（ｍｏｄ  ｎ）に従って定義されるパラメータであり、ｗ2は、ユーザによって一様にランダムに選択されるパラメータであり、
ｌeが、ｌe≧ｌr＋２に従って定義される長さパラメータであり、ｌr＝ｍａｘ（ｌm，ｌN）であり、ｌmはメッセージｍのビット長さであり、ｌNはパラメータＮのビット長さであり、Ｎ＝［ｎ／４］であり、
ｌsが、ｌs≧ｌn＋ｌr＋ｌ＋３に従って定義される長さパラメータであり、ｌnはｎのビット長さであり、ｌはフェア・ブラインド署名方式によって定義されるセキュリティ・パラメータである
請求項１に記載のフェア・ブラインド署名方式。
【請求項３】
前記署名発行フェーズ中に、前記ユーザが、前記信頼される機関に既知の鍵に従って暗号化された少なくとも１つの第２データ要素を含む第２の暗号化されたデータを前記署名者に提供し、前記第２のデータ要素が、前記署名されたメッセージの伝送中に開示され、これによって、前記信頼される機関が、署名発行セッションのトランスクリプトから、どのデジタル署名がそこから生じたかを判定することができる、請求項１または２に記載のフェア・ブラインド署名方式。
【請求項４】
前記暗号化されたデータＥ3およびＥ4が、前記信頼される機関に既知の鍵に従って暗号化された少なくとも１つの第１データ要素ａxu3を含み、前記少なくとも１つの第１データ要素ａxu3が、前記署名発行フェーズ中に前記署名者に開示され、これによって、前記信頼される機関が、送信された署名から、前記署名がどの前記署名発行セッションに発行されたかを判定することができる、請求項２に記載のフェア・ブラインド署名方式。
【請求項５】
その間に前記ユーザが、前記ユーザを識別するように働くパラメータとして前記少なくとも１つの第１データ要素ａxu3を前記信頼される機関に提供するユーザ登録フェーズを含む、請求項４に記載のフェア・ブラインド署名方式。
【請求項６】
前記署名者が、複数のエンティティから構成され、前記ユーザに前記７つの組変数を完成するデータを提供するために、前記エンティティの定足数の協力が必要である、請求項１〜５のいずれか一つに記載のフェア・ブラインド署名方式。
【請求項７】
前記信頼される機関が、複数の信頼される機関によって構成され、前記デジタル署名の前記匿名性の取消を、前記複数の信頼される機関のうちの定足数の協力によって得ることができる、請求項１〜６のいずれか一つに記載のフェア・ブラインド署名方式。
【請求項８】
少なくとも１つのユーザ・コンピューティング・デバイス、署名者コンピューティング・デバイス、および信頼される機関コンピューティング・デバイスを含むコンピューティング・システムで使用される時に、前記コンピューティング・システムに請求項１〜７のいずれか一つに記載のフェア・ブラインド署名方式を実施させる命令の組を有するコンピュータ・プログラム。
【請求項９】
使用中に、メッセージに対するフェア・ブラインド・デジタル署名を入手するためにユーザが署名発行フェーズで署名者と対話するフェア・ブラインド署名方式を実施するように適合された署名システムであって、前記署名者が公開鍵を有し、信頼される機関が、前記デジタル署名の匿名性を取り消すことができ、前記署名システムが、
少なくとも１つのユーザ装置と、
署名者装置と、
信頼される機関装置と
を含み、前記ユーザ装置またはそのそれぞれが、署名発行プロトコルを実行するために前記署名者装置と協力するように適合され、
前記信頼される機関装置および前記署名者装置が、少なくとも１つのトレーシング・プロトコルを実行するために協力するように適合された署名システムにおいて、
前記署名発行プロトコルの実行が、以下の式（５）を満足するように第１から第７の項目Ａ、ｅ、ｓ、ｔ、ｘu、ｘ、およびｍからなる７つの組変数を前記ユーザ装置が完成できるようにする前記署名者装置からのデータを前記ユーザ装置に提供し、
【数５】
2005253083.tif 000022
ａ0、ａ1、ａ2、ａ3、ａ4、ａ5、およびｎが、前記署名者の公開鍵であり、前記署名者装置で生成され、
ｍが、署名される前記メッセージであり、
ｅおよびｓが、前記署名者装置で一様にランダムに選択されるパラメータであり、
ｔおよびｘuが、前記ユーザ装置で一様にランダムに選択されるパラメータであり、
ｘが、前記ユーザ装置で一様にランダムに選択されるパラメータおよび前記署名者装置で一様にランダムに選択されるパラメータに基づいて前記ユーザ装置で計算される中間値であり、
Ａが、以下の式（６）に従って計算されるパラメータであり、
【数６】
2005253083.tif 000023
Ｃ2が、以下の式（７）に従って前記ユーザ装置で計算されるパラメータであり、
【数７】
2005253083.tif 000024
ＩｄUが、前記ユーザを識別するために前記ユーザ装置で計算されるコードであることを特徴とする、
署名システム。
【請求項１０】
使用中に、メッセージに対するフェア・ブラインド・デジタル署名を入手するためにユーザが署名発行フェーズで署名者と対話するフェア・ブラインド署名方式に参加するように適合されたユーザ装置であって、前記署名者が公開鍵を有し、信頼される機関が、前記デジタル署名の匿名性を取り消すことができ、前記ユーザ装置が、
メッセージｍを提供するメッセージ提供手段と、
所定の署名発行プロトコルに従って前記メッセージｍの署名に関する要求を署名者装置に発する署名要求手段と
を含み、
前記ユーザ装置が、前記署名発行プロトコルを実行するために前記署名者装置と協力するように適合されたユーザ装置において、
前記署名発行プロトコルの実行が、以下の式（８）を満足するように第１から第７の項目Ａ、ｅ、ｓ、ｔ、ｘu、ｘ、およびｍからなる７つの組変数を前記ユーザ装置が完成できるようにする前記署名者装置からのデータを前記ユーザ装置に提供し、
【数８】
2005253083.tif 000025
ａ0、ａ1、ａ2、ａ3、ａ4、ａ5、およびｎが、前記署名者の公開鍵であり、前記署名者装置で生成され、
ｍが、署名される前記メッセージであり、
ｅおよびｓが、前記署名者装置で一様にランダムに選択されるパラメータであり、
ｔおよびｘuが、前記ユーザ装置で一様にランダムに選択されるパラメータであり、
ｘが、前記ユーザ装置で一様にランダムに選択されるパラメータおよび前記署名者装置で一様にランダムに選択されるパラメータに基づいて前記ユーザ装置で計算される中間値であり、
Ａが、以下の式（９）に従って計算されるパラメータであり、
【数９】
2005253083.tif 000026
Ｃ2が、に従って前記ユーザ装置で計算されるパラメータであり、
【数１０】
2005253083.tif 000027
ＩｄUが、前記ユーザを識別するために前記ユーザ装置で計算されるコードであることを特徴とする、
ユーザ装置。
【請求項１１】
コンピュータ装置で使用される時に、請求項１０に記載のユーザ装置を構成するために前記コンピュータ装置を適合させる命令の組を有するコンピュータ・プログラム。
【請求項１２】
使用中に、メッセージに対するフェア・ブラインド・デジタル署名を入手するためにユーザが署名発行フェーズで署名者と対話するフェア・ブラインド署名方式に参加するように適合された署名者装置であって、前記署名者が公開鍵を有し、信頼される機関が、前記デジタル署名の匿名性を取り消すことができ、前記署名者装置が、
ユーザ装置からメッセージｍの署名に関する要求を受信する要求受信手段と、
所定の署名発行プロトコルを実行するために前記ユーザ装置と協力する署名プロトコル実施手段と
を含む署名者装置において、
前記署名発行プロトコルの実行が、以下の式（１１）をを満足するように第１から第７の項目Ａ、ｅ、ｓ、ｔ、ｘu、ｘ、およびｍからなる７つの組変数を前記ユーザ装置が完成できるようにする前記署名者装置からのデータを前記ユーザ装置に提供し、
【数１１】
2005253083.tif 000028
ａ0、ａ1、ａ2、ａ3、ａ4、ａ5、およびｎが、前記署名者の公開鍵であり、前記署名者装置で生成され、
ｍが、署名される前記メッセージであり、
ｅおよびｓが、前記署名者装置で一様にランダムに選択されるパラメータであり、
ｔおよびｘuが、前記ユーザ装置で一様にランダムに選択されるパラメータであり、
ｘが、前記ユーザ装置で一様にランダムに選択されるパラメータおよび前記署名者装置で一様にランダムに選択されるパラメータに基づいて前記ユーザ装置で計算される中間値であり、
Ａが、以下の式（１２）に従って計算されるパラメータであり、
【数１２】
2005253083.tif 000029
Ｃ2が、以下の式（１３）に従って前記ユーザ装置で計算されるパラメータであり、
【数１３】
2005253083.tif 000030
ＩｄUが、前記ユーザを識別するために前記ユーザ装置で計算されるコードであることを特徴とする
署名者装置。
【請求項１３】
コンピュータ装置で使用される時に、請求項１２に記載の署名者装置を構成するために前記コンピュータ装置を適合させる命令の組を有するコンピュータ・プログラム。
【請求項１４】
使用中に、メッセージに対するフェア・ブラインド・デジタル署名を入手するためにユーザが署名発行フェーズで署名者と対話するフェア・ブラインド署名方式に参加するように適合され、前記署名者が公開鍵を有する信頼される機関装置であって、
前記信頼される機関装置が、署名発行プロトコルに従って発行されるデジタル署名の匿名性を取り消すように適合され、前記署名発行プロトコルの実行が、以下の式（１４）を満足するように第１から第７の項目Ａ、ｅ、ｓ、ｔ、ｘu、ｘ、およびｍからなる７つの組変数を前記ユーザが完成できるようにする前記署名者からのデータを前記ユーザに提供し、
【数１４】
2005253083.tif 000031
ａ0、ａ1、ａ2、ａ3、ａ4、ａ5、およびｎが、前記署名者の公開鍵であり、前記署名者によって生成され、
ｍが、署名される前記メッセージであり、
ｅおよびｓが、前記署名者によって一様にランダムに選択されるパラメータであり、
ｔおよびｘuが、前記ユーザによって一様にランダムに選択されるパラメータであり、
ｘが、前記ユーザによって一様にランダムに選択されるパラメータおよび前記署名者によって一様にランダムに選択されるパラメータに基づいて前記ユーザによって計算される中間値であり、
Ａが、以下の式（１５）に従って計算されるパラメータであり、
【数１５】
2005253083.tif 000032
Ｃ2が、以下の式（１６）に従って前記ユーザによって計算されるパラメータであり、
【数１６】
2005253083.tif 000033
ＩｄUが、前記ユーザを識別するために前記ユーザによって計算されるコードであることを特徴とする
信頼される機関装置。
【請求項１５】
コンピュータ装置で使用される時に、請求項１４に記載の信頼される機関装置を構成するために前記コンピュータ装置を適合させる命令の組を有するコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子トランザクションのセキュリティに関し、より詳しくは、デジタル署名の技術分野に関する
【背景技術】
【０００２】
デジタル署名方式は、ユーザおよび署名者を伴う公開鍵暗号プロトコルである。署名者は、秘密鍵とそれに対応する公開鍵を所有している。ユーザは、一般にインターネットなどのネットワークに送信するためのメッセージを生成する。署名者は、そのメッセージの有効性または認証性を示すものとして、自分の秘密鍵（シークレット・キーまたはペライベート・キー）を使用してメッセージのデジタル署名を生成する。望めば誰でも、その署名者の公開鍵のみを用いて署名の認証性を検証することができる。
【０００３】
通常のデジタル署名方式では、署名者は、デジタル署名が適用されるメッセージの内容を知っており、署名アルゴリズム（たとえば、周知のＲＳＡアルゴリズム）を使用することによって、偽造が困難または不可能なデジタル署名を生成する。
【０００４】
ブラインド署名（blind signature）方式では、ユーザは、署名者にメッセージの内容に関する情報を与えることなく、自分のメッセージに対するデジタル署名を得ることができる。デヴィッド・チョム博士（David Chaum）によって開発された周知のブラインド署名方式が、特許文献１に記載されている。ブラインド署名方式は、デジタル・キャッシュ・アプリケーションに用いる方式として提案されることがあり、この方式により、個人は、金融機関によってデジタル・キャッシュの次の使用が追跡されることなく、金融機関からデジタル・キャッシュを購入できる。
【０００５】
通常のブラインド署名方式では、署名者は、異なるユーザの多数の文書に署名する場合、自分が署名したある特定の文書を提示されても、その文書にいつ誰のために署名したかを判断することができない。対照的に、フェア・ブラインド署名方式（ＦＢＳＳ：fair blind signature scheme）では、追加の参加者すなわち、１つまたは複数の信頼される機関（または「判定者（judge）」）があり、署名者は、信頼される機関（または、複数の信頼される機関がある場合に、定足数の信頼される機関）の助けによって、所与の署名セッションからどの署名が生成されたかを識別することができる。
【０００６】
署名者は、特定の署名セッションのトランスクリプトを有する場合、信頼される機関の助けを得て、そのセッションから生じた署名／メッセージ対を判定することができる。これを「署名トレーシング（signature tracing）」と言う。逆に、署名者は、特定のメッセージ／署名対を入手できる場合、信頼される機関の助けを借りて、これを生成した署名セッションを判定できる。これを「セッション・トレーシング（session tracing）」と言う。
【０００７】
フェア・ブラインド署名方式では、「ゼロ知識証明（zero-knowledge proof）」技術を使用する。あるエンティティ（「証明者」）が、あるステートメント（または述部）が真であることを別のエンティティ（「検証者」）に証明する必要がある場合がある。証明者および検証者が適当な対話プロトコル（知識の対話証明）を実行できれば、検証者は、そのステートメントが真であることを確信することができる。知識の証明のプロトコルでは、知識の証明に参加した後に、検証者がステートメントが何であるかの知識を有しない（検証者は、それが真または「有効」であることだけを知る）場合を、「ゼロ知識」と称する。後者の場合、検証者は、ステートメントの有効性を他者に証明することができない。
【０００８】
フェア・ブラインド署名方式は、所与のデジタル署名を所与のユーザにリンクすることができるが、ユーザのメッセージは、まだプライベート状態である。フェア・ブラインド署名方式は、主に、電子オークションなど、破棄可能な匿名性が望ましい応用、および組織化された犯罪との戦い（マネー・ロンダリングの防止など）の応用に関して提案されてきた。
【０００９】
セキュアな状態を実現するために、フェア・ブラインド署名方式は、ワンモア・アンフォージャビリティ（one-more unforgeability）、ブラインドネス（blindness）、およびトレーサビリティ（厳格な取消）の特性を有しなければならない。
【００１０】
「ワンモア・アンフォージャビリティ」は、捏造しようとする者が署名者とｋ回対話した場合であっても、フェア・ブラインド署名方式の下でｋ＋１番目の有効な署名を作ることが計算的に困難であるという事実を示している（これを「（ｋ，ｋ＋１）アンフォージャビリティ」と呼ぶことができる）。この特性は、意図する捏造者と署名者の間の対話が適応的でインターリーブする形で実行される場合であっても保持されなければならない。
【００１１】
「ブラインドネス」は、特定の有効なデジタル署名を作った署名セッションを行ったユーザの識別を可能にする情報が生成されることについては、その署名を与えられた誰によっても（信頼される機関以外）計算的に困難である、という特性を示す。同様に、特定の署名セッションで作られた署名を識別することは、そのセッションのトランスクリプトを与えられた誰もによっても（信頼される機関以外）計算的に困難である。
【００１２】
「トレーサビリティ（厳格な取消）」は、フェア・ブラインド署名方式に組み込まれたトレーシング手順を回避することは、誰もによっても（署名者以外）困難であるという特性を示す。具体的にいうと、信頼される機関によってトレースできない有効な署名、または信頼される機関によって対応するユーザにマッチングすることができない有効な署名を作ることは、誰によっても（署名者以外）計算的に困難である。
【００１３】
今まで、様々なフェア・ブラインド署名方式が提案されてきた（例えば、非特許文献１参照）。しかしながら、提案された方式のほとんどが、非効率的であるか、非セキュアであるか、標準的でない仮定が設けられた場合に限ってセキュアと証明されるかのいずれかである。
【００１４】
効率的なフェア・ブラインド署名方式の１つが、阿部および大久保によって提案されている（非特許文献２参照）。この方式のセキュリティ（すなわち、署名のアンフォージャビリティ）は、離散対数問題に頼っている。この方式によれば多項式セキュリティ（polynomial security）が提供される、と主張しているが、実際には、ポリ対数セキュリティ（poly-logarithmic security）だけを提供する（すなわち、ポリ対数個の署名だけがセキュアに発行され、このポリ対数個数は、セキュリティ・パラメータに関して定義される）。
【００１５】
【特許文献１】欧州特許出願公開第０１３９３１３号明細書
【非特許文献１】Ｍ．スタッドラー（M. Stadler）他著，「フェア・ブラインド署名（Fair Blind Signatures）」，暗号論の進展（Advances in Cryptology）、ユーロクリプト’９５（Eurocrypt '95），コンピュータサイエンスの講義ノートの第９２１巻（volume 921 of Lecture Notes in Computer Science），ベルリン（Berlin），スプリンガー社(Springer-Verlag），ｐｐ２０９−２１９
【非特許文献２】阿部，大久保著，「厳格な取消しを伴う証明可能なセキュア・フェア・ブラインド署名（Provably Secure Fair Blind Signatures with Tight Revocation）」，アジアクリプト’０１の予稿集（Proceedings of Asiacrypt'01），コンピュータサイエンスの講義ノートの第２２４８巻（vol.263 of Lecture Notes in Computer Science），ベルリン（Berlin），スプリンガー社(Springer-Verlag），ｐｐ５８３−６０１
【発明の開示】
【発明が解決しようとする課題】
【００１６】
本発明の目的は、効率的であり、多項式個数の署名をセキュアに発行できるフェア・ブラインド署名方式を提供することである。
【課題を解決するための手段】
【００１７】
上述した課題を解決し、目的を達成するために、本発明は、メッセージに対するフェア・ブラインド・デジタル署名を入手するためにユーザが署名発行フェーズで署名者と対話するフェア・ブラインド署名方式であって、前記署名者が、公開鍵を有し、信頼される機関が、前記デジタル署名の匿名性を取り消すことができるフェア・ブラインド署名方式において、前記ユーザが、以下の式（１）を満足するように第１から第７の項目Ａ、ｅ、ｓ、ｔ、ｘu、ｘ、およびｍからなる７タプルを完成するために前記署名者からデータを入手し、
【数１】
2005253083.tif 000003
ａ0、ａ1、ａ2、ａ3、ａ4、ａ5、およびｎが、前記署名者の公開鍵の要素であり、前記署名者によって生成され、ｍが、署名される前記メッセージであり、ｅおよびｓが、前記署名者によって一様にランダムに選択されるパラメータであり、ｔおよびｘuが、前記ユーザによって一様にランダムに選択されるパラメータであり、ｘが、前記ユーによって一様にランダムに選択されるパラメータおよび前記署名者によって一様にランダムに選択されるパラメータに基づいて前記ユーザによって計算される中間値であり、Ａが、以下の式（２）に従って計算されるパラメータであり、
【数２】
2005253083.tif 000004
Ｃ2が、以下の式（３）に従って前記ユーザによって計算されるパラメータであり、
【数３】
2005253083.tif 000005
ＩｄUが、前記ユーザを識別するために前記ユーザによって計算されるコードであることを特徴とする。
【発明を実施するための最良の形態】
【００１８】
本発明の好ましい実施形態によるフェア・ブラインド署名プロセスの詳細な説明を提供する前に、フェア・ブラインド署名方式のある基本的な原理および数学的表記について想起していただければ以下の説明がより有効なものとなる。
【００１９】
フェア・ブラインド署名方式（ＦＢＳＳ）は当技術分野で周知なので、その形式的定義を示す必要はないと思われる。しかしながら、それについて関心があるならば、そのような定義について上で示した非特許文献２を参照するとよい。
【００２０】
ＦＢＳＳに、３タイプの参加者すなわち、メッセージに署名されることを望むユーザＵと、ブラインド・デジタル署名を作る署名者（Ｓ）と、「判定者」と呼ぶこともできる信頼される機関（ＴＡ）とが含まれるものと想定する。本発明のフェア・ブラインド署名方式では、３つの異なる種類のプロトコル、すなわち、ユーザが自分の選んだメッセージの署名を得ることを可能にした、ユーザと署名者の間で行われる署名発行プロトコルと、ユーザがメッセージと共に署名をサブミットすることを可能にした、ユーザと誰かの間で行われる署名サブミッション・プロトコルと、どちらもが署名者Ｓと信頼される機関ＴＡの間で行われる署名トレーシング・プロトコルおよび／またはセッション・トレーシング・プロトコルがあるトレーシング・プロトコルとが使用される。
【００２１】
本発明の好ましい実施形態で使用されるセッション・トレーシング・プロトコルでは、信頼される機関が、特定のメッセージ／署名対の生成につながった署名セッションを行ったユーザの識別をその対から判定できるようにすることに留意されたい。よって、この好ましいプロトコルは、「ユーザ・トレーシング」プロトコルと呼べる。実際には、ユーザのトレーシングは、特定のメッセージ／署名対の生成をもたらした署名セッションを単純に識別することより有用である（一部の方式では、真のセッション・トレーシング・プロトコルによって識別された署名セッションを行ったユーザを判定するために、大きなデータベースを検索する必要がある）。
【００２２】
以下の説明では、次の数学的表記を使用する。
ｘ∈RＥは、ｘが、集合Ｅから一様にランダムに選択されることを意味する。言い換えると、ｘは、一様分布に従って集合Ｅからランダムに選択される。
ｘが整数である場合に、｜ｘ｜は、ｘのバイナリ・サイズ（または長さ）を表す。
集合Ｉdは、０からｄ−１までの整数の集合を意味する。言い換えると、Ｉdは、集合｛０，１，２，．．．，ｄ−１｝に対応する。
【００２３】
整数ｎについて、Ｚ／（ｎ）は、ｎを法とする剰余環を表し、Ｚ／（ｎ）*は、Ｚ／（ｎ）の可逆元の乗法群を表す。
集合Ｚ／（ｎ）で一様にランダムに選択される要素αについて（言い換えると、α∈RＺ／（ｎ）について）、Ｚ／（ｎ）*でのアルファの次数をｏｒｄ（α）と表す。
Ｚ／（ｎ）*で一様にランダムに選択される要素αによって生成される（言い換えると、α∈RＺ／（ｎ）*によって生成されるＺ／（ｎ）*の部分群を、＜α＞と表す。
【００２４】
集合ＱＲ（ｎ）は、ｎを法とするすべての平方剰余の集合を表す。
記号‖は、２つの（バイナリ）ストリング（または、整数要素および群要素の２進表現）の連結を表す。
記号Ｈは、任意の適当なハッシュ関数を表す。
【００２５】
ＳＫ（α：ｆ（α，．．．））（ｍ）は、メッセージｍに対する「知識の署名」を表す。知識の署名ＳＫを提供することによって、証明者は、述部ｆを定義する式を満足する値αを知っていることを第三者（「検証者」）に実証する。
【００２６】
ＳＫ（α，β：ｆ（α，．．．）∧ｇ（β，．．．））（Ｍ）は、ｆを定義する式およびｇを定義する式を満足する値αおよびβを証明者が知っていることを示す、メッセージＭに対する「知識の署名」を表す。
【００２７】
「知識の署名」は、周知のファイアット・シャミア法（Fiat-Shamir heuristic)（Ａ．ファイアット，Ａ．シャミア著，「自己証明法：認証および署名の問題の実用的な解決法（How to Prove Yourself: Practical Solutions to Identification and Signature Problems）」，クリプト’８６の予稿集（Proceedings of Crypt '86），コンピュータサイエンスの講義ノートの第２６３巻（vol.263 of Lecture Notes in Computer Science），ｐｐ１８６−１９４，ベルリン（Berlin），スプリンガー社(Springer-Verlag），１９８７年を参照されたい）を使用する知識のゼロ知識証明から導出される署名である。基礎になる知識の証明がセキュアである場合に、それから導出される知識の署名が、ランダム・オラクル・モデル（random oracle model）でセキュアであることを示すことができる。
【００２８】
知識の署名で参照される述部ｆ、ｇなどの性質に応じて、証明者は、知識のゼロ知識証明を確立するために、検証者に異なる情報を送信する必要がある。後述する基本構成要素１の説明以降において、述部と、関連する述部を満足する値の所有を証明するために証明者が送信できる情報とを示す。
【００２９】
本発明の好ましい実施形態によるフェア・ブラインド署名方式を、図１を参照して以下に説明する。このシステムに、デジタル署名を発行する署名者Ｓ、各々のメッセージに対する（フェア・ブラインド）デジタル署名を得ることを求めるユーザＵ、およびデジタル署名の匿名性を取り消すことが可能な１つまたは複数の信頼される機関ＴＡが含まれることを想定する。
【００３０】
図１は、本発明の好ましい実施形態によるフェア・ブラインド署名方式を実施するのに使用される主要なプロセスおよびプロトコルを示す図である。
【００３１】
図１からわかるように、ある方式パラメータの値が決定される、初期セットアップ・フェーズがある。このセットアップ・フェーズ中に、第１および第２のセキュリティ・パラメータｌおよびｌpの値が、（システム設計者によって）選択される。その後、署名者Ｓは、それぞれがセキュリティ・パラメータｌpと等しいビット数を有するランダムな秘密の素数ｐ’およびｑ’を選択する。ｐ’およびｑ’は、値ｐ＝２ｐ’＋１およびｑ＝２ｑ’＋１の両方が素数になるように選択される。署名者は、秘密鍵（シークレット・キーまたはプラベート・キー）としてＰＲＫs＝（ｐ’，ｑ’）を使用する。法ｎには、値ｎ＝ｐｑがセットされ、さらなるパラメータＮおよびｌnが、以下の式（４）に従って決定される。
【００３２】
【数４】
2005253083.tif 000006
【００３３】
署名者Ｓは、他者に関するランダムな生成元のそれぞれの離散対数が未知になるように、ＱＲ（ｎ）のランダムな生成元（ａ0，ａ1，ａ2，ａ3，ａ4，ａ5，ｇ，ｈ）も選択する。
【００３４】
セットアップ・フェーズで、信頼される機関は、ｙ∈RＩNを選択する（言い換えると、ＴＡは、集合｛０，１，．．．，Ｎ−１｝で一様にランダムに選択することによって、パラメータｙの値を選択する）。このパラメータｙは、信頼される機関の秘密鍵になる。次に、ＴＡは、ｆ＝ｇy（ｍｏｄ  ｎ）として公開鍵ｆを計算する。
【００３５】
全体的なフェア・ブラインド署名システムの公開鍵は、ＰＵＢＫ＝（ｎ，ａ0，ａ1，ａ2，ａ3，ａ4，ａ5，ｆ，ｇ，ｈ）である。署名者の公開鍵は、全体的なシステムの公開鍵と同一であるが、値ｆがない、すなわち、（ｎ，ａ0，ａ1，ａ2，ａ3，ａ4，ａ5，ｇ，ｈ）と同一である。
【００３６】
下の表１に、セットアップ・フェーズ中に定義される値を有するパラメータの一部を要約する。
【００３７】
【表１】
2005253083.tif 000007
【００３８】
セットアップの後に、本発明のフェア・ブラインド署名システムは、使用の準備ができている、すなわち、署名者が、ユーザのメッセージにデジタル署名する準備ができている。
【００３９】
本発明にとって必須ではないが、ユーザがシステムに登録することが有用で有り得る。これによって、システムが、セッション・トレーシングだけではなくユーザ・トレーシングを実行できるようになる。したがって、本発明の好ましい実施形態のＦＢＳＳに、図１で破線のボックスによって示される、登録フェーズが含まれる。
【００４０】
登録フェーズでは、ユーザＵが、秘密の値ｘu∈RＩNを選択する（言い換えると、Ｕは、集合｛０，１，．．．，Ｎ−１｝で一様にランダムに選択することによって、パラメータｘuの値を選択する）。次に、Ｕは、以下の式（５）に示すように、自分自身を識別するコードＩｄUを計算する。
【００４１】
【数５】
2005253083.tif 000008
【００４２】
ユーザは、自分が底ａ3のＩｄUの離散対数を知っていることを信頼される機関に証明する。これは、任意の便利な手順を使用して行うことができる（たとえば、Ｇ．ポーパード（G. Poupard），Ｊ．ステム（J. Stem）著，「オンフライ認証および署名の生成のセキュリティ分析（Security Analysis of a Practical "on the fly" Authentication and Signature Generation）」，ユーロクリプト’９８の予稿集（Proceedings of Eurocrypt'98），コンピュータサイエンスの講義ノートの第１４０３巻（vol.1403 of Lecture Notes in Computer Science），ｐｐ４２２−４３６，ベルリン（Berlin），スプリンガー社(Springer-Verlag），１９９８年、または、Ｍ．ジャロウ（M. Girault）著，「合成数ごとの離散対数法に基づいた識別式認証方法（An Identity-based Identification Scheme Based on Discrete Logarithms Modulo a Composite Number）」，ユーロクリプト１９９０の予稿集（Proceedings of Eurocrypt 1990），コンピュータサイエンスの講義ノートの第４７３巻（vol.473 of Lecture Notes in Computer Science），ｐｐ４８１−４８６，ベルリン（Berlin），スプリンガー社(Springer-Verlag）を参照されたい）。信頼される機関は、ＩｄUとユーザによって供給された証明の両方を公開し、したがって、署名発行プロトコル（下記を参照されたい）の実行中にユーザを認証できるようにする。これで登録フェーズが完了する。
【００４３】
図１からわかるように、好ましい実施形態のフェア・ブラインド署名方式には、署名発行プロトコル、署名サブミッション・プロトコル、ならびに署名トレーシング・プロトコルおよび／またはセッション・トレーシング・プロトコル（この場合にはユーザ・トレーシング・プロトコル）を含むトレーシング・プロトコルが含まれる。明らかに、署名発行プロトコルは、メッセージの署名に関してユーザが署名者に連絡するたびに使用され、署名サブミッション・プロトコルは、ユーザが第三者に署名付きメッセージを供給するたびに使用されるが、署名トレーシング・プロトコルおよびセッション・トレーシング・プロトコルは、デジタル署名の匿名性を取り消すことが望まれる（たとえば、オンライン・オークションの成功裡の入札者の詳細を取り出すことが望まれるので）場合に限って呼び出される。これらのプロトコルを、これから順番に検討する。
【００４４】
［署名発行プロトコル］
４つの長さパラメータｌr、ｌm、ｌe、およびｌsを、以下の式（６）に示す３つの関係を満足するように定義する。
【数６】
2005253083.tif 000009
ここで、ｌは、第１セキュリティ・パラメータ、ｌnは、法ｎのビット長さ、ｌNは、セットアップ・フェーズの上の説明で述べたパラメータＮのビット長さである。署名されるメッセージｍは、ビット長さｌmのメッセージである、言い換えると、ｍは、集合｛０，１，．．．，（２lm−１）｝に含まれる整数とすることができる。本発明の好ましい実施形態では、これらの長さパラメータの値を決定するのは、署名者であるが、本発明は、この可能性に制限されない。本発明の他の実施形態では、他の当事者、たとえば信頼される機関が、これらの長さパラメータの値をセットすることができる。
【００４５】
ユーザと署名者によって対話的に実行される署名発行プロトコルは、２パートプロトコルと考えることができる。署名発行プロトコルの第１部分では、ユーザと署名者が、対話し、ユーザは、あるパラメータ・データ（特にｘ＾（ｘの頭上にハット記号：以下同様に表現する）、Ａ、ｅ、およびｓ）を署名者から入手する。署名発行プロトコルの第２部分では、ユーザが、署名者から入手したパラメータ・データを利用して、所望のデジタル署名を生成する。
【００４６】
署名発行プロトコルの第１部分では、次のステップが実行される。
ユーザは、集合｛０，１，．．．，Ｎ−１｝から一様にランダムにパラメータｘ〜（ｘの頭上にチルダ文字：以下同様に表現する）およびパラメータｒ〜を選択する。言い換えるとｘ〜∈RＩNかつｒ〜∈RＩNである。
【００４７】
ユーザは、パラメータＣ1および２つの知識の署名Ｕ0およびＵ1を以下の式（７）に従って生成する。
【数７】
2005253083.tif 000010
【００４８】
次に、ユーザは、Ｃ1、ユーザの識別コードＩｄU、ならびに２つの知識の署名Ｕ0およびＵ1を署名者に送信する。
【００４９】
署名者は、２つの知識の署名Ｕ0およびＵ1を検証する。次に、知識の署名が成功裡に検証された場合に、署名者は、集合｛０，１，．．．，Ｎ−１｝で一様にランダムに選択することによってパラメータｘ＾の値をセットする。言い換えると、ｘ＾∈RＩNである。このパラメータが、ユーザに送り返される。
【００５０】
次に、ユーザは、署名者から受信したパラメータｘ＾を使用して、さらなるパラメータｘ＝ｘ〜＋ｘ＾（ｍｏｄ  ｎ）を生成する。
【００５１】
次に、ユーザは、集合｛０，１，．．．，Ｎ−１｝から一様にランダムにパラメータｔおよびパラメータｒを選択する。言い換えると、ｔ∈RＩNかつｒ∈RＩNである。
【００５２】
次に、ユーザは、３つのさらなるパラメータＣ2、Ｅ1、およびＥ2ならびに２つのさらなる知識の署名ＶおよびＷを、以下の式（８）のように計算する。
【数８】
2005253083.tif 000011
として計算する。パラメータＥ1が、信頼される機関の公開鍵ｆに従って暗号化されたデータａ1xに対応することに留意されたい。ユーザは、この３つのパラメータおよび２つの知識の署名（Ｃ2，Ｅ1，Ｅ2，Ｖ，Ｗ）を署名者に送信する。
【００５３】
署名者は、２つの知識の署名ＶおよびＷを検証する。この知識の署名の両用が有効である場合には、署名者は、集合｛０，１，．．．，（Ｉ2ls−１）｝で一様にランダムに第１パラメータｓを選択し、２le-1と２leの間の素数からなる集合で一様にランダムに選択することによって第２パラメータｅを選択する。言い換えると、以下の式（９）のようになる。
【数９】
2005253083.tif 000012
【００５４】
署名者は、次に、以下の式（１０）のように、パラメータＡを計算する。
【数１０】
2005253083.tif 000013
【００５５】
署名者は、Ａ、ｅ、およびｓをユーザに送信し、ユーザは、次の式（１１）に示す関係が真であることを検証する。
【数１１】
2005253083.tif 000014
この後者の２つの検証によって、署名発行プロトコルの第１部分が終わる。
【００５６】
署名発行プロトコルの第２部分では、ユーザが、自分のメッセージｍの実際のデジタル署名を生成する。これには、次の要素（この好ましいＦＢＳＳに従って、集合｛０，１，．．．，（２lm−１）｝の整数であるメッセージｍの有効なデジタル署名を構成する）を生成することが含まれる。
【００５７】
−  値Ｉsig
−  ＥｌＧａｍａｌ暗号文Ｅ＝（Ｅ3，Ｅ4）
−  知識の署名Ｐ。これは、Ｕがタプル（Ａ，ｅ，ｓ，ｔ，ｘu，ｘ）を知っており、
・（Ｐ1）：Ｉsig＝（ａ1x  ｍｏｄ  ｎ）かつｘ∈ＩN
・（Ｐ2）：Ａg＝ａ0  Ｉsig  ａm2  ａt4  ａg5  ａxu3（ｍｏｄ  ｎ）かつｘuおよびｔがＩNに属し、ｓがＩ2lkに属する
・（Ｐ3）：Ｅがａxu3（ｍｏｄ  ｎ）の暗号化である
ことを証明する。
【００５８】
ＥｌＧａｍａｌ暗号文の性質は、当業者に周知であり、本明細書では詳細に説明しない。しかし、望むならば、Ｇ．Ｒ．ブラックレー（G. R. Blackley），Ｄ．チャウム（D. Chaum）著，Ｔ．エル ガマル（T. El Gamal）編，「離散対数に基づく公開鍵暗号システムおよび署名方法（A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms）」、クリプト’８４の予稿集（Proceedings of Crypt '84），コンピュータサイエンスの講義ノートの第１９６巻（vol.196, Lecture Notes in Computer Science），ｐ１０−１８，ベルリン（Berlin），スプリンガー社(Springer-Verlag），１９８５にさらなる情報がある。
【００５９】
ｍに対する署名ＳＫは、その知識の証明ＰＫが有効である場合に有効である。ユーザは、知識の複数の異なる署名ＳＫを作ることができるが、メッセージｍに対するデジタル署名は、値Ｉsigによって一意に決定され、この値は、ユーザと署名者によって協同で計算される。ｍに対する２つの署名が、めいめいの異なるＩsig値を有する場合に、これらの署名は、異なるものと考えられる。ｍに対する２つの署名が、Ｉsigの同一の値を有する場合に、これらは、各々の知識の署名ＳＫが異なる場合であっても、同一と考えられる。
【００６０】
本発明の好ましい実施形態によれば、適当な知識の署名ＳＫは、次のように構成することができる。
【００６１】
ユーザが、Ｉsig＝ａ1x（ｍｏｄ  ｎ）を計算する。
ユーザが、３つのパラメータｗ、ｗ1、およびｗ2を集合｛０，１，．．．，ＩN−１｝で一様にランダムに選択する。言い換えると、ｗ、ｗ1、ｗ2∈RＩNである。
【００６２】
ユーザは、ＥｌＧａｍａｌ暗号文Ｅ3およびＥ4ならびに２つの他のパラメータＤ1およびＤ2を以下の式（１２）のように計算する。
【数１２】
2005253083.tif 000015
【００６３】
知識の署名ＳＫは、以下の式（１３）として計算される。
【数１３】
2005253083.tif 000016
【００６４】
上の知識の署名は、うわべは複雑な外見を有するが、上の定義のコロンの右側の１１個の述部を満足する値α、β、γ、δ、η、ζ、ι、ε、およびμの値をユーザが知っていることを示す知識の署名になることを、当業者はすぐに諒解するであろう。
【００６５】
当業者は、この分野での共通の一般的な知識から、知識の証明ＳＫから特定のタイプの述部を小計するために、検証者にどのデータを送信しなければならないかをすぐに理解するであろう。実際に、異なるタイプの秘密の知識の所有を証明す知識の署名を生成する方法に関する非常に大量の技術文献が、当技術分野に存在しており、たとえば、Ｊ．カメニッシュ（J. Camenisch），Ｍ．スタッドラー（M. Stadler）著，「大グループに対して効果的なグループ署名（Efficient Group Signature Schemes for Large Groups）」，暗号論の進展（Advances in Cryptology）、ユーロクリプト’９７（Eurocrypt '97），コンピュータサイエンスの講義ノートの第１２９４巻（volume 1294 of Lecture Notes in Computer Science），ベルリン（Berlin），スプリンガー社(Springer-Verlag），ｐｐ４１０−４２４，１９９７年を参照されたい。
【００６６】
しかし、秘密の知識がある特定の形をとる時に、証明者が関連する秘密の知識を所有することを証明するのに適当な知識の署名のいくつかをここで想起することが有用である可能性がある（下記を参照されたい）。これらは、本発明の好ましい実施形態で使用される基本構成要素と考えることができる。
【００６７】
［基本構成要素１（ユーザが底ｇに関するｙの離散対数であるｘを知っている）］
ユーザが、底ｇに関する数ｙの離散対数ｘ（すなわちｙ＝ｇx）を知っており、ｇおよびｙの両方が群Ｇに含まれる場合を検討されたい。
【００６８】
ユーザが、値ｘ（底ｇに関するｙの離散対数）を漏らさずにｘを知っていることを証明したい場合に、ユーザは、次のようにそれを行うことができる。まず、ユーザは、集合｛０，１，．．．，Ｉe(lG+k)−１｝からパラメータｒを一様にランダムに選択し、ｃ＝Ｈ（ｇ‖ｙ‖ｇr‖ｍ）およびｓ＝ｒ−ｃｘ（剰余環Ｚにおいて）に従って２つの証拠パラメータｃおよびｓの値を決定する。証明者が、離散対数値ｘを真に知っており、証拠パラメータｃおよびｓを生成する時に適当な値を使用した場合に、データ対（ｃ，ｓ）は、式ｃ＝Ｈ（ｇ‖ｙ‖ｙcｇs‖ｍ）を満足する。ここで、ｃおよびｓは、それぞれ集合Ｉk×Ｉe(lG+k)+1の要素である。
【００６９】
したがって、ユーザが、ｃ＝Ｈ（ｇ‖ｙ‖ｙcｇs‖ｍ）を満足するこのデータ対（ｃ，ｓ）の値を含む知識の署名を生成する場合に、これによって、ユーザが、メッセージｍ∈｛０，１｝*に対する底ｇに関する離散対数ｙを知っていることが証明される。対応する知識の署名は、ＳＫ（α：ｙ＝ｇα）（ｍ）と表すことができる。
【００７０】
［基本構成要素２（ユーザが、底ｇに関するｙ1の離散対数であり、かつ、底ｈに関するｙ2の離散対数であるｘを知っている）］
この例では、ユーザは、ｙ1＝ｇxおよびｙ2＝ｈxを知っている。ユーザは、次のように、ｘを漏らさずにこの知識の所有を実証することができる。
【００７１】
まず、ユーザは、集合｛０，１，．．．，Ｉe(lG+k)−１｝からパラメータｒを一様にランダムに選択し、ｃ＝Ｈ（ｇ‖ｈ‖ｙ1‖ｙ2‖ｇr‖ｈr‖ｍ）およびｓ＝ｒ−ｃｘ（剰余環Ｚにおいて）に従って２つの証拠パラメータｃおよびｓの値を決定する。証明者が、離散対数値ｘを真に知っており、底ｇに関するｙ1のこの離散対対数が、ｈに関するｙ2の離散対数と同一であり、証明者が、証拠パラメータｃおよびｓを生成する時にｘの適当な値を使用した場合に、データ対（ｃ，ｓ）は、式ｃ＝Ｈ（ｇ‖ｈ‖ｙ1‖ｙ2‖ｙ1cｇs‖ｙ2cｈs‖ｍ）を満足し、ｃおよびｓは、集合Ｉk×Ｉe(lG+k)+1の要素である。
【００７２】
したがって、ユーザが、ｃ＝Ｈ（ｇ‖ｈ‖ｙ1‖ｙ2‖ｙ1cｇs‖ｙ2cｈs‖ｍ）を満足するデータ対（ｃ，ｓ）の値を含む知識の署名を生成する場合に、これによって、ユーザが、メッセージｍ∈｛０，１｝*に関して、底ｇに関するｙ1の離散対数および底ｈに関するｙ2の離散対数の両方を知っていることが証明される。対応する知識の署名を、ＳＫ（α，β：ｙ1＝ｇ1α∧ｙ2＝ｇ2β）（ｍ）と表すことができる。
【００７３】
［基本構成要素３（ユーザが、底ｇおよび底ｈに関するｙの表現であるｘ1およびｘ2を知っている）］
この場合に、ユーザは、ｙ＝ｇx1ｈx2であることを知っている。ユーザは、次のように、ｘ1およびｘ2を漏らさずに、この知識の所有を実証することができる。
【００７４】
まず、ユーザは、集合｛０，１，．．．，Ｉe(lG+k)−１｝から一様にランダムに２つのパラメータｒ1およびｒ2を選択し、ｃ＝Ｈ（ｇ‖ｈ‖ｙ‖ｇx1ｈx2‖ｍ）、ｓ1＝ｒ1−ｃｘ1、およびｓ2＝ｒ2−ｃｘ2（剰余環Ｚにおいて）に従って、３つの証拠パラメータｃ、ｓ1、およびｓ2の値を決定する。証明者が、底ｇおよび底ｈに関するｙの表現を真に知っており、証拠パラメータｃ、ｓ1、およびｓ2を生成する時に適当な値を使用した場合に、データ・セット（ｃ，ｓ1，ｓ2）は、式ｃ＝Ｈ（ｇ‖ｈ‖ｙ‖ｙcｇs1ｈs2‖ｍ）を満足し、ｃ、ｓ1、およびｓ2のそれぞれは、集合Ｉk×Ｉe(lG+k)+1×Ｉe(lG+k)+1の要素である。
【００７５】
したがって、ユーザが、ｃ＝Ｈ（ｇ‖ｈ‖ｙ‖ｙCｇs1ｈs2‖ｍ）を満足するデータ・セット（ｃ，ｓ1，ｓ2）の値を含む知識の署名を生成した場合に、これによって、ユーザが、メッセージｍ∈｛０，１｝*の、底ｇおよび底ｈに関するｙの表現を知っていることが証明される。対応する知識の署名を、ＳＫ（α，β：ｙ＝ｇαｈβ）（ｍ）と表すことができる。
【００７６】
［基本構成要素４（ユーザが、底ｇに関するｙの離散対数と、この離散対数が特定の区間に含まれることを知っている）］
この場合に、ユーザは、ｙ＝ｇxであることと、ｘが区間］Ｘ−２e(l+k)，Ｘ＋２e(l+k)［に含まれることを知っている。ユーザは、次のように、ｘを漏らさずにこの知識の所有を実証することができる。
【００７７】
まず、ユーザは、集合｛０，１，．．．，Ｉe(lG+k)−１｝から一様にランダムにパラメータｒを選択し、ｃ＝Ｈ（ｇ‖ｙ‖ｇr‖ｍ）、ｓ＝ｒ−ｃ（ｘ−Ｘ）（剰余環Ｚにおいて）に従って２つの証拠パラメータｃおよびｓの値を決定する。証明者が、底ｇに関するｙの離散対数と、これが含まれる区間を真に知っており、証拠パラメータｃおよびｓを生成する時に適当な値を使用した場合に、データ対（ｃ，ｓ）は、式ｃ＝Ｈ（ｇ‖ｙ‖ｙCｇs-cX‖ｍ）を満足し、ｃおよびｓは、それぞれ、集合Ｉk×Ｉe(lG+k)+1の要素である。
【００７８】
したがって、ユーザが、ｃ＝Ｈ（ｇ‖ｙ‖ｙCｇs-cX‖ｍ）を満足するデータ対（ｃ，ｓ）の値を含む知識の証明を生成する場合に、これによって、ユーザが、メッセージｍ∈｛０，１｝*の、底ｇに関するｙの離散対数とそれが含まれる区間を知っていることが証明される。対応する知識の署名を以下の式（１４）のように表すことができる。
【数１４】
2005253083.tif 000017
【００７９】
［署名サブミッション・プロトコル］
フェア・ブラインド署名システムＦＢＳＳに戻ると、本発明の好ましい実施形態によれば、ユーザは、署名されたメッセージの生成を完了したならば、そのメッセージを望み通りに他者にサブミットすることができる。署名されたメッセージが供給されるエンティティ（署名者など）は、このＦＢＳＳを使用して生成された特定の署名の有効性について確信することを望む場合がある。したがって、そのエンティティは、署名されたメッセージに関連する知識の署名Ｐの有効性を検証することを望む場合がある。知識の署名Ｐは、上で述べたすべての基本構成要素の組合せであり、ユーザ（証明者）と検証者（たとえば署名者）を伴う対話型手順を使用して検証することができる。
【００８０】
［トレーシング・プロトコル］
［署名トレーシング・プロトコル］
所与の署名発行セッションから生じた特定の署名のトレースが望まれる時に、署名者は、その署名発行セッション中に観察された対（Ｅ1，Ｅ2）を信頼される機関に供給することができ、信頼される機関は、この暗号文を暗号化解除してＩsigを判定することができる。したがって、信頼される機関は、署名が問題の署名発行セッションから生じたかどうかを識別することができる。
【００８１】
［セッション・トレーシング・プロトコル］
特定の署名の生成をもたらした署名発行セッションのトレースが望まれる時に、署名者は、有効な署名からの対（Ｅ3，Ｅ4）を信頼される機関に供給することができ、信頼される機関は、この暗号文を暗号解除して、値Ｉｄuを判定することができ、この値Ｉｄuによって、この署名を入手したユーザが識別される。
【００８２】
［応用例］
本発明のフェア・ブラインド署名方式は、様々な応用で使用することができる。可能な応用例（本発明がこれらの例に制限されないことを理解されたい）としては、電子オークション、不正な金融取引のトレーシング、本願と同時に出願された、「フェア・ブラインド署名を用いた電子投票プロセス（Electronic Voting Process Using Fair Blind  Signatures）」と題する本出願人の同時係属の欧州特許出願に記載のものなどのオンライン投票方法などがある。
【００８３】
本発明は、フェア・ブラインド署名方式の実施に使用できる特定のソフトウェアおよびハードウェアに関して特に制限されない。当業者は、当技術分野での共通の一般的知識から、本発明を実施するのに適当なソフトウェア・ルーチンおよびハードウェアを選択する方法をすぐに理解するであろう。
【００８４】
しかし、本発明を、パーソナル・コンピュータ、ウェブ・サーバ、携帯情報端末、ネットワークＰＣ、適当な備えを有する携帯電話機など、協同して動作する、適当にプログラムされた汎用コンピューティング・デバイスの組を使用して実施できることに留意されたい。その代わりに、この署名方式の一部またはすべてを、特殊目的データ処理装置を使用して実施することができる。一般に、（それぞれの）署名者、（それぞれの）信頼される機関、およびそれぞれのユーザについて、１つのデータ処理／計算デバイスがある。しかし、この署名方式に含まれる様々なエンティティが、集中化デバイスではなく、あるサブルーチンまたはプログラム・モジュールが分散されたユニットで実行される分散コンピューティング・システムを利用できることを理解されたい。
【００８５】
本発明を、特定の好ましい実施形態に関して説明したが、請求項で定義される本発明から逸脱せずに、好ましい実施形態の様々な特徴を変更し、適合させ、かつ／または他の特徴によって置換することができることを、当業者はすぐに理解するであろう。
【００８６】
たとえば、本発明によるＦＢＳＳの上で説明した好ましい実施形態には、ユーザ登録フェーズが含まれるが、セッション・ログに基づいてターゲット署名の発行時刻を判定できることで十分と思われる場合には、これを省略することができる。言い換えると、「ユーザ・トレーシング」ではなく「セッション・トレーシング」を実行できることで十分である場合には、ユーザ登録フェーズを省略することができる。
【００８７】
さらに、好ましい実施形態を、上では単一の信頼される機関を使用するＦＢＳＳに関して説明したが、その代わりに信頼される機関の組を使用することができ、定足数の信頼される機関が協力する時に限って匿名性を取り消すことができることを、当業者はすぐに諒解するであろう（言い換えると、署名トレーシング・プロトコルおよびセッション・トレーシング・プロトコルが、単一の信頼される機関ではなく信頼される機関の組によって実施される）。複数の信頼される機関がある場合への上で説明したＦＢＳＳの拡張は、当業者には単純であり、したがって、本明細書では詳細に説明しない。望まれる場合に、複数の信頼される機関がある場合へのこの技法の拡張の方法の１つに関するガイダンスを、Ａ．シャミア（A. Shamir）著，「秘密共有方法（How to Share a Secret）」，ＡＣＭ通信の予稿集（Proc. of Communications of the ACM），ｐｐ．６１２−６１３，１９７９年を検討すれば得ることができる。
【００８８】
さらに、好ましい実施形態を、署名者として単一のエンティティを使用するＦＢＳＳに関して上で説明したが、その代わりにエンティティの組を使用して署名者を構成することができ、有効な署名を生成するためにユーザが必要とするデータが、定足数の署名者を構成するエンティティの協力によって得られることを、当業者はすぐに諒解するであろう。言い換えると、本発明は、閾値フェア・ブラインド署名方式（threshold fair blind signature scheme）として実施することができる。署名者がエンティティの組によって構成される場合への上で説明したＦＢＳＳの拡張は、当業者には単純であり、したがって、本明細書では詳細に説明しない。望まれる場合に、この拡張を実行する方法に関するガイダンスが、Ｐ−Ａ  フォーク（P-A Fouque），Ｊ．スタン（J. Stern）著，「標準的な仮定における完全分散スレショルドＲＳＡ（Fully distributed threshold RSA under standard assumptions）」，アジアクリプト’０１の予稿集（Proc. of Asiacrypt '01），コンピュータサイエンスの講義ノートの第２２４８巻（vol.2248 of Lecture Notes in Computer Science），ベルリン（Berlin），スプリンガー社(Springer-Verlag），ｐｐ３１０−３３０にある。
【００８９】
さらに、本発明が、署名方式にかかわる様々なエンティティの間でデータが渡される形に関して特に制限されないことを理解されたい。多くの応用で、このデータ伝送がインターネットを介して行われる可能性が高いが、これは、本発明の必要条件ではない。具体的には、他の通信ネットワーク（ＬＡＮ、ＷＡＮなどを含む）を使用することができる。
【図面の簡単な説明】
【００９０】
【図１】実施形態によるフェア・ブラインド署名方式を説明するためのブロック図である。
【図１】
2005253083.tif 000034