Lattice-based extended withdrawability

技術要約：格子ベースの拡張的撤回可能性（Lattice-based Extended Withdrawability）

問題提起
デジタル署名は伝統的に永続性を提供する：一度署名されると、メッセージは署名者の公開鍵の下で無期限に検証可能である。しかし、多くの分散型アプリケーション（例：期間限定のアクセス、撤回可能な合意、分散型エスクロー）では、秘密鍵を明かすことなく、あるいは他の署名を無効にすることなく、署名を「撤回（withdraw）」する能力が必要となる。Liu、Susilo、およびBaekは、署名を真の署名者が「確定（confirm）」するまで、署名を潜在的な署名者の一群の中で曖昧な状態に留めることを可能にする「拡張的撤回可能署名（extended withdrawable signatures: EWS）」を導入した。彼らの構成法は、離散対数問題に基づくプリミティブ（Schnor署名および1-out-of-N署名）に依存している。

本論文は、「ポスト量子ギャップ」に対処するものである。Shorのアルゴリズムは、既存のEWSの基礎である離散対数問題を打破する。格子ベースの署名（Dilithiumなど）は存在するが、Liu-Susilo-Baek（LSB）の構成法を格子へと直接的に「逐語的に転写（literal transcription）」することは、構造的な障害により失敗する。具体的には、LSBスキームは、署明者の寄与を再ランダム化するために、公開鍵の乗法的シフトを公開することに依存している。格子設定において、このようなシフトは $As_1 s_j$ の形式をとるが、これは署明者の公開鍵 $t_i = As_1 + s_2$ と共通因子 $As_1$ を共有してしまう。このようなシフトを公開することは、署明者のアイデンティティを漏洩させ、要求される曖昧性を破壊する。

手法
著者らは、LSBのアプローチから脱却し、スキームを「請求可能なリング署名（claimable ring signature）」（ParkおよびSealfon）として扱う、格子ベースのEWSのための新しい構成法を提案する。公開鍵を明示的に再ランダム化しようとする代わりに、この構成法はEWSの2つの核となる機能を分離する：

1. 曖昧性（Ambiguity）：ブラックボックスとして使用される、匿名な1-out-of-N（リング）署名によって提供される。
2. 確定（Confirmation）：署明者の「クレーム（主張）」によって提供される。これは、撤回可能なオブジェクトに対する結合的な署名と、署明者のインデックスに対する隠蔽コミットメントの開封からなる。

この構成法は、Fiat-Shamir with abortsパラダイム上で動作し、3つのモジュール的な要素に依存している：

• ベースとなる署名スキーム（例：no-hint, full-$t$ のDilithiumスタイルのスキーム）。
• 匿名な1-out-of-N署名（格子1-out-of-many証明によってインスタンス化される）。
• 隠蔽および結合（hiding-and-binding）コミットメントスキーム（Ajtaiスタイルのもの）。

撤回可能署名 $\sigma$ は、メッセージに対するリング署名 $\sigma_r$ と、署明者のインデックスに対するコミットメント $C$、および公開鍵の集合で構成される。確定するためには、署明者は $C$ の開封 $(i, \rho)$ を明らかにし、自身のベース秘密鍵を用いて撤回可能なオブジェクト $\langle \mu, \pi, \sigma \rangle$ 全体に署名を行う。

主な貢献

1. セキュリティモデルの洗練：著者らはLSBのセキュリティモデルを洗練させている。

   • LSBの「完全性（completeness）」の定義を、隠蔽保証を明示的に捉えた「クレームまでの匿名性（anonymity-until-claim）」の識別ゲーム（定義14）に置き換えた。
   • 「クレーム可能性の健全性（claimability soundness）」（定義16）を導入し、確定された署名が唯一の署明者インデックスに結合することを保証し、攻撃者が同じ署名を異なるリングメンバーに帰属させることを防ぐ。
   • 固定されたターゲットインデックスを持つ「内部者による汚染下での不偽造性（unforgeability under insider corruption）」を定式化し、LSBの証明に見られる乗法的 $q_H$（ハッシュクエリ）減少を回避した。

2. 汎用的な構成：Fiat-Shamir with abortsパラダイムにおけるEWSの汎用的な構成が提示されている。決定的なことは、署明者に由来する値を一切、明示的に公開しない点である。曖昧性は、リング署名のゼロ知識特性のみから導かれ、追跡可能性はコミットメントの結合特性から導かれる。

3. 不可能性の結果：本論文は、LSBの1-out-of-N署名（加法的チャレンジ分割を使用するもの）をそのまま格子へ転写することは安全ではないことを証明している（命題2）。疎な（sparse）チャレンジを用いる格子設定では、正直な署明者が有効なチャレンジ分割を生成する確率は無視できるほど小さく（$2^{-\Omega(n)}$）、仮に完全性がパッチ適用されたとしても、シミュレートされたトランスクリプトは実際のトランスクリプトと区別不能ではなくなるため、匿名性が失われる。

4. 完全なセキュリティ証明：著者らは、（量子）ランダムオラクルモデル（QROM）において、以下の項目に関する明示的なゲームベースの簡約（reduction）を提供している：

   • 正当性（Correctness）：基礎となるプリミティブの正当性への簡約。
   • 拡張的撤回可能性（Extended Withdrawability）：コミットメントの隠蔽性（Decisional MLWE）および1-out-of-N署名の匿名性への簡約。
   • 不偽造性（Unforgeability）：ベース署名のEUF-CMAセキュリティへの簡約（リワインディングなし、および $q_H$ 損失なし）。
   • クレーム可能性の健全性（Claimability Soundness）：コミットメントの結合性（MSIS）への簡約。

5. インスタンス化：本スキームは、no-hint, full-$t$ のDilithiumスタイルのベース署名と、確立された格子1-out-of-many証明を用いてインスタンス化される。論文ではパラメータの選択について議論されており、HAETAEが代替のベースとなり得ることも述べている。

結果
本論文は、提案された構成法が以下の特性を持つことを確立している：

• 正当である：正直な署名は極めて高い確率で検証可能である。
• 拡張的に撤回可能である：すべての秘密鍵を保持する攻撃者であっても、署明者が確定するまで、どのリングメンバーが撤回可能署名を作成したかを区別できない。
• 偽造不可能である：ターゲット以外のすべてのリングメンバーの秘密鍵と署名オラクルへのアクセス権を持つ攻撃者であっても、新しいメッセージに対する確定された署名を偽造することはできない。
• 健全である：確定された署名が、2つの異なる署明者に帰属することはない。

セキュリティは、標準的なモジュール格子仮定（Decisional MLWE、MSIS、およびSelfTargetMSIS）と、1-out-of-N証明のゼロ知識特性に依拠している。

意義
本論文は、拡張的撤回署名の初の安全なポスト量子実現を提供することで、その意義を主張している。LSBの離散対数構成法は、共有値の「自由な再ランダム化」が欠如しているため、格子へ直接移植できないことを示している。問題を「請求可能なリング署名」として再定義し、コミットメントベースの確定メカニズムを利用することで、著者らは以下の特性を持つスキームを実現した：

• ポスト量子安全：格子仮定を通じて量子攻撃者に対して耐性を持つ。
• 公開検証可能：指定検証者型（designated-verifier）のバリアントとは異なり、あらゆる当事者が撤回可能署名を検証できる。
• モジュール化：セキュリティ証明は基礎となるプリミティブのインターフェースにのみ依存しているため、システム全体を再証明することなく、異なる格子ベースのコンポーネント（異なるベース署名やリング証明など）を置換することが可能である。
• 本来の目的への忠実性：設計は、構造的な欠陥を修正しつつ、元のLSBスキームの機能的な目標と直感を維持している。