免責事項：本研究はウォレットを順位付けしたり、特定のデバイスが優れていると主張したりするものではありません。テストしたすべてのウォレットで、同じreference C library（1、2、3）を使用し、ウォレットごとに必要な調整だけを加えてbenchmarkを実施しました。最適化された最高効率の実装ではなく、平均的なものです。各teamは自身のdeviceに深い知識を持ち、より良い結果を得られる可能性があります。本記事の数値を上回る結果、技術、実装があれば共有を歓迎します。Self-custody型ビットコインを支えるすべてのteamに感謝します。

謝辞：開発者用Jade Plusを提供してくださったJade Team、特にRich Grambergs氏、Ledger上でcustom appを起動する方法を教えてくださったCharles Guillemet氏をはじめとするLedger Team、一般向けwalletでもcustom firmwareを比較的容易にuploadできる環境を提供するSatoshiLabs Group、開発者用BitBox02 Novaを提供してくださったBitBox team、特にJad氏に感謝します。開発deviceの入手を支援してくださったAnastasiia Sapozhkova氏とPavel Kravchenko氏、慎重なreviewと貴重なfeedbackをくださったJonas Nick、Mike Kudinov、Viktor Mashtaliar、Yaroslava Chopaにも感謝します。

問題の現状

耐量子（PQ）暗号は既存hardware walletへの実装が難しい、または不可能だという懸念があります。複数のinterview、thread、記事で、この重要な論点が取り上げられています。

研究はまだ一部しか完了していないため、すべてのPQ primitiveについて一般化はできません。しかし、すでに明確なことがあります。PQ署名方式は主要なhardware walletすべてで動作します。

本記事では、実device上の実装とbenchmarkでこれを示します。正確には、device上でのhash-based署名生成だけが対象です。耐量子firmwareの検証、格子方式、isogenyは対象外で、今後テストします。

前提：Blockstream Researchはhash-based署名とビットコインへの適合性を研究してきました。

既存hardware walletはhash-based PQ署名を実行できるのか。意外にも、多くの処理が可能です。

Walletと署名候補

Jade、Trezor、Ledger（7、8、9）、BitBox02の4製品で、5つのhash-based署名方式を評価しました。

  1. SLH-DSA-128s（FIPS 205）：署名7,856バイト、264回署名、stateless。
  2. 縮小版SPHINCS+：署名5,776バイト、240回署名、stateless。SHRINCSのstateless部分の有力候補。
  3. UXMSS（SHRINCS-Bのstateful部分）：324バイト以上、statefulで最小のSHRINCS署名。
  4. UXMSS（SHRINCS-Lのstateful部分）：overgrindingあり・なし（Swn = 140/96）で1,092バイト以上。以前Liquidへ導入したverifierが検証する署名。
  5. XMSS：210回署名可能なstateful方式、696バイト。

実装の詳細

全deviceで同じ平均的な署名実装をテストしましたが、wallet間の厳密な比較は困難です。

  • Codeの実行方法：LedgerはSecure Element内でappを実行できます。OS crypto functionはsystem call overheadが大きいため、app内のcustom SHA-256で高速化しました。Jadeは汎用chip上で動作します。TrezorとBitBox02はmain microcontroller上でcustom firmwareを実行し、Secure ElementはPINとsecretの保護だけを担当します。
  • Crypto primitive：Jadeはlibsecp256k1とhash functionを包むlibwally、Trezorはtrezor-crypto、BitBox02は独自実装、Ledgerはcxlibを使います。Reference libraryを各componentへ接続し、一部ではdevice内部のhash・endianness helperを再利用したため、数値にも影響します。
  • Toolchainとhash functionのhardware実装が異なります。
  • CPU周波数は70～240MHzで異なります。
  • Data transmission時間が異なります。

したがって本記事はwalletの優劣ではなく、全deviceがhash-based署名を生成できることに焦点を当てます。

測定結果

数値は各操作を100回実行した平均です。

KeyGen3

KeyGen / WalletJade PlusTrezor Safe 3Ledger Nano gen5/s+BitBox02 Nova
SLH-DSA-SHA2-128 / SPHINCS+ 2^407.06 s8.64 s15.82 s12.7 s
UXMSS (SHRINCS-L)1.81 s2.35 s6.1 s3.3 s
UXMSS (SHRINCS-B)18.87 s22.8 s40.18 s28.8 s
XMSS 2^1057.78 s75.64 s117.85 s79.5 s

SLH-DSA、SPHINCS+ 240、SHRINCS-Lはほぼ全deviceで実用的です。SHRINCS-Bは大きなWinternitz parameter（w=256）を使い、KeyGen時にstateful tree全体を構築するため時間が増えます。XMSSは鍵生成に約1分かかりますが、cacheにより署名生成を効率化できます。

SigGen

署名 / WalletJade PlusTrezor Safe 3/5/7Ledger Nano gen5/s+BitBox02 Nova
SLH-DSA-SHA2-128 (7856 B)52.85 s65.31 s120.12 s100.1 s
SPHINCS+ 2^40 (5776 B)43.28 s53.45 s94.98 s78.4 s
SHRINCS-L (swn=96, 1092 B)3.31 s3.01 s8.04 s5.5 s
UXMSS SHRINCS-L (swn=140)225.63 s264.74 s572.78 s334.6 s
UXMSS SHRINCS-B (324 B)21.75 s25.82 s41.83 s30.9 s
XMSS 2^10 (696 B)57.8 s75.63 s118.2 s79.6 s
  • SLH-DSA：約53～120秒。遅いと言えますが不可能ではありません。240回署名可能なSPHINCS+は少し速くなります。
  • UXMSS（SHRINCS-B）：同じhardwareで22～42秒。
  • UXMSS（SHRINCS-L）：overgrindingにより約226～573秒ですが、検証の複雑さを大幅に下げるtrade-offです。Overgrindingなしなら3秒以上です。
  • XMSS：cold modeで1署名58～118秒。SLH-DSAに近いもののcacheで効率的に高速化できます。

Cacheの活用

表は署名のたびにすべてを最初から計算するcold modeです。Hash-based署名は各署名で同じ処理の多くを繰り返す構造なので、計算結果を保存して再利用できます。詳細はこちらの記事をご覧ください。次の記事ではhardware wallet上の実用的な上限とcache効率を検討します。

おまけ：署名生成を退屈にしない

ビットコイン管理で署名に数分かかることは大きな問題ではないと考えています。Lightning Networkでは高速な方式が望ましいものの、stateful署名とcacheを使えば実用的です。

それでも待ち時間は退屈です。大きなdisplayを備えるwalletなら、Trezor Safe 7で試したように「Sign」を押した後、ビットコインのレーシングゲームを表示できます。TetrisやChessでも構いませんが、Pac-Manにはさらに大きなdisplayが必要です。

Trezorで耐量子署名中に動くracing game

Safe 7はPQ署名生成processと、game描画・入力処理processを切り替えます。Multithreadingではなくprocess switchingなので、gameを速くすると署名が長くなります。Gameを停止した数値が表の結果です。

冗談めいた副作用として、gameplayからentropyをsampleできます。Hash-based署名にもrandomizerが必要です。ただし、これはside-channel対策ではありません。描画や入力によるnoiseだけでは弱い保護であることが研究（10、11）で示されています。実際の対策では通常、秘密値をrandomized shareへ分割して相関をなくすmasking（12）を使います。

最終benchmark中には、大きなdisplayを持つwalletでできる他の例（13、14）も見つかりました。

結論

既存hardware walletではPQ署名を生成できないという懸念は、少なくともhash-based方式には当てはまりません。現在購入・利用できるhardware walletで、SLH-DSAは約1分、SHRINCSのstateful部分は数秒で署名できます。

残る課題は基本的な実現可能性ではなく、最適化、遅延、cache、hash高速化というengineering上の問題です。

脚注

  1. 仕様は作成中で、まだ公開されていません。↩
  2. このvariantはleafにWOTS+C one-time signatureを使います。署名size削減に加え、署名生成costと検証の複雑さを交換できます。
  3. SHRINCSの完全な鍵生成はstatefulとstatelessのKeyGenを組み合わせるため、合計時間は両者の和です。↩
  4. Gameのsearch stackに追加20～30KBのRAMが必要です。

原文：Are Hardware Wallets Ready to Produce Post-Quantum Signatures?