ランポート署名

ランポート署名とは

ランポート署名（Lamport signature）は、1979年にレスリー・ランポートによって考案されたデジタル署名方式です。この署名方式は、任意の一方向性関数を利用して構築でき、特に暗号学的ハッシュ関数を用いた実装が一般的です。ランポート署名の大きな特徴は、将来的な量子コンピュータの登場によってRSAなどの既存の暗号技術が脅かされる可能性がある中で、長いハッシュ値を持つハッシュ関数を用いることで安全性を担保できると考えられている点です。

ランポート署名の基本原理

ランポート署名では、署名鍵は1つのメッセージの署名にしか利用できないという制約があります。しかし、ハッシュ木を利用することで、1つの鍵で複数のメッセージに署名することが可能になります。この仕組みは、ランポート署名を実用的なものにする上で重要な要素です。

署名方式の詳細

ここでは、ランポート署名の具体的な手順について解説します。

前提条件

まず、署名対象のメッセージは固定長（kビット）であるとします。任意の長さのメッセージに署名したい場合は、まずメッセージをハッシュ長がkビットの暗号学的に安全なハッシュ関数でハッシュ化し、そのハッシュ値に対して署名を行います。

鍵生成

1. 乱数の選択: 署名者は、一方向性関数fの定義域から2k個の値を独立かつ一様ランダムに選択します。これらの値をy1,0, y2,0, ..., yk,0 および y1,1, y2,1, ..., yk,1とします。
2. ハッシュ値の計算: 次に、各yi,jに一方向性関数fを適用して、z1,0 = f(y1,0), ..., zk,0 = f(yk,0)およびz1,1 = f(y1,1), ..., zk,1 = f(yk,1)を計算します。
3. 鍵の構成: 署名鍵（秘密鍵）は(y1,0, y2,0, ..., yk,0, y1,1, y2,1, ..., yk,1)であり、検証鍵（公開鍵）は(z1,0, z2,0, ..., zk,0, z1,1, z2,1, ..., zk,1)となります。

メッセージの署名生成

kビットのメッセージm = m1...mk (各miは0または1)に対して、署名は以下のように生成されます。

sig(m1...mk) = (y1,m1, ..., yk,mk) = (s1, ..., sk)

署名の検証

メッセージm = m1...mkと署名(s1, ..., sk)を受け取った検証者は、すべての1 ≤ i ≤ kに対して、f(si) = zi,miが成り立つかを検証します。これがすべて成り立つ場合、署名は受理されます。

安全性の直感的説明

ランポート署名の安全性の根拠は、一方向性関数の性質にあります。署名を偽造するためには、公開されているyi,jからf(si) = zi,jを満たすsiを計算する必要があります。しかし、fが一方向性関数である限り、この計算は困難であるため、偽造は事実上不可能であるとされています。

具体例

例として、出力が256ビットのハッシュ関数hash()を用いる場合を考えてみましょう。

鍵ペアの生成

• - 秘密鍵: 256×2個のランダムな256ビット列(y1,0, ..., y256,0, y1,1, ..., y256,1)です。
• - 公開鍵: 256×2個の256ビットハッシュ値(z1,0, ..., z256,0, z1,1, ..., z256,1)です。それぞれ128Kibitになります。

署名の生成

256ビットのメッセージmに対して、各ビットmiが0ならばyi,0を、1ならばyi,1を署名に含めます。例えばm=001…1の場合、署名は(y1,0, y2,0, y3,1, ..., y256,1)となり、全体のサイズは64Kibitです。

署名の検証

検証者は、署名内の各siのハッシュ値を計算し、メッセージのiビット目が0ならばzi,0と、1ならばzi,1と一致するかを確認します。全て一致すれば、署名は正しいと判断します。

パラメータの選択

ランポート署名の安全性は、ハッシュ関数の安全性とハッシュ関数の入力長に依存します。ハッシュ関数がnビットのハッシュ値を出力する場合、理想的なハッシュ関数では、原像を求めるのに必要な計算量は古典計算機で2^n、量子計算機ではO(2^(n/2))となります。そのため、十分大きなnを選択する必要があります。また、ハッシュ関数への入力yi,jが短いと、署名が容易に偽造される可能性があるため、入力と出力は同程度の長さに設定する必要があります。耐量子計算機安全性を考慮すると、各要素はセキュリティパラメータの2倍以上の長さが必要です。

最適化と亜種

ランポート署名には、いくつかの最適化と亜種が存在します。

秘密鍵の短縮

秘密鍵のすべての乱数は、十分な長さのシードと暗号論的擬似乱数生成器から生成できるため、シードのみを秘密鍵として保存できます。これにより、鍵のサイズを大幅に削減できます。

公開鍵の短縮

ハッシュリストと組み合わせることで、公開鍵を単一のハッシュ値に短縮できます。これにより、公開鍵のサイズを大幅に削減できます。

鍵と署名の短縮

Winternitz署名の圧縮手法を用いると、秘密鍵、公開鍵、署名のサイズを小さくできますが、その代わりに、署名の生成・検証の計算量が大きくなります。

複数メッセージに対応する公開鍵の短縮

ハッシュ木を利用することで、多数のメッセージに対応する公開鍵を1つのトップハッシュにまとめることができます。これにより、鍵管理が容易になります。

まとめ

ランポート署名は、シンプルながら強力なデジタル署名方式です。その安全性は、利用する一方向性関数（特にハッシュ関数）の強度に依存します。量子コンピュータの脅威に対する耐性も期待されており、今後の暗号技術において重要な役割を果たす可能性があります。ただし、パラメータの選択や最適化手法の適用には注意が必要であり、用途に応じて適切な設定を行うことが求められます。

もう一度検索