ランポート署名のソースを表示

{{出典の明記|date=2017年1月24日 (火) 02:12 (UTC)}}
ランポート署名（ランポートしょめい、{{lang-en-short|Lamport signature}}）とは、[[デジタル署名]]を構築するための手法である。ランポート署名は、任意の[[一方向性関数]]を用いて構成でき、一般には[[暗号学的ハッシュ関数]]を用いて実装される。

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

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

ランポート署名は、1979 年に[[Leslie Lamport]]によって発明され、発明者の名前にちなんで名付けられた。<ref name="lamport1979">{{cite journal |last1=Lamport |first1=Leslie |title=Constructing Digital Signatures from a One Way Function |journal=SRI International |date=October 1979 |issue=CSL-98 |url=https://www.microsoft.com/en-us/research/publication/constructing-digital-signatures-one-way-function/ |access-date=20 August 2023}}</ref>

== 署名方式 ==

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

<math>f</math> を[[一方向性関数]]とする。

=== 鍵生成 ===

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

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

=== メッセージの署名生成 ===

<math>k</math>ビットのメッセージを <math>m = m_1 \ldots m_k \in \{0, 1\}^k</math> とする。
署名は
:<math>\operatorname{sig}(m_1 \ldots m_k) = (y_{1,m_1}, \ldots, y_{k,m_k}) = (s_1, \ldots, s_k)</math>
である。

=== 署名の検証 ===

メッセージ <math> m = m_1 \ldots m_k </math> と署名 <math>(s_1, \ldots, s_k)</math> を持つ検証者は、全ての<math>1 \leq i \leq k</math> に対して
<math>f(s_i) = z_{i,m_i}</math> が成り立つことをチェックし、成り立てば署名を受理する。 

=== 直感的な安全性の説明 ===

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

== 例 ==

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

=== 鍵ペア ===

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

=== 署名 ===

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

　　<math>\vdots </math> 
* (<math> i=255</math>) <math> m_{256} = 1 </math> より、<math> s_{256} = y_{256,1} </math> 
とおき、署名を <math> (s_1,s_2,s_3,\ldots,s_{256}) </math> とする。署名は 256×256 bits = 64 Kibitである。

=== 検証 ===

検証者が256ビットのメッセージと、256個の<math>s_i</math>からなる署名を得たとする。検証鍵は、256個のハッシュ値のペア <math>(z_{i,0},z_{i,1})</math> から成る。そこで、署名内の各 <math>s_i</math> のハッシュ値を計算し、メッセージの <math>i</math> ビット目が0ならば <math>z_{i,0}</math> とハッシュ値を等しいかを、1ならば <math>z_{i,1}</math> とハッシュ値と等しいかを確認する。
例えば上の例の場合、
* (<math> i=1</math>) <math> hash(s_1) = z_{1,0} </math> が成り立つか？
* (<math> i=2</math>) <math> hash(s_2) = z_{2,0} </math> が成り立つか？
* (<math> i=3</math>) <math> hash(s_3) = z_{3,1} </math> が成り立つか？

　　<math>\vdots </math> 
* (<math> i=255</math>) <math> hash(s_{256}) = z_{256,1} </math> が成り立つか？
を確認する。全て成り立つならば、署名を正しいものとする。

== パラーメータの選択 ==

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

ハッシュ関数が <math>n</math> ビットのメッセージダイジェスト（ハッシュ値）を出力する場合、
理想的な[[暗号学的ハッシュ関数#特性|原像計算困難性]]を持つハッシュ関数において、
一つのハッシュ値の原像を求めるために必要な計算量は <math> 2^n </math> である。（古典的計算機モデルの場合。）また、量子計算機の場合、[[グローバーのアルゴリズム]]を用いることで、原像を求めるために必要な計算量は <math> O(2^{n/2})</math> に減らすことができることが知られている。
したがって、<math> 2^n </math> ないしは <math> 2^{n/2} </math> が十分大きくなるように、長いハッシュ値を出力するハッシュ関数を利用する必要がある。
<!-- 公開鍵と署名の各ビットは、ハッシュ関数の呼び出しを 1 回だけ必要とする短いメッセージに基づいています。 -->

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

グローバーのアルゴリズムの存在により、耐量子計算機安全性のためには、公開鍵の各要素 <math>z_{i,j}</math>、秘密鍵の各要素 <math>y_{i,j}</math> および署名の各要素  <math>s_i</math> は、システムのセキュリティパラメータの 2 倍以上でなければならない。つまり、
* 80 ビットセキュリティのシステムでは、160 ビット以上の長さを持つ要素を利用する。
* 128 ビットセキュリティのシステムでは、256 ビット以上の長さを持つ要素を利用するである。

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

== 最適化と亜種 ==

=== 秘密鍵の短縮 ===

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

<!-- Note a cryptographically secure hash (or at least whose output is not XORed with the seed) can not be used instead of CSPRNG 
because signing a message would reveal additional random values from the private key. If the adversary can access the signature before the intended recipients can, then 
he can forge a signature with a halving of security level for each doubling of the revealed random values from the private key.
 -->
同様に、１つのシードと疑似乱数生成器を用いて、多数の鍵ペア（公開鍵と秘密鍵）を作成することもできる。その場合、[[ランダムアクセス]]可能な擬似乱数生成器を使用する必要がある。

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

=== 公開鍵の短縮 ===

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

ハッシュリストの代わりに暗号学的アキュムレータを使用することで、署名にハッシュ値を追加しないで済む方法も知られている<ref>{{cite web|title=Can one use a Cryptographic Accumulator to efficiently store Lamport public keys without the need of a Merkle Tree?|url=https://crypto.stackexchange.com/q/12253 |access-date=20 August 2023}}</ref>。

=== 鍵と署名の短縮 ===

Winternitz署名の圧縮手法を用いると、秘密鍵、公開鍵、署名のサイズを小さくすることができ、その代わり、署名を生成・検証する計算量が大きく増加する。
この圧縮手法では、メッセージの1ビットごとに乱数およびハッシュ値を2つずつ用意する代わりに、メッセージを固定長のチャンクに分割し，チャンクごとに乱数および（多重）ハッシュ値を1つずつ用意する。したがって、チャンクを <math>L</math> ビットとすると、鍵のサイズはオリジナルのランポート署名の鍵サイズに比べて <math>1/2L</math> 程度に小さくなり、署名のサイズも<math>1/L</math> 程度に小さくなる。署名の生成・検証には、チャンクごとに多重ハッシュを計算する必要があり、コストは約 <math>2^L/L</math> 倍になる
<!-- A cryptographically secure hash suffices instead of the requirement for a CSPRNG.-->
<ref name="Merkle">{{cite web|title=A Certificated Digital Signature |url=https://link.springer.com/content/pdf/10.1007/0-387-34805-0_21.pdf|access-date=20 August 2023}}</ref>
<ref>{{cite web|title=Winternitz one-time signature scheme|url=https://gist.github.com/karlgluck/8412807#comment-1258433|access-date=20 August 2023}}</ref>。

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

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

== 脚注 ==
{{reflist}}

{{cryptography navbox|public-key}}
{{computer-stub}}

{{デフォルトソート:らんほおとしよめい}}
[[Category:暗号]]
[[Category:暗号技術]]
[[Category:エポニム]]