ランポート署名

暗号化において、Lamport 署名またはLamport ワンタイム署名方式は、デジタル署名を作成する方法です。Lamport 署名は、暗号的に安全な一方向関数から作成できます。通常は、暗号ハッシュ関数が使用されます。

量子コンピュータの潜在的な開発は、RSAなどの多くの一般的な暗号化形式のセキュリティを脅かすが、その場合でも、大きなハッシュ関数を持つランポート署名は安全であると考えられている。各ランポート鍵は、1つのメッセージに署名するためにのみ使用できる。しかし、多くのランポート署名は1つのマークルハッシュツリーで処理できるため、1つのハッシュツリー鍵を多くのメッセージに使用でき、これはかなり効率的なデジタル署名方式になります。

ランポート署名暗号システムは1979年に発明され、発明者であるレスリー・ランポートにちなんで名付けられました。^[1]

アリスは256 ビットの暗号化ハッシュ関数と何らかの安全な乱数ジェネレータを持っています。彼女は、Lamport キー ペア、つまり秘密キーと対応する公開キーを作成して使用したいと考えています。

秘密鍵を作成するために、アリスは乱数ジェネレータを使用して 256 組の乱数 (合計 2×256 個) を生成します。各数値のサイズは 256 ビットで、合計 2×256×256 ビット = 128キビットになります。これがアリスの秘密鍵であり、後で使用するために安全な場所に保管します。

公開鍵を作成するために、彼女は秘密鍵内の 512 個の乱数をそれぞれハッシュし、それぞれ 256 ビットのサイズの 512 個のハッシュを作成します。(合計も 128 キロビットです。) これらの 512 個のハッシュが彼女の公開鍵を形成し、彼女はそれを世界中に共有します。

その後、アリスはメッセージに署名しようとします。まず、アリスはメッセージを 256 ビットのハッシュ サムにハッシュします。次に、ハッシュの各ビットについて、ビットの値に基づいて、秘密鍵を構成する対応する数字のペアから 1 つの数字を選択します (つまり、ビットが 0 の場合は最初の数字が選択され、ビットが 1 の場合は 2 番目の数字が選択されます)。これにより、256 個の数字のシーケンスが生成されます。各数字自体が 256 ビットの長さであるため、アリスの署名の合計サイズは 256×256 ビット = 65536 ビット = 64 Kibit になります。これらの (最初にランダムに選択された) 数字がアリスの署名であり、アリスはこれをメッセージとともに公開します。

アリスの秘密鍵は一度使われたら、二度と使用してはならないことに注意してください。アリスは署名に使用しなかった残りの 256 個の数字を破棄する必要があります。そうしないと、秘密鍵を再利用した署名が増えるごとに、後で偽の署名を作成する可能性のある敵対者に対するセキュリティ レベルが低下します。 ^[2]

次に、ボブはアリスのメッセージ署名を検証します。また、メッセージをハッシュして 256 ビットのハッシュ サムを取得します。次に、ハッシュ サムのビットを使用して、アリスの公開キーのハッシュを 256 個選択します。アリスが署名の乱数を選択したのと同じ方法でハッシュを選択します。つまり、メッセージ ハッシュの最初のビットが 0 の場合、最初のペアの 最初のハッシュを選択します。

次に、ボブはアリスの署名にある 256 個のランダムな数字をそれぞれハッシュします。これにより、256 個のハッシュが得られます。これらの 256 個のハッシュが、アリスの公開鍵から選択した 256 個のハッシュと正確に一致すれば、署名は正常です。一致しない場合は、署名が間違っています。

アリスがメッセージの署名を公開する前は、秘密鍵内の 2×256 個の乱数を知っている人は誰もいないことに注意してください。したがって、署名用の 256 個の乱数の適切なリストを作成できる人は誰もいません。また、アリスが署名を公開した後も、他の​​人は他の 256 個の乱数を知らないため、他のメッセージ ハッシュに適合する署名を作成できません。

以下は、数学的記法で書かれた、Lamport 署名の仕組みの簡単な説明です。この説明の「メッセージ」は、適切なサイズの固定サイズのブロックであり、署名された任意の長さのメッセージのハッシュ結果である可能性があります (ただし、必ずしもそうとは限りません)。

を正の整数とし、をメッセージの集合とします。を一方向関数とします。 ${\displaystyle k}$${\displaystyle P=\{0,1\}^{k}}$${\displaystyle f:\,Y\rightarrow Z}$

およびについては、署名者はランダムに選択して を計算します。 ${\displaystyle 1\leq i\leq k}$${\displaystyle j\in \{0,1\}}$${\displaystyle y_{i,j}\in Y}$${\displaystyle z_{i,j}=f(y_{i,j})}$

秘密鍵 は値で構成されます。公開鍵 は値で構成されます。 ${\displaystyle K}$${\displaystyle 2k}$${\displaystyle y_{i,j}}$${\displaystyle 2k}$${\displaystyle z_{i,j}}$

メッセージにし ましょう。${\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 f(s_{i})=z_{i,m_{i}}}$${\displaystyle 1\leq i\leq k}$

メッセージを偽造するために、Eve は一方向関数を反転する必要があります。これは、適切なサイズの入力と出力に対しては処理不可能であると想定されます。 ${\displaystyle f}$

Lamport 署名のセキュリティは、一方向ハッシュ関数のセキュリティとその出力の長さに基づいています。

n ビットのメッセージ ダイジェストを生成するハッシュ関数の場合、 1 回のハッシュ関数呼び出しで理想原像および 2 次原像耐性が実現されるためには、従来の計算モデルでは衝突を見つけるのに約 2 ^{n 回}の操作が必要です。グローバーのアルゴリズムによると、量子計算モデルでは、理想ハッシュ関数の 1 回の呼び出しで原像衝突を見つけるには O(2 ^{n /2} ) 回の操作が上限です。ランポート署名では、公開鍵と署名の各ビットは、ハッシュ関数を 1 回呼び出すだけで済む短いメッセージに基づいています。

各秘密鍵y _i,jとそれに対応する公開鍵ペアz _i,jについて、入力の長さに対する原像攻撃の実行が出力の長さに対する原像攻撃の実行よりも速くならないように、秘密鍵の長さを選択する必要があります。たとえば、退化したケースでは、各秘密鍵y _i,j要素の長さが 16 ビットしかない場合、メッセージ ダイジェストの長さに関係なく、出力と一致するものを見つけるために、 2 ^{16 回の演算ですべての 2 16}の可能な秘密鍵の組み合わせを網羅的に検索するのは簡単です。したがって、バランスの取れたシステム設計により、両方の長さがほぼ等しくなります。

グローバーのアルゴリズムに基づく量子セキュア システムでは、公開鍵要素z _i,j、秘密鍵要素y _i,j、署名要素s _i,jの長さは、システムのセキュリティ評価の 2 倍以上である必要があります。つまり、次のようになります。

• 80 ビットのセキュア システムでは、160 ビット以上の要素の長さが使用されます。
• 128 ビットの安全なシステムでは、256 ビット以上の要素の長さを使用します。

ただし、上記の理想的な作業推定は理想的な（完全な）ハッシュ関数を想定しており、一度に 1 つの原画像のみをターゲットとする攻撃に限定されているため、注意が必要です。従来のコンピューティング モデルでは、2 ^{3 n /5 個の}原画像を検索すると、原画像あたりの総コストは 2 ^{n /2}から2 ^{2 n /5}に減少することがわかっています。^[3]複数のメッセージ ダイジェストのコレクションを考慮して最適な要素サイズを選択することは、未解決の問題です。512 ビット要素や SHA-512 などのより大きな要素サイズと強力なハッシュ関数を選択すると、これらの未知の要素を管理するためのセキュリティ マージンが大きくなります。

秘密鍵のすべての乱数を作成して保存する代わりに、十分なサイズの単一の鍵を保存できます。(通常、秘密鍵の乱数の 1 つと同じサイズです。) その後、単一の鍵を暗号的に安全な疑似乱数生成器(CSPRNG) のシードとして使用し、必要に応じて秘密鍵のすべての乱数を作成できます。 暗号的に安全なハッシュ (または少なくとも出力がシードと XOR されていないもの) は、メッセージに署名すると秘密鍵からの追加の乱数値が明らかになるため、CSPRNG の代わりに使用できないことに注意してください。 攻撃者が意図した受信者よりも先に署名にアクセスできる場合、秘密鍵から明らかにされた乱数が 2 倍になるごとにセキュリティ レベルが半分になる署名を偽造できます。

同様に、1 つのキーを CSPRNG と組み合わせて使用​​して、多数の Lamport キーを作成することもできます。その場合は、何らかのポスト量子セキュアランダム アクセスCSPRNG を使用する必要があります。特に、 BBS のような従来の CSPRNG は使用しないでください。

Lamport 署名はハッシュ リストと組み合わせることができ、公開鍵のすべてのハッシュではなく、単一のトップ ハッシュのみを公開することができます。つまり、値の代わりにです。単一のトップ ハッシュに対して検証するには、署名に乱数と公開鍵のハッシュ リストからの未使用のハッシュを含める必要があり、署名のサイズは約 2 倍になります。つまり、すべての の値を含める必要があります。 ${\displaystyle 2k}$${\displaystyle z_{ij}}$${\displaystyle (z_{ij})}$${\displaystyle j\neq m_{i}}$

ハッシュリストの代わりに暗号アキュムレータを使用する場合、未使用のハッシュを署名に含める必要はありません。 ^[4]

ウィンターニッツ署名圧縮により、秘密鍵と公開鍵のサイズは 1/10 よりわずかに小さくなり、署名のサイズはその半分になります。計算量は 1/10 よりわずかに大きくなります。CSPRNG の代わりに暗号的に安全なハッシュで十分です。^[5]${\displaystyle 2\langle {\text{chunk size in bits}}\rangle }$${\displaystyle 2^{\langle {\text{chunk size in bits}}\rangle }/\langle {\text{chunk size in bits}}\rangle }$

前のセクションで説明したように、署名のサイズが 2 倍になるという犠牲を払って、ハッシュ リストを使用して公開キーを 1 つの値に短縮することもできます。

各 Lamport 公開鍵は 1 つのメッセージにのみ署名できます。つまり、多数のメッセージに署名する場合は、多数の鍵を公開する必要があります。ただし、これらの公開鍵に対してハッシュ ツリーを使用すれば、代わりにハッシュ ツリーの最上位ハッシュを公開できます。これにより、署名にハッシュ ツリーのブランチを含める必要があるため、結果として得られる署名のサイズは大きくなりますが、単一のハッシュを公開して、その後多数の将来の署名を検証できるようになります。

• S/キー

• L. Lamport、「一方向関数からのデジタル署名の構築」、技術レポート SRI-CSL-98、SRI 国際コンピュータサイエンス研究所、1979 年 10 月。
• Merkle ツリーの効率的な使用 -効率的なワンタイム署名方式としての Merkle ツリー + Lamport 署名の本来の目的に関するRSA ラボの説明。
• Adam Langley によるハッシュベース署名と Merkle 署名の紹介。
• BLAKE2b (C++) 上の Lamport スキームのリファレンス実装
• SHA256、SHA512、または Blake2b (Rust) に基づく Lamport 署名のリファレンス実装
• 任意の 2 のべき乗サイズのハッシュ上の Merkle-Lamport 署名の小規模な実装 (C)