セキュリティ

論文翻訳: Chameleon Hashing and Signatures

Takami Torao 1997年の論文 #ChameleonHash #ChameleonSignature
  • このエントリーをはてなブックマークに追加

Hugo Krawczyk*, Tal Rabiny†
October 1997

Abstract

我々はカメレオン署名 (chameleon signature) を導入する。この署名は通常のデジタル署名と同様に署名者が署名文書の内容に対して否認不可能なコミットメントを提供するものだが、同時に、署名の受信者は署名者の同意なしに署名された情報の内容を第三者に開示することができない。カメレオン署名は "否認不可署名" (undeniable signature) と密接に関連しているが、カメレオン署名の方がより単純かつ効率的な実現を可能にする。特に、カメレオン署名は本質的に非対話的であり、従来の否認不可署名が基礎としているゼロ知識証明の設計や複雑さを必要としない。その代わりに、カメレオン署名は標準的な hash-then-sign 方式で生成される。ただし、使用されるハッシュ関数はカメレオンハッシュ関数 (chameleon hash function) である。これらのハッシュ関数は、署名者にとっては衝突困難だが受信者にとっては衝突発見可能という非標準的な性質を持つ。

我々はカメレオンハッシュとカメレオン署名の単純かつ効率的な構成法を提示する。前者は、総員数分解や離散対数の困難性と言った標準的な暗号学的仮定に基づいて構築でき、これらの仮定に基づく効率的な実装が可能である。署名の部分については、任意のデジタル署名方式 (RSA や DSS など) を使用できる。その結果として得られるカメレオン署名の偽造不可能性は、使用する規則的なデジタル署名の偽造不可能性のみに基づいて証明される。

Table of Contents

  1. Abstract
  2. 1 導入
    1. 1.1 カメレオンハッシュ
    2. 1.2 カメレオン署名
    3. 1.3 関連研究
    4. 1.4 変換可能性
  3. 2 カメレオンハッシュ
    1. 2.1 クロウフリートラップドア置換に基づくカメレオンハッシュ
      1. 2.1.1 一般的構成
      2. 2.1.2 素因数分解の困難性に基づく効率的な実装
    2. 2.2 離散対数に基づくカメレオンハッシュ
  4. 3 カメレオン署名スキームの基礎
    1. 3.1 基本的な構成要素
      1. 3.1.1 カメレオン署名生成
      2. 3.1.2 カメレオン検証
      3. 3.1.3 紛争
    2. 3.2 基本スキームの強化
    3. 3.3 セキュリティ要件
  5. 4 完全なカメレオン署名方式
  6. 5 任意のカメレオンハッシュ関数を用いた暴露フリー性
  7. 6 変換可能性
  8. 7 カメレオン署名と否認不可能証明書
  9. ACKNOWLEDGMENTS
  10. REFERENCES
  11. APPENDIX A: クロウフリー置換の構成の証明
  12. APPENDIX B: DISCRETE LOG BASED CHAMELEON SIGNATURES
  13. 翻訳抄
  1. *Department of Electrical Engineering Technion Haifa 32000, Israel, an IBM T.J Watson Research Center, New York, USA. Email: hugo@ee.technion.ac.il.
  2. †IBM T.J. Watson Research Center, PO Box 704, Yorktown Heights, New York 10598, USA Email: talr@watson.ibm.com.

El Camaleón, Mamá, el Camaleón,
cambia de colores según la ocasión.
Latin American Song1

カメレオンだよ、ママ、カメレオン、
場合に合わせて色を変えるんだよ。

1 導入

企業や個人間の典型的なビジネス関係では当事者間で合意や契約という形でコミットメントが交わされる。デジタル署名は、紛争が生じたときに必要となる否認不可能性 (non-repudiation) を提供する主要な暗号学的ツールである。しかし、同時にデジタル署名はいずれかの当事者が相手方のコミットメントを外部に開示し (かつ証明し!) 得るという性質も持つ。これは多くのビジネス状況において望ましくない場合がある。例えば、署名済み契約をジャーナリストや競合企業に開示することは、一方の当事者には利益をもたらすが他方の利益を損なう可能性がある。機密協定の早期流出は株式市場での不正な利益獲得に利用される可能性がある。入札で敗北した者は、オークション終了後であっても自らの入札額の開示を防ぎたいと考える場合がある。これらをはじめとする多くの例が示すように、プライバシー、機密性、法的問題は、第三者や署名受信者自身による、合意や契約内容の恣意的な流布を防ぐ必要性を提起する。それでもなお、これらすべてのケースにおいて、法的紛争が生じた際には否認不可能性を保持することが不可欠である。そうした場合、権限を持つ裁定者は、契約、合意、またはコミットメントの妥当性を判断できるべきである。

否認不可能性と制御された開示という矛盾する要求の間の橋渡しをするために、Chaum と Van Antwerpen は否認不可署名 (undeniable signature) [CA89] を導入した (これはその後、[Cha90, BCDP90, DY91, FOO91, Ped91, CvHP91, Cha94, Oka94, Mic96, DP96, JY96, GKR97] など、多数の研究の対象となった)。このタイプの対話的な署名はワンタイム署名に基づいて Michael Rabin が 1976 年に既に提案 [Rab78] していたことに注意。この種の署名の背後にある基本的なパラダイムは、署名の検証には署名者の協力が必要となるため、署名者が署名付き文書の開示先を制御できるという点にある。これらの署名にとって重要な要件は、署名文字列が非転送性 (non-transferable) を持つと言うこと、すなわち、署名者と直接特定のプロトコルを実行する当事者以外には、署名された文書の内容に関するいかなる情報も伝達しないことである。このようなプロトコルによって、署名者は有効な署名を確認したり、無効な署名を否認したりできる。情報の漏洩を防ぐため、これらのプロトコルはゼロ知識証明に基づいている。通常のデジタル署名に対して追加される性質と技術は、当然ながら、スキームの複雑さを増大させる。これは概念的にも計算および通信コストの両面においても言える。

この論文では、上記の問題を解決するための単純で斬新な代替手段、すなわち、はるかに低いコストと複雑さで実現可能な否認不可能性と制御された開示を橋渡しする方法を導入する。我々は否認不可署名の対話的なゼロ知識パラダイムから離れ、代わりに、通常のデジタル署名に非常に似た署名を構築し、従来の hash-then-sign アプローチに従う。通常の署名とカメレオン署名の主な違いは、使用するハッシュ関数の種類、つまり後述するカメレオンハッシュ (chameleon hashing) にある (署名自体には RSA や DSS のような任意の一般的なデジタル署名を使用できる)。

基本的な考え方は署名スキームを次のように構築することである: 署名者 から受信者 に提供される署名により、 は のさらなる署名を自由に偽造 (forge) する能力を得る (つまり、一度 が文書 上の の署名を受け取ると、 は他の任意の文書 に対する の署名を生成できる)。これによって は自分自身でそのような署名を生成できるため、明らかに は の署名の妥当性を第三者に証明 (proving) することができなくなる。これで、誰もその妥当性や不当性を判断できないのであれば、そのような署名には何の価値があるのかという疑問を生じさせる。ポイントは、署名者 に偽造を証明する排他的な (exclusive) 能力を提供することでこのスキームに価値を持たせることである。言い換えれば、 は第三者にとって真正な署名と区別が付かない偽造を生成できるが、 は自身が望む時や (法律などで) 強制される時、第三者に対して偽造を証明できる。我々の方法は本質的に非対話的である。署名は受信者が (非対話的に) 検証できるバイト列として提供されるが、一方で偽の署名を否認するためには署名者は偽造の証拠として短い情報を提供するだけで良い。

ここで、我々の構成における主要なツールであるカメレオンハッシュ (chameleon hashing) について簡単に紹介する。我々の文脈における応用については後ほど動機付けを行う。

1.1 カメレオンハッシュ

カメレオン (またはトラップドア) ハッシュ関数 (chameleon or trapdoor hash function) は非標準の衝突耐性ハッシュ関数である。カメレオンハッシュ関数は、公開鍵と秘密鍵のペアと関連付けられており (秘密鍵はトラップドア (trapdoor) と呼ばれる)、以下の性質を持つ:

  1. 公開鍵を知っている者は誰でも関連するハッシュ関数を計算できる。

  2. トラップドアを知らない者にとって、この関数は通常の意味で衝突耐性を持つ。すなわち、同じ出力に写像される 2 つの入力を見つけることは不可能である。

  3. しかしトラップ情報の保持者は任意の入力に対して容易に衝突を見つけることができる。

セクション 2 で示すカメレオンハッシュの実際の定義にはこれらの関数の出力分布に関する要件も追加されている (特に、ランダム化されている必要がある)。カメレオンハッシュの概念は "カメレオンコミットメントスキーム" (chameleon commitment scheme) [BCC88] と密接に関連しており、後者は暗黙的にカメレオンハッシュ関数の構成を導く (この関係についてはセクション 2 で詳述する)。"カメレオン" という名称は、トラップドア所有者が出力を変更することなく関数への入力を任意の値に変更できる能力を指している。

我々は因数分解や離散対数の計算困難性と言った標準的な暗号学的仮定に基づくカメレオンハッシュの構成法をいくつか示す。また、トラップドア置換のクロウフリーペア (claw-free pairs of trapdoor permutation) [GMR88] に基づく一般的な構成法も示す。これらの構成の効率性は通常のデジタル署名と同等 (またはそれ以上) である。

1.2 カメレオン署名

なぜ我々の文脈でカメレオンハッシュを検討する価値があるのか? まず、与えられたメッセージに対して通常のデジタル署名 (例えば RSA や DSS) を衝突困難なハッシュ (例えば SHA アルゴリズムを使用) に適用するという標準的な方法を検討する。次に、標準的なハッシュ関数をカメレオンハッシュ に置き換える。ここで (Recipient の頭文字) は のトラップドア情報を保持する当事者であり、署名の受信対象者である。新たに得られた署名スキームにはいくつかの興味深い性質がある:

  1. 通常のデジタル署名と同様に、署名者 は自身が生成した署名を否認 (または拒否) できない。なぜなら、 はハッシュにおいて衝突を見つけることができないためである。

  2. 受信者は、 の署名が特定のメッセージ に対応していることを第三者に証明できない。なぜなら、 はトラップドアハッシュ2を使って署名されたメッセージを任意の方法で "開封" (open) できるためである。

  3. 署名は受信者特定的 (recipient-specific) である。すなわち、同じメッセージを 2 人の異なる受信者に意図している場合、署名者は各受信者に対して 1 回ずつ、計 2 回署名する必要がある (カメレオンハッシュ関数は各受信者に特定的であり、受信者ごとに異なるため)。

言い換えると、これらの署名は同時に否認不可能性 (性質 1) と非転送性 (性質 2) である。非転送性とは、意図した受信者のみが署名の妥当性を確信できるが、(受信者の助けがあったとしても) 第三者はその妥当性を確信できず、また署名されたメッセージの内容に関する他の情報も得られないことを意味する。これは、我々の署名を制御されない流布の危険から保護する中核的な性質である。しかし第三者が署名の有効性または無効性を判断できない場合、否認不可能性の性質をどのように実装できるだろうか?

ポイントは、否認不可能署名と同じ原則に従って上記のような署名が署名者との協力によって (in collaboration with the signer) 検証または否認できるということである。 と の間で法的紛争が生じた場合、 は裁定者の前に召喚され、 に対して が主張する署名を受け入れるか、さもなければ否認するように求めることができる。我々は署名を否認する非常に単純な手続きを示す。 が無効な署名を提示した場合、 はカメレオンハッシュ関数 で衝突を示すことができるという特性を利用する。これは の不正行為の十分な証拠となる (そうでなければ、関数は にとって衝突困難であるため)。一方、 が正直である場合、 が署名を否認する方法は存在しない。さらに、署名者 から署名の検証 (否認) を得た裁定者 (または他の当事者) が、 から得たすべての情報を第三者 (例えばジャーナリストや競合企業) に提供したとしても、その第三者が署名を検証 (否認) する方法は依然として存在しない。

上記のアプローチに従って得られる署名を、我々はカメレオン署名 (chameleon signature) と呼ぶ (この絵画的 (pictorial) な名称は受信者が署名の内容を任意の方法で "開封" する能力を有していることを表している)。さらに考慮すべき技術的な詳細がいくつかある (次のセクションでそれを行う) が、上記の記述はこの新しい概念をかなり正確に表現している。

通常のデジタル署名方式とカメレオンハッシュの組み合わせにより、カメレオン署名の単純かつ効率的な構成が得られる。このような方式の総コストは、通常のデジタル署名 (例えば RSA や DSS など) のコストの約 2 倍である。我々のカメレオン署名のセキュリティは標準的な暗号学的仮定に基づいて署名される。特に、偽造不可能性は使用する基礎的なデジタル署名の偽造不可能性のみに基づいて証明される。否認不可能性は、カメレオンハッシュ関数を構築するために必要な過程、例えば素因数分解や離散対数の計算困難性と同じ仮定に基づく。非転送性も基礎となるカメレオンハッシュ関数に依存する。注目すべきは、我々は非転送性が無条件に (unconditionally)、すなわち情報理論的に達成されるカメレオン署名の構成を示すことができる。つまり、署名バイト列によって署名されたメッセージは情報理論的に隠蔽される。

前述のように、カメレオン署名は否認不可署名と同じ基本的な概念によって動機付けられている。多くのアプリケーションにおいてカメレオン署名は否認不可能な署名のより安価な代替手段である。カメレオン署名の実用上の利点は、その単純性 (特に通常の署名をハッシュ関数に採用するという伝統的な形式に従っているため)、検証や否認のためにインタラクションが不要であること、より優れた計算性能、およびいくつかの分析上の利点 (特に、標準的な暗号学的過程の十分性) である。特筆すべきは、対話的なゼロ知識証明の使用に起因する否認不可署名の固有の複雑さはここで一挙に回避される3。一方、カメレオン署名の受信者特定的な性質により、同じ署名バイト列を異なる受信者が検証する必要があるアプリケーションや署名者と受信者の身元を秘密に保つ必要がある場合には適さない (これらの身元を隠す方法についてはセクション 9 参照)。それでも、カメレオン署名は否認不可署名を動機付けるアプリケーションの多くをカバーしており、特にこの導入の冒頭で記述し例示した合意の機密性の保護である。

フェイルストップ署名 (Fail-Stop Signature) [PP97] に関する研究に精通している読者にとって、我々の技術とフェイルストップ署名の構築方法の類似点を指摘することは興味深いだろう。フェイルストップ署名は、署名者が暗号解析似る偽造を (署名者の秘密署名鍵の盗難による偽造とは対照的に) 証明できるという性質を持つ。技術的には、これは署名者が暗号解析による偽造を提示された場合に限り衝突を見つけることができる特殊なタイプのハッシュを使用することで実現される。したがって、フェイルストップ署名とカメレオン署名の目標と構成は非常に異なるが、衝突によって偽造を証明するというアプローチは両者のケースで類似している。

1.4 変換可能性

多くの否認不可署名の文献において注目を集めてきた性質が変換可能性 (convertibility) である。[BCDP90] で導入されたこの概念は、署名者が最終的に秘密情報の一部を公開し、署名を通常のデジタル署名に変換する能力を表す。通常のデジタル署名では、署名者の助け成しに誰でもそれを検証できる。これは、一定期間後または何らかのイベント後に非転送精養軒を失う署名にとって有用な性質である。我々のカメレオン署名スキームは変換可能性を達成するための単純な方法を提供する。我々は選択的 (selective) および全体的 (total) な変換技術を提示する。前者は、個々の (選択された) 署名が、その署名に特定的な情報を提供することで変換できることを意味する。全体的変換は、署名者が事前に指定された集合内のすべての署名を通常の署名に変換する (短い) 情報を公開することを意味する。

  1. 1http://mork.clarin.com.ar/MedioSoglo/clucla.htm の歌。
  2. 2この意味は、署名はメッセージに依存しない付加的な署名のようなもので、 がある文書から別の文書へカットアンドペーストできる署名のようなもの (例えば手書きの署名のように) である。
  3. 3非対話型検証を備えた否認不可能署名は最近 [JSI96] と [Cha] で発表された。彼らの解決策では依然としてゼロ知識証明が使用され、さらに対話性を排除するために理想的なハッシュ関数を想定している。この方式は特定の離散対数関連の構築に基づいている。興味深いことに、彼らはトラップドアコミットメントも使用しているが、我々の場合のように署名生成ではなく確認証明に適用している。[JSI96] では非対話型の否認プロトコルが提案されているが、その詳細と実用性は不明確である。

2 カメレオンハッシュ

カメレオンハッシュ関数は、公開 (ハッシュ) 鍵 を公開し、対応する秘密鍵 (衝突発見のためのトラップドア) を保持するユーザ と関連付けされている。公開鍵と秘密鍵のペアは特定の生成アルゴリズムに従って が生成する。公開鍵 は と表記されるカメレオンハッシュ関数を定義する。この関数は の値が与えられれば効率的に計算できる。メッセージ とランダムバイト列 を入力として、この関数はハッシュ値 を生成する。これは以下の性質を満たす:

  • 衝突困難性 (collision resistance): 公開鍵 を入力として与えられたとき、 となるような であるペア と を見つける効率的なアルゴリズムは、無視できる確率を除いて存在しない。

  • トラップドア衝突 (trapdoor collision): 秘密鍵 、任意のペア 、および任意の追加メッセージ を入力として与えられたとき、 となるような値 を見つける効率的なアルゴリズムが存在する。

  • 一様性 (uniformity): すべてのメッセージ は、一様にランダムに選択された に対して、 に同じ確率分布を誘導する (特に、ランダムに選択された に対して を観測してもメッセージ について何も学習できない)。この条件は、上記の分布がすべてのメッセージに対して必ずしも同一でなく、計算量的に識別不可能 [GM84] であることを要求するように緩和できる。

我々は上記の定義で効率性や無視できる確率の厳密な概念を特定していない。これらは多項式境界でモデル化することも、明示的な (具体的な) 時間と確率の境界で定量化することもできる。第一条件の衝突発見における確率は、衝突発見アルゴリズムの内部ランダムビットと、ハッシュの秘密鍵と公開鍵のペアを生成するアルゴリズムのランダムな選択方法に依存することに注意 (例えば、衝突の発見が容易なペアが存在する可能性があるが、生成アルゴリズムはそれらを無視できる確率でのみ出力する)。

カメレオンハッシュ関数は任意の長さのメッセージに作用し、固定長 (または制限長) の出力を生成することを目的としている。カメレオンハッシュの重要な性質を次の補題に示す。これは容易に検証できる。

補題 1: カメレオンハッシュ関数と (通常の) 衝突困難ハッシュ関数の合成 (後者が最初に適用) は、カメレオンハッシュ関数となる。

したがって、任意のメッセージを長さ のハッシュ値に写像する衝突困難ハッシュ関数があれば (たとえば SHA-1 [fST95] の場合 )、長さ の要素をハッシュするカメレオンハッシュ関数を設計すれば十分である。我々はこの事実を以降の実装やカメレオン署名へのこれらの関数の適用においても使用する。場合によっては、我々が直接構築するカメレオンハッシュ関数が任意長のメッセージを直接サポートしてたとしても、最初に (より高速な) 通常の衝突困難関数をメッセージに適用してからカメレオンハッシュを適用する方がより効率的である。

これはカメレオン署名の構築における中心的なツールであることから、標準的な暗号学的仮定に基づくカメレオンハッシュの効率的な構成を示すことが重要である。以下では、カメレオンハッシュ関数のいくつかの構成を低知る。特に、素因数分解の困難性に基づく効率的な構成と、離散対数の困難性に基づく別の構成を示す。

備考: カメレオンハッシュはカメレオンコミットメント (chameleon commitment) (カメレオンブログ (chameleon blob) またはトラップドアコミットメント (trapdoor commitment) とも呼ばれる) の概念に根ざしている。これはゼロ知識証明の文脈で Brassard, Chaum, および Crepeau [BCC88] によって最初に導入された。非対話的なコミットメントフェーズを持つカメレオンコミット方式はカメレオンハッシュ関数を誘導し、その逆も成り立つ。これを理解するにはカメレオンハッシュの衝突困難性によって関数 がコミット者を特定の値 に束縛することに注意。これは、コミット者がコミットメントを 2 つの異なる方法で開封することができないためである。トラップドア特性は がハッシュバイト列 を任意の可能な原像値 で開封することを可能にするため "カメレオン" 特性を与える。一様性は、値 を調べる第三者がハッシュされたメッセージについて情報を推論することを防ぐ。ただし、コミットメント方式とカメレオンハッシュの基本的な違いは、前者が (コミットメントフェーズと開示フェーズを持つ) 対話的プロトコルを指すのに対し、後者はハッシュ値を生成するために何らかの情報に適用される関数を指すことである。

2.1 クロウフリートラップドア置換に基づくカメレオンハッシュ

我々は、クロウフリートラップドア置換 (claw-free trapdoor permutations) に基づくカメレオンハッシュの一般的な構成と、素因数分解の困難性に基づく特定の効率的な実装を提示する。この構成は通常のデジタル署名を構築するために Goldwasser, Micali, Rivest [GMR88] によって最初に導入され、衝突困難ハッシュ関数を構築するために Damgard [Dam87] によって使用された。我々は、これらの置換のトラップドア情報を使用してカメレオンハッシュのトラップド

2.1.1 一般的構成

非公式には、共通のドメイン上の置換ペア は、 となるようなドメインから値 と を見つけることが計算量的に実行不可能である場合、"クロウフリー" (claw-free) と呼ばれる。Figure 1 はこのようなペアに基づくカメレオンハッシュの構成を示す。ただし、ペアの各地間が反転トラップドアを持つことを前提とする。我々はハッシュ関数が適用されるメッセージ空間が接頭辞フリー (suffix-free) であることを仮定する (すなわち、あるメッセージが別のメッセージの接尾辞として表現されることがない)。このようなメッセージ表現は、メッセージの長さをその末尾に付加することで、または同じ長さのメッセージを使用することで達成できる。後者は、(例えば SHA などの) 衝突困難ハッシュ関数の出力にカメレオンハッシュ関数を適用する自然なケースである (補題 1 参照)。長さ のメッセージ の二進数表現を と表記する。ここで は最初のメッセージビット、 は最後のメッセージビットである。

設定
  1. クロウフリートラップドア置換のペア 。
  2. 秘密鍵 、公開鍵 。
関数
  1. 与えられたメッセージ に対して、我々はハッシュを次のように定義する:
Figure 1. カメレオンハッシュ ── クロウフリー置換に基づく

補題　2: Figure 1 の構成は、 がクロウフリートラップドア置換のペアであり、メッセージ空間が接尾辞フリーであるという条件のもとで、カメレオンハッシュスキームである。

証明. 我々はこのスキームがセクション 2 で定義された性質を満たすことを証明する。

衝突困難性: が与えられたとき (ただしトラップドアは与えられていない)、 となるような のペア と を見つけられると仮定する。 と が異なるビットの最大インデックスを とする (すなわち、 であり、すべての に対して である)。このようなビットは接尾辞フリー性により存在する。 と に対するハッシュ関数の結果が同じであり、メッセージが位置 において同一であると仮定しているため、 番目のビット後の計算結果も両方のメッセージで同じでなければならない ( と の両方が置換であるという事実を使用する)。したがって、 であるが であるような値のペア と が見つかったことになる。これは がクロウフリーペアであるという事実に矛盾する。

トラップドア衝突: 任意のペア 、追加のメッセージ 、およびトラップドアの知識が与えられたとき、値 は以下のように計算される:

一様性: 関数 は置換であるため、その合成も置換である。したがって、メッセージ が与えられたとき、すべての値 に対して となるような値 がちょうど 1 つだけ存在する。

2.1.2 素因数分解の困難性に基づく効率的な実装

Figure 2 では、素因数分解の困難性のみに基づくカメレオンハッシュのある実装を提示する。これは以下のクロウフリートラップドア置換のペアに基づいている。

および となる素数を選び、 を計算する。以下を定義する:

これらの関数のドメインを とする。

上記の構成が素因数分解が困難であるという仮定の下でクロウフリー置換であることの証明は付録 A に示されている。この証明は [GMR88] の証明の単純な変形である。

これらの関数の逆関数を計算するときは、それ自体が平方剰余である平方根を選択する必要があることに注意。

入力
  1. メッセージ
  2. 上で定義した
  3. 乱数 を選択


Figure 2. カメレオンハッシュ ── 素因数分解に基づく

計算量の分析. このカメレオンハッシュを計算するために必要な演算回数は、 回の二乗と、せいぜい 回の (4 による) 乗算 である。我々のアプリケーションでは、通常、 はハッシュ化されたメッセージであり、したがって期待される乗算回数は であり、 自体は約 160 ビット長に過ぎない。したがって、総コストは での完全な長い指数演算、特に RSA 署名よりも大幅に低い。上記の関数で を の最上位ビット、 を最下位ビットとする場合は を計算することに注意。

2.2 離散対数に基づくカメレオンハッシュ

このカメレオンハッシュのソリューションは Boyar ら [BKK90] にようよく知られたカメレオンコミットメントスキームに基づいている ([BCC88] も参照)。

設定
  1. となるような素数 と 。ここで は十分に大きな素因数
  2. の位数 の元
  3. である秘密鍵
  4. である公開鍵 (, , は公開鍵の暗黙的な部分)
関数
  1. メッセージ が与えられると乱数値 を選択
  2. ハッシュを と定義
Figure 3. カメレオンハッシュ ── 離散対数に基づく

Figure 3 のスキームの衝突困難性は ( を知らない者に対して) 離散対数計算の困難性に基づいている。 とトラップドア情報の知識によりトラップドア衝突を計算できる。すなわち、与えられた任意の および に対して、 となるような値 を見つけることができる。これは、方程式 において を解くことで行われる。このことから の一様性も成り立つことがわかる。

3 カメレオン署名スキームの基礎

ここでは、カメレオン署名方式の基本的な構成要素と要件について詳しく説明する。前述したように、カメレオン署名はメッセージのカメレオンハッシュ値にデジタル署名することで生成される。セクション 3.1 ではカメレオン署名方式に関連する基本的な関数を導入する。セクション 3.2 では基本的な方式の制限について議論し、セクション 4 および 6 で提示する完全な解法のより詳細な部分を動機付ける。

3.1 基本的な構成要素

カメレオン署名の設定を記述することから始める。この設定はプレーヤーと合意された関数および鍵を定義する。

プレーヤー
署名者 と受信者 。我々はさらに裁定者 を参照する。 は と の間の紛争を解決する責任を持つ当事者を表し、 はこの裁定者と協力すると想定する。
関数
プレーヤーは以下について合意する:

  • デジタル署名方式 (例えば RSA や DSS)。これは署名者に関連する公開鍵と秘密鍵の集合であり、署名 ( と表記) と検証 ( と表記) という通常の操作を定義する。つまり、 はメッセージ を入力として受け取って署名者の秘密鍵の下でメッセージに対する署名を返し、 はメッセージとその署名を受け取って署名者の公開鍵を使用して署名の妥当性 (または不当性) を判定する。我々はこの署名方式が偽造不可能 [GMR88] であると仮定する (通常、実際には署名される情報の適切なエンコーディング (例えば暗号ハッシュ関数の使用) を必要とする)。

  • カメレオンハッシュ関数。これはハッシュの "所有者" に関連する公開鍵と秘密鍵の集合と、メッセージに対するハッシュを生成するための 操作を定義する。我々の設定では、ハッシュ関数の "所有者" は受信者となる。

鍵

  • 署名者 は合意された署名方式に対応する公開署名鍵と秘密署名鍵を持つ。これらをそれぞれ と と表記する。

  • 受信者 は合意されたカメレオンハッシュ方式に対応する公開鍵と秘密鍵を持つ。これらをそれぞれ と と表記する。

我々は、すべての公開鍵が何らかの信頼できる認証局に登録されていると仮定できる (与えられたアプリケーションの法的要件に依存する)。人がカメレオンハッシュに必要な公開データを登録する際には、そのハッシュのトラップドア情報 (すなわち対応する秘密鍵) を知っていることを証明しなければならないことに注意する必要がある4。

次に、カメレオン署名方式の 3 つの基本フェーズとその基本的な実装を提示する (より完全な詳細は後続のセクションで示す):

3.1.1 カメレオン署名生成

メッセージ と鍵 、 が与えれたとき、署名者は次の方法で に対する署名を生成する: 署名者はランダムな要素 を選択肢、 および を計算する。そのトリプル が から に送信される。

注意: 非転送性を保証するため (セクション 3.3 参照)、 から に送信される値 と が、 関数の下で署名される情報の一部ではないことが重要であることを強調する。例えば対称鍵 MAC 方式などを使用してその認証が否認可能である限り、 と の間のチャネルは認証できる。

3.1.2 カメレオン検証

トリプル と、署名者 () および受信者 () の両方の公開鍵が入力として与えられると、カメレオン検証は以下のように行われる。値 を として計算し、バイト列 を の下で標準署名方式の 関数を使用して検証する (すなわち が に対する の有効な署名であるかどうか)。 と表記されるカメレオン検証は、署名検証が有効または無効を出力する場合、署名が適切または不適切なカメレオン署名であることを出力する。

注意: この検証関数は が署名の妥当性の保証を得るために十分である (すなわち、 は が後で署名を否認できないことを確信できる)。しかし、他の当事者にとっては検証の成功は が特定のメッセージに署名したという証明にはならない。なぜなら ( を知っている) が自分自身でその署名を生成した可能性があるからである。

用語. 我々は、 と の公開鍵を使用してトリプル にカメレオン検証を適用することを と表する。この関数の出力が "適正" (proper) である場合、我々は を -適正トリプル (-proper triple) と呼ぶ (これらの値が文脈から明らかな場合、ペア は省略する)。

3.1.3 紛争

署名の妥当性について紛争が生じた場合、 は権限のある裁定者 に訴えることができる。裁定者は からトリプル を受け取る。 はこれに対して上記の 関数を適用する。裁定者によるこの最初のテストは、このトリプルがメッセージ に対する -適正署名であることを検証するためである。この検証が失敗した場合、主張された署名は によって拒否される。そうでない場合、 は署名者を召喚して、その主張を否認/受理させる。この場合、署名者は裁定者に (例えば法的な力で) 協力すると仮定する。 はトリプル を に送る。署名者が署名を受理したい場合、単にこの事実を裁定者に確認する。一方、 が署名が無効であると主張したい場合、ハッシュ関数における衝突、すなわち である値 と において となることを提供する必要がある。 が無効の場合 (すなわち が元々 によって とは異なる何らかのペア から生成されている場合)、 は常にそのようなペア を提示できることに注意。言い換えれば、偽の署名を主張することで受信者 は関数 での衝突を に提供する。しかし署名 が有効な場合、 はハッシュ関数の衝突を提出できず、署名を否認できない。したがって、 の妥当性は がハッシュ関数への衝突を提示できる場合に によって却下され、そうでない場合は受理される。

3.2 基本スキームの強化

上記の方式は我々の構成の主要なアイデアを伝えているが、完全かつ実用的なカメレオン署名方式を得るために解決する必要のあるいくつかの制限を抱えている。

受信者の身元. 上記の方式は、 (または の公開鍵) の身元が の値に束縛されていない。この場合、署名者 は署名が別の当事者 のために異なる文書に対して発行されたものであると主張することで署名を否認できる。これは、 が のハッシュトラップドア情報を知っている場合に可能である。なぜなら、その場合 は のために署名された任意のメッセージを表すように署名を開封することができるためである。したがって受信者の身元をハッシュされた値に束縛する必要がある。それには と の身元 ( と表記する) の両方を の署名で署名する。これが、我々の方式で の身元が隠蔽されない理由である (実際の実装では、 の身元には の特定の公開鍵に関する情報だけではなく、特定のカメレオンハッシュ方式や認証局にカンする情報が含まれる可能性がある)。 の身元の開示を避けるべき応用についてはセクション 9 でこの問題を軽減するメカニズムを紹介する。

暴露フリー性. 裁定者 が署名者 を召喚して偽造 を否認させようとした場合、 は によって となる何らかのメッセージ とバイト列 を使用する署名として生成されたはずである ( が最初に をカメレオン検証手続きの下で検証するために、このことは保証されている)。 の主張が偽である場合、 は常にその署名に元々使用されていた実際の と を公開することでハッシュ関数における衝突を示すことができる。しかし、それは が隠蔽したいと考えている情報 (すなはち に対する署名の存在) を開示することになる。これは特定のアプリケーションにおいて望ましくない場合がある。我々は、署名者が偽造を否認する際に、自分が署名した任意のメッセージの実際の内容を暴露することなく否認できることを要求する。そして、、これを我々のすべてのカメレオン署名スキームの性質とする (我々が提示するソリューションはこの目標を強い意味で達成する。すなわち、 は元の値 や が署名した他の任意のメッセージとは全く無関係でランダムなメッセージ を提示することで署名を否認できる)。我々はこのような性質を暴露フリー (exposure free) と呼ぶ。

メモリ要件. 前述の通り、署名者は、主張された署名 の 成分が、あるメッセージ に対して署名者によって ( のために) 生成された署名に対応する場合にのみ、署名の否認に参加する必要がある。この署名が実際に偽造である場合、我々の方式でそれを否認するために、署名者は に対応する実際のメッセージがなんであったかを見つけ出す必要がある。一つの解決策は、署名者がすべての署名を対応する署名済みメッセージと共に保存することである。これは一部のアプリケーションでは実用的かもしれないが、他のアプリケーションでは禁止されている可能性がある。我々はこの情報の保存を受信者に転送することでこの必要性を緩和する方法を示す。これは、 が常に署名と対応するメッセージを保存しなければならないため、合理的な要件であることに注意。これは次のような方法で行われる: 署名者は何らかの秘密鍵 を持ち、その下で と を暗号化して を生成する。この値は および の身元と共に署名される (衝突困難ハッシュ関数の下で のハッシュ値を、 全体ではなく暗号化すれば十分であることに注意。この場合、 は のハッシュ値に を適用するのであって、 自体に適用するのではない)。暗号化は意味的安全 [GM84] でなければならず、対象または非対称暗号系を使用して実装できる。このオプションが使用される場合、以下で議論する非転送性の性質は情報理論的には達成できないことに注意。

3.3 セキュリティ要件

ここでカメレオン署名方式に要求するセキュリティ特性を要約する。形式的な定義は本論文の最終版で提示される。

署名者 、受信者 、裁定者 によって実行される署名方式が、セクション 3 で説明された関数で構成されている場合、以下の性質が満たされて言えれば安全なカメレオン署名方式であると言う (以下では、署名者と受信者とは異なる任意の当事者を第三者と呼ぶ)。

偽造不可能性 (unforgeability): 第三者は、署名者 によって過去に生成されていない -適正トリプル を生成できない。意図された受信者 は、 によって過去に生成された 値に対してのみ、-適正タプル を生成できる。

非転送性 (non-transferability): 署名者自身を除き、誰も、与えられたトリプル を署名者が生成したことを、そのような任意のトリプルについて別の当事者に証明できない。これは、受信者および任意の第三者 (例えば署名者との否認/受理プロトコルに参加した裁定者) について真でなければならない。

否認 (denial): 紛争において、署名者 が自分によって生成されていないトリプル を提示された場合、 は (正直な) 裁定者 に を却下させることができる。

否認不可能性 (non-repudiation): 紛争において、署名者 が自分によって生成されたトリプル を提示された場合、 は (正直な) 裁定者 に を却下させることができない。

暴露フリー性 (exposure free): カメレオン署名スキームが暴露フリーであるとは、署名者が偽の署名 (すなわち署名者によって生成されていないトリプル ) を、自分が実際に署名したメッセージを暴露することなく否認できることを言う。

  • 4秘密鍵が第三者 によって選択されたり のみが知っているようなケースを回避するためには、登録者 は秘密鍵を知っていることを証明する必要がある。このようなケースでは、トラップドア情報を知っているのは のみで は知らないため、 は に対して行われた署名を確定できるようになる。

4 完全なカメレオン署名方式

このセクションでは前述の機能性とセキュリティ要件を満たすカメレオン署名の特定のシステムについて具体的に記述する。以下に記述する実装は暴露フリーの性質を達成する。すなわち、署名者は否認において自分の署名済みメッセージのいずれも暴露することなく署名の無効性を証明できる。メモリ管理の詳細、つまりメッセージ とその署名を紛争の可能性に備えて署名者が保持するか、あるいはハッシュされたメッセージの暗号化を署名に追加するかについては省略する。セクション 3.2 で説明したこれらの問題を解決する技術は、使用するカメレオンハッシュの種類とは独立しており、ここに容易に追加できる。

使用するカメレオンハッシュはセクション 2.1 で説明した素因数分解クロウフリーに基づくカメレオンハッシュである (離散対数に基づく別の例については付録 B を参照)。 関数に加えて、例えばセクション 3.1 で議論した署名引数の適切なエンコーディングを伴う RSA などの何らかの特定署名スキームによって定義される と 関数を使用する。この署名スキームに基づいて は秘密鍵と公開鍵のペアを生成する。

上記に基づいて、カメレオン署名生成のための関数 およびカメレオン検証のための関数 を定義できる。これらを Figure 4 に記述する。この構成は署名の下に を追加したセクション 3.1 の基本スキームに従っている。署名への入力として使用されるメッセージ は、最初に衝突困難ハッシュ関数 (例えば SHA) を使用してハッシュでき、このハッシュの結果をカメレオンハッシュ関数への入力として使用できることに注意 (補題 1 参照)。

カメレオン署名生成 -
署名者の入力
  1. メッセージ
  2. の秘密署名鍵
  3. と の公開鍵
  1. 乱数 を選択し、 を計算することで、 のカメレオンハッシュを生成 (Figure 2)
  2. を設定
  3. メッセージ に対する署名は からなる
カメレオン署名検証 -
入力
  2. の秘密検証鍵
  3. と の公開鍵
  1. を計算
Figure 4. カメレオンハッシュ ── 生成と検証

セクション 3.1 で説明したように、紛争のとき、署名者には 検証を通過するトリプル が提示される。 はつまり署名者によってメッセージ に対して生成された可能性のある署名である。署名者がハッシュ関数における衝突を提供できる場合、署名は無効と見なされる。さらに、この署名の否認は署名者が署名した下のメッセージを暴露することなく達成されるべきである。セクション 6 ではこの目標を達成するための一般的な方法を説明するが、ここではクロウフリー置換カメレオンハッシュ方式の基礎となる性質を利用することで暴露フリー性を可能にする。この特定の解法では、受信者が (カメレオン検証を通過する) 偽造を提示すると、署名者は特定の署名を否認できるだけでなく、 の秘密鍵 を暴露することもできる。 の知識は署名者がこのカメレオンハッシュを使用して署名した他のすべてのメッセージを否認することを可能にする。これはトラップドアの知識により衝突発見が可能になるという事実による。秘密鍵の抽出は以下の方法で達成される: 不正を行うため、 は署名者によって実際に署名された値 を提示しなければならいが、ここで偽のメッセージを与える。したがって はハッシュ関数に衝突を提供していることになり、特定の構成では、これは がクロウを提供していることを意味する。[GMR88] によって示されているように、このようなクロウにより を法として因数分解できる。因数分解が計算されると、署名者は と の両方を反転できる。署名者が秘密鍵を抽出し、ハッシュに無関係な衝突を生成するために実行するプロトコルを Figure 5 に記述する。

衝突の生成
署名者の入力: 偽造
  1. は を計算するために使用された元の値 を取得aする。ここで であり が成立する。
  2. であり、かつ となるすべての に対して であるようなインデックス を見つける。したがって何らかの値 に対して が成り立つ。
  3. と を計算する。
  4. は と を計算する。これにより が定義される。
  5. は任意のメッセージ を選択し、関数のドメインにある値を選択するために を計算する。
  6. を出力する。
  1. a と の取得は、 のアーカイブから、またはセクション 3.2 で説明した暗号化技術を使用して行うことができる。
Figure 5. 衝突の生成 ── クロウフリーに基づく構成

紛争プロトコルにおいて署名者が署名 を受理することを決定した場合、 にこの妥当性の "証明" は提出されず、単に は受け入れを宣言するだけである。その結果として、署名が実際には有効ではないにもかかわらず今は が受理することにして、あとで否認することを決定する可能性がある。この状況が真に懸念と見なされるアプリケーションでは、否認手続きを 2 段階で実行するコトで克服できる: まず、 は主張されたメッセージ と署名 を に送る。 が署名を有効として受理したとき、 に対して に等しい値 を送る必要がある。 が署名を無効であると主張する場合、否認手続きは上記で指定された通りに完了する (すなわち は を に送り、 は衝突で応答する)。

定理 1. 安全なデジタル署名方式と素因数分解の困難性を仮定すると、上記の鉄付きにより、非転送性、偽造不可能性、否認不可能性、否認、および暴露フリー性の性質を満たすカメレオン署名方式を形成する。

Proof.

非転送性

署名者 が受信者 のために生成した署名 が与えられると、受信者は第三者にその有効性を確信させることができない。これは、任意のメッセージ に対して が となるような値 を計算できるという事実による (セクション 2.1 参照)。したがって は -適正署名である。さらに、任意のメッセージ に対して適正タプル を生成する の値が 1 つだけ存在するため、署名バイト列 を観察しても の値については何も分からない。したがって、非転送性は無条件、つまり情報理論的な意味で達成される。さらに、第三者は受信者と共謀している可能性があるため、署名の妥当性を検証できない。

偽造不可能性

第三者は、署名者 によって過去に生成されていない -適正タプル を生成できない。これには、基礎となるデジタル署名方式を破るか、カメレオンハッシュにおいて衝突を見つける必要があり、後者は の秘密のトラップドア情報を計算することを意味する。受信者は、署名者によって過去に署名されていない 成分を含む -適正タプル を生成できない。これには基礎となるデジタル署名スキームを破る必要がある。

否認不可能性

署名者によって生成された -適正タプル が与えられた場合、署名者は である別の -適正タプル を生成できない。これは秘密のトラップドア情報 (すなわち の素因数) を計算することと等価であり、素因数分解の困難性により実行不可能であると想定されている。

暴露フリー性

我々は基礎となるデジタル署名が偽造不可能であると仮定しているため、署名者 は、元々 によって生成されていない -適正であるタプル に対してのみ署名を否認する必要がある可能性がある。この場合、 は実際に が署名した別の適正タプル を所有しているはずである。これらの値を使用して、 は Figure 5 に記述されているように秘密のトラップドア情報 を抽出する。このトラップドアが与えられると、署名者は自分の選択したメッセージを使用して衝突を提示することで署名を拒否できる。

5 任意のカメレオンハッシュ関数を用いた暴露フリー性

セクション 3 では任意のカメレオンハッシュに基づく一般的なカメレオン署名方式を示した。しかしその一般的なスキームは暴露フリー性を保証しない。これはセクション 4 で特定のカメレオンハッシュ関数を使用して達成された。基礎となるハッシュ関数の特定の性質に頼ることなく、署名の否認時に署名済みメッセージに関する情報が漏洩しない性質である暴露フリー性を保証する方法を示すことが残されている。特に、我々は、ハッシュにおける 2 つの点の単一の衝突の知識が、他のそのようなペアを見つける方法を提供するという仮定をしない、一般的なカメレオンハッシュ を仮定する。

署名者が署名したいメッセージ が与えられた場合、署名者は となるような 2 つのランダムなメッセージ と を選択する。次に、署名者は と の両方をハッシュして署名することで に対するカメレオン署名を生成する。すなはち: 主張された署名を提示するために、受信者はハッシュされた各成分に対して 2 つのペア と を提示しなければならない。受信者が偽造を提示している場合、少なくとも と の一方はそれぞれ と とは異なっていなければならない。 であると仮定する。この場合、署名者は単に を暴露できる。これは実際に署名されたメッセージ についての情報を何も明らかにしない。署名者が元のペアのうち両方を暴露すると元のメッセージを再構築できてしまうため、1 つだけを公開することが重要である。したがって、 に関する将来の紛争のために、署名者は ( を暴露したと仮定して) を保存しなければならない。同じ署名に関して次に紛争が生じたとき、受信者が元の と 2 つ目の要素を変更した値を渡したとしても、署名者は を提示することで依然として 1 つ目の成分の衝突を示すことができる。

同じ署名に関して 回の紛争に対処する前に情報を保存する必要性を回避するように上記の方法を一般化することは簡単である。これは の 個の成分を使用するだけでよい。すなわち とする。

定理 2. 任意のカメレオンハッシュ関数と安全なデジタル署名方式が与えられた場合、非転送性、偽造不可能性、否認不可能性、否認、および暴露フリー性の特性を満たすカメレオン署名方式を構築できる。

Proof. セクション 3 の技術と暴露フリー性に対する前述の方法を組み合わせる。

6 変換可能性

否認不可署名の変換可能性 (convertibility) の概念は Boyer, Chaum, Damgard, Pederson [BCDP90] によって導入された。この考え方は、何らかの情報を公開することで否認付加署名を通常の公開検証可能な (否認不可能な) 署名に変換するというものである。変換可能性の概念には、完全変換可能性と選択的変換可能性という変種がある。完全変換可能性は同じ鍵で生成されたすべての署名を変換するのに対し、選択的変換可能性は単一の署名のみを変換する。変換可能な否認付加署名の問題に対する安全な解決策は Damgard と Paderson [DP96] および Gennaro, Krawczyk, Rabin [GKR97] に記載されている。

セクション 3.2 では署名者がメッセージを保存する必要性を回避する方法を導入した。同じ技術を使用して変換可能性を実現できる。このメカニズムは署名されたメッセージの暗号化を署名者の署名の下に含めるというものであった。変換可能性を実現するには、署名者は公開鍵暗号を使用してメッセージを暗号化する必要がある。さらに、メッセージの暗号化と共にこの公開鍵に署名することで、署名者は使用している暗号化公開鍵に対してコミットする (これは暗号化に署名する際に [AN95] で指摘された問題と同様の問題を防ぐ)。したがって、署名者は何らかの暗号化バイト列にコミットしている。しかし、暗号化されたバイト列の内容は暗号化の意味的安全性により第三者が知ることはできない。これで、特定の各リグ的暗号間使用されるランダムビットを署名者が暴露することで選択的変換可能性を達成でき、復号鍵を暴露することで完全変換可能性を達成できる(このコミットメントは暗号化関数の一対一性により一意である)。

7 カメレオン署名と否認不可能証明書

[GKR96] において否認不可能証明書 (undeniable certificates) の概念が導入された。ここでは否認不可能証明書方式とカメレオン署名を組み合わせる方法を示す。

否認不可証明書では、署名者 と検証者 の間に何らかの初期インタラクションがあり、その後、多数の否認不可署名が から に提供でき、それ以上のインタラクションを必要とせずに によって検証できる。これは、初期インタラクション中に が によって選択された署名公開鍵に対する "証明書" を に提供することで達成される（この公開鍵は通常のデジタル署名方式のためのものである)。公開鍵の証明書は認否不可署名方式を使用して によって署名されている。検証者は、 とインタラクションすることで署名の正しさを検証できる。その後、 は証明された公開鍵を使用して (通常のデジタル署名を使用して) を対象とするさらなるメッセージに署名できる。

この方法では、署名者が第三者に対して自分の証明書を確認すると、その証明書の下で署名されたすべての署名も確認することになることに注意。このような方式は多くのアプリケーションにおいて受け入れられる可能性がある (例えば、全体として保護/公開される必要のある一連の文書に署名するために特定の証明書を使用する場合)。しかし、場合によっては同じ証明書の元で署名された他のすべての署名を暴露することなく、単一の署名を確認できることが望ましい。以下では、認否不可署名をカメレオン署名と組み合わせることでこれを回避できることを示す。最初に、前述のように署名者の公開鍵に対する証明書が発行されるが、これで後述のすべての署名がカメレオン署名方式を使用してこの鍵で生成される。したがって、証明書が暴露されても署名は依然としてカメレオン署名であり、したがってそれらの内容は暴露されない。

さらに、カメレオン署名の上に否認不可署名を使用することで、証明書が検証されない限り、署名者と受信者の身元は秘密に保たれる。

ACKNOWLEDGMENTS

We would like to thank Mihir Bellare and Daniele Micciancio for suggestions of implementations of Chameleon Hashing, and Ivan Damgard for clarifying what the state of the art is concerning hashing with claw-free permutations. And special thanks go to Shimon Even for telling us about the results of Michael Rabin.

REFERENCES

  1. [AN95] R. Anderson and R. Needham. Robustness principles for public key protocols. In D. Coppersmith, editor, Advances in Cryptology | Crypto '95, pages 236–247, Berlin, 1995. Springer-Verlag. Lecture Notes in Computer Science No. 963.
  2. [BCC88] G. Brassard, D. Chaum, and C. Crepeau. Minimum disclosure proofs of knowledge. JCSS, 37(2):156–189, 1988.
  3. [BCDP90] J. Boyar, D. Chaum, I. Damgård, and T. Pedersen. Convertible undeniable signatures. In A. J. Menezes and S. Vanstone, editors, Advances in Cryptology | Crypto '90, pages 189–205, Berlin, 1990. Springer-Verlag. Lecture Notes in Computer Science No. 537.
  4. [BKK90] J. F. Boyar, S. A. Kurtz, and M. W. Krentel. A discrete logarithm implementation of perfect zero-knowledge blobs. Journal of Cryptology, 2(2):63–76, 1990.
  5. [CA89] David Chaum and Hans Van Antwerpen. Undeniable signatures. In G. Brassard, editor, Advances in Cryptology | Crypto '89, pages 212–217, Berlin, 1989. Springer-Verlag. Lecture Notes in Computer Science No. 435.
  6. [Cha] David Chaum. Private Signatures and Proof Systems. US Patent 5,493,614.
  7. [Cha90] D. Chaum. Zero–knowledge undeniable signatures. In I. Damgård, editor, Advances in Cryptology | Eurocrypt '90, pages 458–464, Berlin, 1990. Springer-Verlag. Lecture Notes in Computer Science No. 473.
  8. [Cha94] David Chaum. Designated confirmer signatures. In A. De Santis, editor, Advances in Cryptology | Eurocrypt '94, pages 86–91, Berlin, 1994. Springer-Verlag. Lecture Notes in Computer Science No. 950.
  9. [CvHP91] D. Chaum, E. van Heijst, and B. Pfitzmann. Cryptographically strong undeniable signatures, unconditionally secure for the signer. In J. Feigenbaum, editor, Advances in Cryptology | Crypto '91, pages 470–484, Berlin, 1991. Springer-Verlag. Lecture Notes in Computer Science No. 576.
  10. [Dam87] I. Damgard. Collision free hash functions. In D. Chaum, editor, Advances in Cryptology | Eurocrypt '87, pages 203–216, Berlin, 1987. Springer-Verlag. Lecture Notes in Computer Science No. 304.
  11. [DP96] I. Damgard and T. Pedersen. New convertible undeniable signature schemes. In Ueli Maurer, editor, Advances in Cryptology | Eurocrypt '96, pages 372–386, Berlin, 1996. Springer-Verlag. Lecture Notes in Computer Science No. 1070.
  12. [DY91] Y Desmedt and M. Yung. Weaknesses of undeniable signature schemes. In J. Feigenbaum, editor, Advances in Cryptology | Crypto '91, pages 205–220, Berlin, 1991. Springer-Verlag. Lecture Notes in Computer Science No. 576.
  13. [FOO91] A. Fujioka, T. Okamoto, and K. Ohta. Interactive bi-proof systems and undeniable signature schemes. In D. Davies, editor, Advances in Cryptology | Eurocrypt '91, pages 243–256, Berlin, 1991. Springer-Verlag. Lecture Notes in Computer Science No. 547.
  14. [fST95] National Institute for Standards and Technology. Secure Hash Standard, April 17 1995.
  15. [GKR96] R. Gennaro, H. Krawczyk, and T. Rabin. Undeniable Certificates. Manuscript, 1996.
  16. [GKR97] R. Gennaro, H. Krawczyk, and T. Rabin. RSA-based Undeniable Signatures. In B. Kaliski, editor, Advances in Cryptology | Crypto '97, pages 132–149, Berlin, 1997. Springer-Verlag. Lecture Notes in Computer Science No. 1294.
  17. [GM84] S. Goldwasser and S. Micali. Probabilistic encryption. JCSS, 28(2):270–299, April 1984.
  18. [GMR88] Shafi Goldwasser, Silvio Micali, and Ronald L. Rivest. A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Computing, 17(2):281–308, April 1988.
  19. [JSI96] M. Jakobsson, K. Sako, and R. Impagliazzo. Designated verifier proofs and their applications. In Ueli Maurer, editor, Advances in Cryptology | Eurocrypt '96, pages 143–154, Berlin, 1996. Springer-Verlag. Lecture Notes in Computer Science No. 1070.
  20. [JY96] M. Jakobsson and M. Yung. Proving without knowing: On oblivious, agnostic and blindfolded provers. In N. Koblitz, editor, Advances in Cryptology | Crypto '96, pages 201–215, Berlin, 1996. Springer-Verlag. Lecture Notes in Computer Science No. 1109.
  21. [Mic96] M. Michels. Breaking and repairing a convertible undeniable signature scheme. In ACM Conference on Computer and Communications Security, 1996.
  22. [Oka94] Tatsuaki Okamoto. Designated confirmer signatures and public-key encryption are equivalent. In Y. Desmedt, editor, Advances in Cryptology | Crypto '94, pages 61–74, Berlin, 1994. Springer-Verlag. Lecture Notes in Computer Science No. 839.
  23. [Ped91] T. Pedersen. Distributed provers with applications to undeniable signatures. In D. Davies, editor, Advances in Cryptology | Eurocrypt '91, pages 221–242, Berlin, 1991. Springer-Verlag. Lecture Notes in Computer Science No. 547.
  24. [PP97] T. Pedersen and B. Pfitzmann. Fail-stop signatures. SIAM. J. Computing, 26(2):291–330, April 1997.
  25. [Rab78] M. Rabin. Digitalized Signatures. In R. Demillo and et.al, editors, Foundations of Secure Computations, pages 155–165. Academic Press, 1978.

APPENDIX A: クロウフリー置換の構成の証明

セクション 2.1.2 の構成を再掲: および となる素数を選択し、 を計算する。

以下を定義する:

これらの関数のドメインは とすべきである。

この と の選択の下で以下の性質が成立することに注意:

  1. -1 は , を法として平方余剰ではない

以下の証明は異なるドメインの選択に対処するために [GMR88] に示されている証明の変形である。

補題 3. 関数 と は置換である。

Proof. である が存在し、 であると仮定する。つまり である。素数 , は を割り切ることはできない。なぜならそれは を意味し、これは についても同様に不可能であるためである。したがって と は を意味する を割り切れなければならず、これは矛盾である。

が置換であると言う事実は、 が置換であると言う事実から直接導かれる。そして、 は単に 4 による乗数であり、これは置換性を維持する。

補題 4. , はクロウフリーペアである。

Proof. となる を見つけることができると仮定する。つまり が成立する。我々は であることを示し、したがって を計算することで の (非自明な) 因数を計算できることを示す。

  • は、 であり、2 は (性質 2) であり、 と の両方が であるためである。

  • は、 であり、-1 は (性質 3 と 1) であり、 と の両方が であるためである。

APPENDIX B: DISCRETE LOG BASED CHAMELEON SIGNATURES

翻訳抄

秘密鍵 (トラップドア情報) を持っている者は衝突の発見が可能というカメレオンハッシュ関数を用いてデジタル署名方式を提案する 1997 年の論文。この方式では通常のデジタル署名と同じ否認不可能性に加えて非転送性を実現する。署名の受信者が秘密鍵を持ち、署名を有効なまま書き換えることができることができるため、受信者が「署名者はメッセージ に署名した」と主張するだけでは第三者はそれが事実かを確信できない。紛争が生じた場合、裁定者がその署名が署名者によって行われたものかを判定する。カメレオンハッシュは管理者のみが変更可能なブロックチェーン (redactable blockchain) を実現するための基礎技術として研究・応用されている。現在でも、格子暗号ベースの耐量子計算機版の構築や、アクセス制御機能との統合などの研究が続いている。

  1. KRAWCZYK, Hugo; RABIN, Tal. Chameleon Hashing and Signatures. Cryptology ePrint Archive, 1998.