論文翻訳: A CERTIFIED DIGITAL SIGNATURE

ABSTRACT

従来の暗号化関数と同等に安全な、従来の暗号化関数に基づく実用的な電子署名システムについて述べる。認証済みの従来システムが利用可能であるため、未検証のシステムの認証に必要な年数の遅れはなく、迅速に実装することができる。

キーワードと語句: 公開鍵暗号システム、デジタル署名、暗号、電子署名、受領者、認証、電子送金。

Table of Contents

1. ABSTRACT
2. 1. 導入
3. 2. 一方向関数
4. 3. The Lamport-Diffie ワンタイム署名
5. 4. An Improved One Time Signature
6. 5. The Winternitz Improvement
7. 6. ツリー認証
8. 7. パス再生成アルゴリズム
9. 8. 結論
10. 9. ACKNOWLEDGEMENTS
11. 10. BIBLIOGRAPHY
12. 翻訳抄

1. 導入

電子署名は電話 (またはその他の通信機器) による商取引に革命をもたらすと期待されている [1] が、現在知られている電子署名方式 [5, 6, 7, 8, 10, 13] は認証 (certified) されていないか、その他の欠点がある。従来の暗号化関数のセキュリティに依存する署名システムは、基礎となる暗号化関数が認証されている限り事前認証済み (pre-certified) となるだろう。新たな認証作業の遅延と費用を回避できる。Lamport と Diffie [1, 10] はそのようなシステムを提案したが性能面で大きな欠点がある。それにもかかわらず、Lapton と Matyas [4] は、差し迫った問題に対する唯一の短期的解決策としてその使用を提案した。

この論文では「事前認証」され、(正確なセキュリティ要件に依存する) 約 1～3 キロバイトの署名を生成し、署名 1 件につき基礎となる暗号化関数を数千回適用し、数キロバイトのメモリのみを必要とする電子署名システムについて述べる。基礎となる暗号化関数が 1 ブロックの暗号化に 10 マイクロ秒かかるとすると、署名の生成には 20 ミリ秒程度を要するだろう。

この新しい署名手法はツリー署名 (tree signature) と呼ばれる。以下の主要な点を扱う:

1. 一方向関数についての議論

2. Lamport-Diffie ワンタイム署名の説明

3. Lamport-Diffie ワンタイム署名の改良

4. Winternitz ワンタイム署名

5. ツリー署名の説明

2. 一方向関数

一方向関数 [2, 9] はこの論文の基礎である。直感的には、一方向関数 \(F\) とは、計算するのは容易だが逆計算が困難な関数のことである。\(y=F(x)\) のとき、\(x\) と \(F\) が与えられれば \(y\) を計算するのは容易だが、\(y\) と \(F\) が与えられても \(x\) を計算するのは事実上不可能である。

この論文の要点のみに興味のある読者は、このセクションを読み飛ばして第 3 セクションに進むことを推奨する。

セキュリティを向上させるために \(F\) をパラメータ化、すなわち \(F_1\), \(F_2\), \(\ldots\), \(F_i\), \(\ldots\) という一方向関数の族 (family) を作成する。繰り返し使用される一つの関数を解析する方が、すべての異なる \(F_i\) を解析するよりも容易である。多くの場合、\(F_i\) は大きな入力 (例えば 10,000 ビット) を小さな出力 (例えば 100 ビット) に圧縮することも求められる。これは一方向ハッシュ関数 (one-way hash function) と呼ばれ、すべての \(i\) について以下が要求される:

1. \(F_i\) は任意のサイズの任意の引数に適用できる。
2. \(F_i\) は常に固定サイズを出力する。具体的には、われわれはこれを 100 ビットと仮定する。
3. \(x\) が与えられれば \(F_i(x)\) を計算するのは容易である。
4. \(F_i(x)=F_i(x')\) となるような \(x\ne x'\) を見つけることは計算上困難である。
5. \(F_i(x)\) が与えられても \(x\) を決定することは計算上困難である。

重要な記法: 2 つの引数 \(x_1\) と \(x_2\) を連結したいときは \(\langle x_1, x_2 \rangle\) と記述する。したがって、\(x_1\) と \(x_2\) が共に 100 ビット長であれば、\(\langle x_1, x_2 \rangle\) は　200 ビットの連結となる。

一方向関数の主な用途は認証である。値 \(y\) が認証可能であれば: \[ F_i(x)=y \] を計算することによって \(x\) を認証できる。\(y\) を生成する他の入力 \(x'\) は (おそらく存在はするが) 見つけることはできない。100 ビットの \(y\) は任意の大きさの \(x\) を認証することができる。この性質は大量の情報を簡便に認証するために重要である (100 ビットの \(y\) は妥当であるが、実際のシステムにおけるサイズの選択には、より小さなサイズによるコスト削減と効率の向上、より大きなサイズによるセキュリティの向上というトレードオフが含まれる)。

\(F_i\) のような関数は、従来の暗号化関数 [6] の観点から定義できる。したがって、300 ビットの鍵サイズを持ち、100 ビットの平文ブロックを 100 ビットの暗号文ブロックに暗号化する従来の暗号化関数 \(C({\rm key},{\rm plaintext})\) があると仮定する。

\(F_i\) が優れた一方交換数であることを証明するために、それが基づく従来の暗号化関数についていくつかの過程を置く必要がある (Rabin もこの問題を検討している [13])。特に、我々は \(F_i\) が特定の性質を持つことを要求する。

\({\rm length}(p)={\rm length}(c) \le {\rm length}(k)\) である認証済み (certified) 暗号化関数 \(C(k,p)=c\) は、以下の性質を持たなければならない:

1. \(C(k,p)=c=C(k',p)\) かつ \(k\ne k'\) となる任意の 4 つの値 \(k\), \(k'\), \(p\), \(c\) を見つけるのに必要な平均計算量は \(2^{{\rm length}(p)/2}\) より大きい。

2. 以下の条件が成り立つ場合、\(C(k,p)=c=C(k',p)\) かつ \(k\ne k'\) となる 4 つの値 \(k\), \(k'\), \(p\), \(c\) を見つけるのに必要な平均計算量は \(2^{{\rm length}(p)-1}\) である:

   • \({\rm plaintext}\) と \(p\) は既知で固定されている。

   • 鍵空間は互いに疎な部分集合 \(S_1, S_2, \ldots\) に分割されている。

   • \(k\) は集合 \(\{k_1,k_2,\ldots\}\) の要素である。

   • 各 \(k_i\) は \(S_i\) からランダムに選ばれる。

   • 各 \(S_i\) は少なくとも \(2^{{\rm length}(p)}\) 個の要素を持つ。

   • \(k\) と \(k'\) の両方は同じ部分集合 \(S_i\) の要素でなければならない。

この論文の残りの部分では、これらを特性 1 と特性 2 と呼ぶ。

特性 1 はかなり明確である: 同じ平文と暗号文のペアに対して 2 つの鍵 \(k\) と \(k'\) を見つけるには、どのような状況下でも一定の最小計算量が必要である。

特性 2 にはより多くの説明が必要である。これは、特定の条件が満たされるなら、おなじ平文と暗号文のペアに対する 2 つの鍵 \(k\) と \(k'\) を見つけるには完全な全数探索が必要であることを述べている (無条件に適用される特性 1 は、\(k\) と \(k'\) を見つけるのに必要な計算量が単純な全数探索の平方根に比例することを述べていることに注意)。

最も重要な条件は 2d である: \(k\) はランダムに選ばれなければならない。\(k\) がランダムに選ばれれば |(c=C(k,p)\) もランダムになるはずである。ランダムな \(c\) が与えられたとき、\(C(k',p)=c\) となる \(k'\) を見つける問題は完全な全数探索を必要とするはずである。

この追加条件は、2 つの互いに疎な鍵空間からの 2 つの鍵で 2 つの平文を暗号化することは、一方の鍵空間からの鍵で暗号化されたメッセージを解読する方法の知識が、他方の鍵空間からの鍵で暗号化されたメッセージの解読には役に立たないことから、2 つの無関係な暗号による暗号化と実質的に等価と解釈できる。\(F\) がパラメータ化される主な理由は、特性 2 のこの側面を利用するためである。\(i\ne j\) であれば \(F_i\) と \(F_j\) は個別の一方向関数であり、\(F_i\) を破ることと \(F_j\) を破ることは 2 つの独立した問題である。\(F\) がパラメータ化されていなければ、異なる引用に対する異なる人々による \(F\) の多くの適用が、相互に関連する単一の問題を構成することになる。ある引用への \(F\) の特定の適用を逆転させる問題より、多くの可能な頻用の 1 つへの \(F\) の何らかの適用を逆転させる問題の方がはるかに解決しやすいだろう。この問題全体はパラメータ化によって回避できる。

特性 1 と特性 2 の両方は \(C\) がランダム暗号 (random cipher) である場合に満たされる。これは Shannon [12] によって記述された概念である。現代の暗号化関数の強度は、それらのランダム暗号への類似性に基づいている。Feisterl [11] の Lucifer についての記述を引用すると「入力が連続する層を通過するにつれ、生成される 1 のパターンが増幅され、予測不可能な雪崩効果をもたらす。結局、最終的な出力は平均して 0 と 1 が半分ずつになる…。」

特性 1 と 2 を満たさない暗号は「認証済み」と呼ぶべきであろうか? これは主に用語の適切な定義の問題である。著者はそのような暗号をいかなる目的にも使うことも確実に躊躇するであろう。

読者は、特性 1 が特性 2 よりもはるかに堅牢であることに注意すべきである。特性 2 に依存するシステムの設計には特別な注意が必要である。

\(F_i\) を段階的に定義する。まず特性 2, 3, 4, 5 を満たすが、入力が 200 ビット以下に制限された一方向関数 \(G_{\langle i,j \rangle}\) を定義する。我々は \[ G_{\langle i,j \rangle}(x) = y = C(\langle x,i,j \rangle, \underline{0}) \] を定義する。\(G_{\langle i,j \rangle}\) は最大 200 ビットの入力 \(x\)、50 ビットのパラメータ \(i\) と \(j\) を受け入れ、100 ビットの出力 \(y\) を生成する。さらに、\(y\) が与えられたときに \(G_{\langle i,j\rangle}(x')=y\) となる \(x'\) を見つける問題は、\(y=C(\langle x',i,j\rangle, \underline{0})\) となる鍵 \(x'\) を見つけることと等価である。

\(C\) が特性 1 と 2 を満たすとき、これは計算上不可能である。

ここで \(C_{\langle i,j\rangle}\) の観点から \(F_i\) を定義できる。\(F_i\) への入力 \(x\) が 100 ビット以下であれば、ちょうど 100 ビットになるまで 0 を追加することで \(x\) をパディングし、\(F_i(x)=G_{\langle i,1\rangle}(\langle\underline{0},x\rangle)\) と定義する (ここで \(\underline{0}\) は 100 ビットの 0 である)。

入力が 100 ビットを超える場合は 100 ビットの断片に分割する。\[ \underline{x} = \langle x_1,x_2,\ldots,x_n \rangle \] であり、各 \(x_k\) が 100 ビット長であると仮定する。そして \(F_i\) は \(G_{\langle i,j\rangle}\) の繰り返し適用として定義される。まず \(G_{\langle i,1\rangle}\) を \(x_1\) に適用して \(y_1=G_{\langle i,1\rangle}(\langle\underline{0},x_1\rangle)\) を得る。次に、\(y_2\)=\(G_{\langle i,2\rangle}(\langle y_1,x_2\rangle)\)、\(y_3\)=\(G_{\langle i,3\rangle}(\langle y_2,x_3\rangle)\)、\(y_4\)=\(G_{\langle i,4\rangle}(\langle y_3,x_4\rangle)\)、… \(y_j\)=\(G_{\langle i,j\rangle}(\langle y_{j-1},x_j\rangle)\)、… \(y_n\)=\(G_{\langle i,n\rangle}(\langle y_{n-1},x_n\rangle)\) となる。\(F_i(\underline{x})\) は \(y_n\)、つまり系列の最後の \(y\) として定義される。

\(F_i\) が任意に大きな \(x\) の値を受け入れられることは明らかである。\(F_i(\underline{x})=F_i(\underline{x}')\) となるような \(\underline{x}\) とは異なるベクトル \(\underline{x}'\) を見つけることが計算上困難であることは (事実ではあるが) 自明ではない。そのような \(\underline{x}'\) を見つけることを、我々は \(F_i\) を破る (breaking) と呼ぶ。

\(C\) が認証済み暗号化関数、つまり特性 1 または 2 が成り立つと仮定すれば、\(F_i\) を破ることは計算上困難であることを帰納的に証明できる。仮定 1 を利用すれば \(\underline{x}'\) を計算するのに必要な平均労力が少なくとも \(2^{{\rm length}(p)/2}\) であることを証明できる。一方、仮定 2 を利用すれば、\(x'\) がランダムであることを要求するものの、\(\underline{x}'\) を計算するのに必要な平均労力が少なくとも \(2^{{\rm length}(p)-1}\) であることを証明できる。

基本的に、定義により \(n=1\) のときに \(F_i(\underline{x})=G_{\langle i,1\rangle}(\langle\underline{0},x_1\rangle)=C(\langle\underline{0},x_1,i,1\rangle,\underline{0})\) であり、仮定により \(C\) についてもこの特性が成り立つため、この特性が成り立つ。\(n\) に対して成り立つならば \(n+1\) についても成り立つことを示すためには、\(F_i(\underline{x})=F_i(\underline{x}')\) ならば以下の 2 つの条件のいずれかが成り立つ必要があることに注意するだけでよい:

1. すべての \(k \le n\) について \(x_k=x'_k\)
2. ある \(k \le n\) について \(x_k\ne x'_k\)

B が成り立つ場合、帰納法の仮定により、ある \(k \le n\) に対して \(x_k\ne x'_k\) を件際するために必要な労力はすでに費やしている。

A が成り立ち、\(\underline{x}\ne \underline{x}'\) であれば、\(x_{n+1} \ne x'_{n+1}\) である。\(x'_{n+1}\) が \(x_{n+1}\) と異なるが、\(G_{\langle i,n+1\rangle}(\langle y_n,x'_{n+1}\rangle)\) が \(G_{\langle i,n+1\rangle}(\langle y_n,x_{n+1}\rangle)\) と等しいことを計算するために必要な労力は、\(G_{\langle i,n+1\rangle}\) の定義と特性 1 と 2 により、(特性 1 を使用する場合) \(2^{{\rm length}(p)/2}\)、または (特性 2 を使用する場合) \(2^{{\rm length}(p)-1}\) でなければならない。

特性 2 の条件が成り立たない場合には、特性 1 が適用される。

実際には、特性 2 を使用できる場合と特性 1 のみを使用できる場合を区別することが重要である。特性 2 を使用すると、同じレベルのセキュリティを維持しながら、ブロック暗号のサイズを 1/2 に削減できる。これにより、以下のアルゴリズムにおけるほとんどの保存コストと転送コストの大部分が 2 つ削減される。

以降の説明を明確にするためにこの論文の残りの部分では \(F\) から添え字を省略するが、読者は特性 2 を利用するためには \(F\) をパラメータ化することが不可欠であることを覚えておく必要がある。特性 1 を使用する場合でも、依然として \(F\) をパラメータ化することが推奨される。

3. The Lamport-Diffie ワンタイム署名

Lamport-Diffie ワンタイム署名 [1] は一方向関数 [2, 9] の概念に基づいている。\(y=F(x)\) が一方向関数 \(F\) を入力 \(x\) に提供した結果である場合、重要な洞察は以下の通りである:

\(y=F(x)\) を計算した人物だけが \(x\) を知っている。\(y\) が公開されていれば、\(y\) の発行者だけが \(x\) を知ることができ、自分の意思で \(x\) を開示するか秘匿するかを選択できる。

これは例で説明するのが最も分かりやすいだろう。ある人物 A が株式を保有しており、いつでも売却できるとする。A は緊急に株式を売却したいと考えており、ブローカーに電話でその旨を伝えたいと考えている。ブローカー B は電話による承認だけで売却することは望んでいない。この問題を解決するために、A は \(y＝F(x)\) を計算して B に渡しておく。両者は A が株式を売却したい場合には \(x\) を B に開示することに合意する (この場合は、\(y\) の値と \(F\) の説明を含むが、\(x\) の値を含まない書面契約 [4] として正式に作成できる)。その後、B (訳注: A の誤記?) は \(x\) を提示し、\(F(x)=y\) を証明できるため、B は A が株式を売却したかったことを証明できる。

A が後に株式の売却を否認した場合、B は契約書と \(x\) を裁判官に示して、A の発言に反して実際に株式を売却したことの証拠とできる。\(F\) と \(y\) はどちらも元の (書面による) 契約に記載されているため、裁判官は \(F(x)\) を計算し、それが \(y\) に等しいことを検証することができる。\(x\) を知り得る唯一の人物は A であり、B が \(x\) を知り得た唯一の方法は A が \(x\) を開示した場合のみである。したがって、A は \(x\) を開示したに違いない。つまり、事前の合意により A が株式を売却したいとしていたことを意味する行為である。

この例は 1 ビットの情報に「署名」する署名システムを示している。A は株式を売却したか、しなかったかのいずれかである。A がブローカーに株式 10 株を売却するように指示したい場合、A は数ビットのメッセージに署名できなければならない。一般的な Lamport-Diffie 方式では、A が \(s\) ビットのサイズのメッセージ \(m\) に署名したい場合、\(F(x_1)=y_1\), \(F(x_2)=y_2\), \(F(x_3)=y_3\), … \(F(x_s)=y_s\) を計算する。A と B はベクトル \(Y=y_1,y_2,\ldots,y_s\) に合意する。\(m\) の \(j\) 番目のビットが 1 であれば A は \(x_j\) を開示する。\(m\) の \(j\) 番目のビットが 0 であれば A は \(x_j\) を開示しない。本質的には、\(m\) の各ビットは個別に署名される。任意のメッセージを 1 ビットずつ署名できる。

実際には、(100 ビットを超える) 長いメッセージは一方向関数によって短いメッセージ (100 ビット) にマッピングされ、短いメッセージのみを署名する。特性 2 (セクション 2 で説明) は常に使用できる。\(F\) は (セクション 2 でも説明した) \(F_i\) としてパラメータ化でき、メッセージは署名前に署名者によって新しく生成されたランダム鍵で暗号化され、ランダム鍵がメッセージに付加される。したがって、その新しく署名されたメッセージはランダムとなる (ランダム鍵による暗号化がメッセージを効果的にランダム化するという事実を仮定する。これは現代の暗号化関数について一般に認められている [11]。) これらの手順は特性 2 の条件を満たす。したがって、一般性を失うことなく、すべてのメッセージが固定長、たとえば 100 ビットであると仮定できる。

これまで述べた方法には、B が 1 であるビットを 0 に変更することで \(m\) を改変できるという欠点がある。B は (実際には受診したにもかかわらず) 単に \(x\) を受信したことを拒否する。しかし、0 を 1 に変更することはできない。Lamport と Diffie は、\(m\) のちょうど 2 倍の長さで、\(m\) と \(m\) のビットごとの補数を連結することで計算される新しいメッセージ \(m'\) に署名することでこの問題を克服した。つまり、元のメッセージの各ビット \(m_j\) は、新しいメッセージ \(m'\) において 2 つのビット、\(m_j\) と \(m_j\) の補数によって表現される。明らかに、どちらかのビットは 0 でなければならない。メッセージを変更するには、B は 0 を 1 に変更しなければならないが、これは不可能である。

これで、この方法が「ワンタイム」署名である理由が明確になったはずである。各 \(Y=y_1,y_2,\ldots,y_{2*s}\) は 1 つのメッセージにのみ署名するために使用できる。複数のメッセージに署名する場合は、新しい値 \(Y_1,Y_2,Y_3,\ldots\) が必要であり、各メッセージに対して新しい \(Y_i\) が必要である。

ワンタイム署名は、必要な大量のデータを交換する意思のある 1 組のユーザ間では実用的だが、さらなる改良なしには大部分のアプリケーションには実用的ではない (Rabin [13] は異なるワンタイム署名方法を説明している)。

4. An Improved One Time Signature

5. The Winternitz Improvement

6. ツリー認証

新しいプロトコルは大容量のストレージ要件を解消するだろう。A がメッセージへの署名直前に \(Y_i\) を B に送信すれば、B は事前に A から \(Y_i\) のコピーを取得して保管する必要がない。しかし、残念ながらそのようなプロトコルは機能しない。誰でも A であると主張し偽の \(Y_i\) を送信して、実際には何も受け取っていないにもかかわらず適切に認証された署名を受け取ったと B に思い込ませることができる。B は自分が受け取った \(Y_i\) が偽造ではなく正しいものであることを何らかの方法で確認する必要がある。

この問題は A の \(Y_i\) を認証することである。最も単純な (しかし不十分な) 方法は、A の \(Y_i\) のコピーを補完することである。このセクションでは、あらゆるユーザのあらゆる \(Y_i\) を迅速かつ容易に認証でき、最小限のストレージしか必要としないツリー認証 (tree authentication) と呼ばれる方法について述べる。

ツリー認証は電子署名を含まない認証問題の解決にも使用できる。この論文ではツリー署名を生成するために使用しているが、読者はそれが唯一の応用であると誤解すべきではない。

問題定義: データ項目のベクトル \(\underline{Y}=Y_1,Y_2,\ldots,Y_n\) が与えられたとき、ランダムに選択された \(Y_i\) を迅速に認証でき、かつメモリ使用量が控えめ、つまり \(Y_1,Y_2,\ldots,Y_n\) のテーブルを持たないアルゴリズムを設計せよ。

\(Y_i\) を認証するために分割統治法 (divide and conquer) を適用する。関数 \(H(i,j,\underline{Y})\) を次のように定義する:

1. \(H(i,i,\underline{Y})=F(Y_i)\)
2. \(H(i,j,\underline{Y})=F(\langle H(i,(i+j-1)/2,\underline{Y}),H((i+j+1)/2,j,\underline{Y})\rangle)\)

\(H(i,j,\underline{Y})\) は \(Y_i,Y_{i+1},\ldots,Y_j\) の関数である。\(H(i,j,\underline{Y})\) は \(Y_1\) から \(Y_n\) までの認証に使用できる。\(H(1,n,\underline{Y})\) は 100 ビットしかないため簡単に保存できる。この方法により、任意の葉 (leaf) \(Y_i\) を選択的に認証できる。これを理解するために \(n=8\) の例を使用する。\(H(1,8,\underline{Y})\) を計算するために必要な再帰呼び出しの順序を Figure 1 に示す。\(Y_5\) を認証するには以下の方法で進めることができる:

1. \(H(1,8,\underline{Y})\) は既知で認証済みである。

2. \(H(1,8,\underline{Y}) = F(\langle H(1,4,\underline{H}), H(5,8,\underline{Y}) \rangle)\) である。\(H(1,4,\underline{H})\) と \(H(5,8,\underline{Y})\) を送信し、受信者に \(H(1,8,\underline{Y})\)\(=\)\(F(\langle H(1,4,\underline{Y}), H(5,8,\underline{Y}) \rangle)\) を計算させて正しいことを確認させる。

3. 受信者は \(H(5,8,\underline{Y})\) を認証した。\(H(5,8,\underline{H})\) と \(H(5,6,\underline{Y})\) を送信し、受信者に \(H(5,8,\underline{Y})\)\(=\)\(F(\langle H(5,6,\underline{Y}), H(7,8,\underline{Y}) \rangle)\) を計算させて正しいことを確認させる。

4. 受信者は \(H(5,6,\underline{Y})\) を認証した。\(H(5,5,\underline{H})\) と \(H(6,6,\underline{Y})\) を送信し、受信者に \(H(5,6,\underline{Y})\)\(=\)\(F(\langle H(5,5,\underline{Y}), H(6,6,\underline{Y}) \rangle)\) を計算させて正しいことを確認させる。

5. 受信者は \(H(5,5,\underline{Y})\) を認証した。\(Y_5\) を送信し、受信者に \(H(5,5,\underline{Y})\)\(=\)\(F(Y_5)\) を計算させて正しいことを確認させる。

6. 受信者は \(Y_5\) を認証した。

この方法では約 200 ビットの送信が \(\log_2 n\) 回のみ必要である。アルゴリズムを詳しく調べると送信の半分が冗長であることが分かる。例えば、\(H5,6,\underline{Y})\) は \(H(5,5,\underline{Y})\) と \(H(6,6,\underline{Y})\) から計算できるため、実際には \(H(6,6,\underline{Y})\) を送信する必要はない。同様に、\(H(5,8,\underline{Y})\) は \(H(5,6,\underline{Y})\) と \(H(7,8,\underline{Y})\) から計算できるため \(H(6,8,\underline{Y})\) も送信する必要が無い。(いずれにしても、受信側は適切な認証のためにこれらの値を計算しなければならない。) したがって、\(Y_5\) を認証するには \(H(1,8,\underline{Y})\) を事前に認証済みであることと、\(Y_5\)、\(H(6,6,\underline{Y})\)、\(H(7,8,\underline{Y})\)、\(H(1,4,\underline{Y})\) を送信することのみが必要である。すなわち、任意の \(Y_i\) を認証するには \(100 \times \log_2 n\) ビットの情報が必要である。

この方法は \(H(1,n,\underline{Y})\) の計算が再帰呼び出しの二分木を形成するためツリー認証 (tree authentication) と呼ばれている。ツリー内の特定の葉 \(Y_i\) を認証するには、葉から開始してルートへと進む、すなわち \(H(i,i,\underline{Y})\) から \(H(1,n,\underline{Y})\) までの \(H()\) の値のみが必要である。\(H(1,n,\underline{Y})\) は認証ツリーのルート、または \(R\) と呼ばれる。\(R\) から \(H(i,i,\underline{Y})\) へのパス近傍で \(Y_i\) の認証に必要な情報は、\(Y_i\) の認証パス (authentication path) と呼ばれる。

認証パスが実際に選択された葉を認証することの証明は、セクション 2 で \(F(x)\) が \(x\) を認証することの証明と同様であるため繰り返さない。特性 1 と特性 2 のどちらを使用すべきかを決定することが重要である。特性 1 を使用する場合、同じレベルのセキュリティを保持するために認証パスのサイズを 2 倍にしなければならない。この選択は、最初に認証ツリーを計算した人物を信用するかどうかに依存する。信頼する場合は特性 2 を選択できる。信用しない場合は特性 1 を使用しなければならない。これは特性 1 が計算方法から独立しているためである。特性 2 はランダム選択を要求し、ランダムでは内線宅によって破られる可能性がある。

これで、ツリー認証を使用してツリー署名を作成することはほぼ明らかとなった。A は \(Y_i\) を B に送信する。その後、A は \(Y_i\) の認証パスを送信する。B は事前の取り決めにより認証ツリーのルート \(R\) を知っている。そこで B は \(Y_i\) を認証でき、A からの署名済みメッセージを本物として受け入れることができる。

\(j\) 番目のユーザがルート \(R_j\) を持つ明確な認証ツリーを持っている場合、ツリー認証は \(Y_i\) の認証と同様に \(R_j\) の認証にも容易に使用できる。各ユーザが認証を行うためにすべての \(R_j\) を記憶する必要はない。中央クリアリングハウス (clearinghouse; 清算機関) が \(u\) 人のユーザすべてから \(R_j\) を受け取り、\(H(1,u,\underline{R})\) を計算できる。この 100-200 ビットの単一値は分散され、すべての \(R_j\) の認証に使用され、さらに \(Y_i\) の認証にも使用される。実際には A は \(R_A\) と \(R_A\) の認証パスを記憶し、\(Y_i\) と \(Y_i\) の認証パスと共にそれらを B に送信する。

一度計算された「ユーザツリー」に新しい葉 (あたらしユーザを表す) を追加することは不可能であるため、定期的に新しいユーザツリーを計算して発行する必要がある。この「柔軟性の欠如」こそまさに中央クリアリングハウスを信頼する必要がない理由である。新しいユーザを追加できないのであれば、なりすましユーザを追加することも不可能である。一方、新しいユーザを迅速かつ容易に、そして便利に追加できるシステムは、なりすましを迅速かつ容易に、そして便利に追加することによって破られる可能性がある。

別の認証方法として、クリアリングハウスがワンタイム署名を使用してシステムの新しいユーザに対すして「推薦状 (letters of reference)」を電子署名する方法がある。これは利便性党利点があるが、クリアリングハウスが (秘密裏に) 偽の推薦状に署名しないという信頼を得る必要がある。Kohnfielder [3] はこの方法を他の公開鍵暗号システムと組み合わせて使用することを提案している。

ツリー認証、電子署名、ワンタイム書目を使用するプロトコルの詳細な議論は、この論文の範囲をはるかに超えている。

7. パス再生成アルゴリズム

A は \(Y_i\) を B に送信する前にその認証パスを知っておく必要がある。しかし、そのためには \(i\) と \(j\) の様々な値に対して \(H(i,j,\underline{Y})\) を計算する必要がある。この例では、\(H(6,6,\underline{Y})\)、\(H(7,8,\underline{Y})\)、\(H(1,4,\underline{Y})\) を計算して \(Y_i\) と共に B に送信する必要があった。これは我々の例で使用した小さなツリーでは単純だが、送信直前に \(H(4194304,8388608,\underline{Y})\) を計算することは耐えがたい負担になるだろう。明らかな解決策の一つは、\(H(1,n,\underline{Y})\) を事前に計算し、すべての中間計算を保存すること、つまり、すべての認証パスを事前に計算することである。これにより \(Y_i\) の認証パスを迅速に再生成できるが、大量のメモリが必要となる。

より満足のゆく解決策は \(Y_1\), \(Y_2\), \(Y_3\), \(Y_4\), … をこの順序で認証したいという点に着目することである。\(Y_i\) の認証パスを再構築する際に使用される計算のほとんどは \(Y_{i+1}\) の認証パスの計算にも使用できる。必要なのは増分計算のみであり、その計算量は非常に控えめである。

さらに、(\(Y_i\) が生成される元の) \(X_i\) はランダムに見えるはずだが、実際には真にランダムな小さなシードを用いて擬似ランダムな方法で (安全に) 生成できる。\(X_i\) をメモリに保持する必要はなく、\(X_i\) の生成に使用した真にランダムな小さなシードのみを保持すれば十分である。

これらの考察の結果、各 \(Y_i\) とその認証パスを高速かつ控えめなメモリ使用量で再計算できるアルゴリズムが得られる。このアルゴリズムを説明する前に問題を確認する。

問題定義: 控えめな時間および空間の制約内で \(Y_1\), \(Y_2\), \(Y_3\), …, \(Y_n\) の認証パスを順次生成せよ。

アルゴリズムがすべての認証パスを効率的に生成する方法を理解する最も単純な方法は、小さな例を使ってすべての認証パスを生成することである。

\(n=8\) のすべての認証パスの例は:

TABLE 1 の各エントリを個別に計算しなければならない場合、認証パスを効率的に生成することは不可能である。幸いなことに、多くの重複がある。すべての重複エントリを削除すれば、TABLE 1 は TABLE 2 となる:

TABLE 2 の \(2\times n-1\) 個のエントリをそれぞれ個別に計算することによって、すべての認証パスを生成できることは明らかであるが、これは「効率的」なのだろうか? この疑問に答え、これらのエントリの計算コストを決定する前に、この「コスト」を測定する際に使用する単位を決定する必要がある。すべての計算は最終的に、基礎となる暗号化関数 \(C({\rm key},{\rm plaintext})\) に基づいて定義する必要があるため、計算コストは \(C\) の適用回数で定義することが適切と思われる。\(C\) の 1 回の適用が計算の 1「単位」となる。この「単位」を "et" (イーティーと発音) と呼び、これは「暗号化時間 (encryption time)」を表す。

\(F\) の計算にはその入力の長さに比例する数の et が必要である。特に、入力が \(k\times 100\) ビットで構成される場合、\(F\) は \(k-1\) et を必要とする。

まずここのエントリの計算コストを決定しなければならない。\(H(i,j,\underline{Y})\) のアルゴリズムは \(Y_i\), \(Y_{i+1}\), \(Y_{i+1}\), …, \(Y_j\) を葉とする部分木のツリー走査を行う。この走査の各非葉ノードで 1 et の計算 (200 ビットの引数に対する \(F\) の 1 回の適用) が実行される。非葉ノードは \(j-i\) 個あるため、計算には葉を除いて \(j-i\) 回の et が必要である。葉を再生成するために必要な計算は固定かつ有限である。葉を再生成するために必要な et 数 (固定) を \(r\) とする。\((j-i+1)\) 個の葉があるため、\(H(i,j,\underline{Y})\) を計算する全体的なコストは \((j-i)+(j-i+1)\times r\) et である。\(r\) が大きい場合、これを \((j-i+1)\times r\) et で近似できる。

これで TABLE 2 の各エントリの計算コストを近似できる。\(n\) 個のエントリは約 \(r\) et、\(n/2\) 個のエントリは約 \(2\times r\) et、\(n/4\) 個のエントリは \(4\times r\) et、\(n/8\) 個のエントリは \(8\times r\) et である。つまり、1 つの列のすべてのエントリを計算するのにかかる総コストは約 \(8 \times r\) et であることを意味する。4 列あるため、総計算量は約 \(4\times i\times r=32\times r\) et である。一般に、TABLE 2 を計算するために必要な計算量は \(n\times(1+\log_2 n)\times r\) et である。これは、各列のすべてのエントリを計算するのに \(n\times r\) et が必要であり、\(1+\log_2 n\) 列あるためである。

この結果は、認証パスを順次生成するアルゴリズムがパスあたりに約 \[ \begin{equation} \log_2 n \times r \label{eq1} \end{equation} \] et を必要とすることを示唆している。ここで \(r\) は葉を再生成するために必要な et 数を表す定数である。これは非常に合理的である。(次の 2 つの段落で説明するように、ピーク時の計算負荷も合理的である。)

確認証パスの生成にかかる時間はわずかだが、必要な記憶領域も小さいことを保証する必要がある。これは TABLE 2 をもう一度見ることで実現できる。認証パスを順次生成する際、列のエントリを順番に通過する。これは、任意の時点で我々の関心にある列のエントリが 2 つしかないことを意味する。つまり現在の認証パスに必要なエントリと、その直後のエントリである。現在の認証パスのエントリを知っておく必要がある。これがなければそのパスを生成できない。ある時点で、次の認証パスを生成するために列の次のエントリが必要になる。次のエントリを一度にすべて計算することは大きな労力を要する可能性があり、高いピーク負荷を生み出すため、増分的に計算し、実際に認証パスの生成に必要となる時間よりもかなり前に計算を開始する必要がある。

例えば、\(Y_1\), \(Y_2\), \(Y_3\), \(Y_4\) の認証パスには \(H(5,8,\underline{Y})\) が必要であり、\(Y_5\), \(Y_6\), \(Y_7\), \(Y_8\) の認証パスには \(H(1,4,\underline{Y})\) が必要である。最初の認証パスの \(H()\) の値は事前に計算されていなければならない。この事前計算が完了すると、後続の認証パスで必要な \(H()\) の値を増分的に計算されなければならない。最初の 4 つの認証パスを生成するとき、\(Y_5\) に到達するときに使用できるように \(H(1,4,\underline{Y})\) を継続的かつ増分的に計算しなければならない。さらに、最初の認証パスを生成する時に \(H(1,2,\underline{Y})\) の計算を開始しなければならず、\(Y_3\) に到達したときに \(H(7,8,\underline{Y})\) の計算を開始しなければならず、\(Y_5\) に到達したときに \(H(5,6,\underline{Y})\) の計算を開始しなければならず、以下同様に続く。

認証パスに必要な \(H()\) の値を増分的に計算することにより、ピーク時の計算量 (認証パスあたり \(O(\log_2 n)\) と平均計算量の両方が低くなることを保証する。

適切なブロックサイズ (100 ビット) を仮定して定数項を無視すれば、この方法で必要なメモリ量を計算できる。まず各列の計算に必要なメモリ量を決定し、次に \(\log_2 n\) 列すべてを合計する。列の現在のエントリを格納するためにブロックが 1 つ必要である。列の次のエントリを計算するために十分なメモリも必要である。\(H(i,j,\underline{Y})\) の計算に必要なメモリは \(1+\log_2(j-i+1)\) ブロックである。これは最大スタック深度が \(1+\log_2(j-i+1)\) となる単純な再帰アルゴリズムを前提としている。葉の再計算 (\(H(i,i,\underline{Y})\) の再計算) に必要なメモリ量は小さく (数ブロック程度)、定数であり、すべての列で同じメモリを共有できるため無視する。\(H()\) のメモリ要件を TABLE 2 と同じ形式で新しい表で表現すると TABLE 3 が得られる:

TABLE 3 は、TABLE 2 の各エントリを計算するために必要なエントリを示している。各列に必要なメモリは、次のエントリの計算に必要なメモリとほぼ同じである。つまり、必要なメモリの総量は約 \(3 + 2 + 1 = 9\) (訳注: 6 の誤記?) ブロックであることを意味する (これは \(H(1,8,\underline{Y})\) を再計算しないと仮定している)。

\(\log_2 n\) 列があり、各列は平均して \((\log_2 n)/2\) ブロックを必要とする。必要な総メモリは約: \[(\log_2 n)^2 / 2\] ブロックとなる。これは ^(n=2^{20}\) (1,048,576) の場合に必要なメモリが約 \(20 \times 20 / 2 = 200\) ブロックであることを意味する。100 ビットブロックの場合、これは 20 キロビット、すなはち 2.5 キロバイトを意味する。その他のオーバーヘッドは 2 または 3 キロバイトに及ぶ可能性があり、合計で 5 または 6 キロバイトのメモリを必要とするアルゴリズムが得られる。

このアルゴリズムは 2 つのマルチプロセッシングプリミティブを追加した Pascal 風の言語で記述された以下のプログラムで記述できる:

1. While <条件> wait
2. Fork <文>

さらに、関数 "MakeY(i)" は \(Y_i\) の値を再生成する。\(n\) は 2 のべき乗でなければならないことに注意。

このプログラムの一般的な構造はシンプルである。メインルーチンが \(\log_2 n\) 個のプロセスをフォークして \(\log_2 n\) 個の列を処理する。次の、各プロセスからの出力を順に出力することで各認証パスを出力する。このプログラムで大きく欠落しているのは、各プロセスが計算を出力する速度である。しかし、各プロセスには次の出力を計算するのに十分な時間があることは明らかである。これは "Emit" を 1 回呼び出すだけで \(2^i\) 個の認証パスに十分な出力を生成するが、次のエントリを計算するのに必要な時間が約 \(2^i\) であるという観察から導かれる。

このアルゴリズムを改善する主な方法が 3 つある。一つ目は各プロセスが他のプロセスから完全に独立していることである。しかし、別々のプロセスは多くの場合 \(H()\) の同じ中間値を必要とするため、これらの値を一度計算して結果を共有することができる。

二つ目は、\(H()\) の値は使用後に破棄され、必要に応じて後で再計算する必要があることである。\(H()\) のすべての値を保存するとメモリを大量に消費するが、一部の値を保存することで計算時間を短縮し、メモリ要件も削減できる。メモリ使用量の削減は、保存された値が再計算されない場合のメモリ節約によるものである。値を再計算するには計算のためのメモリが必要であるが、値を保存するには 1 ブロックしか必要ない。

最後に、プロセスを注意深くスケジューリングすることでメモリ要件を削減できる。各プロセスは約 \(\log_2 n\) ブロックのメモリを必要とするが、これは最大値であり標準的な値ではない。プロセスが大量のメモリを使用しているときに実行を高速化し、少量のメモリを使用しているときに減速することにより、プロセスの平均メモリ使用量 (ブロック秒単位で測定) を大幅に削減できる。一つのプロセスのピークメモリ要件が他のプロセスの最小メモリ要件と一致するようにプロセスをスケジューリングすることにより、必要な総メモリを削減できる。

これら 3 つのアプローチすべてがより注意深い研究に値する。時間と空間の潜在的な節約は大きい可能性がある。

アルゴリズムの時間要件を完全に分析するには MakeY の説明が必要である。つまり、式 (\(\ref{eq1}\)) の \(r\) を決定しなければならない。Lamport-Diffie アルゴリズムの改良版を使用すると仮定すれば、MakeY は疑似乱数 \(X_i\) ベクトルを生成し、そこから \(Y_i\) ベクトルを生成できなければならない。メッセージがすべて 100 ビットであれば、\(X_i\) ベクトルは \(100 + \log_2 100 = 107\) 個の要素を持つ。(より長いメッセージは、セクション 2 で説明した一方向関数を用いて 100 ビットのメッセージ空間にマッピングできる。)

\(X_i\) ベクトルは従来の暗号 \(C(\text{key},\text{plaintext})\) を使用して生成できる。\(X_i\) ベクトルを生成する疑似乱数プロセスの「シード」として 300 ビットの秘密鍵が 1 つ必要である。\(C\) の出力は常に 100 ビットであり、入力は 100 ビット以下でなければならない。ここで \(x\) を \[ x_{i,j} = C(\text{seedkey},\langle i,j \rangle) \] と定義できる。(ここで "seedkey" は、このやや型破りな疑似乱数生成器の「シード」として使用される、300 ビットの秘密かつ真にランダムな鍵である。) 添字 \(i\) は 1 から \(n\) までの範囲で、添字 \(j\) は 1 から 107 までの範囲である。\(n\) 個のメッセージがあり、それぞれ長さは 100 ビットである。各 \(X_i\) はベクトル \(x_{i,1}\), \(x_{i,2}\), …, \(x_{i,107}\) である。

他の \(x_{i,j}\) をいくつか知った上で任意の \(x_{i,j}\) を決定することは、既知平文攻撃 (known plaintext attack) の下で \(C\) を暗号解読する問題と同等である。\(C\) が認証済み暗号化関数である場合、鍵を事前に知ることなしに任意の \(x_{i,j}\) を決定することは不可能である。したがって秘密ベクトル \(X_i\) は安全である。

我々は \(y_{i,j} = F(x_{i,j})\) であり \(H(i,i,\underline{Y}) = F(Y_i) = F(\langle y_{i,1},y_{i,2},y_{i,3},\ldots,y_{i,107} \rangle)\) であることが分かっている。\(Y_i\) が \(107 \times 100\) ビットであるため、\(H(i,i,\underline{Y})\) の計算コストは 106 ビットである。\(H(i,i,\underline{Y})\) を計算する総労力は、\(X_i\) ベクトルの要素を生成する労力、\(F(x_{i,1})\), \(F(x_{i,2})\), …, \(F(x_{i,n})\) を計算する労力、そして \(F(Y_i)\) を計算する労力の合計である。これは、\(X_i\) ベクトルの計算に 107 et、\(Y_i\) ベクトルの計算に 107 et、\(F(Y_i)=H(i,i,\underline{Y})\) の計算に 106 et かかる。つまり、認証ツリーの各葉を再生成するのに合計 320 et かかる。

式 (\(\ref{eq1}\)) を使用すると認証パスあたりのコストは \(\log_n 2 \times 320\) et であることがわかる。\(n=2^{20}\) の場合、これは 6400 et である。1 秒あたり 1 つの認証パスを生成するには、1 et が約 160 マイクロ秒であることを意味する。ハードウェアでは容易に実現できるが、現在のコンピュータのソフトウェアではこの速度を達成するのは困難である。認証パスあたりの et 数を削減することは価値のある目標である。これは、\(H(i,i,\underline{Y})\) の計算コストを削減するか、\(H(i,i,\underline{Y})\) を計算する回数を減らすことによって効率的に行うことができる。

前述の通り、以前に計算した \(H()\) の値を破棄せずに保持し、\(\log_2 n\) 個のプロセス間で共通して使用される \(H()\) の値を共有することで、確認証パスの計算コストを削減できる。実際には (\(n=2^{20} の場合) 6,000 et を超える値から約 1,300 et への削減を達成できる (ただし、改良の複雑さのためここでは説明しない)。(これを視野に入れると、MakeY は 320 et を必要とし、認証パスごとに少なくとも 1 回実行されなければならない。したがって、320 et が MakeY を変更せずに達成できる絶対的な最小値である。) これは、基盤となる暗号化関数 \(C\) がソフトウェアで実装されている場合でも、パス再生成アルゴリズムが合理的な時間 (数秒) で実行できることを意味する。

8. 結論

公開鍵暗号システムを必要としない電子署名システムは、実現可能であるだけではなく認証も容易である。この論文では必要な空間と時間が比較的少なく、署名サイズが 1～3 キロバイトのシステムについて説明した。この論文で説明した方法は、認証に伴う長い遅延なしに迅速に実装できる。

9. ACKNOWLEDGEMENTS

It is a great pleasure for the author to acknowledge the pleasant and informative conversations he had with Dov Andelman, Whitfield Diffie, John Gill, Martin Hellman, Raynold Kahn, Loren Kohnfelder, Leslie Lamport, and Steve Pohlig.

10. BIBLIOGRAPHY

1. Diffie, W., and Hellman, M. New directions in cryptography. IEEE Trans. on Inform. IT-22, 6(Nov. 1976), 644-654.
2. Evans A., Kantrowitz, W., and Weiss, E. A user authentication system not requiring secrecy in the computer. Comm. ACM 17, 8(Aug. 19741, 437-442.
3. Kohnfelder, L.M. Using certificates for key distribution in a public-key cryptosystem. Private communication.
4. Lipton, S.M.,a nd Matyas, S.M. Making the digital signature legal--and safeguarded. Data Communications (Feb. 1978), 41-52.
5. McEliece, R.J. A public-key cryptosystem based on algebraic coding theory. DSN Progress Report, JPL, (Jan. and Feb. 1978), 42-44.
6. Merkle, R. Secure Communications over Insecure Channels. Comm. ACM 21, 4(Apr. 1978), 294-299.
7. Merkle, R., and Hellman, M. trapdoor knapsacks. IEEE Trans. on Inform. IT-24, 5(Sept. 1978), 525-530. Hiding information and signatures in
8. Rivest, R.L., Shamir, A., and Adleman, L. A method for obtaining digital signatures and public-key cryptosystems. Comm. ACM 21, 2(Feb. 1978), 120-126.
9. Wilkes, M.V., Time-sharing Computer Systems. Elsevier, New York, 1972.
10. Lamport, L., Constructing digital signatures from a one way function. SRI Intl. CSL - 98
11. Feistel, H., Cryptography and computer security. Scientific American, 228(May 1973), 15-23.
12. Shannon, C.E., Communication theory of secrecy systems. Bell Sys. Tech. Jour. 28(0ct. 1949) 656-715.
13. Rabin, M.O., Digitalized signatures. In Foundations of Secure Computation, R. Lipton and R. DeMillo, Eds., Academic Press, New York, 1978, pp. 165-166.

翻訳抄

公開鍵暗号に依存せず、従来の暗号化関数のみを使用して一方向関数とツリー構造を組み合わせたデジタル署名システムを提案する 1979 年の論文。現代の Merkle Tree やハッシュベース署名の基礎となる先駆的研究である。

1. Merkle, R.C. (1990). A Certified Digital Signature. In: Brassard, G. (eds) Advances in Cryptology — CRYPTO’ 89 Proceedings. CRYPTO 1989. Lecture Notes in Computer Science, vol 435. Springer, New York, NY. https://doi.org/10.1007/0-387-34805-0_21