論文翻訳: A DIGITAL SIGNATURE BASED ON A CONVENTIONAL ENCRYPTION FUNCTION

2025年7月16日 1987年の論文

by Ralph C. Merkle
Elxsi
2334 Lundy Place
San Jose, CA 95131

ABSTRACT

従来型暗号化関数 (conventional encryption function) (DESなど) のみに基づいた新しいデジタル署名が記述されている。これは基盤となる暗号化関数と同等のセキュリティを持ち、セキュリティは素因数分解の困難性に依存せず、モジュラー算術の高い計算コストも回避される。この署名システムは無制限のメッセージに署名でき、署名サイズは署名されたメッセージの数の関数として対数的に増加する。「典型的な」システムにおける署名サイズは数百バイトから数キロバイトの範囲で、署名の生成には基盤となる従来型暗号化関数の計算が数百から数千回必要となる場合がある。

ABSTRACT
INTRODUCTION
一方向関数
1 ビットメッセージの署名
数ビットメッセージの署名
ワンタイム署名の無限ツリー
新しい署名アルゴリズム
結論
REFERENCES
翻訳抄

INTRODUCTION

従来の暗号化関数 (または一方向関数) のみに依存するデジタル署名システムが提案されてきたが [1, 3, 5, 10]、素因数分解 [2, 4] などのより複雑な数学的問題に基づくシステムのような利便性を提供するには至っていない。セキュリティが一方向関数のみに基づいているシステムに関心が寄せられる重要な理由は、そのような関数の存在が確実であるように思われるのに対し、素因数分解の複雑さや最も効率的な素因数分解アルゴリズムが依然として大きな関心事である未解決の問題だからである。これは純粋に学術的な関心事にとどまらず、その後破られた「破られない」暗号システムの数の多さを鑑みても特に重要である。

第二の利点は、モジュラー算術を必要とするシステムと比較して計算コストが削減されることである。DES (データ暗号化標準; the Data Encryption Standard) のソフトウェア実装は、 $N$ を法とする指数計算よりもはるかに高速に動作するため、DES の使用に基づくデジタル署名システムも同様に恩恵を受ける。この節約はハードウェア実装においてさらに顕著となる。なぜなら、DES チップは多くのメーカーから低コストで入手可能であり、既存の多くのシステムにすでに搭載されているためである。新しいデジタル署名システムは、すでに DES チップ (または任意の従来型暗号化関数のハードウェア実装) を搭載しているシステムに後付けすると、非常に高速に動作します。

本稿を自己完結型にするため、まず一方向関数とワンタイム署名に関する既知の結果を簡単にレビューし、次いで、このアプローチの受け入れと使用を妨げてきた制限と欠点を克服するデジタル署名システムを、ワンタイム署名システムを新しい方法で使用することでどのように提供できるかを示す。

一方向関数

一方向関数 $F$ は、計算は容易だが反転は困難な関数である。 $x$ が与えられたとき、 $y=F(x)$ の計算は容易だが、 $y$ が与えられた場合に $F(x)=y$ となるような $x$ を決定することは困難である。

一方向関数は、平文と暗号文が与えられた場合に鍵を推測することが非常に困難であるという観察に基づいて、従来の暗号化関数に基づかせることができる。従来の暗号化関数を $S_{key}(\text{plaintext}) = \text{ciphertext}$ と定義すると、一方向関数 $F(x)=y$ を $S_x(0)=y$ と計算することで定義できる。つまり、 $x$ を鍵として定数を暗号化する。結果の暗号文は一方向関数の出力です。 $y$ が既知の場合に $x$ を推測することは、平文が 0 で暗号文が $y$ であることが既知の場合に鍵を決定することと同等となる。

一方向ハッシュ関数、例えば任意に大きな入力 (数キロバイトなど) を受け取り、小さな固定サイズの出力 (64 ビットなど) を生成する一方向関数では、同様の方法で従来の暗号化関数の繰り返し適用に基づいて構築できる。一方向ハッシュ関数の設計には注意が必要である。最も明白なアプローチは、「平方根」攻撃 (square root attack) に対して脆弱な可能性がある。例えば DES を使用して 112 ビットを 64 ビットに削減したい場合、明白な手法は 112 ビットを 2 つの 56 ビットブロックに分割し、固定定数を二重暗号化することである。つまり 2 つの 56 ビットブロックを $K1$ と $K2$ と指定した場合、 $S_{K2}(S_{K1}(0))$ を計算する。残念ながら、「中間一致」(meet in the middle) または「平方根」攻撃を使用して、同じ結果を生成する新しい $K1'$ と $K2'$ を約 $2^{28}$ の操作で決定することが可能である。このような攻撃は回避できるが、それらの存在を知り、それらから防御することが重要である。

セキュアな一方向ハッシュ関数が利用可能であり、おそらく何らかの従来の暗号化関数に基づいていると仮定する。この関数を $F$ と表記する。

1 ビットメッセージの署名

このセクションと次のセクションでは、ワンタイム署名に不慣れな読者向けにワンタイム署名について簡単に説明する。これらの 2 つのセクションは連続性を損なうことなくスキップできる。

人物 A は次のプロトコルを使用して B に対して 1 ビットメッセージに署名できる: まず、事前計算において、A は $F$ を使用して $x$ の 2 つの値 $x[1]$ と $x[2]$ を一方向暗号化し、 $y$ の 2 つの値 $y[1]$ と $y[2]$ を生成する。次に、A は $y[1]$ と $y[2]$ を公開し、 $x[1]$ と $x[2]$ を秘密に保つ。最後に、1 ビットメッセージが '1' の場合、Aは $x[1]$ を B に与えることで署名する。1 ビットメッセージが '0' の場合、A は $x[2]$ を B に与えることで署名する。

1 ビットメッセージが '1' であった場合、B は $x[1]$ を提示して $F(x[1])=y[1]$ を示すことで A が署名したことを証明できる。 $F$ と $y$ の値は公開されているため誰でもこの計算結果を検証できる。A のみが $x[1]$ と $x[2]$ を知ることができるため、B が $x[1]$ を知っていることは A が $x[1]$ を B に与えたことを意味し、これは事前の合意により A がメッセージ '1' に署名したことを意味する。

数ビットメッセージの署名

A が多くの $x$ と $y$ を生成した場合、A は多くのビットを含むメッセージに署名できる。これは Lamport-Diffie のワンタイム署名 [1] である。 $n$ ビットのメッセージに署名するには $2n$ 個の $x$ と $2n$ 個の $y$ が必要である。

Merkle [5] はこの方法の改良を提案し、署名サイズをほぼ 2 倍に削減した。メッセージの各ビットに対して 2 つの $x$ と 2 つの $y$ を生成する代わりに、A は署名するメッセージの各ビットに対して 1 つの $x$ と 1 つの $y$ のみを生成する。署名するメッセージのビットの 1 つが '1' の場合、A は対応する $x$ の値を公開するが、署名するビットが '0' の場合は A は何も公開しない。これにより B は一部の $x$ を受け取らなかったふりをして、署名されたメッセージの一部の '1' ビットが '0' であったふりをすることができるため、A はメッセージ中の '0' ビットの数も署名しなければならない。B が '1' ビットを実際には '0' ビットであったふりをするには、B はカウントフィールドの値を増やさなければならないが、これは不可能である。カウントフィールドには $\log_{2}n$ ビットしかないため、署名サイズは $2n$ から $n+\log_{2}n$ へとほぼ半減する。

例えば 8 ビットメッセージ '0100 1110' に署名したい場合、まず '0' ビットの数を数え (4 つ存在する)、次に 3 ビットのカウントフィールド (値 4) を元の 8 ビットメッセージに追加して 11 ビットメッセージ '0100 1110 100' を生成する。これに $x[2]$ , $x[5]$ , $x[6]$ , $x[7]$ 、および $x[9]$ を公開することで署名する。B は $x[2]$ を受け取らなかったふりをすることはできない。なぜなら、結果として得られる誤ったメッセージ '0000 1110 100' には 4 ではなく 5 つの '0' が含まれるためである。同様に $x[9]$ を受け取らなかったふりをすると誤ったメッセージ '0100 1110 000' が生成され、そこではカウントフィールドが '0' が全くないことを示す。B が受け取らなかったふりをすることで、正当なメッセージをでっち上げることができる $x$ の組み合わせは存在しない。

Winternitz [6] は署名サイズを数倍に削減する改良を提案しました。A は $y[1]=F(x[1])$ と $y[2]=F(x[2])$ を事前計算することで 1 ビットメッセージに署名できる代わりに、 $y[1]=F(F(F(F(x[1]))))$ と $y[2]=F(F(F(F(x[2]))))$ を事前計算することで 2 ビットメッセージに署名できるようになる。表記上、関数 $F$ の繰り返し適用を上付き文字で示します。つまり $F^{3}(x)$ は $F(F(F(x)))$ 、 $F^{2}(x)$ は $F(F(x))$ 、 $F^{1}(x)$ は $F(x)$ 、 $F^{0}(x)$ は x である。A がメッセージ $m$ ('0', '1', '2', '3' いずれかでなければならない) に署名したい場合、A は (F^{m}(x[1])\) と $F^{3-m}(x[2])$ を公開する。B は、 $y$ に到達するために $F$ がさらに何回適用される必要があるかを数えることで、A が使用した $F$ のべき乗を簡単に検証できる。B は、A が実際に送ったよりも高いべき乗を受け取ったふりをする可能性があるため、 $x[1]$ と $x[2]$ の両方の相補的なべき乗を計算する必要がある。つまり、A が $F^{2}(x[1])$ を B に送った場合、B は $F^{3}(x[1])$ を計算でき、代わりに A がこの値を送ったふりをすることができる。しかし B がこれを行う場合、B は $F^{0}(x[2])$ も計算しなければならず、これは A が実際にメッセージ '3' に署名した場合に計算して B に送ったはずの値である。A が実際に送ったのは $F^{1}(x[2])$ であるため、これは B が $F(x[2])$ のみから $x[2]$ を計算しなければならないことを意味するが、これは不可能である。この手法で $x[1]$ と $x[2]$ の相補的なべき乗を送ることは、Lamport-Diffie の方法で $x[1]$ または $x[2]$ のいずれかを公開することと直接類似している。

この例は 4 つのメッセージのうちの 1 つに署名する方法を示しているが、このシステムは $y[1]=F^{n-1}(x[1])$ と $y[2]=F^{n-1}(x[2])$ を事前計算することで、 $n$ 個のメッセージのうちの 1 つに署名するように一般化できる。

Merkle によって提案された 1 ビットワンタイム署名に対するほぼ 2 倍の改善は、Winternitz ワンタイム署名に一般化される。

したがって、Lamport と Diffie によって提案され Winternitz と Merkle によって改良された元のワンタイム署名システムは、任意のメッセージに署名するために使用でき、優れたセキュリティを持っている。単一メッセージに署名するためのストレージと計算要件は非常に合理的である。残念ながら、より多くのメッセージに署名するにはより多くの $x$ と $y$ が必要となり、その結果、( $y$ を保持する) 公開ファイルのエントリが非常に大きくなる。A が 1000 のメッセージに署名できるようにするには約 10,000 の $y$ が必要となる可能性があり、システムに 1000 の異なるユーザーがいて、それぞれが 1000 のメッセージに署名したい場合、公開ファイルのストレージ要件は何百メガバイトにも増加し、これは扱いにくく、これらのシステムの使用を事実上妨げている。

ワンタイム署名の無限ツリー

新しいシステムの一般的な考え方は、ワンタイム署名の無限ツリーを用いることである。簡略化のためツリーは二分木であると仮定する。無限ツリーの根は公開ファイルに置くことで簡潔に認証される。ツリーの各ノードは三つの機能を果たす。すなわち、(1) 左サブノードの認証、(2) 右サブノードの認証、(3) 単一メッセージへの署名である。ツリーには無限のノードが存在するため、無限のメッセージに署名が可能となる。これら三つの機能を遂行するために、各ノードは三つの署名、すなわち「左」署名、「右」署名、「メッセージ」署名を有さねばならない。「左」署名は左サブノードへの「署名」に用いられ、「右」署名は右サブノードへの「署名」に用いられる一方、「メッセージ」署名はユーザーメッセージへの署名に利用される。

表記上、ツリー内のノードに以下の方法で番号を付けると便利である。

ルートノードを '1' で指定する。
ノード $i$ の左サブノードを $2i$ で指定する。
ノード $i$ の右サブノードを $2i+1$ で指定する。

この番号付けの割り当てには多くの便利な特性がある。無限ツリー内のすべてのノードを一意に番号付けし、左サブノードと右サブノードは親ノードから容易に計算でき、また親ノードはサブノードから単純な整数除算 2 によって計算できる。ノード 1 から開始し、各ノードで左サブノードを辿ると、ノード番号は 1, 2, 4, 8, 16, 32, 64, ... となる点に注意。

ツリーの異なるノードにおいて異なるメッセージに署名するために用いられる $x$ と $y$ を区別すべく、いくつかのさらなる表記規則を採用する。特に、 $x$ と $y$ の 3 次元配列を用いる。すなわち、配列 $x[$ <node number>, <left,right, or message>, <index within the one-time signature> $]$ である。元の Lamport-Diffie 方式 (署名ごとに 128 個の $x$ を使用) を用いる場合、ノード $i$ のすべての $x$ は以下のようになる:

$x[i, \text{left}, 1], x[i, \text{left}, 2] \ldots x[i, \text{left}, 128]$
$x[i, \text{right}, 1], x[i, \text{right}, 2] \ldots x[i, \text{right}, 128]$
$x[i, \text{message}, 1], x[i, \text{message}, 2] \ldots x[i, \text{message}, 128]$

ノード $i$ の「左」署名に関するすべての $x$ を $x[i,\text{left},*]$ と指定する。同様に、ノード $i$ のメッセージ署名に関連するすべての $y$ を $y[i,\text{right},*]$ と指定する。ノード $i$ のすべての $x$ (左、右、メッセージ) を $x[i,*,*]$ と指定する。

特定の署名のすべての $y$ に一方向ハッシュ関数を適用したい場合が多いため、表記 $F(y[i,right,*])$ を、ノード $i$ の右署名のすべての $y$ に一方向ハッシュ関数 $F$ を適用することと定義する。

したがって、我々の基本的なデータ構造は $x$ と $y$ という二つの無限 3 次元配列となり、各 $y$ は対応する $x$ から $F$ を適用することによって計算される。

特定のノードにおけるすべての $y$ の「ハッシュ合計」を計算したい場合が多々ある。これを行うには、まず各署名に個別に $F$ を適用し、次に三つの結果値に $F$ を適用する。ここで、関数 ${\rm HASH}(i)$ を以下のように定義する: ${\rm HASH}(i) = F(F(y[i,\text{left},*]), F(y[i,\text{right},*]), F(y[i,\text{message},*]))$

これはノード $i$ の一方向ハッシュ合計である。この合計は重要な特性を有しており、もし我々が既に ${\rm HASH}(i)$ を知っており、誰かが $y[i,*,*]$ の値だと主張するものを送ってきた場合、関数を再計算することで彼らが正しい値を送ってきたことを確認できる (あるいは間違った値を送ってきたことを示す)。送られてきた値から計算された ${\rm HASH}(i)$ の値が我々が既に知っている値と一致すれば、我々は正しい $y[i,*,*]$ の値を受け取ったことになる。

署名プロトコルに先立ち A は ${\rm HASH}(1)$ を公開ファイルに入力する。この値は A の認証ツリーのルートノードを認証し、それは誰にでも公に知られているものと仮定される。

これで、A が署名 $i$ でメッセージ $m$ に署名するために使用するアルゴリズム、および B がその署名をチェックするために使用するアルゴリズムを説明できる。

新しい署名アルゴリズム

A と B は署名するメッセージ $M$ について事前に合意する。A は署名に使用するノード $i$ を選択します。

A は $i$ と $y[i,\text{message},*]$ を B に送信する。
A は $x[i,\text{message},*]$ の適切な $x$ のサブセットを B に送信することでメッセージ $M$ に署名する。
B は、公開された $x[i,\text{message},*]$ のサブセットが $y[i,\text{message},*]$ と照合されたときに、メッセージ $M$ に正しく署名されているかを確認する。
A は $F(y[i,\text{left},*])$ , $F(y[i,\text{right},*])$ 、および $F(y[i,\text{message},*])$ を B に送信する。
A は ${\rm HASH}(i)$ を計算する。定義によりこれは次のようになる: $F(F(y[i,\text{left},*]), F(y[i,\text{right},*]), F(y[i,\text{message},*]))$
$i$ の値が 1 の場合、B は A が送信した値から計算された ${\rm HASH}(1)$ の値が公開ファイルのエントリ ${\rm HASH}(1)$ と一致するかを確認し、アルゴリズムは終了する。
$i$ が偶数の場合、
- A は B に $y[i/2,\text{left},*]$ を送信する。
- A は $x[i/2,\text{left},*]$ の正しいサブセットを送信することで ${\rm HASH}(i)$ に署名する。
- B は ${\rm HASH}(i)$ を計算し、 $x$ を $y[i/2,\text{left},*]$ と照合して適切に署名されていることを検証する。
$i$ が奇数の場合、
- A は $y[i/2,\text{right},*]$ を B に送信する。
- A は $x[i/2,\text{right},*]$ の正しいサブセットを送信することで ${\rm HASH}(i)$ に署名する。
- B は ${\rm HASH}(i)$ を計算し、 $x$ を $y[i/2, \text{right},*]$ の $y$ と照合して適切に署名されていることを検証する。
A と B の両方は $i$ を $i/2$ に置き換えてステップ 4 に進む。

アルゴリズムが終了すると、B は $\log_2 i$ 個のワンタイム署名を有しており、そのうちの一つは B が実際に必要としたメッセージ $M$ のワンタイム署名である。残りの各署名は次の署名の正確性と有効性を検証し、さらに「ルート」署名の有効性は公開ファイルのエントリによって証明される。したがって、このワンタイム署名の「監査証跡 (audit trail)」は ${\rm HASH}(1)$ から始まり、 ${\rm HASH}(i)$ に進み、最終的にメッセージ $M$ のワンタイム署名で終了する。

この「メタシステム」があらゆるワンタイム署名システムを利用できること、そしてワンタイム署名システムの改善がメタシステムの性能に相応の改善をもたらすことは明らかである。現在のワンタイム署名システムが完成の域に達したと信じる特別な理由はなく、したがってワンタイム署名システムに関するさらなる研究は、価値ある性能向上をもたらす可能性が十分にある。

二分木の使用が任意であることもまた明らかである。これは容易に $K$ -ary ツリーとすることも可能であり、おそらく実用上はそうなるであろう。二分木は $log_2 i$ 個のワンタイム署名を必要とする一方、 $K$ -aryツリーは $\log_K i$ 個のワンタイム署名しか必要とせず、これは一般に $K$ の値が大きいほど全体の署名サイズを小さくする。しかしながら、 $K$ -aryツリーにおいては、 ${\rm HASH}(i)$ の計算は以下のようになる: $\begin{align*} F( \\ & F(y[i,\text{first-sub-node},*]),\\ & F(y[i,\text{second-sub-node},*]),\\ & F(y[i,\text{third-sub-node},*]),\\ & \ \vdots \\ & F(y[i,\text{$K$th-sub-node},*])\\ & F(y[i,\text{message},*])\\ &) \end{align*}$

各ノードでの計算は、 $K$ 個の全サブノードのすべての $y$ が再計算される必要があるため、より時間がかかる。また、結果として得られる署名内の各ノードはより多くのメモリを必要とする。したがって $K$ の最適な値はこれらの制約に抵触しないようあまり大きくすることはできない。

$K$ の値が増加するにつれて各ノード内で必要とされる追加の認証情報を最小化するという問題は、それ自体が興味深いものである。上記で述べたように、各ノードの署名の一部として必要とされる情報は $K$ に線形に比例して増加する。これは、著者の以前の「ツリー署名」法において $\log_2 K$ に削減されている。この二つのシステムを単一のハイブリッドに結合することは非常に適切と思われ、かなり大きなKの値を効率的に使用できるようになるだろう。著者の以前の「ツリー署名」法 [3, 7 page 170] は、両者ともツリーを使用しているものの、現在の方法とは概念的にかなり異なる。Goldwasser, Micali, Rivest [8, 9] もまたデジタル署名において望ましい理論的特性を提供するためにツリー状の構造を使用している点は興味深い。彼らの署名システムは「...大きな素数を掛け合わせることで構築される (RSAシステムのように)「爪なし (claw-free)」な [トラップドア] 置換の存在に基づく」ものである。

最後に、一部の読者は無限の 3 次元配列 $x$ と $y$ をユーザー A が保存するのは扱いにくいと異議を唱えるかもしれない。そのため圧縮スキームが適切であると思われる。 $y$ の配列は $x$ の配列から計算されるため $y$ を実際に保存する必要はない。 $x$ の配列は A が望む任意の方法で A によってランダムに選択される。A は $x$ を安全な擬似乱数的な方法で生成することもできる。特に、A は $i$ , $j$ , $k$ を連結し、秘密鍵を使用して従来の暗号化関数でこのビットパターンを暗号化することで $x[i,j,k]$ を計算できる。すなわち、 $x[i,j,k]=S_{\text{A's secret key}}(\langle i,j,k \rangle)$ である。もし DES を使用するなら A の秘密鍵はわずか 56 ビットでよい。たとえ多くの $x$ が (様々なメッセージに署名する過程で) 公開された後でも A の秘密鍵を決定することは不可能である。ペア $(\langle i,j,k\rangle, x[i,j,k])$ は平文と暗号文のペアであり、定義上、多くのそのようなペアが知られている場合でも、従来の暗号化関数の鍵を決定することはできない。

実用上、A が記憶しておく必要があるのは単一の秘密鍵 (おそらく56ビット) と最後にメッセージに署名するために使用されたツリー内のノードを追跡するための単純な整数カウンタ (おそらく 20 または 30 ビット) のみである。計算が正しく順序付けされていれば、署名の生成は非常に少ないメモリで行うことができる (128バイトのRAMで十分)。このような少ないメモリ (さらに少ないメモリも) は「スマートカード」(コンピュータ内蔵のクレジットカード) のような低コストで大量生産されるアプリケーションでよく見られる。

結論

従来の暗号化関数のみに基づいたデジタル署名システムが提示された。署名および署名チェックのアルゴリズムは高速であり、ごく少量のメモリしか必要としない。署名のサイズは、署名されたメッセージの数の対数として増加する。署名サイズとメモリ要件は、計算要件とトレードオフ可能である。

REFERENCES

'New Directions in Cryptography', IEEE Trans. on Information Theory, IT-22, 6(Nov. 1976), 644-654
'A method for obtaining digital signatures and public-key cryptosystems.' CACM 21,2, Feb. 1978 120-126
'Secrecy, Authentication, and Public Key Systems', Ralph C. Merkle, UMI Research Press 1982.
'How to Prove Yourself: Practical Solutions to Identification and Signature Problems', Amos Fiat and Adi Shamir, 1986.
'Making the Digital Signature Legal -- and Safeguarded', S.M. Lipton, S.M. Matyas, Data Communications, Feb. 1978 41-52.
Private Communication, Robert Winternitz, 1980.
'Cryptography and Data Security', by Dorothy E.R. Denning, Addison Wesley 1982.
'A "Paradoxical" solution to the Signature Problem', by Shafi Goldwasser, Silvio Micali and Ronald L. Rivest, from the Symposium on the Foundations of Computer Science, 1984, page 441-448.
'A Digital Signature Scheme Secure Against Adaptive Chosen Message Attack', by Shafi Goldwasser, Silvio Micali and Ronald L. Rivest, extended abstract, 1986.
'Cryptography: a New Dimension in Computer Data Security', by Carl H. Meyer and Stephen M. Matyas, Wiley 1982.

翻訳抄

従来型暗号化関数のみに基づき、素因数分解の困難性やモジュラー算術の高い計算コストに依存しないデジタル署名システムについて論じた 1987 年の論文。R.C.Merkle が以前に提唱したツリー構造に基づく認証 (後の Merkle Tree の基礎) を、従来型暗号化関数を用いたデジタル署名システムへ応用し、その実用性を高めている。

Merkle, R.C. (1987) A Digital Signature Based on a Conventional Encryption Function. Conference on the Theory and Application of Cryptographic Techniques, Santa Barbara, 16-20 August 1987, 369-378. https://doi.org/10.1007/3-540-48184-2_32