ランポート署名
メッセージ(あるいはそのハッシュ値)は256ビットであり、各ビットに対して乱数のペア ( y i , 0 , y i , 1 ) {\displaystyle (y_{i,0},y_{i,1})} が署名鍵として選ばれている。そこで,メッセージの i {\displaystyle i} ビット目が0ならば y i , 0 {\displaystyle y_{i,0}} を署名に入れ、1ならば y i , 1 {\displaystyle y_{i,1}} を署名に入れる。例えばメッセージが m = m 1 m 2 m 3 ... m 256 = 001 ... 1 {\displaystyle m=m_{1}m_{2}m_{3}\ldots m_{256}=001\ldots 1} であった場合、
( i = 1 {\displaystyle i=1} ) m 1 = 0 {\displaystyle m_{1}=0} より、 s 1 = y 1 , 0 {\displaystyle s_{1}=y_{1,0}}
署名を偽造するためには、偽造者は公開されている y i , j {\displaystyle y_{i,j}} から、 f ( s i ) = z i , j {\displaystyle f(s_{i})=z_{i,j}} を満たす s i {\displaystyle s_{i}} を計算しなければならない。したがって、 f {\displaystyle f} が一方向性関数である限り、偽造は不可能である。
ランポート署名(ランポートしょめい、英: Lamport signature)とは、デジタル署名を構築するための手法である。ランポート署名は、任意の一方向性関数を用いて構成でき、一般には暗号学的ハッシュ関数を用いて実装される。
将来的に量子コンピュータの登場でRSAのような多くの暗号技術が脅威にさらされる中で、長いハッシュ値を持つハッシュ関数を用いたランポート署名は安全性を担保できると考えられている。
ランポート署名において、署名鍵は1つのメッセージの署名にしか利用できないという制約がある。だが、ハッシュ木を利用することで、1つの鍵で、複数のメッセージの署名をすることが可能である。
ランポート署名は、1979 年にLeslie Lamportによって発明され、発明者の名前にちなんで名付けられた。
署名されるメッセージは固定の長さ( k {\displaystyle k} ビット)であるとする。もし、任意の長さのメッセージに署名したい場合には、まずハッシュ長が k {\displaystyle k} ビットの暗号学的に安全なハッシュ関数でハッシュ値を計算し、そのハッシュ値に対して署名の手続きをすることで署名することができる。
f {\displaystyle f} を一方向性関数とする。