(57)【要約】【課題】仮署名スキームの一部を実現する方法及び装置が開示されている。【解決手段】一実施形態において、前記方法は、メッセージ上でオペレーションを行うことにより仮署名を生成する工程と、前記仮署名を完了してメッセージ上の最終署名を生成する工程とを含む。そのようなスキームは、サーバアシスト型署名スキーム、指定確認者署名スキーム、及び、ブラインド署名スキームに用いられてもよい。
2008512060.tif 000002
【特許請求の範囲】
【請求項１】
メッセージ上でオペレーションを実行して仮署名を生成する工程と、
前記仮署名を完了して前記メッセージ上で最終署名を生成する工程とを含む方法であって、
前記仮署名を生成する工程は、
第１の秘密シードを用いて第１の値ｘｉを生成する工程と、
第２の秘密シードを用いて第２の値ｃｉを生成する工程と、
ｍｉが、前記メッセージである場合に、
【数１】
2008512060.tif 000034
を満たす第３の値ｒｉを特定する工程と、
前記第３の値ｒｉを前記仮署名として出力する工程とを含むことを特徴とする方法。
【請求項２】
前記仮署名を完了する工程は、
前記仮署名のインデックスｉを受け取る工程と、
前記インデックスｉに応じて、対応する値
【数２】
2008512060.tif 000035
及びｈｉを取得する工程と、
前記最終署名
【数３】
2008512060.tif 000036
（ｍｉは、前記メッセージであり、ｒｉは、前記仮署名である。）を出力する工程とを含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記最終署名を検証する工程を更に含むことを特徴とする請求項１に記載の方法。
【請求項４】
前記最終署名を検証する工程は、
【数４】
2008512060.tif 000037
を計算する工程と、
【数５】
2008512060.tif 000038
であることを確認する工程と、
前記確認が取れた場合にのみ、前記最終署名を受け付ける工程とを含むことを特徴とする請求項３に記載の方法。
【請求項５】
メッセージ上でオペレーションを実行して仮署名を生成する工程と、
前記仮署名を完了して前記メッセージ上に最終署名を生成する工程とを含む方法であって、
前記仮署名を生成する工程は、
Ｍが、前記メッセージであり、ｒが、ランダム文字列である場合に、コミットメントＣ（Ｍ，ｒ）を、前記メッセージに対して生成する工程と、
Ｓｉｇ（Ｃ（Ｍ，ｒ））が、前記コミットメントＣ（Ｍ，ｒ）の署名を表す場合に、Ｓ＝Ｓｉｇ（Ｃ（Ｍ，ｒ））を生成する工程と、
Ｅが、強秘匿公開鍵暗号スキームである場合に、前記仮署名として、（Ｍ，Ｓ，ＥＰＫ，（ｒ））を出力する工程とを含むことを特徴とする方法。
【請求項６】
前記仮署名を確認する工程を更に含むことを特徴とする請求項５に記載の方法。
【請求項７】
前記仮署名を確認する工程は、
Ｍが、前記メッセージであり、ｒが、ランダム文字列であり、Ｓが、前記コミットメントＣ（Ｍ，ｒ）に署名することを表す場合に、Ｖｅｒ（Ｓ）が１に等しく、コミットメントＳｉｇ（Ｃ（Ｍ，ｒ））がＳに等しくなるような値ｒの知識についてのゼロ知識証明を実行する工程を含むことを特徴とする請求項６に記載の方法。
【請求項８】
前記仮署名を否認する工程を更に含むことを特徴とする請求項５に記載の方法。
【請求項９】
前記仮署名を否認する工程は、
Ｖｅｒ（Ｓ）が１に等しく、コミットメントＣ（Ｍ’，ｒ）がＳに等しく、Ｄｃｈ（Ｅｃｈ（ｒ））がｒに等しく、Ｍ’≠Ｍとなるようなｒ及びＭ’の知識についてのゼロ知識証明を実行する工程を含むことを特徴とする請求項８に記載の方法。
【請求項１０】
メッセージ上でオペレーションを実行して仮署名を生成する工程と、
前記仮署名を完了して前記メッセージ上に最終署名を生成する工程とを含む方法であって、
前記仮署名をメッセージ上でオペレーションを実行して生成する工程は、
ランダム値ｒを選択する工程と、
Ｍが、前記メッセージである場合に、コミットメントＣ（Ｍ，ｒ）と等しい値Ｘを計算する工程と、
前記値Ｘを署名者に送信する工程と、
前記値Ｘが前記コミットメントＣ（Ｍ，ｒ）に等しくなるような前記ランダム値ｒ及び前記メッセージＭの知識についてのゼロ知識証明を実行する工程と、
前記証明が成功した場合にのみ、前記値Ｘに署名して、Ｓｉｇ（Ｘ）を戻す工程と、
Ｓｉｇ（Ｘ）＝Ｓｉｇ（Ｃ（Ｍ，ｒ））である場合に、Ｍ上の前記仮署名を出力する工程とを含むことを特徴とする方法。
【請求項１１】
前記仮署名を完了し、前記メッセージ上に最終署名を生成することには、
第２のランダム値ｒ’を生成し、
前記メッセージＭ上の前記最終署名を（Ｃ（Ｓｉｇ（Ｃ（Ｍ，ｒ）），ｒ’））として出力することを含む、請求項１０に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本願は、「Ｍｅｔｈｏｄ  ａｎｄ  Ａｐｐａｒａｔｕｓ  ｆｏｒ  Ｐｒｏｖｉｓｉｏｎａｌ  Ｓｉｇｎａｔｕｒｅ  Ｓｃｈｅｍｅｓ，  Ｉｎｃｌｕｄｉｎｇ  Ｓｅｒｖｅｒ-Ａｓｓｉｓｔｅｄ，  Ｄｅｓｉｇｎａｔｅｄ  Ｃｏｎｆｏｒｍｅｒ，  ａｎｄ  Ｂｌｉｎｄ  Ｓｉｇｎａｔｕｒｅ  Ｓｃｈｅｍｅｓ」と題され、２００４年８月２７日に出願された、対応する米国仮特許出願第６０/６０５,２０６号に基づく優先権を主張する。
【０００２】
本発明は、暗号技術の分野に関する。特に、本発明は、サーバアシスト型デジタル署名を構築するための仮署名、指定確認者署名、及びブラインド署名スキームを含む仮署名スキームに関する。
【背景技術】
【０００３】
一般的なデジタル署名の分野で最も普及している署名スキームは、ＲＳＡ及び楕円曲線上のＵＳデジタル署名アルゴリズム（ＥＣＤＳＡ）である。適当なパラメータを有するＲＳＡアルゴリズムは、非常に高速で検証することができるが、署名を生成するのは遅い。また、ＲＳＡにおける署名は、少なくとも１キロバイトの大きさであるため、ＳＩＭカードや製品登録用としては不向きとなっている。
【０００４】
「オンライン／オフライン」のデジタル署名用のスキームが、Ｓｈａｍｉｒ及びＴａｕｍａｎによって提案されている（非特許文献１参照）。彼らのスキームは、カメレオンハッシュ関数を利用し、仮署名を効率的に生成するために用いることができる「ハッシュ-署名-切り換え」パラダイムを導入している。しかしながら、彼らは、彼らのスキームを、サーバアシスト方式で処理を行う場合に応用することについて考えなかった。
【非特許文献１】Ｓｈａｍｉｒ及びＴａｕｍａｎ著、「Ｉｍｐｒｏｖｅｄ  Ｏｎｌｉｎｅ-Ｏｆｆｌｉｎｅ  Ｓｉｇｎａｔｕｒｅ  Ｓｃｈｅｍｅ」、ＣＲＹＰＴＯ２００１
【非特許文献２】Ｐ.  Ｎｇｕｙｅｎ及びＪ.  Ｓｔｅｒｎ著、「Ｔｈｅ  Ｂｅｇｕｉｎ-Ｑｕｉｓｑｕａｔｅｒ  Ｓｅｒｖｅｒ-Ａｉｄｅｄ  ＲＳＡ  Ｐｒｏｔｏｃｏｌ  ｆｒｏｍ  Ｃｒｙｐｔ’９５  ｉｓ  ｎｏｔ  ｓｅｃｕｒｅ」、Ａｓｉａｃｒｙｐｔ  ９５、
【非特許文献３】Ｐ.  Ｂｅｇｕｉｎ及びＪ.  Ｊ.   Ｑｕｉｓｑｕａｔｅｒ著、「Ｆａｓｔ  ｓｅｒｖｅｒ-ａｉｄｅｄ  ＲＳＡ  ｓｉｇｎａｔｕｒｅｓ  ｓｅｃｕｒｅ  ａｇａｉｎｓｔ  ａｃｔｉｖｅ  ａｔｔａｃｋｓ」、ＣＲＹＰＴ  １９９５
【非特許文献４】Ｍ.   Ｊａｋｏｂｓｓｏｎ及びＳ.   Ｗｅｔｚｅｌ著、「Ｓｅｃｕｒｅ  Ｓｅｒｖｅｒ-Ａｉｄｅｄ  Ｓｉｇｎａｔｕｒｅ  Ｇｅｎｅｒａｔｉｏｎ」、Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｐｒａｃｔｉｃｅ  ａｎｄ  Ｔｈｅｏｒｙ  ｉｎ  Ｐｕｂｌｉｃ  Ｋｅｙ  Ｃｒｙｐｔｏｇｒａｐｈｙ、２００１年
【非特許文献５】Ｂｉｃａｃｋｉ及びＢａｙａｌ著、「Ｓｅｒｖｅｒ  Ａｓｓｉｓｔｅｄ  Ｓｉｇｎａｔｕｒｅｓ  Ｒｅｖｉｓｉｔｅｄ」、ＲＳＡ  Ｃｒｙｐｔｏｇｒａｐｈｅｒｓ’  Ｔｒａｃｋ  ２００３
【非特許文献６】Ｖ.   Ｇｏｙａｌ著、「Ｍｏｒｅ  Ｅｆｆｉｃｉｅｎｔ  Ｓｅｒｖｅｒ  Ａｓｓｉｓｔｅｄ  Ｓｉｇｎａｔｕｒｅｓ」、Ｃｒｙｐｔｏｇｒａｐｈｙ  Ｅｐｒｉｎｔ  Ａｒｃｈｉｖｅ、２００４年
【非特許文献７】Ｓ.   Ｇｏｌｄｗａｓｓｅｒ及びＥ.   Ｗａｉｓｂａｒｄ著、「Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅ  Ｓｃｈｅｍｅ  ｉｎｔｏ  Ｄｅｓｉｇｎａｔｅｄ  Ｃｏｎｆｉｒｍｅｒ  Ｓｉｇｎａｔｕｒｅ  Ｓｃｈｅｍｅｓ」、２００４年
【発明の開示】
【発明が解決しようとする課題】
【０００５】
サーバアシスト型のデジタル署名では、別のサーバを利用して署名に要求される計算処理及び通信のオーバーヘッドを減らすことが望ましい。これは、サーバアシスト型署名（ＳＡＳ：Ｓｅｒｖｅｒ  Ａｓｓｉｓｔｅｄ  Ｓｉｇｎａｔｕｒｅｓ）として公知である。もちろん、効率的なデジタル署名が望まれ、第三者が利用可能であるいくつかのシナリオが想定可能である。署名者の通信及び計算を減らすという問題は、最も現実的な関心事である。なぜならば、それによって、より効率的なエネルギー利用が可能となり、移動通信機器の寿命が延びるからである。先行して提案されたＳＡＳの多くは、安全でないことが分かっているし、署名ごとに大容量データの通信が署名者に要求されたり、クライアントごとに大容量の状況を記憶することがサーバに要求されたりするものもある。
【０００６】
ＳＡＳの応用例に、製品登録がある。署名者は、認証鍵をソフトウェアや新規に購入した電話機に配布したいと希望しているかもしれない。検証者は、サーバに対して接続性を有すると考えられるソフトウェア自体を含む。認証鍵は、ソフトウェア自体の署名及びシリアル番号によって構成されている。さらに、デジタル署名は、ソフトウェアと共に出荷される用紙又はラベル上にタイプされる。
【０００７】
ＳＡＳの応用の他の例として、ＵＩＭカードがある。ＵＩＭカードは、プロセッサ及び小容量のストレージを含むスマートカードである。ＵＩＭカードは、電話から電話へ又は電話からパソコンへ等というように機器から機器へ移動する際に、ユーザに、単一のアイデンティティを保持させることができる。また、ＵＩＭカードは、ＲＳＡを使用してユーザをウェブサイトに対して認証する「ＦｉｒｓｔＰａｓｓ ＳＳＬのクライアント認証」において用いられている。現在のＵＩＭカードには、ＲＳＡデジタル署名を実行するための特殊用途プロセッサが必要であり、署名ごとに１/２秒程かかる。さらに、ＲＳＡ秘密鍵は、ＵＩＭカード上に１キロバイトの容量をとり、そのため、カード上の鍵の数は、５つに制限される。
【０００８】
サーバアシスト型署名の問題に対する従来の解決策には、いくつかの欠点があった。Ｂｅｇｕｉｎ及びＱｕｉｓｑｕａｔｅｒによるスキームは、Ｎｇｕｙｅｎ及びＳｔｅｒｎによって安全でないことが示されている。そのため、実用向きとは考えられない（詳細については、非特許文献２及び非特許文献３参照）。Ｊａｋｏｂｓｓｏｎ及びＷｅｔｚｅｌによる方法は安全そうであるが、その使用は、ＤＳＡ及びＥＣＤＳＡのみに限定されている。なぜならば、署名は、少なくとも３２０ビットの大きさがあるからである（非特許文献４参照）。Ｂｉｃａｃｋｉ及びＢａｙａｌによるスキームでは、サーバは、署名ごとの署名者当たり、５キロバイトを記憶するように要求される（非特許文献５参照）。例えば、署名者当たり、１日に１０個の署名を生成する８０００万人の署名者がいたとすると、これには、大まかに見積もって、一日当たり、３．７テラバイトを記憶しなければならない。Ｇｏｙａｌのスキームは、この問題に取り組んでおり、署名当たり、４８０バイトのサーバストレージを必要としている（非特許文献６参照）。８０００万人の署名者で、１日当たり１０個の署名があれば、このスキームでは、１日に、大まかに見積もっても、３５７ギガバイトが必要である。
【０００９】
さらに悪いことに、両方のスキームにおいて、サーバが記憶しなければならないデータ量は、限界なく増加する。これは、サーバが、不正行為を働いたとして、ある署名者から告訴された場合に備えて、データが保持されているからである。そのため、サーバが告訴される可能性がないと確信できるまで、実際に、何カ月も、又は、何年も、データを保持しなければならない。「時効」を1年間と仮定すると、Ｇｏｙａｌのスキームでは、１２７テラバイトのサーバストレージが必要となる。何れかのデータが欠けていたり、署名に不備があったりした場合、サーバは、自らが正しく行動したことを証明できなくなってしまう。
【００１０】
Ｇｏｙａｌ及びＢｉｃａｃｋｉ-Ｂａｙａｌのスキーム双方における他の欠点は、署名者が、１つ１つのメッセージごとに、１回限りの署名に対する公開鍵をサーバに送信しなければならないことである。Ｇｏｙａｌの論文で提案された実施形態では、署名ごとの通信に２６キロバイトが要求される。この容量の大きい通信は、製品登録への応用を不可能なものにしている。
【００１１】
署名の他の種類として、「指定確認者署名（ｄｅｓｉｇｎａｔｅｄ  ｃｏｎｆｉｒｍｅｒ  ｓｉｇｎａｔｕｒｅ）がある。指定確認者デジタル署名では、メッセージ上の署名について、特別な「指定確認者」の支援なしで検証することはできない。署名者は、署名が生成されると、指定確認者を選択する。指定確認者は、署名をとり、署名が本物であるかを確認、又は、署名者によって実際に生成されたものでない署名を否認するが、かかる指定確認者は、新規の署名を生成できない。また、かかる指定確認者は、署名を、誰もが検証できる通常の署名に変換することもできる。
【００１２】
指定確認者を使用する応用例に、電子契約の署名がある。求職者及び雇用主になる可能性のある者が、雇用契約の交渉を物理的に同じ部屋に居合わせることなく行うことができる。雇用主は、従業員に他の雇用主候補との取引材料として契約書を使って欲しくないと考えるだろう。そのため、雇用主は、指定確認者の署名を用いて署名することができ、裁判所を、かかる指定確認者として指定することができる。争議が生じた場合、そのようにして署名を検証することができるが、その一方で、他の雇用主が署名を検証することはできない。
【００１３】
指定確認者を利用する応用例には、ソフトウェアパッチの検証がある。ソフトウェアのベンダーは、ソフトウェアパッチの使用を、ソフトウェアを正規に購入したユーザだけに制限したいと考えている。この制限を実現する１つの方法として、指定確認者署名スキームでパッチに署名し、登録ユーザだけに確認したことを知らせる方法がある。未登録のユーザは、署名を検証することができず、危殆化したソフトウェアパッチをインストールするリスクを負うことになる。
【００１４】
最近では、指定確認者デジタル署名を実装するには、ＲＳＡ等のアルゴリズムの特殊用途プロパティを用いる。これらの特定のアルゴリズムが安全でないと分かった場合、これらのスキームも安全ではない。Ｇｏｌｄｗａｓｓｅｒ及びＷａｉｓｂａｒｄは、いくつかの既存の署名スキームを、指定確認者署名スキームに変換する方法を開示している（非特許文献７参照）。
【００１５】
他の署名の種類として、「ブラインド署名（ｂｌｉｎｄ  ｓｉｇｎａｔｕｒｅ）」がある。ブラインド署名では、署名者は、メッセージＭの「ブラインドされた」バージョンＸに署名する。ブラインドされたバージョンＸは、ブラインド要素ｒを用いて生成される。「ブラインダ（ｂｌｉｎｄｅｒ）」は、メッセージＭを署名者に明らかにすることなく、Ｍ上の署名を取得したいと考えている。これは、署名者に対して、ＭのブラインドされたバージョンであるメッセージＸに署名するようにブラインドした状態で依頼することで、実現できる。署名後、署名は、ブラインド要素を使ってＭ上の署名を取得するために「ブラインドをはずす」ことができる。ブラインド要素なしでは、ブラインドされたメッセージＸ上の署名をブラインドされていないメッセージＭとリンクさせることは不可能である。Ｘ上の署名から、ブラインダは、Ｍ上の署名を回復することができる。Ｘ上の署名は、「仮署名」であり、また、Ｍ上の署名は、「最終署名」である。
【００１６】
ブラインド署名の応用例として、リンクができない電子キャッシュトークンがある。銀行でさえ異なる取引を追跡できないことを保証することで、ユーザのプライバシーを強化することが目的である。ユーザは、ある額面に対してトークンを生成し、そのトークンをブラインドする。銀行は、ブランドされたトークンに署名し、それをユーザに戻す。そして、ユーザは、ブラインドをはずし、トークン上の銀行の署名を取得する。トークンと、トークン上の銀行の署名により、ユーザは、金融取引に参加することができる。なぜならば、第三者が銀行の署名を確認することができるからである。一方、銀行は、ブラインドされたトークンに署名したため、トークンをユーザまで追跡することはできず、ユーザに匿名性を与える。不正行為を行うユーザを防ぐために、ユーザが、１００以上の同じ額面のトークンを生成し、銀行が、最後のトークンに署名する前に、１００のトークンのうちランダムに選択した９９のトークンを見せてもらうように依頼する「切断選択法（ｃｕｔ-ａｎｄ-ｃｈｏｏｓｅ）」を用いてもよい。
【課題を解決するための手段】
【００１７】
仮署名スキームの一部を実現する方法及び装置が開示されている。一実施形態において、かかる方法は、メッセージ上でオペレーションを行うことにより仮署名を生成する工程と、仮署名を完了してメッセージ上の最終署名を生成する工程とを有する。そのようなスキームは、サーバアシスト型署名スキーム、指定確認者署名スキーム、及びブラインド署名スキームに用いられてもよい。
【発明を実施するための最良の形態】
【００１８】
本発明は、以下に詳細な説明及び本発明の様々な実施形態の添付図からより完全に理解できるであろう。しかし、それらは、本発明を特定の実施形態に限定するためのものあると考えられるべきでなく、説明と理解のためだけのものであると考えられるべきである。
【００１９】
仮署名スキームを説明する。特に、署名者は、第三者のサーバによって「最終署名」に変換される「仮署名」を生成する。これらの最終署名は、検証者によって検証することができる。一実施形態では、第三者のサーバが、危殆化している、又は、不具合を起こしている可能性を相殺するために、サーバ自体は、文書に署名できず、署名者によって生成された仮署名を変換できるだけである。一実施形態では、サーバは、ほとんど計算を行わず、大勢の署名者を取り扱うことができるように、署名ごとに小さい容量のデータだけを記憶する。
【００２０】
仮署名スキームには、サーバアシスト型署名スキーム、指定確認者署名スキーム、及びブラインド要素スキームが含まれる。一実施形態では、サーバアシスト型署名スキームは、製品登録や装置の計算負荷軽減用に使用されている。一実施形態では、指定確認者署名スキームは、デジタル契約の公正な取引に使用されている。一実施形態では、ブラインド署名スキームは、匿名の電子キャッシュを生成するために使用されている。
【００２１】
本発明の複数の実施形態には、署名者やサーバや検証者の計算要件、及び、これらが通信するチャネルの帯域要件の点で、効率的で安全なサーバアシスト型署名用スキームが含まれる。本発明の一実施形態では、かかるスキームが、署名ごとに１６０バイトだけという署名者の通信の複雑度を有する。かかる通信の複雑度は、以前のＳＡＳスキームより大幅に改善された水準である
一実施形態において、本明細書においてＵＩＭカードを使用するとして説明されているＳＡＳ法では、秘密鍵ごとに必要なスペースは、１２８ビットだけであるため、特殊用途の共同プロセッサを使用しなくても高速署名が可能となっている。
【００２２】
以下の説明において、本発明をより完全に説明するために、多くの詳細を記載する。しかしながら、当業者においては、本発明は、これらの特定の詳細なしで実施することが可能であることが自明であろう。また、公知の構造及び装置については、本発明が不明瞭になることを避けるために、詳細を示すのではなくブロック図の形式で示した。
【００２３】
以下に続く詳細な説明のいくつかの箇所は、アルゴリズムやコンピュータメモリ内のデータビットにおけるオペレーションの記号による表現で表されている。これらのアルゴリズム的な説明及び表現方法は、データ処理技術の分野の技術者によって利用される手段であり、彼らの仕事内容を他の技術者に最も効果的に伝えるものである。ここでのアルゴリズムは、一般的に、所望する結果へ導く自己無撞着一連のステップであると考えられている。これらのステップには、物理量の物理的な操作が必要である。通常、必ず必要であるという訳ではないが、これらの量は、記憶、転送、結合、比較が可能、又は、その他の操作が可能な電気的、又は、磁気的信号の形式をとる。主に共同利用のために、これらの信号をビット、値、エレメント、シンボル、特徴、用語、数などとして参照することが時々便利であると証明されている。
【００２４】
しかしながら、これら全ての又は同様の用語が、適当な物理量に関連付けられ、これらの物理量に適用した便利なラベルに過ぎないことを留意する必要がある。以下の議論から明らかなように、特別に言及しない限り、明細書を通して、「処理する（ｐｒｏｃｅｓｓｉｎｇ）」、「計算する（ｃｏｍｐｕｔｉｎｇ）」、「計算する（ｃａｌｃｕｌａｔｉｎｇ）」、「決定する（ｄｅｔｅｒｍｉｎｇ）」、「表示する（ｄｉｓｐｌａｙｉｎｇ）」等の用語を利用する議論では、コンピュータシステムのレジストリやメモリ内の物理的（電気的）量として表されるデータを操作し、コンピュータシステムメモリ、レジストリ、他の情報ストレージ、或いは、通信又は表示装置内の物理量として同様に表される他のデータに変換するコンピュータシステムのアクションやプロセス、又は、同様の電子計算装置を意味すると考えられる。
【００２５】
本発明は、本明細書においてオペレーションを実行する装置にも関する。この装置は、要求される目的のために特別に構成されてもよいし、コンピュータに記憶されたコンピュータプログラムによって選択的に稼働させたり、又は、再構築されたりした汎用コンピュータによって構成してもよい。限定される訳ではないが、フロッピィディスク、光学ディスク、ＣＤ−ＲＯＭ、及び光磁気ディスクなどのコンピュータで読み取り可能な記憶媒体、読み取り専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気、又は、光学カード、又は、電気的命令を記憶するのに適している全ての種類の媒体、及びコンピュータシステムバスに連結されたそれぞれに、そのようなコンピュータプログラムを記憶してもよい。
【００２６】
本明細書に表すアルゴリズムや表示は、本質的に、特定のコンピュータ、又は、その他の装置に関するものではない。様々な汎用コンピュータシステムは、本明細書の教示に従ってプログラムを使って使用しても、又は、必要な方法のステップを実行するためにより特定した装置を構成することが都合よいことを証明してもよい。様々なこれらのシステムの必要な構造は以下の説明から明らかとなる。また、本発明の説明に特定のプログラム言語を参照することはしないが、様々なプログラム言語を、本明細書に説明したように、本発明の教示を実施するために使用してもよいことが理解されよう。
【００２７】
機械で読み取り可能な媒体には、情報を機械（例えば、コンピュータ）で読み取り可能な形式で記憶したり、送信したりする、どのメカニズムも含まれる。例えば、機械で読み取り可能な媒体には、読み取り専用メモリ（「ＲＯＭ」）、ランダムアクセスメモリ（「ＲＡＭ」）、磁気ディスクストレージ媒体、光学ストレージ媒体、フラッシュメモリ装置、電気的、光学的、音響的、又は、他の形式の伝搬シグナル（例えば、キャリアウェーブ、赤外信号、デジタル信号等）等が含まれる。
【００２８】
＜定義及び仮定＞
本明細書の目的にとって、関数ｆ（ｎ）は、多項式関数ｑ（ｎ）に対して、全てのｎ＞ｎ０に対してｆ（ｎ）＜１/ｑ（ｎ）となるような値ｎ０が存在する場合、無視してもよい。そのような無視可能な関数の例としては、ｆ（ｎ）＝１/２ｎがある。
【００２９】
ａ及びｂが、ａ≦ｂである２つの整数である場合、［ａ，ｂ］は、ａ以上ｂ以下の間の整数の集合を表す。すなわち、［ａ，ｂ］＝｛ｃ∈Ｚ｜ａ≦ｃ≦ｂ｝である。
【００３０】
Ｓが、エレメントｓの集合であり、Ｄが、Ｓにおけるサンプル可能な確率分布である場合、分布Ｄに従って、Ｓからエレメントｓを取るプロセスは、
【数１】
2008512060.tif 000003
【００３１】
で表される。
【００３２】
多くの暗号技術の安全性が、ある計算処理が難しくなるような仮定を作ることに依拠することは、当業者には公知である。例えば、特定の番号を素因数に効率的に分解することが難しい限り、暗号システムが安全であることを証明しようとすることができる。「計算による（ｃｏｍｐｕｔａｔｉｏｎａｌ）」という用語を、暗号技術のこのクラスを確認するために用いられることがよくある。一実施形態において、本明細書に説明した本発明の実施形態の安全性を証明することに関する仮定の集合を以下に説明する。
【００３３】
＜離散対数の仮定＞
群Ｇにおける離散対数の仮定は、群のジェネレータｇが与えられており、値ｙ＝ｇｘが与えられており、計算によって、ｘを得ることが困難であることを示している。我々は、楕円曲線の有理点の群に特別な関心を寄せている。離散対数問題を定義する標準的な数学的群を構成する。そのような楕円曲線群の位数ｑに対して、離散対数を見つけるための公知の最良の手法では、時間
【数２】
2008512060.tif 000004
【００３４】
が必要とされる。
【００３５】
＜カメレオンハッシュ関数＞
カメレオンハッシュ関数は、公開鍵ＰＫｃｈ及び確率的多項式の時間アルゴリズムＧ（１ｋ）によって生成される秘密鍵ＳＫｃｈによって定義される関数ＣＨ（ｍ，ｒ）である。公開鍵ＰＫｃｈが与えられているので、ＣＨ（ｍ，ｒ）を評価することは容易である。秘密鍵無しでは、ＣＨ（ｍ，ｒ）＝ＣＨ（ｍ’，ｒ’）となるようなタプル（ｍ，ｍ’，ｒ，ｒ’）を見つけることは困難である。一方、秘密鍵が有れば、ｍ，ｍ’及びｒが与えられているので、ＣＨ（ｍ，ｒ）＝ＣＨ（ｍ’，ｒ’）となるようなｒ’を見つけることは容易である。
【００３６】
カメレオンハッシュ関数の特定のファミリは、離散対数の仮定が以下のように保持する位数ｑの群Ｇに対して、定義されている。秘密鍵ＳＫｃｈは、
【数３】
2008512060.tif 000005
【００３７】
における均一なランダム値ｘであるが、公開鍵は、値ｈ＝ｇｘである。ＣＨ（ｍ，ｒ）が、ＣＨ（ｍ，ｒ）＝ｇｘｈｒとなるように定義されている。特定群の事例について、Ｇは、適切に選択された楕円曲線上の点の群である。パラメータを適切に選択することによって、出力の長さが１６０ビットのカメレオンハッシュを取得する。本明細書に説明した本発明の実施形態には、このカメレオンハッシュ関数を利用することが含まれるが、他のカメレオンハッシュ関数を用いてもよいことが、当業者には明らかであろう。
【００３８】
＜疑似ランダムジェネレータ＞
疑似ランダムジェネレータＧは、入力としてビットの短いランダムシードを取り、ｋビットの文字列を出力する。ここで、ｋ＞ｓとする。出力文字列は、ランダム文字列から区別することができないという意味において疑似ランダムである。
【００３９】
＜ビットコミットメントスキーム＞
ビットコミットメントスキームＣ（Ｍ，ｒ）は、統計学的に隠れており、計算により結合しているというプロパティを満たす。「統計学的に隠す」とは、無視できる確率を除いて、ｒを知らなければ、Ｃ（Ｍ，ｒ）からＭを回復することができる敵は、たとえ、どんなに強い敵であっても、いないということである。「計算により結合している」とは、コミットメントＣ（Ｍ，ｒ）は、確率的な多項式の時間アルゴリズムによって、値Ｍ’≠Ｍに開くことはできないということである。
【００４０】
＜概要＞
図１は、仮署名プロセスの一実施形態の流れ図である。ハードウェア（例えば、回路、専用ロジック等）、ソフトウェア（汎用コンピュータシステムや専用マシーン上で作動するもの等）、又は、その両方の組み合わせを含んでもよい処理ロジックによって、このプロセスを実行してもよい。
【００４１】
図１を参照すると、メッセージ上のオペレーションを実行して仮署名を生成する処理ロジックによって始まる（処理ブロック１０１）。次に、処理ロジックは、仮署名を完成させ、メッセージ上に最終署名を生成する（処理ブロック１０２）。処理ブロック１０１及び処理ブロック１０２は、共に、１つ又は２つの秘密鍵を使用して実行される。最終署名が完了してから、処理ロジックは、最終署名を検証する（処理ブロック１０３）。
【００４２】
図２は、検証者プロセスの一実施形態の流れ図である。図２を参照すると、本明細書に説明する仮署名プロセスを利用することで生成された署名は、かかる署名、メッセージｍ及び公開鍵を検証者に入力し、かかる署名が有効かどうかの表示（例えば、Ｙｅｓ/Ｎｏ）を受け取ることによって検証される。
【００４３】
本明細書に説明する仮署名は、サーバアシスト型署名スキーム、指定確認者署名スキーム、及びブラインド署名スキームに適用されてもよい。これらのスキームの実施形態を以下に説明する。
【００４４】
＜サーバアシスト型署名のためのシステム例＞
一実施形態において、署名者と検証者とサーバとの間でデータを通信するシステムは、サーバアシスト型の署名を提供する。署名者は、仮署名を生成し、生成した仮署名を通信ネットワーク上で検証者に送信する。検証者は、仮署名を通信ネットワーク上でサーバに送信する。その後、検証者は、サーバから最終署名を受信し、結果としての最終署名を検証する。サーバは、仮署名を最終署名に変換し、その最終署名を通信ネットワーク上で検証者に送信する。
【００４５】
署名者、検証者及びサーバのそれぞれには、ハードウェア（例えば、回路、専用ロジック等）、ソフトウェア装置（例えば、汎用コンピュータシステムや専用マシーン上で作動するもの等）、又は、その両方の組み合わせを含んでもよい処理ロジックを有するコンポーネントが含まれている。図３は、そのようなコンポーネントの一実施形態を図示している。図３を参照すると、コンポーネント３００には、プロセッサ３０１、メモリ３０２、ネットワークインターフェイス３０３が含まれている。プロセッサ３０１は、メモリ３０２及びネットワークインターフェイス３０３に連結される。
【００４６】
署名者は、処理ロジックを有するプロセッサロジック３０１を含む。これにより、署名者は、外部ネットワークインターフェイス３０３を通してメッセージを受け取り、仮署名を生成する方法を適用し、その結果、メッセージ上の仮署名を取得する。
【００４７】
検証者は、処理ロジックを有するプロセッサ３０１を含む。これにより、署名者は、外部ネットワークインターフェイス３０３を通してメッセージ及び最終署名を受信し、署名を検証する方法を適用し、その結果、表示された署名者にそのメッセージが由来しているという確信を得る。
【００４８】
サーバは、処理ロジックを有するプロセッサ３０１を含む。これにより、サーバは、ネットワークリクエストの一部としての入力として、外部ネットワークインターフェイス３０３を通して仮署名を受信する。そして、サーバは、仮署名を最終署名に変換する方法によって与えられた出力をネットワーク３０４に送信する。
【００４９】
図５は、サーバアシスト型デジタル署名技術用の鍵生成プロセスの一実施形態の流れ図である。プロセスは、ハードウェア（例えば、回路、専用ロジック等）、ソフトウェア（汎用コンピュータシステムや専用マシーン上で作動するもの等）、又は、その両方の組み合わせを含んでもよい処理ロジックによって実施されてもよい。
【００５０】
図５を参照すると、プロセスは、セキュリティパラメータｋ及びいくつかの署名Ｓ（処理ブロック５０１）を特定する処理ロジックにより開始される。次に、処理ロジックは、ランダムな１６０ビットの楕円曲線を、ジェネレータ点ｇと共に生成する（処理ブロック５０２）。ジェネレータを選択する標準的な技術がある。例えば、１つの手法としては、ランダムエレメントをとり、偶然にも有効なジェネレータでないかどうかを確認する。一実施形態において、この曲線及びジェネレータは、システムにおける全てのエンティティに対して使用する。本明細書の目的として、及び、慣習との決別として、楕円曲線上の点の群は、乗法的な群として表記されている。そのような表記を、どのように標準付加表記へ変換するのかについては、当業者には明らかであろう。なお、他の楕円曲線を用いることもできることに留意されたい（例えば、１６１ビットの楕円曲線、１０２４ビットの有限フィールド）。一般的には、スキームは、離散対数が難しい、どの代数群も用いることができ、ジェネレータｇは、その群に由来しなければならない。
【００５１】
曲線及びジェネレータが生成された後、処理ブロックは、ランダムに、２つのシードｓ１及びシードｓ２を均一に選択する（処理ブロック５０３）。次に、処理ロジックは、１≦ｉ≦Ｓである場合、ランダムシードｓ１でシードされるＰＲＧの連続出力として、値ｘｉの数列を生成し（処理ブロック５０４）、１≦ｉ≦Ｓとである場合、ランダムシードｓ２でシードされるＰＲＧの連続出力として、値ｃｉの数列を生成する（処理ブロック５０５）。一旦、２つの数列が生成されると、処理ロジックは、１≦ｉ≦Ｓである場合、値ｈｉ＝ｇｘｉの数列を計算する（処理ブロック５０６）。そして、処理ロジックは、標準署名スキーム用の鍵のペア（ＳＫ，ＰＫ）を計算する（処理ブロック５０７）。秘密鍵ＳＫは、Ｓ個の署名
【数４】
2008512060.tif 000006
【００５２】
の数列を生成するために用いられる。
【００５３】
一旦計算が終了すると、処理ロジックは、シードｓ１及びシードｓ２を署名者に送信し（処理ブロック５０８）、値ｈｉ及び値Ｓｉｇｉをサーバに送信する（処理ブロック５０９）。また、処理ロジックは、署名者の公開鍵として、公開鍵ＰＫを、ｇ及びサーバのアドレスと共に発行する。
【００５４】
図６は、サーバアシスト型署名スキームに用いられる仮署名生成プロセスの一実施形態の流れ図である。プロセスは、ハードウェア（例えば、回路、専用ロジック等）、ソフトウェア（汎用コンピュータシステムや専用マシーン上で作動するもの等）、又は、その両方の組み合わせを含んでもよい処理ロジックを含んでもよい処理ロジックによって実行されてもよい。一実施形態において、処理ロジックは、署名者の一部である。
【００５５】
図６を参照すると、かかるプロセスは、秘密シードｓ１を用いて値ｘｉを生成する処理ロジックによって始まり（処理ブロック６０１）、秘密シードｓ２を用いて値ｃｉを生成する（処理ブロック６０２）。次に、処理ロジックは、
【数５】
2008512060.tif 000007
【００５６】
となるようなｒｉを見つけ（処理ブロック６０３）、ｒｉをメッセージｍｉの仮署名として出力する（処理ブロック６０４）。
【００５７】
図７は、サーバアシスト型署名スキームの仮署名終了プロセスの一実施形態の流れ図である。プロセスは、ハードウェア（例えば、回路、専用ロジック等）、ソフトウェア（汎用コンピュータシステムで走っているようなもの、又は、専用マシーン等）、又は、その組み合わせを含んでもよい処理ロジックにより実行されてもよい。一実施形態において、処理ロジックは、サーバの一部である。
【００５８】
図７を参照すると、プロセスは、仮署名ｒｉのインデックスｉを受信する処理ロジックにより開始される（処理ブロック７０１）。次に、処理ロジックは、署名
【数６】
2008512060.tif 000008
【００５９】
及びｈｉに対応する数列の値を調べて戻し（処理ブロック７０２）、最終署名
【数７】
2008512060.tif 000009
【００６０】
を出力する（処理ブロック７０３）。
【００６１】
図８は、サーバアシスト型署名スキーム用の最終署名の検証プロセスの一実施形態の流れ図である。プロセスは、ハードウェア（例えば、回路、専用ロジック等）、ソフトウェア（汎用コンピュータシステムや専用マシーン上で作動するもの等）、又は、その両方の組み合わせを含んでもよい処理ロジックによって開始されてもよい。一実施形態において、処理ロジックは、検証者の一部である。
【００６２】
図８を参照すると、プロセスは、
【数８】
2008512060.tif 000010
【００６３】
を計算する処理ロジックにより開始され（処理ブロック８０１）、ＶＰＫ（Ｓｉｎｇ（ｇｉｈｉ））＝１を確認することで署名を検証する（処理ブロック８０２）。次に、処理ロジックは、かかる確認が取れた場合、及び、かかる確認が取れた場合のみに有効であるとして署名を受け付ける（処理ブロック８０３）。
【００６４】
或いは、サーバアシスト型署名スキームは、「ハッシュ-署名-切り換え」パラダイムを用いて選ばれたメッセージ攻撃下に存在する偽造に対して安全な基礎となる署名スキームを変換する、サーバアシスト型の１回だけの署名スキームと見なすこともできる。既存の署名スキーム（Ｇｅｎ，Ｓｉｇ，Ｖｅｒ）は、適応性のある選ばれたメッセージの攻撃下に存在する偽造に対して安全であり、合計Ｓ個の署名が署名されると考えられている。
【００６５】
１．鍵生成：  まず、基礎となる署名スキームに対して、鍵ペアＰＫｓｉｇ及びＳＫｓｉｇを生成する。そして、シードｓ１を有するＰＲＧを用いて、ｉに対して１からＳまでのカメレオンハッシュ鍵ペア
【数９】
2008512060.tif 000011
【００６６】
の数列を生成する。最後に、シードｓ２及びシードｓ３を用いて、疑似ランダム値ｖ１、・・・、ｖｓ、及び、疑似ランダム値ｗ１、・・・、ｗｓを生成する。変数ｃｉは、ｃｉ＝ＣＨｉ（ｗｉ，ｖｉ）、すなわち、カメレオンハッシュ鍵
【数１０】
2008512060.tif 000012
【００６７】
下の（ｗｉ，ｖｉ）のカメレオンハッシュとなるように定義されている。ＳＫｐｒｏｖは、シードｓ１及びシードｓ２からなり、一方、ＳＫｃｏｍｐ値は、
【数１１】
2008512060.tif 000013
【００６８】
からなる。公開鍵ＰＫは、ＰＫｓｉｇ及びサーバのアドレスからなる。
【００６９】
２．ＰｒｏｖＳｉｇｎ：  次の値ｉのために、（Ｍ，ｉ）を入力し、ｓ１を用いて、
【数１２】
2008512060.tif 000014
【００７０】
を計算し、ｓ２を用いて、ｖｉを計算し、ｓ３を用いて、ｗｉを計算する。そして、ＣＨｉ（Ｍｉ，ｒｉ）＝ＣＨi（ｖi,ｗi）となるようなｒｉを計算する。ｒｉを、Ｍ上の仮署名として戻す。値ｉを使用済みとして印を付ける。
【００７１】
３．完了：  入力（±，ｉ）において、
【数１３】
2008512060.tif 000015
【００７２】
を戻す。そして、最終署名は、
【数１４】
2008512060.tif 000016
【００７３】
である。
【００７４】
４．検証：
【数１５】
2008512060.tif 000017
【００７５】
を入力し、
【数１６】
2008512060.tif 000018
【００７６】
の場合のみ、署名を有効として受け付ける。
【００７７】
終了オペレーションであるＳＫｃｏｍｐ用の「秘密鍵」全体を、敵に最終署名を偽造させることなく明らかにすることができることに留意されたい。従って、このサーバアシスト型署名スキームにおけるサーバは、攻撃的に複製されてもよい。さらに、サーバは、計算を実行せず、単に、静的な読み取り専用値ＰＫｃｈ及びＳｉｇ（ｃ，ＰＫｃｈ）を戻すだけである。
【００７８】
一実施形態において、署名者と検証者とサーバアシスト型デジタル署名を行うサーバとの間でデータ通信を行うためのシステムには、仮署名を生成可能なクライアントコンポーネント、仮署名を終了して最終署名を生成することが可能なサーバコンポーネント、及び、最終署名を検証可能な検証コンポーネントが含まれる。
【００７９】
一実施形態において、サーバアシスト型署名スキームを実行する署名者、検証者及びサーバのそれぞれは、ハードウェア装置（例えば、回路、専用ロジック等）、ソフトウェア装置（汎用コンピュータシステムや専用マシーン上で作動するもの等）、又は、処理ロジックを実行可能な、その両方の組み合わせであってもよい。これらのコンポーネントのそれぞれは、図３に示すコンポーネントとして実装されてもよい。サーバアシスト型の署名者は、仮署名のリクエストを受信するために外部ネットワークインターフェイスと、仮署名を生成して外部ネットワークを介して仮署名を依頼者に戻すために外部ネットワークインターフェイス及びメモリに連結されているプロセッサとを用いる。サーバアシスト型の署名検証者コンポーネントは、外部ネットワークインターフェイスを使って最終署名を受信する。サーバアシスト型署名サーバコンポーネントは、仮署名を受信するために外部ネットワークインターフェイスと、サーバアシスト型署名スキームの完了した最終署名をネットワークに送信するために外部ネットワークインターフェイス及びメモリに連結されているプロセッサとを用いる。
【００８０】
サーバアシスト型署名スキームの一実施形態におけるカメレオン関数は、ＣＨ（ｍ，ｒ）＝ｇｘｈｒである。そのような場合、署名者ストレージは、以下の説明に用いる変数「ｉ」を表すために、１２８ビットの長さのシードｓ及び２０ビットの長さのカウンタのみを記憶する必要がある。よって、署名者ストレージの合計は、署名の数に関係なく１４８ビットである。ＲＳＡのような最新の公開鍵署名スキームでは、もっと大きいサイズの秘密鍵が要求されることに留意されたい。署名者の計算に関しては、署名者は、ＰＲＧを一定の回数評価し、ｘｉを取得し、そして、Ｏ（ｌｏｇ２ｑ）オペレーションを実行し、仮署名ｒｉを計算する。ここで、ｑは、群Ｇの位数である。署名者は、１６０ビットであるｒｉを通信するだけでよい。サーバには、署名ごとに、ｈｉ及びＳｉｇｉを記憶するストレージが含まれている。本実施形態では、値ｈｉは、１６０ビットであり、一方、適当に短い署名スキームを用いることで、Ｓｉｇｉも、３２０ビット以下に低減することができる。サーバは、オンラインの計算を行わない。その代わりに、サーバは、ペア（ｈｉ，Ｓｉｇｉ）を単に検索し、それを検証者に戻す。検証者の計算に関する限り、検証者は、１つの楕円曲線の点の乗法及び１つの通常の署名の検証を行わなければならない。
【００８１】
＜指定確認者スキームの例＞
仮署名を生成して仮署名を完了するプロセスを、指定確認者スキームに用いてもよい。そのようなスキームの例を、以下に説明する。
【００８２】
図９は、指定確認者署名スキームにおいて用いられる鍵生成プロセスの一実施形態の流れ図である。プロセスは、ハードウェア（例えば、回路、専用ロジック等）、ソフトウェア（汎用コンピュータシステムや専用マシーン上で作動するもの等）、又は、その両方の組み合わせを含んでもよい処理ロジックによって実行されてもよい。
【００８３】
図９を参照すると、プロセスは、標準的で安全なデジタル署名スキーム用の鍵ペアＰＫＳとＳＫＳを生成し（処理ロジック９０１）、強秘匿公開鍵暗号スキーム用の鍵ペアＰＫｄｃ及びＳＫｄｃを生成する（処理ブロック９０２）処理ロジックによって開始される。これは、当技術分野において公知であるやり方で行われる。
【００８４】
図１０は、指定確認者署名スキームに用いられる仮署名生成プロセスの一実施形態の流れ図である。プロセスは、ハードウェア（例えば、回路、専用ロジック等）、ソフトウェア（汎用コンピュータシステムや専用マシーン上で作動するもの等）、又は、その両方の組み合わせを含んでもよい処理ロジックによって実行されてもよい。一実施形態において、処理ロジックは、署名者の一部である。
【００８５】
図１０を参照すると、プロセスは、メッセージＭに対して、コミットメントＣ（Ｍ，ｒ）を生成し（処理ブロック１００１）、コミットメントＳ＝Ｓｉｇ（Ｃ（Ｍ，ｒ））に署名する（処理ブロック１００２）処理ロジックによって開始される。次に、処理ロジックは、仮署名（Ｍ，Ｓ，ＥＰＫ（ｒ））を出力する（処理ブロック１００３）。ここで、Ｅは、強秘匿公開鍵暗号スキームである。
【００８６】
図１１は、指定確認者署名スキームにおける仮署名確認プロセスの一実施形態の流れ図である。プロセスは、ハードウェア（例えば、回路、専用ロジック等）、ソフトウェア（汎用コンピュータシステムや専用マシーン上で作動するもの等）、又は、その両方の組み合わせを含んでもよい処理ロジックによって実行されてもよい。一実施形態において、処理ロジックは、指定確認者の一部である。
【００８７】
図１１を参照すると、プロセスは、ｃｏｍｍ＝Ｃ（Ｍ，ｒ）となるような値ｒの知識についてのゼロ知識証明を実行する処理ロジックによって始まる（処理ブロック１１０１）。ここで、ｃｏｍｍは、仮署名に対応するコミットメントに対応する変数であり、Ｍは、署名者が署名したとされるメッセージである。
【００８８】
図１２は、指定確認者署名スキーム用の仮署名否認プロセスの一実施形態の流れ図である。プロセスは、ハードウェア（例えば、回路、専用ロジック等）、ソフトウェア（汎用コンピュータシステムや専用マシーン上で作動するもの等）、又は、その両方の組み合わせを含んでもよい処理ロジックによって実行されてもよい。一実施形態において、処理ロジックは、指定確認者の一部である。
【００８９】
図１２を参照すると、プロセスは、（Ｍ，Ｓ，ＥＰＫｄｃ（ｒ））として署名と考えられているものを構文解析することにより開始される（処理ブロック１２０１）。そして、処理ロジックは、（Ｍ，Ｓ，ＥＰＫｄｃ（ｒ））を解読し、ｒを回復する（処理ブロック１２０２）。最後に、処理ロジックは、Ｖｅｒ（Ｓ）＝１、Ｃ（Ｍ’，ｒ）＝Ｓ、Ｄｃｈ（Ｅｃｈ（ｒ））＝ｒ）及びＭ’≠Ｍとなるようなｒ及びＭ’の知識についてのゼロ知識証明を実行する（処理ブロック１２０３）。
【００９０】
他の実施形態において、処理ロジックは、追加の情報を検証者に送信する。これにより、処理ロジックは、請求されたメッセージ確認者が、ｃｏｍｍ＝Ｃ（Ｍ，ｒ）となるように、ｃｏｍｍ、Ｓ、及び、ｒの知識についてのゼロ知識証明を送信することを、（ゼロ知識において）検証者に確信させる。ここで、Ｍは、署名者が署名したとされるメッセージである。検証者は、Ｍが署名されたことを検証するために、ゼロ知識証明を確認し、Ｓが、ｃｏｍｍ上の有効な署名であることを確認する。
【００９１】
図１３は、指定確認者署名スキームにおける仮署名完了プロセスの一実施形態の流れ図である。プロセスは、ハードウェア（例えば、回路、専用ロジック等）、ソフトウェア（汎用コンピュータシステムや専用マシーン上で作動するもの等）、又は、その両方の組み合わせを含んでもよい処理ロジックによって実行されてもよい。一実施形態において、処理ロジックは、指定確認者の一部である。
【００９２】
図１３を参照すると、プロセスは、ＥＰＫ（ｒ）を解読してｒを取得する処理ロジックによって開始される（処理ブロック１３０１）。次に、処理ロジックは、Ｍ上の最終署名として（Ｍ，ｒ，Ｓ）を出力する（処理ブロック１３０２）。
【００９３】
図１４は、指定確認者署名スキームにおける最終署名検証プロセスの一実施形態の流れ図である。プロセスは、ハードウェア（例えば、回路、専用ロジック等）、ソフトウェア（汎用コンピュータシステムや専用マシーン上で作動するもの等）、又は、その両方の組み合わせを含んでもよい処理ロジックによって実行されてもよい。一実施形態において、処理ロジックは、検証者の一部である。
【００９４】
図１４を参照すると、プロセスは、Ｃ（Ｍ，ｒ）と等しい変数ｃｏｍｍを計算する処理ロジックによって開始され（処理ブロック１４０１）、ＰＫＳの下で有効な署名であるかを確認する（処理ブロック１４０２）。ここで、Ｓは、署名スキームの公開鍵である。そして、処理ロジックは、かかる確認が取れた場合のみに受け付けを行う（処理ブロック１４０３）。
【００９５】
一実施形態において、署名者と検証者とサーバとの間において、指定確認者デジタル署名を実行するためのデータ通信システムには、仮署名を生成可能なクライアントコンポーネント、仮署名を終了し最終署名を得ることが可能なサーバコンポーネント、及び、最終署名を検証可能な検証コンポーネントが含まれる。
【００９６】
一実施形態において、指定確認者署名スキームを実施する一実施形態における署名者、検証者、及びサーバのそれぞれは、ハードウェア装置（例えば、回路、専用ロジック等）、ソフトウェア装置（汎用コンピュータシステムや専用マシーン上で作動するもの等）、又は、処理ロジックを実行可能な、その両方の組み合わせであってもよい。これらのコンポーネントのそれぞれは、図３に示したコンポーネントのように実装されてもよい。指定確認者の署名者は、仮署名のリクエストを受信するために外部ネットワークインターフェイスと、仮署名を生成し外部ネットワークを介して仮署名を依頼者に戻すために外部ネットワークインターフェイス及びメモリに連結されているプロセッサとを用いる。指定確認者署名の検証者コンポーネントは、外部ネットワークインターフェイスを使って最終署名を受信する。指定確認者署名サーバコンポーネントは、仮署名を受信するために外部ネットワークインターフェイスと、指定確認者署名スキームの完了した最終署名をネットワークに送信するために外部ネットワークインターフェイス及びメモリに連結されているプロセッサとを用いる。
【００９７】
＜効率的変換の実現＞
本明細書に記載の変換を使用して効率的に実施するのがおそらく最も困難なステップは、否認プロトコル及び結果として生じるゼロ知識証明である。なぜならば、「この指定確認者署名は、無効である」ということが、ゼロ知識において証明することが可能なＮＰ-ステートメントであるという事実に基づいているだけだからである。
【００９８】
興味深いことに、指定確認者署名に含まれている暗号文がうまく形成されない可能性は、基礎となる暗号スキームについてのいくつかの仮定によって削除することができる。例えば、ビット文字列の無視可能な端数を除いた場合、その出力が密な暗号文である（ｃｉｐｈｅｒｔｅｘｔ-ｄｅｎｓｅ）暗号システムは、有効な暗号文である。否認プロトコルが、密な暗号文の暗号システムで作動する場合、ビット文字列は、無効な暗号文であり、それを証明する必要はない。
【００９９】
一実施形態において、密な暗号文の公開鍵暗号スキームは、以下のようにトラップドア順列から構成されている。公開鍵を、ｆ：｛０，１｝ｋ→｛０，１｝ｋとし、秘密鍵を、逆数ｆ-１とする。単一ビットｂを暗号化するためには、ｘｉｒ←Ｒ｛０，１｝ｋが用いられる。そして、暗号文は、
【数１７】
2008512060.tif 000019
【０１００】
である。ここで、ＧＬは、「Ｇｏｌｄｒｅｉｃｈ-Ｌｅｖｉｎ  ｐｒｅｄｉｃａｔｅ」である。スキームの強秘匿性を破る敵が、「Ｇｏｌｄｒｅｉｃｈ-Ｌｅｖｉｎ  ｐｒｅｄｉｃａｔｅ」を予測しており、ｆの一方向性に矛盾することが容易に分かる。さらに、記号「，」は、連結を意味し、２ｋ＋１ビットの各文字列は、有効な暗号文である。或いは、ランダムな回復を提供する暗号スキームを用いることができる。つまり、ランダムｒを用いた暗号ＥＰＫ（ｍ）が与えられているので、復号には、ランダムｒ及びｍが含まれる。
【０１０１】
＜Ｎ次剰余仮定に基づく効率的インスタンシエーション＞
基本的に、当技術分野において公知であるペリエ暗号は、以下のように行われる。受取人は、因子分解法が秘密にする合成係数Ｎを選択する。受取人は、また、Ｎ２を法とする「十分に大きな」群、例えば、位数Ｎφ（Ｎ）/２の群、を生成する数字ｇ∈Ｚ/Ｎ２Ｚを発行する。０≦ｍ≦Ｎを満たすｍを暗号化するためには、送信者は、ランダムなｒ∈Ｚ/Ｎ２Ｚを選択し、暗号文ｃ＝ｒＮｇｍ（ｍｏｄ  Ｎ２）を設定する。解読するためには、受取人は、基本的に、ｍ＝ｌｏｇｇｃ（ｍｏｄ  Ｎ）を計算する。ペリエ暗号では、決定的なＮ次剰余仮定の問題は難しいと仮定して強秘匿である。
【０１０２】
一実施形態において、効率的な指定確認者署名スキームは、基本となる署名スキームを、強秘匿であるペリエ暗号とともに用いて、以下のように構築することができる。
【０１０３】
１）鍵生成：  署名者は、標準的で安全なデジタル署名スキームに対して、鍵ペア（ＰＫＳ；ＳＫＳ）を生成する。指定確認者は、ペリエ係数Ｎ及びＮ２を法とする適当なジェネレータｇを生成する。また、Ｎは、正しい形式であることを証明する証明書も生成する。最後に、指定確認者は、第２の群Ｇ２及び位数Nをもつジェネレータｇ２∈Ｇ２の説明を提供してもよい。
【０１０４】
２）ＰｒｏｖＳｉｇｎ（Ｍ）：
ａ）署名者は、
【数１８】
2008512060.tif 000020
【０１０５】
を計算するランダムｈ２∈Ｇ２及びランダムｒ∈Ｚ／ＮＺを生成して、メッセージｍに対してコミットメントを生成する。
【０１０６】
ｂ）署名者は、Ｓ＝Ｓｉｇ（ｃ，ｈ２）を生成する。
【０１０７】
ｃ）署名者は、ｒ＝ｒ＋ａＮを設定し、ＥＮ（ｒ）＝ｇｒ’（ｍｏｄ  Ｎ２）を設定するランダムａ∈Ｚ／ＮＺを生成して、ｒ∈Ｚ／ＮＺのペリエ暗号を生成する。
【０１０８】
ｄ）仮署名は、（ｍ，Ｓ，ｃ，ｈ２，ＥＮ（ｒ））である。
【０１０９】
３）署名者によって確認：  署名者は、その指定確認者署名が正しく構築されたことを、ＥＮ（ｒ）＝ｇｒ（ｇＮ）２（ｍｏｄ  Ｎ２）、及び、
【数１９】
2008512060.tif 000021
【０１１０】
となるようなr及びａの知識についてのゼロ知識証明を実行することにより証明する。これは、標準的な技術を用いて実施することもできる。指定確認者は、ペリエ暗号を通してｒ’（ｍｏｄ  Ｎ）を回復することができ、ｒ’（ｍｏｄ  Ｎ）は、
【数２０】
2008512060.tif 000022
【０１１１】
を完全に明らかにするので（Ｇ２が位数Ｎを持つため）、検証者は、指定確認者が慣習的な署名（ｍ，Ｓ，ｈ２，ｒ）を指定確認者署名から「取り出す」ことができるという知識についてのゼロ知識証明によって確信させられる。知識の証明は、非常に効率的に実施することができることに留意されたい。
【０１１２】
４）指定確認者による確認：  確認するために、指定確認者は、仮署名、及び、
【数２１】
2008512060.tif 000023
【０１１３】
の知識についてのゼロ知識証明だけを提供する。ペリエ暗号から容易にｒ回復することができる。
【０１１４】
５）否認：  指定確認者署名が、悪く形成されている場合、Ｓは、（検証するのが非常に簡単である）（ｃ，ｈ２）の有効な署名でなければ、
【数２２】
2008512060.tif 000024
【０１１５】
でもない。つまり、
【数２３】
2008512060.tif 000025
【０１１６】
を設定した場合、ｌｏｇｇ２ｃ’≠ｌｏｇ（ＥＮ（ｒ））（ｍｏｄ  Ｎ）でなければならない。この不等式が成り立つことを証明するためには、指定確認者は、まず、ペリエ暗号を用いて、ｄ＝ｌｏｇｇ（ＥＮ（ｒ））（ｍｏｄ  Ｎ）を回復する。ｘ＝φ（Ｎ）及びｙ＝ｄφ（Ｎ）の場合、ＢＮ（ｒ）ｘ＝ｇｙ（ｍｏｄ  Ｎ２）であるが、
【数２４】
2008512060.tif 000026
【０１１７】
である。指定確認者は、とても標準的な技術を用いて、これらｘ及びｙの知識についてのゼロ知識証明を提供することができる。特に、１）確認者に、値
ｕ，ｖ∈Ｚ/ＮＺを選択させ、
【数２５】
2008512060.tif 000027
【０１１８】
を送信し、２）検証者に、ランダムにｂ∈{０，１}を選ばせ、３）ｂ＝０の場合、
【数２６】
2008512060.tif 000028
【０１１９】
となり、ｂ＝１の場合、
【数２７】
2008512060.tif 000029
【０１２０】
となるような値ｕ’，ｖ’∈Ｚ/ＮＺを確認者に送り返させることによって、通常の３ラウンドのゼロ知識証明を構築することができる。最後のステップにおいて、確認者は、ランダムな０≠ｋ∈Ｚ/ＮＺを生成し、ｕ’＝ｕ＋ｂｋｘ（ｍｏｄ  Ｎ）及びｖ’＝ｖ‐ｂｋｙ（ｍｏｄ  Ｎ）を設定することによって、そのような（ｕ’，ｖ’）を生成することができる。
【０１２１】
指定確認者は、ｒの値を解読するので、指定確認者署名を誰もが検証可能な「通常の」署名に変換する。この通常の署名は、（ｍ，Ｓ，ｈ２，ｒ）からなり、検証者は、Ｓが、
【数２８】
2008512060.tif 000030
【０１２２】
に対する（ｃ，ｈ２）上の有効な署名であることを確認する。しかしながら、確認者の安全性を証明するために、すなわち、指定確認者と対話する悪質な敵は、結局、確認者の役割を侵害することができず、指定確認者署名を誰もが検証できる署名に変換する能力を得ることができない。ペリエ暗号の強秘匿なバージョンは、十分ではないと言えそうである。
【０１２３】
しかしながら、上記の強秘匿なバージョンを、Ｃａｍｅｎｉｓｃｈ及びＳｈｏｕｐが説明したペリエ暗号のＩＮＤ−ＣＣＡ２安全バージョンと入れ換えることは、比較的単純な問題である。ゼロ知識証明は、基本的に同じである。主な違いは、暗号スキームが、ＩＮＤ−ＣＣＡ２なので、確認者は、悪質な敵が選択した暗号文の復号を確実に明らかにすることができ、そのため、上述したように通常の署名を、指定確認者署名から安全に取り出すことができる。
【０１２４】
＜ブラインド署名スキームの例＞
図１５は、ブラインド署名スキーム用の鍵生成プロセスの一実施形態の流れ図である。プロセスは、ハードウェア（例えば、回路、専用ロジック等）、ソフトウェア（汎用コンピュータシステムや専用マシーン上で作動するもの等）、又は、その両方の組み合わせを含んでもよい処理ロジックによって実行されてもよい。一実施形態において、処理ロジックは、署名者の一部である。
【０１２５】
図１５を参照すると、標準的で安全なデジタル署名スキーム用の鍵ペアＰＫＳ及びＳＫＳを生成する処理ロジックによって開始される（処理ブロック１５０１）。
【０１２６】
図１６は、ブラインド署名スキーム用の仮署名生成プロセスの一実施形態の流れ図である。プロセスは、ハードウェア（例えば、回路、専用ロジック等）、ソフトウェア（汎用コンピュータシステムや専用マシーン上で作動するもの等）、又は、その両方の組み合わせを含んでもよい処理ロジックによって実行されてもよい。一実施形態において、処理ロジックは、ブラインダ、又は、署名者の一部である。
【０１２７】
図１６を参照すると、ランダムな値ｒをとる処理ロジックによって開始され、Ｘ＝Ｃ（Ｍ，ｒ）を計算する（処理ブロック１６０１）。次に、処理ロジックは、Ｘを署名者に送信し、Ｘ＝Ｃ（Ｍ，ｒ）となるようなｒ及びＭの知識についてのゼロ知識証明を実行する（処理ブロック１６０２）。かかる証明が成功した場合にのみ、処理ロジックは、Ｘに署名し、Ｓｉｇ（Ｘ）を戻し（処理ブロック１６０３）、Ｍ上の仮署名を、Ｓｉｇ（Ｘ）＝Ｓｉｇ（Ｃ（Ｍ，ｒ））として出力する（処理ブロック１６０４）。
【０１２８】
図１７は、ブラインド署名スキームの仮署名完了プロセスの一実施形態の流れ図である。プロセスは、ハードウェア（例えば、回路、専用ロジック等）、ソフトウェア（汎用コンピュータシステムや専用マシーン上で作動するもの等）、又は、その両方の組み合わせを含んでもよい処理ロジックによって実行されてもよい。一実施形態において、処理ロジックは、ブラインダの一部である。
【０１２９】
図１７を参照すると、プロセスは、新規のランダム値ｒ’を生成する処理ロジックによって開始される（処理ブロック１７０１）。次に、処理ブロックは、Ｍ上の最終署名を（Ｃ（Ｓｉｇ（Ｃ（Ｍ，ｒ）），ｒ’））として計算する処理ロジックによって開始される（処理ブロック１７０２）。
【０１３０】
図１８は、ブラインド署名スキーム用の最終署名検証プロセスの一実施形態の流れ図である。プロセスは、ハードウェア（例えば、回路、専用ロジック等）、ソフトウェア（汎用コンピュータシステムや専用マシーン上で作動するもの等）、又は、その両方の組み合わせを含んでもよい処理ロジックによって実行されてもよい。一実施形態において、処理ロジックは、ブラインダ、又は、署名者の一部である。
【０１３１】
図１８を参照すると、プロセスは、Ｓが、値Ｓｉｇ（Ｃ（Ｍ，ｒ）、Ｖｅｒ（Ｓｉｇ（Ｃ（Ｍ，ｒ）））＝１とコミットせず、Ｃ（Ｍ，ｒ）が、Ｍとコミットしないようなｒ及びｒ’の検証者に対して、知識のＺＫ証明を行う処理ロジックによって開始される（処理ブロック１８０１）。
【０１３２】
上述の対話型署名は、「Ｆａｓｔ-Ｓｈａｍｉｒ-ｈｅｕｒｉｓｔｉｃ」を通して、ランダムなオラクルを使用して非対話型として表すことができる。
【０１３３】
図１９は、カメレオンハッシュ関数の検証用に予め計算した値を生成するプロセスの一実施形態の流れ図である。プロセスは、ハードウェア（例えば、回路、専用ロジック等）、ソフトウェア（汎用コンピュータシステムや専用マシーン上で作動するもの等）、又は、その組み合わせを含んでもよい処理ロジックによって実行されてもよい。一実施形態において、処理ロジックは、ブラインダ、又は、署名者の一部である。
【０１３４】
問題は、Ｇが、位数ｑの群であり、ｇ，ｙ∈Ｇ及びｘ∈［１，ｑ］であるとすると、（Ｇ，ｇ，ｙ，ｘ）が与えられているので、Ｇにおいて、ｇｘ＝ｙであることを証明して説明してもよい。
【０１３５】
便宜上、ｃｍａｘをチャレンジｃがとることができる最大値、ｋを上述した整数のパラメータとする、整数ｄに対するｄｌｏｇｑ（ｃｍａｘ＋１）e＝ｋｄであるとする。
【０１３６】
図１９を参照すると、プロセスは、定められたｋに対して、Ｘ＝｛ａｂ：ａ＝２ｋｄ’，０≦ｄ’＜ｄ，１≦ｂ＜２ｋ｝とする値ｘｉ∈Ｘを見つける処理ロジックによって開始される（処理ブロック１９０１）。その後、処理ロジックは、（ｘｉ，ｇｘｉ）として定義されている予め計算された値を定義する（処理ブロック１９０２）。
【０１３７】
図２０は、カメレオンハッシュ関数の検証用の予め計算された値を証明するプロセスの一実施形態の流れ図である。プロセスは、ハードウェア（例えば、回路、専用ロジック等）、ソフトウェア（汎用コンピュータシステムや専用マシーン上で作動するもの等）、又は、その両方の組み合わせを含んでもよい処理ロジックによって実行されてもよい。
【０１３８】
図２０を参照すると、プロセスは、値（ｘｉ，ｇｘｉ）上のメルクルツリー（Ｍｅｋｌｅ  ｔｒｅｅ）を計算することにより開始される（処理ブロック２００１）。次に、処理ロジックは、ルートとしてｈ０を持つ、メルクルツリーのノードに対応する値ｈｉによって構成される出力を出力する（処理ブロック２００２）。
【０１３９】
図２１は、カメレオンハッシュ関数の検証用の予め計算された値を検証するプロセスの一実施形態の流れ図である。プロセスは、ハードウェア（例えば、回路、専用ロジック等）、ソフトウェア（汎用コンピュータシステムや専用マシーン上で作動するもの等）、又は、その両方の組み合わせを含んでもよい処理ロジックによって実行されてもよい。一実施形態において、処理ロジックは、ブラインダ、又は、署名者である。
【０１４０】
図２１を参照すると、処理ロジックは、値
【数２９】
2008512060.tif 000031
【０１４１】
を与え、（ｘ，ｇｘ）に対する有効な認証パスをｈｉが形成していることを確認する（処理ブロック２１０１）。
【０１４２】
図２２は、カメレオンハッシュ関数の検証用の予め計算された値を用いるカメレオンハッシュを確認するプロセスの一実施形態の流れ図である。プロセスは、ハードウェア（例えば、回路、専用ロジック等）、ソフトウェア（汎用コンピュータシステムや専用マシーン上で作動するもの等）、又は、その両方の組み合わせを含んでもよい処理ロジックによって実行されてもよい。
【０１４３】
図２２を参照すると、プロセスは、値ごとの認証パス及び請求された（ｘ，ｇｘ）を有する、予め計算された値
【数３０】
2008512060.tif 000032
【０１４４】
を与える処理ロジックにより開始され、予め計算された値を検証する（処理ブロック２２０１）。次に、処理ロジックは、Σｙ１＝ｘを確認する（処理ブロック２２０２）。その後、
【数３１】
2008512060.tif 000033
【０１４５】
を確認する（処理ブロック２２０３）。処理ロジックは、全ての確認がとれた場合のみ、カメレオンハッシュ関数を受け付ける（処理ブロック２２０４）。
【０１４６】
一実施形態において、署名者と検証者とサーバとの間のデータ通信を行うためのシステムには、仮署名を生成可能なクライアントコンポーネント、仮署名を終了し最終署名を得ることが可能なサーバコンポーネント、及び最終署名を検証可能な検証コンポーネントが含まれる。
【０１４７】
一実施形態において、ブラインド署名スキームを実施する、署名者、検証者、及びサーバのそれぞれは、ハードウェア装置（例えば、回路、専用ロジック等）、ソフトウェア装置（汎用コンピュータシステムや専用マシーン上で作動するもの等）、又は、処理ロジックを実行可能な、その両方の組み合わせであってもよい。これらのコンポーネントのそれぞれは、図３に示したコンポーネントのように実装されてもよい。指定確認者の署名者は、仮署名のリクエストを受信するために外部ネットワークインターフェイスと、仮署名を生成し外部ネットワークを介して仮署名を依頼者に戻すために外部ネットワークインターフェイス及びメモリに連結されているプロセッサとを用いる。ブラインド署名の検証者コンポーネントは、外部ネットワークインターフェイスを使って最終署名を受信する。ブラインド署名サーバコンポーネントは、仮署名を受信するために外部ネットワークインターフェイスと、ブラインド署名の完了した最終署名をネットワークに送信するために外部ネットワークインターフェイス及びメモリに連結されているプロセッサとを用いる。
【０１４８】
＜コンピュータシステムの例＞
図４は、本明細書に説明した１つ以上のオペレーションを実行するコンピュータシステムの一例を示すブロック図である。図４を参照すると、コンピュータシステムは、典型的なクライアント、又は、サーバコンピュータシステムを含んでもよい。コンピュータシステムは、通信メカニズム、又は、情報を通信するバス、及び情報を処理するためのバスに連結されたプロセッサを含んでいる。プロセッサには、マイクロプロセッサに限定されるわけではないが、例えば、Ｐｅｎｔｉｕｍ(登録商標)、ＰｏｗｅｒＰＣ、Ａｌｐｈａ等のマイクロプロセッサが含まれる。
【０１４９】
システムには、更に、ランダムアクセスメモリ（ＲＡＭ）、又は、情報及びプロセッサにより実行される命令を記憶するバスに連結された他のダイナミックストレージ装置（メインメモリと呼ぶ）を含む。メインメモリを、プロセッサが命令を実行している間に、一時的な変数、又は、他の中間的な情報を記憶するために用いてもよい。
【０１５０】
コンピュータシステムには、読み取り専用メモリ（ＲＯＭ）、及び／又は、静的な情報及びプロセッサ用の命令を記憶するバスに連結された他の静的ストレージ装置、及び磁気ディスク、又は、光学ディスク、及び、その対応するディスクドライブなどのデータ記憶装置も含まれる。データストレージ装置は、情報及び命令を記憶するバスに連結されている。
【０１５１】
コンピュータシステムは、更に、コンピュータのユーザに情報を表示するバスに連結されたブラウン管（ＣＲＴ）、又は、液晶ディスプレイ（ＬＣＤ）等の表示装置に連結されていてもよい。英数字及び他のキーを含む英数字入力装置も、情報及びコマンドの選択をプロセッサに対して通信するバスに連結されていてもよい。追加的なユーザ入力装置は、指示情報やコマンドの選択をプロセッサに通信し、ディスプレイ上でのカーソルの動きを制御するためのバスに連結されたマウス、トラックボール、トラックパッド、スティラス、又は、カーソル指示キーなどのカーソル制御である。
【０１５２】
バスに連結された他の装置は、命令、データ、又は他の情報を、紙、フィルム、又は、同様の種類の媒体などの媒体上に印刷するために使用してもよいハードコピー装置である。さらに、オプションとして、スピーカー及び／又はマイクなどの音声録音再生装置は、コンピュータシステムと音的にインターフェイスするバスに連結させることもできる。バスに連結されてもよい他の装置は、電話、又は、手のひらサイズの装置と通信する有線／無線通信能力である。
【０１５３】
本発明において、システム及び関連するハードウェアのコンポーネントのどれでも、全てを使用してもよいことに留意されたい。一方で、コンピュータシステムの他の構成は、装置のいくらか、又は、全てを含んでよいことを理解することができる。上記の説明により、本発明の多くの変更及び修正が当業者には明らかとなることは疑いがなく、図により示し説明した特定の実施形態のどれも、本発明を制限しようとするものではないことが分かる。
【０１５４】
上述の説明により、本発明の多くの変更及び修正が当業者には明らかとなることは疑いがなく、図により示し説明した特定の実施形態のどれも、本発明を制限しようとするものではないことが分かる。よって、様々な実施形態の詳細に対する参考文献が、本発明にとって必要不可欠であると見なされる特徴だけを述べた請求項の範囲を制限しようとしたものではない。
【図面の簡単な説明】
【０１５５】
【図１】仮署名プロセスの一実施形態の流れ図である。
【図２】検証者プロセスの一実施形態の流れ図である。
【図３】署名者、サーバ、又は、検証者のコンポーネントの一実施形態を示す。
【図４】コンピュータシステムの一例を示す。
【図５】サーバアシスト型鍵生成プロセスの一実施形態の流れ図である。
【図６】サーバアシスト型鍵生成スキームにおける仮署名プロセスの一実施形態の流れ図である。
【図７】サーバアシスト型署名スキームにおける仮署名終了プロセスの一実施形態の流れ図である。
【図８】サーバアシスト型署名スキームにおける最終署名の検証プロセスの一実施形態の流れ図である。
【図９】指定確認者署名スキーム用の鍵生成プロセスの一実施形態の流れ図である。
【図１０】指定確認者署名スキーム用の鍵生成プロセスの一実施形態の流れ図である。
【図１１】指定確認者署名スキームの確認プロセスの一実施形態の流れ図である。
【図１２】指定確認者署名スキームの否認プロセスの一実施形態の流れ図である。
【図１３】指定確認者署名スキームのためのプロセスの一実施形態の流れ図である。
【図１４】指定確認者署名スキームの用の最終署名検証プロセスの一実施形態の流れ図である。
【図１５】ブラインド署名スキーム用の鍵生成プロセスの一実施形態の流れ図である。
【図１６】ブラインド署名スキーム用の仮生成プロセスの一実施形態の流れ図である。
【図１７】ブラインド署名の検証プロセスの一実施形態の流れ図である。
【図１８】ブラインド署名の検証プロセスの一実施形態の流れ図である。
【図１９】カメレオンハッシュ関数を予め計算するプロセスの一実施形態の流れ図である。
【図２０】カメレオンハッシュ関数の検証のための予め計算された値を証明するプロセスの一実施形態の流れ図である。
【図２１】カメレオンハッシュ関数の検証のための予め計算された値を証明するプロセスの一実施形態の流れ図である。
【図２２】カメレオンハッシュ関数の検証のための予め計算された値を使ってカメレオンハッシュを確認するプロセスの一実施形態の流れ図である。
【図１】
2008512060.tif 000039
【図２】
2008512060.tif 000040
【図３】
2008512060.tif 000041
【図４】
2008512060.tif 000042
【図５】
2008512060.tif 000043
【図６】
2008512060.tif 000044
【図７】
2008512060.tif 000045
【図８】
2008512060.tif 000046
【図９】
2008512060.tif 000047
【図１０】
2008512060.tif 000048
【図１１】
2008512060.tif 000049
【図１２】
2008512060.tif 000050
【図１３】
2008512060.tif 000051
【図１４】
2008512060.tif 000052
【図１５】
2008512060.tif 000053
【図１６】
2008512060.tif 000054
【図１７】
2008512060.tif 000055
【図１８】
2008512060.tif 000056
【図１９】
2008512060.tif 000057
【図２０】
2008512060.tif 000058
【図２１】
2008512060.tif 000059
【図２２】
2008512060.tif 000060
【手続補正書】
【提出日】平成19年6月11日(2007.6.11)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
メッセージ上でオペレーションを実行して仮署名を生成する工程と、
前記仮署名を完了して前記メッセージ上で最終署名を生成する工程とを含む方法であって、
前記仮署名を生成する工程は、
第１の秘密シードを用いて第１の値ｘｉを生成する工程と、
第２の秘密シードを用いて第２の値ｃｉを生成する工程と、
ｍｉが、前記メッセージである場合に、
【数１】
2008512060.tif 000061
を満たす第３の値ｒｉを特定する工程と、
前記第３の値ｒｉを前記仮署名として出力する工程とを含むことを特徴とする方法。
【請求項２】
前記仮署名を完了する工程は、
前記仮署名のインデックスｉを受け取る工程と、
前記インデックスｉに応じて、対応する値
【数２】
2008512060.tif 000062
及びｈｉを取得する工程と、
前記最終署名
【数３】
2008512060.tif 000063
（ｍｉは、前記メッセージであり、ｒｉは、前記仮署名である。）を出力する工程とを含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記最終署名を検証する工程を更に含むことを特徴とする請求項１に記載の方法。
【請求項４】
前記最終署名を検証する工程は、
【数４】
2008512060.tif 000064
を計算する工程と、
【数５】
2008512060.tif 000065
であることを確認する工程と、
前記確認が取れた場合にのみ、前記最終署名を受け付ける工程とを含むことを特徴とする請求項３に記載の方法。
【請求項５】
メッセージ上でオペレーションを実行して仮署名を生成する工程と、
前記仮署名を完了して前記メッセージ上に最終署名を生成する工程とを含む方法であって、
前記仮署名を生成する工程は、
Ｍが、前記メッセージであり、ｒが、ランダム文字列である場合に、コミットメントＣ（Ｍ，ｒ）を、前記メッセージに対して生成する工程と、
Ｓｉｇ（Ｃ（Ｍ，ｒ））が、前記コミットメントＣ（Ｍ，ｒ）の署名を表す場合に、Ｓ＝Ｓｉｇ（Ｃ（Ｍ，ｒ））を生成する工程と、
Ｅが、強秘匿公開鍵暗号スキームである場合に、前記仮署名として、（Ｍ，Ｓ，ＥＰＫ，（ｒ））を出力する工程とを含むことを特徴とする方法。
【請求項６】
前記仮署名を確認する工程を更に含むことを特徴とする請求項５に記載の方法。
【請求項７】
前記仮署名を確認する工程は、
Ｍが、前記メッセージであり、ｒが、ランダム文字列であり、Ｓが、前記コミットメントＣ（Ｍ，ｒ）に署名することを表す場合に、Ｖｅｒ（Ｓ）が１に等しく、コミットメントＳｉｇ（Ｃ（Ｍ，ｒ））がＳに等しくなるような値ｒの知識についてのゼロ知識証明を実行する工程を含むことを特徴とする請求項６に記載の方法。
【請求項８】
前記仮署名を否認する工程を更に含むことを特徴とする請求項５に記載の方法。
【請求項９】
前記仮署名を否認する工程は、
Ｖｅｒ（Ｓ）が１に等しく、コミットメントＣ（Ｍ’，ｒ）がＳに等しく、Ｄｃｈ（Ｅｃｈ（ｒ））がｒに等しく、Ｍ’≠Ｍとなるようなｒ及びＭ’の知識についてのゼロ知識証明を実行する工程を含むことを特徴とする請求項８に記載の方法。
【請求項１０】
メッセージ上でオペレーションを実行して仮署名を生成する工程と、
前記仮署名を完了して前記メッセージ上に最終署名を生成する工程とを含む方法であって、
前記仮署名をメッセージ上でオペレーションを実行して生成する工程は、
ランダム値ｒを選択する工程と、
Ｍが、前記メッセージである場合に、コミットメントＣ（Ｍ，ｒ）と等しい値Ｘを計算する工程と、
前記値Ｘを署名者に送信する工程と、
前記値Ｘが前記コミットメントＣ（Ｍ，ｒ）に等しくなるような前記ランダム値ｒ及び前記メッセージＭの知識についてのゼロ知識証明を実行する工程と、
前記証明が成功した場合にのみ、前記値Ｘに署名して、Ｓｉｇ（Ｘ）を戻す工程と、
Ｓｉｇ（Ｘ）＝Ｓｉｇ（Ｃ（Ｍ，ｒ））である場合に、Ｍ上の前記仮署名を出力する工程とを含むことを特徴とする方法。
【請求項１１】
前記仮署名を完了し、前記メッセージ上に最終署名を生成することには、
第２のランダム値ｒ’を生成し、
前記メッセージＭ上の前記最終署名を（Ｃ（Ｓｉｇ（Ｃ（Ｍ，ｒ）），ｒ’））として出力することを含む、請求項１０に記載の方法。
【請求項１２】
仮署名を生成する工程と、
ネットワークを介して前記仮署名を検証者に送信する工程とを含む方法であって、
前記仮署名を生成する工程は、
第１の秘密シードを用いて第１の値ｘｉを生成する工程と、
第２の秘密シードを用いて第２の値ｃｉを生成する工程と、
ｍｉが、前記メッセージである場合に、
【数６】
2008512060.tif 000066
を満たす第３の値ｒｉを特定する工程と、
前記第３の値ｒｉを前記仮署名として出力する工程とを含むことを特徴とする方法。
【請求項１３】
仮署名を生成する工程と、
ネットワークを介して前記仮署名を検証者に送信する工程とを含む方法であって、
前記仮署名を生成する工程は、
Ｍが、前記メッセージであり、ｒが、ランダム文字列である場合に、コミットメントＣ（Ｍ，ｒ）を、前記メッセージに対して生成する工程と、
Ｓｉｇ（Ｃ（Ｍ，ｒ））が、前記コミットメントＣ（Ｍ，ｒ）の署名を表す場合に、Ｓ＝Ｓｉｇ（Ｃ（Ｍ，ｒ））を生成する工程と、
Ｅが、強秘匿公開鍵暗号スキームである場合に、前記仮署名として、（Ｍ，Ｓ，ＥＰＫ，（ｒ））を出力する工程とを含むことを特徴とする方法。
【請求項１４】
仮署名を生成する工程と、
ネットワークを介して前記仮署名を検証者に送信する工程とを含む方法であって、
前記仮署名を生成する工程は、
前記仮署名をメッセージ上でオペレーションを実行して生成する工程は、
ランダム値ｒを選択する工程と、
Ｍが、前記メッセージである場合に、コミットメントＣ（Ｍ，ｒ）と等しい値Ｘを計算する工程と、
前記値Ｘを署名者に送信する工程と、
前記値Ｘが前記コミットメントＣ（Ｍ，ｒ）に等しくなるような前記ランダム値ｒ及び前記メッセージＭの知識についてのゼロ知識証明を実行する工程と、
前記証明が成功した場合にのみ、前記値Ｘに署名して、Ｓｉｇ（Ｘ）を戻す工程と、
Ｓｉｇ（Ｘ）＝Ｓｉｇ（Ｃ（Ｍ，ｒ））である場合に、Ｍ上の前記仮署名を出力する工程とを含むことを特徴とする方法。
【請求項１５】
仮署名を生成するように構成されているプロセッサと、
ネットワークを介して前記仮署名を検証者に送信するように構成されている前記プロセッサに接続されているネットワークインターフェイスを具備する装置であって、
前記プロセッサは、
第１の秘密シードを用いて第１の値ｘｉを生成し、
第２の秘密シードを用いて第２の値ｃｉを生成し、
ｍｉが、前記メッセージである場合に、
【数７】
2008512060.tif 000067
を満たす第３の値ｒｉを特定し、
前記第３の値ｒｉを前記仮署名として出力するように構成されていることを特徴とする装置。
【請求項１６】
仮署名を生成するように構成されているプロセッサと、
ネットワークを介して前記仮署名を検証者に送信するように構成されている前記プロセッサに接続されているネットワークインターフェイスを具備する装置であって、
前記プロセッサは、
Ｍが、前記メッセージであり、ｒが、ランダム文字列である場合に、コミットメントＣ（Ｍ，ｒ）を、前記メッセージに対して生成し、
Ｓｉｇ（Ｃ（Ｍ，ｒ））が、前記コミットメントＣ（Ｍ，ｒ）の署名を表す場合に、Ｓ＝Ｓｉｇ（Ｃ（Ｍ，ｒ））を生成し、
Ｅが、強秘匿公開鍵暗号スキームである場合に、前記仮署名として、（Ｍ，Ｓ，ＥＰＫ，（ｒ））を出力するように構成されていることを特徴とする装置。
【請求項１７】
仮署名を生成するように構成されているプロセッサと、
ネットワークを介して前記仮署名を検証者に送信するように構成されている前記プロセッサに接続されているネットワークインターフェイスを具備する装置であって、
前記プロセッサは、
ランダム値ｒを選択し、
Ｍが、前記メッセージである場合に、コミットメントＣ（Ｍ，ｒ）と等しい値Ｘを計算し、
前記値Ｘを署名者に送信し、
前記値Ｘが前記コミットメントＣ（Ｍ，ｒ）に等しくなるような前記ランダム値ｒ及び前記メッセージＭの知識についてのゼロ知識証明を実行し、
前記証明が成功した場合にのみ、前記値Ｘに署名して、Ｓｉｇ（Ｘ）を戻し、
Ｓｉｇ（Ｘ）＝Ｓｉｇ（Ｃ（Ｍ，ｒ））である場合に、Ｍ上の前記仮署名を出力するように構成されていることを特徴とする装置。
【請求項１８】
仮署名を受信する工程と、
前記仮署名を前記最終署名に変換する工程と、
前記最終署名をネットワークの場所に送信する工程とを含む方法であって、
前記仮署名を前記最終署名に変換する工程は、
前記仮署名のインデックスｉを受け取る工程と
前記インデックスｉに応答して、対応する値
【数８】
2008512060.tif 000068
及び、ｈｉを取得する工程と、
ｍｉが、メッセージであり、ｒｉが、前記仮署名である場合に、前記最終署名
【数９】
2008512060.tif 000069
を出力する工程とを含むことを特徴とする方法。
【請求項１９】
仮署名を受信する工程と、
前記仮署名を前記最終署名に変換する工程と、
前記最終署名をネットワークの場所に送信する工程とを含む方法であって、
前記仮署名を前記最終署名に変換する工程は、
第２のランダム値ｒ’を生成する工程と、
メッセージＭ上の最終署名を、（Ｃ（Ｓｉｇ（Ｃ（Ｍ，ｒ）），ｒ’））として出力する工程とを含むことを特徴とする方法。
【請求項２０】
仮署名を受信するように構成されているネットワークインターフェイスと、
前記仮署名を前記最終署名に変換するように構成されているプロセッサとを具備する装置であって、
前記プロセッサは、
前記仮署名のインデックスｉを受け取り、
前記インデックスｉに応答して、対応する値
【数１０】
2008512060.tif 000070
及び、ｈｉを取得し、
ｍｉが、メッセージであり、ｒｉが、前記仮署名である場合に、前記最終署名
【数１１】
2008512060.tif 000071
を出力するように構成されており、
前記ネットワークインターフェイスは、前記最終署名をネットワークの場所に送信するように構成されていることを特徴とする装置。
【請求項２１】
仮署名を受信するように構成されているネットワークインターフェイスと、
前記仮署名を前記最終署名に変換するように構成されているプロセッサとを具備する装置であって、
前記プロセッサは、
第２のランダム値ｒ’を生成し、
メッセージＭ上の最終署名を、（Ｃ（Ｓｉｇ（Ｃ（Ｍ，ｒ）），ｒ’））として出力する要に構成されており、
前記ネットワークインターフェイスは、前記最終署名をネットワークの場所に送信するように構成されていることを特徴とする装置。
【国際調査報告】
2008512060.tif 000072
2008512060.tif 000073
2008512060.tif 000074