技術要約：単純かつ効率的なワンショット署名スキーム

問題提起

ワンショット署名（OSS）は、ユーザーが公開検証鍵（$pk$）と秘密量子署名状態（$|sk\rangle$）を生成できる、特有の量子暗号プリミティブである。この署名状態により、ユーザーが選択したメッセージに対して正確に一度だけ有効な署名を生成することが可能となる。署名を行うと、状態は「自己破壊」し、二度目の署名の生成を防ぐ。OSSは、量子マネー、量子ライトニング、量子ファイア（quantum fire）といった強力なプリミティブの構築を示唆しているが、これらを効率的に構築することは依然として課題であった。

最近のブレークスルーであるShmueliとZhandryによるSZ [SZ25] は、OSSの最初の構成法を提供した。しかし、彼らのスキームには重大な非効率性が存在する：

1. ビット単位の署名： SZの構成は本質的に、メッセージを一度に1ビットずつ署名するものである。$\lambda$ ビットのメッセージに署名するには、並列反復が必要となり、鍵と署名のサイズに線形な増大を招く。
2. 複雑な増幅： 強固なセキュリティを実現するために、SZはDall'AgnolとSpoonerによるDS [DS22] のリダクションに依存しており、これは複雑な量子リワインディングや量子単一値変換（QSVT）回路（具体的には、交互投影またはMarriott-Watrous型のアルゴリズム）を使用する。これは、署名鍵のサイズに $\Theta(\lambda)$ の追加オーバーヘッドを導入する。
3. 不完全な正当性： SZスキームは無視できる程度の正当性エラー（correctness error）を持っており、署名アルゴリズムが有効な署名を生成できない可能性がある。
4. リソースコスト： オラクルモデルにおいて、SZスキームは $\Theta(\lambda^4)$ 量子ビットの署名鍵と $\Theta(\lambda^3)$ ビットの署名をもたらす。プレーンモデルでは、これらのパラメータはさらに大きくなる。

さらに、Çakan、Goyal、およびShmueli（CGS）[C¸GS25] による後続の研究は、OSSを用いて「公開鍵量子ファイア」を構築しようと試みたが、SZスキームが満たしていない「非圧縮性（incompressibility）」という特性に依存していた。

手法

本研究は、従来の近似手法で必要とされる複雑なリダクションや並列反復を回避する、新しい直接的なワンショット署名の構成法を提案する。コアとなる手法は、署名生成の方法における根本的な転換である。

1. グローバー探索による直接構成

特定のビットから始まるハッシュ関数の逆像を探索する（「和の拘束（sum-binding）」問題を扱うための複雑な増幅を必要とする）SZのアプローチとは異なり、本研究では関数の**像（image）**の中で署名を探索する。

• セットアップ： スキームは、ランダムな置換 $\Pi$ と、行列 $\mathbf{A}_y$ およびベクトル $\mathbf{b}_y$ によって定義される部分空間の族を利用する。署名状態 $|sk\rangle$ は、これらのパラメータによって定義されるアフィン部分空間（余集合）上の一様重ね合わせである。
• 署名プロセス： ビット $b$ に署名する場合、アルゴリズムは特定のビット $b$ で始まる逆像を探すのではなく、補助関数 $\mathcal{P}$ の像において、余集合のベクトルが特定のプレフィックス $b$ を持つようにするよう、グローバー探索アルゴリズムを用いて初期の重ね合わせ状態を変換する。
• オラクルの使用： 署名アルゴリズムは、2つの反射オラクルを反復的に適用する：
  1. 画像のプレフィックスがメッセージビットと一致する状態をマークする位相オラクル。
  2. 部分空間の双対（dual）に対して反射を行う双対オラクル $\mathcal{D}$。
     このプロセスを $\ell$ 回繰り返すことで、アルゴリズムは状態をメッセージ全体の有効な署名の重ね合わせへと回転させる。この状態を測定することで、有効な署名が得られる。

2. 完全な正当性の確保

著者らは、行列 $\mathbf{A}_y$ のサンプリングを慎重に設計することで、不完全な正当性の問題に対処している。$\mathbf{A}_y$ の第1列が非ゼロであることを保証することで、任意の公開鍵 $y$ に対して、余集合が0と1の両方で始まるベクトルを含むことを保証する。この構造的保証により、グローバー探索は常に成功し、完全な正当性（確率1）を達成する。

3. 多項式長のメッセージへの対応

$\lambda$ 回の反復によって単一ビットのスキームを繰り返す（これにより $\lambda$ の増大が生じる）のではなく、本スキームは $\lambda$ ビットのメッセージ全体を一回の実行で署名する。グローバー探索は、単一の実行内でビット単位の署名を行うように適応され、$\lambda$ 個の署名を $\Theta(\lambda^2)$ サイズの単一の署名へと圧縮する。任意の多項式長に対しては、標準的なハッシュ・アンド・サイン変換が適用される。

4. 非圧縮性と量子ファイア

本論文は、SZスキームが「強い署名非圧縮性」を満たさないというCGS [C¸GS25] の主張における欠陥を特定している。SZスキームは、署名アルゴリズムが前方および逆方向の両方のオラクル（$\mathcal{P}$ および $\mathcal{P}^{-1}$）へのアクセスを必要とするため、圧縮されたリスト外の鍵に対する署名を生成できてしまう。
新しい構成では、署名に双対オラクル $\mathcal{D}$ のみが要求され、検証には別のオラクル $\mathcal{D}_0$ が使用されるようにスキームを修正する。この分離により、強い署名非圧縮性の証明が可能になり、CGSが提案した量子ファイアの適用可能性が回復される。

主な貢献と結果

効率性の向上

本論文は、SZ構成と比較して、リソース複雑性の大幅な削減を実現している：

• 署名鍵サイズ： $\Theta(\lambda^4)$ 量子ビットから $\Theta(\lambda^2)$ 量子ビットへ削減。
• 署名サイズ： $\Theta(\lambda^3)$ ビットから $\Theta(\lambda^2)$ ビットへ削減。
• 公開鍵サイズ： $\Theta(\lambda^3)$ ビット（オラクルモデル）および $\Theta(\lambda^5)$ ビット（プレーンモデル）から、$\Theta(\lambda^2)$ ビット（オラクルモデル）および $\Theta(\lambda^4)$ ビット（プレーンモデル）へ削減。
• 実行時間： 署名アルゴリズムは、QSVT/リワインディング回路に関連する $\Theta(\lambda)$ のオーバーヘッドを回避し、大幅に少ないオラクルクエリを必要とする。

セキュリティと正当性

• 完全な正当性： SZとは異なり、本スキームは有効な署名が確率1で生成されることを保証する。
• 強い安全性： 本スキームは強い不可偽性（unforgeability）を達成しており、異なるメッセージに対する有効な署名、あるいは同一メッセージに対する異なる署名を生成することは不可能である。
• 非圧縮性： 本スキームは、量子ファイアのような高度なアプリケーションに必要な特性である、強い署名非圧縮性を満たす。

理論的結果

本論文は、これらの改善を2つの主要な定理として定式化している：

1. 定理 1.1： 多項式長のメッセージに対して、完全な正当性を持つ効率的なOSSスキームが、古典的オラクルモデル（無条件）およびプレーンモデル（耐量子識別化仮説およびLWEを仮定）の両方で存在することを確立する。
2. 定理 1.2： 新しい非圧縮OSSスキームが、完全な正当性を伴う公開鍵量子ファイアおよびキーファイアの構築を可能にすることを実証し、CGS [C¸GS25] の研究における誤りを修正する。

意義

本論文は、最先端のワンショット署名スキームに対する、「単純、直接的、かつ効率的」な代替案を提供すると主張している。前述の（DS [DS22] による）複雑なリダクションや並列反復戦略を回避することで、著者らは鍵および署名サイズの二次的な（quadratic）改善を達成している。

本研究の意義は二重にある：

1. 実用的な効率性： 量子ビットおよびビットの要求量を、四次/三次スケールから二次スケールへと削減することで、量子署名スキームを大幅に実現可能なものにする。
2. 基礎的な修正： OSSに関する非圧縮性に関する文献における決定的なギャップを修正する。非圧縮性の特性を修正することで、本論文は、以前はSZスキームに関する誤った仮定に基づいていたとしても可能であると主張されていた「量子ファイア」および関連するプリミティブの構築を正当化し、可能にする。

著者らは、パラメータを大幅に最適化したものの、オラクルモデルにおける $\Theta(\lambda)$ へのさらなる改善には、現在のボトルネックが双対フリー（dual-free）ケースの解析にあるため、全く新しい手法が必要になる可能性があると述べている。同様に、プレーンモデルのパラメータを改善することも未解決の課題である。