ランポート署名

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

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

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

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

署名方式

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

${\displaystyle f}$ を一方向性関数とする。

鍵生成

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

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

メッセージの署名生成

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

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

である。

署名の検証

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

直感的な安全性の説明

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

例

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

鍵ペア

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

署名

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

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

　　${\displaystyle \vdots }$

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

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

検証

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

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

　　${\displaystyle \vdots }$

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

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

パラーメータの選択

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

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

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

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

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

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

最適化と亜種

秘密鍵の短縮

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

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

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

公開鍵の短縮

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

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

鍵と署名の短縮

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

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

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

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

脚注

1. Lamport, Leslie (October 1979). “Constructing Digital Signatures from a One Way Function”. SRI International (CSL-98). https://www.microsoft.com/en-us/research/publication/constructing-digital-signatures-one-way-function/ 20 August 2023閲覧。. 
2. http://csrc.nist.gov/groups/ST/hash/documents/preneel_nist_v2.pdf Bart Preneel, "Design Principles for Iterated Hash Functions Revised"]
3. “Can one use a Cryptographic Accumulator to efficiently store Lamport public keys without the need of a Merkle Tree?”. 20 August 2023閲覧。
4. ^ “A Certificated Digital Signature”. 20 August 2023閲覧。
5. “Winternitz one-time signature scheme”. 20 August 2023閲覧。