ランポート署名
ランポート署名の安全性は、一方向関数として用いるハッシュ関数の安全性と、ハッシュ関数の入力長に依存している。
ハッシュ関数が n {\displaystyle n} ビットのメッセージダイジェスト(ハッシュ値)を出力する場合、 理想的な原像計算困難性を持つハッシュ関数において、 一つのハッシュ値の原像を求めるために必要な計算量は 2 n {\displaystyle 2^{n}} である。(古典的計算機モデルの場合。)また、量子計算機の場合、グローバーのアルゴリズムを用いることで、原像を求めるために必要な計算量は O ( 2 n / 2 ) {\displaystyle O(2^{n/2})} に減らすことができることが知られている。 したがって、 2 n {\displaystyle 2^{n}} ないしは 2 n / 2 {\displaystyle 2^{n/2}} が十分大きくなるように、長いハッシュ値を出力するハッシュ関数を利用する必要がある。
一方、十分大きな n {\displaystyle n} を選択したとしても、ハッシュ関数に入力される y i , j {\displaystyle y_{i,j}} が短い場合、ランポート署名は容易に署名偽造が可能である。例えば y i , j {\displaystyle y_{i,j}} がわずか16ビットの場合、ハッシュ長 n {\displaystyle n} に関係なく、 2 16 {\displaystyle 2^{16}} 回のハッシュ計算で入力を全数探索でき、原像を求められる。