Develop with pleasure!

福岡でCloudとかBlockchainとか。

Great Script RestorationとWinternitz OTS+

Cryptography Bitcoin PQC

Great Script Restoration

Great Script Restoration（GSR）は、2010年にBitcoinで無効化されたopcode群に対して、重みベースのバジェットを付与して再導入するRusty Russellの提案↓

https://github.com/rustyrussell/bips/blob/890656f624e03ebbd31560f651193fcc3e5cf58a/bip-unknown-var-budget-script.mediawiki

Jonas Nickが、このプロジェクトで有効になったopcodeを用いて量子耐性のあるWinternitz OTS+署名を実装したプロジェクトが↓

https://github.com/jonasnick/GreatRSI

Winternitz OTS+

W-OTS+は、量子耐性のあるハッシュベースのワンタイムデジタル署名スキーム。

パラメーター

W-OTS+は、以下の2つのパラメーターを使用する。

  • n：メッセージ、秘密鍵、公開鍵、署名要素の長さ（byte単位）。メッセージダイジェストを生成するハッシュ関数によって決り、WOTSP-SHA2_256の場合は32。
  • w：Winternitzパラメーター。4か16のいずれかを選択*1。WOTSP-SHA2_256の場合は16。

この2つのパラメーターから以下のパラメーターを導出する。

  • len：WOTS+の秘密鍵、公開鍵、署名内のn byte文字列の数。len1 = ceil(8n / lg(w))、len2 = floor(lg(len1 * (w - 1)) / lg(w)) + 1とし、len = len1 + len2。WOTSP-SHA2_256の場合は67。

鍵生成

秘密鍵は、len個のn byte文字列の配列で、各n byte値は単純にランダムに選択するか、暗号学的に安全な疑似乱数法を使用してn byte値からすべて生成する。ワンタイム署名スキームなので、生成した秘密鍵は1つのメッセージへの署名にしか使えない。

対応する公開鍵もlen個のn byte値の配列で、

  1. len個の秘密鍵の各n byte値を起点として、各値をw - 1回ハッシュする連鎖関数を実行し、
  2. ハッシュしたlen個のデータを連結したものが公開鍵となる。

つまり、秘密鍵の各値は、公開鍵を計算するためのハッシュチェーンの起点ノードで、公開鍵の各値はこのハッシュチェーンの終点ノードということ。

署名の生成

W-OTS+の署名生成手順は、

  1. 署名対象のメッセージのハッシュ値H(m)を計算し、
  2. H(m)をlen1個の基数wの整数値に変換する。
  3. 次にチェックサムを計算し、2に追加する。
  4. 3の基数wの各整数値をインデックスとして、公開鍵を生成する際のハッシュチェーンからそのインデックスに対応するノード値をピックアップする
  5. 4の値を連結した値が署名データとなる。

署名の検証

W-OTS+の署名検証手順は、

  1. 署名対象のメッセージのハッシュ値H(m)を計算し、
  2. H(m)をlen1個の基数wの整数値に変換する。
  3. 次にチェックサムを計算し、2に追加する。
  4. 3の基数wの各整数値とw - 1の差分分、連鎖関数を実行し
  5. 4で計算した各ハッシュ値が、公開鍵の各値と一致すれば署名検証は成功。異なる場合は無効な署名。

という仕組み。

ちなみに、W-OTS+を拡張し、マークルツリーでワンタイム性を排除しステートレスなハッシュベースの署名スキームにしたのが現在NISTでポスト量子暗号の標準化対象になっているSPHINCS+。

データサイズ

WOTSP-SHA2_256の場合、秘密鍵、公開鍵、署名のサイズはそれぞれ2,144 byte。同様のハッシュベースのランポート署名の場合、単純な形だと公開鍵のデータ長だけで16KBとかになるので、それに比べるとまだ小さい方。W-OTS+は、基数wとハッシュチェーンの構成によって公開すべきデータが圧縮できているのが大きい。

Bitcoin ScriptでW-OTS+の検証

Bitcoin ScriptでW-OTS+の検証を行う場合、上記の検証ロジックをBitcoin Scriptで実装する必要があり、それが冒頭に貼ったGithubのプロジェクト。プロジェクトをビルドして生成したwotsコマンドを使うと、

  • 鍵ペアの生成
    （各256 bitの67個のシークレット、1つのシード、15個のランダマイザで、合計約2.6kB）
  • 公開鍵をエンコードしたBitcoin Scriptの生成（約20kB）
  • Txに対してWOTS+署名とwitnessを生成（約2.2kB）
  • Txに対してスクリプト及びWOTS+署名の検証

ができる。

量子耐性への対応

上記の検証スクリプトを利用することで、Bitcoinに量子耐性のあるデジタル署名スキームを導入することができるけど、W-OTS+のサポートはTaprootのscript-pathを利用する場合にのみ有効で、Taprootのkey-path条件がまだ利用可能。key-pathの方はSchnorr署名に依存しているのでこちらが利用可能な場合、量子耐性はない。そのため、GSRの導入に加えてTaprootのkey-pathを無効化する必要がある。

サイズの問題

W-OTS+を利用することで量子耐性は得られるけど、

  • 鍵長自体はランポート署名より小さいけど、スクリプト自体のサイズは大きい
  • ワンタイム署名スキームなので、鍵の導出管理などの仕組みが別途必要

あたりがネック。前者はBitcoin Scriptでループができないことが原因で、このあたりを改善しようとしてるAnthony TownsのLisp言語提案とか気になる。

*1:wが大きい方が署名は短くなるが、署名コストは高くなる