🔢 mathematics

Spinel: A Post-Quantum Signature Scheme Based on $\mathrm{SL}_n(\mathbb{F}_p)$ Hashing

本論文は、 $\mathrm{SL}_n(\mathbb{F}_p)$ 上のエクスパンダーグラフにおける探索の困難性を安全性の根拠とする新しい代数的ハッシュ関数を、SPHINCS+の枠組みに統合することで、量子耐性を持つ新たなデジタル署名方式「Spinel」を提案し、その安全性と実用性を検証したものです。

原著者： Asmaa Cherkaoui, Faraz Heravi, Delaram Kahrobaei, Siamak F. Shahandashti

公開日 2026-02-12

📖 1 分で読めます🧠 じっくり読む

CC BY 4.0

原著者： Asmaa Cherkaoui, Faraz Heravi, Delaram Kahrobaei, Siamak F. Shahandashti

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

1. 背景：デジタル界の「最強の鍵」が危ない！

今のインターネットの世界では、私たちが送ったメールやネットショッピングの決済が「本物であること」を証明するために、**「デジタル署名」**という技術が使われています。これは、いわば「絶対に偽造できないデジタルのハンコ」です。

しかし、将来**「量子コンピュータ」**という、今のコンピュータが何万年もかかる計算を数秒で解いてしまうような「魔法の計算機」が登場すると、今使っているハンコの仕組みが、あっという間に偽造されてしまうかもしれない……という恐怖があります。

2. Spinel（スピネル）のアイデア：数学の「迷路」で守る

そこで研究チームが考えたのが、**「Spinel（スピネル）」**という新しいハンコの仕組みです。

これまでのハンコは、「複雑な数字のパズル」を解くのが難しいことを根拠にしていました。しかし、Spinelはもっとユニークな方法を使います。それは、**「巨大で複雑な迷路の中を、ランダムに歩き回る」**という方法です。

【例え話：迷路と足跡】

想像してみてください。あなたは広大な、目に見えないほど複雑な「迷路」の中にいます。

メッセージ（送りたい内容）： これは、迷路の中をどう進むかという「指示書」です。
ハッシュ関数（Spinelの核）： 指示書に従って、迷路の中を「右、左、右、右……」と歩いていきます。
デジタル署名（ハンコ）： 迷路を歩ききった最後に、あなたが**「たどり着いた場所（座標）」**が、あなたのハンコになります。

量子コンピュータがどれほど賢くても、この迷路が「あまりにも複雑で、ルールが数学的にガチガチに固められている」ため、逆算して「どの指示書（メッセージ）を使えば、その場所にたどり着けるか？」を当てることは、ほぼ不可能だと考えられています。

3. この研究のすごいところ（3つのポイント）

この論文では、単に「新しいアイデアを思いついた」だけでなく、以下の3つを証明しました。

「この迷路は本当にデタラメか？」をテストした
新しい迷路（数学的な計算）を作っても、歩き方が偏ってしまうと、逆にパターンを見破られてしまいます。研究チームは、この迷路の歩き方が「完全にランダムで、予測不能であること」を、厳しい統計テスト（NISTテスト）で証明しました。
「使いやすさ」を計算した
新しい仕組みを作っても、署名を作るのに1時間かかったり、ハンコのサイズが巨大すぎたりしたら、実用的ではありません。研究チームは、「速さ」と「サイズ」のバランスをどう取ればいいか、数学的なシミュレーションを行いました。
実際に動くものを作った
理論だけでなく、実際にコンピュータ上で動くプログラムを作り、「これなら将来のインターネットでも使えるぞ！」という実力を見せつけました。

4. まとめ：未来の守護神

この論文が提案する Spinel は、いわば**「量子コンピュータという最強の泥棒が来ても、絶対に迷い込んで抜け出せなくなる、数学的に設計された超複雑な迷路」**です。

これによって、将来どんなに計算能力が上がっても、私たちのオンライン上のやり取り（銀行振込や契約など）が安全に守られるための、新しい「守りの道具箱」に、強力な新しいツールが加わったのです。

論文要約：Spinel — $SL_n(\mathbb{F}_p)$ ハッシュに基づく耐量子デジタル署名スキーム

1. 背景と問題意識 (Problem)

現在のデジタル署名（RSAや楕円曲線暗号など）は、量子コンピュータの出現によって、素因数分解や離散対数問題の困難性が崩壊し、安全性が脅かされることが予測されています。これに対し、ハッシュ関数に基づく署名スキーム（例：SPHINCS+）は、量子耐性を持つ有力な候補です。

しかし、SPHINCS+などの既存のハッシュベース署名スキームの安全性は、SHA-256やSHAKE-256といったヒューリスティック（経験則的）な安全性に依存するハッシュ関数に依拠しています。これらの関数の安全性は、数学的な困難性問題に直接還元されているわけではありません。本論文の核心的な問いは、**「代数的な構造を持つハッシュ関数を用いることで、ハッシュベース署名の理論的基盤をより強固にできるか？」**という点にあります。

2. 手法 (Methodology)

著者らは、SPHINCS+のフレームワークを維持しつつ、その基盤となるハッシュ関数を、数学的に解析された代数的なハッシュ関数に置き換えた新しい署名スキーム**「Spinel」**を提案しています。

A. 代数的なハッシュ関数 (The Spinel Hash)

基盤理論: Tillich–Zémorパラダイムに基づき、特殊線形群 $SL_n(\mathbb{F}_p)$ 上のケイリーグラフにおける非後退ランダムウォーク (Non-backtracking random walk) を利用します。
構成: 入力データを3進数（trits）に変換し、それを生成元（ $A, B$ およびその逆元）の選択プロセスとして用います。行列の積を計算し、その結果を $SL_4(\mathbb{F}_p)$ の要素として出力します。
パラメータ: 行列の次元 $n=4$ 、素数 $p = 2^{31}-1$ を採用。行列の各要素を32ビット整数としてシリアライズすることで、512ビットの固定長ダイジェストを実現しています。 $n \ge 3$ とすることで、低次元群（ $SL_2$ ）で見られるような既知の攻撃を回避しています。

B. SPHINCS+ への統合

Spinelは、SPHINCS+の構造（WOTS+, FORS, Hypertree）をそのまま継承しています。

ドメイン分離: Tweakable hash function の概念を維持し、アドレス（ADRS）をハッシュ入力に含めることで、異なるコンテキスト間での衝突を防ぎます。
安全性モデル: SPHINCS+の安全性証明を利用し、代数的なハッシュ関数がランダムオラクルとして振る舞う限り、署名スキーム全体の安全性が保たれることを示しています。

3. 主な貢献 (Key Contributions)

新しい署名スキームの提案: 経験的なハッシュ関数に代わり、数学的な困難性（拡大グラフ上のナビゲーション問題）に基づくハッシュ関数を組み込んだ「Spinel」を設計。
ハッシュ関数の実証的検証: 提案したハッシュ関数が、NISTの統計テストスイート（STS）の全15カテゴリに合格することを確認し、出力のランダム性を実証。
セキュリティ劣化のモデル化: 署名が発行されるたびにFORS（Few-Time Signature）の秘密情報が一部漏洩する現象に対し、ポアソン分布を用いた数学的モデルを適用し、署名数に応じた有効セキュリティビット数の減少を定量化。
実装とベンチマーク: C言語による実装を行い、計算効率と署名サイズに関する詳細なデータを提供。

4. 結果 (Results)

A. 統計的評価

提案ハッシュ関数は、NIST STSにおいて極めて高いランダム性を示しました。これにより、代数的な構造を持ちながらも、統計的に一様な出力が得られることが証明されました。

B. パフォーマンス特性

計算コスト: 署名（Signing）は検証（Verification）に比べて約3桁（1000倍）遅い傾向にあります。これはハッシュベース署名全般に共通する特性です。
トレードオフ:
- 署名速度重視: Hypertreeの高さ $h$ を低く設定することで高速化が可能。
- 署名サイズ重視: FORSのパラメータ（ $b, k$ ）を調整することで、サイズを削減可能。
比較: 既存のSHAKE-256を用いたSPHINCS+と比較すると、行列演算のオーバーヘッドと512ビットのダイジェスト使用により、署名サイズと検証時間は大きくなりますが、これは「より強固な数学的仮定」に対するコストとして妥当な範囲内です。

5. 意義 (Significance)

本研究は、「代数的なハッシュ関数を用いたハッシュベース署名」という新しい設計領域を切り拓いた点に大きな意義があります。

従来のハッシュベース署名は「ハッシュ関数がランダムである」という暗黙の前提に依存していましたが、Spinelは「特定の数学的問題（群論的な困難性）が解けない」という明示的な理論的根拠を署名スキームに持ち込みました。これは、将来的に量子コンピュータが高度化し、既存のハッシュ関数の構造的な弱点が発見されたとしても、異なる数学的基盤を持つ署名スキームを選択できるという、ポスト量子暗号の「ツールキット」を拡張する重要な成果です。