ランポート署名

ランポート署名（ランポートしょめい、英: Lamport signature）とは、デジタル署名を構築するための手法である。ランポート署名は、任意の一方向性関数を用いて構成でき、一般には暗号学的ハッシュ関数を用いて実装される。

将来的に量子コンピュータの登場でRSAのような多くの暗号技術が脅威にさらされる中で、長いハッシュ値を持つハッシュ関数を用いたランポート署名は安全性を担保できると考えられている。

ランポート署名において、署名鍵は1つのメッセージの署名にしか利用できないという制約がある。だが、ハッシュ木を利用することで、1つの鍵で、複数のメッセージの署名をすることが可能である。

ランポート署名は、1979 年にLeslie Lamportによって発明され、発明者の名前にちなんで名付けられた。^[1]

鍵生成

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

$f$ を一方向性関数とする。

署名者は、 $f$ の定義域から独立一様ランダムに $2k$ 個の値 $y_{1,0},y_{2,0},\ldots ,y_{k,0}$ および $y_{1,1},y_{2,1},\ldots ,y_{k,1}$ をランダムに選ぶ。次に、各 $y_{i,j}$ に $f$ を作用させることで $z_{1,0}=f(y_{1,0}),\ldots ,z_{k,0}=f(y_{k,0})$ および $z_{1,1}=f(y_{1,1}),\ldots ,z_{k,1}=f(y_{k,1})$ を計算する。

署名鍵（秘密鍵）は $(y_{1,0},y_{2,0},\ldots ,y_{k,0},y_{1,1},y_{2,1},\ldots ,y_{k,1})$ であり、検証鍵（公開鍵）は $(z_{1,0},z_{2,0},\ldots ,z_{k,0},z_{1,1},z_{2,1},\ldots ,z_{k,1})$ である。

メッセージの署名生成

$k$ ビットのメッセージを $m=m_{1}\ldots m_{k}\in \{0,1\}^{k}$ とする。署名は

\operatorname {sig} (m_{1}\ldots m_{k})=(y_{1,m_{1}},\ldots ,y_{k,m_{k}})=(s_{1},\ldots ,s_{k})

である。

署名の検証

メッセージ $m=m_{1}\ldots m_{k}$ と署名 $(s_{1},\ldots ,s_{k})$ を持つ検証者は、全ての $1\leq i\leq k$ に対して $f(s_{i})=z_{i,m_{i}}$ が成り立つことをチェックし、成り立てば署名を受理する。

直感的な安全性の説明

署名を偽造するためには、偽造者は公開されている $y_{i,j}$ から、 $f(s_{i})=z_{i,j}$ を満たす $s_{i}$ を計算しなければならない。したがって、 $f$ が一方向性関数である限り、偽造は不可能である。

例

一方向性関数として、出力が256ビットであるハッシュ関数hash( )を用いるとしよう。

鍵ペア

署名に用いる秘密鍵は、ランダムな256×2個の256ビット列 $(y_{1,0},\ldots ,y_{256,0},y_{1,1},\ldots ,y_{256,1})$ である。検証に用いる公開鍵は、256×2個の256ビットハッシュ値 $(z_{1,0},\ldots ,z_{256,0},z_{1,1},\ldots ,z_{256,1})$ である。それぞれ128 Kibit である。

署名

メッセージ（あるいはそのハッシュ値）は256ビットであり、各ビットに対して乱数のペア $(y_{i,0},y_{i,1})$ が署名鍵として選ばれている。そこで，メッセージの $i$ ビット目が0ならば $y_{i,0}$ を署名に入れ、1ならば $y_{i,1}$ を署名に入れる。例えばメッセージが $m=m_{1}m_{2}m_{3}\ldots m_{256}=001\ldots 1$ であった場合、

( $i=1$ ) $m_{1}=0$ より、 $s_{1}=y_{1,0}$
( $i=2$ ) $m_{2}=0$ より、 $s_{2}=y_{2,0}$
( $i=3$ ) $m_{3}=1$ より、 $s_{3}=y_{3,1}$

　　 $\vdots$

( $i=255$ ) $m_{256}=1$ より、 $s_{256}=y_{256,1}$

とおき、署名を $(s_{1},s_{2},s_{3},\ldots ,s_{256})$ とする。署名は 256×256 bits = 64 Kibitである。

検証

検証者が256ビットのメッセージと、256個の $s_{i}$ からなる署名を得たとする。検証鍵は、256個のハッシュ値のペア $(z_{i,0},z_{i,1})$ から成る。そこで、署名内の各 $s_{i}$ のハッシュ値を計算し、メッセージの $i$ ビット目が0ならば $z_{i,0}$ とハッシュ値を等しいかを、1ならば $z_{i,1}$ とハッシュ値と等しいかを確認する。例えば上の例の場合、

( $i=1$ ) $hash(s_{1})=z_{1,0}$ が成り立つか？
( $i=2$ ) $hash(s_{2})=z_{2,0}$ が成り立つか？
( $i=3$ ) $hash(s_{3})=z_{3,1}$ が成り立つか？

　　 $\vdots$

( $i=255$ ) $hash(s_{256})=z_{256,1}$ が成り立つか？

を確認する。全て成り立つならば、署名を正しいものとする。

パラーメータの選択

ランポート署名の安全性は、一方向関数として用いるハッシュ関数の安全性と、ハッシュ関数の入力長に依存している。

ハッシュ関数が $n$ ビットのメッセージダイジェスト（ハッシュ値）を出力する場合、理想的な原像計算困難性を持つハッシュ関数において、一つのハッシュ値の原像を求めるために必要な計算量は $2^{n}$ である。（古典的計算機モデルの場合。）また、量子計算機の場合、グローバーのアルゴリズムを用いることで、原像を求めるために必要な計算量は $O(2^{n/2})$ に減らすことができることが知られている。したがって、 $2^{n}$ ないしは $2^{n/2}$ が十分大きくなるように、長いハッシュ値を出力するハッシュ関数を利用する必要がある。

一方、十分大きな $n$ を選択したとしても、ハッシュ関数に入力される $y_{i,j}$ が短い場合、ランポート署名は容易に署名偽造が可能である。例えば $y_{i,j}$ がわずか16ビットの場合、ハッシュ長 $n$ に関係なく、 $2^{16}$ 回のハッシュ計算で入力を全数探索でき、原像を求められる。よって、バランスの取れたシステム設計においては、ハッシュ関数への入力と出力は、同程度の長さとする。

グローバーのアルゴリズムの存在により、耐量子計算機安全性のためには、公開鍵の各要素 $z_{i,j}$ 、秘密鍵の各要素 $y_{i,j}$ および署名の各要素 $s_{i}$ は、システムのセキュリティパラメータの 2 倍以上でなければならない。つまり、

80 ビットセキュリティのシステムでは、160 ビット以上の長さを持つ要素を利用する。
128 ビットセキュリティのシステムでは、256 ビット以上の長さを持つ要素を利用するである。

ただし、上記の攻撃コストの見積もりは、理想的なハッシュ関数を前提とし、1つのハッシュ値をターゲットとして原像を求めようとする攻撃に限定しているため、注意が必要である。従来の計算機モデルにおいて $2^{3n/5}$ 個の原像を同時に求める場合、1つの原像あたりのコストが $2^{n/2}$ から $2^{2n/5}$ に減少することが知られている ^[2]。複数の原像を同時に計算する攻撃を考慮して最適な要素サイズを選択することは、未解決の問題である。 512 ビット要素や SHA-512 など、より大きな要素サイズと強力なハッシュ関数を利用すれば、これらの未知の問題に対して、より大きなセキュリティマージンが保証される。

最適化と亜種

秘密鍵の短縮

秘密鍵のすべての乱数は、十分な長さ（通常、秘密鍵内の1つの乱数と同じ長さ）のシードと暗号論的擬似乱数生成器から生成できる。したがって、シードのみを秘密鍵として保存しておくことができる。乱数は必要な時にシードから再生成すればよい。

同様に、１つのシードと疑似乱数生成器を用いて、多数の鍵ペア（公開鍵と秘密鍵）を作成することもできる。その場合、ランダムアクセス可能な擬似乱数生成器を使用する必要がある。

耐量子計算機安全性を考えるならば、BBS のような古典的な擬似乱数生成器ではなく、耐量子安全なものを使うべきである。

公開鍵の短縮

ランポート署名は、ハッシュリストと組み合わせることで、公開鍵をただ一つのハッシュ値とすることができる。すなわち、 $2k$ 個のハッシュ値 $z_{ij}$ から、さらにハッシュ値 $z=hash(z_{1,0}\|z_{2,1}\|\cdots \|z_{k,1})$ を計算し， $z$ のみを公開鍵として公開する。 $z$ を用いて署名の検証を行うためには、署名には、メッセージの各ビットに対応する乱数だけでなく、各ビットに対応していない乱数のハッシュ値を含める必要がある。その結果、署名のサイズは約2倍になる。

ハッシュリストの代わりに暗号学的アキュムレータを使用することで、署名にハッシュ値を追加しないで済む方法も知られている^[3]。

鍵と署名の短縮

Winternitz署名の圧縮手法を用いると、秘密鍵、公開鍵、署名のサイズを小さくすることができ、その代わり、署名を生成・検証する計算量が大きく増加する。この圧縮手法では、メッセージの1ビットごとに乱数およびハッシュ値を2つずつ用意する代わりに、メッセージを固定長のチャンクに分割し，チャンクごとに乱数および（多重）ハッシュ値を1つずつ用意する。したがって、チャンクを $L$ ビットとすると、鍵のサイズはオリジナルのランポート署名の鍵サイズに比べて $1/2L$ 程度に小さくなり、署名のサイズも $1/L$ 程度に小さくなる。署名の生成・検証には、チャンクごとに多重ハッシュを計算する必要があり、コストは約 $2^{L}/L$ 倍になる ^[4] ^[5]。

さらに、上述のようにハッシュリストを使用して、公開鍵をハッシュ値一つのみに短縮することもできる。（署名サイズは2倍になる。）

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

ランポート署名では、一つの（ $2k$ 個の値からなる）鍵は、一つのメッセージの署名にしか利用できない。もし、多くのメッセージに署名をしたいならば、多くの公開鍵を公開しておかなければならない。しかし、これら多くの公開鍵にハッシュ木を適用することで、ただ一つのトップハッシュのみを公開しておくことができる。このとき、署名には検証に必要はハッシュ木の一部の情報を含める必要があり、署名長は少し長くなるが、トップハッシュを公開鍵として多くのメッセージの検証をすることができる^[4]。