The SQInstructor: a guide to SQIsign and the Deuring Correspondence with level structures

本論文は、レベル構造の対応付けを要件として含めることで SQIsign 署名方式を一般化する新たな枠組みを提案し、レベル構造付き超特異楕円曲線に対する明示的なデュエリン対応と拘束付きノルム方程式の解法を提供するものである。

要約

SQInstructor: 超ひも理論の「レベル構造」を使った新しいデジタル署名のガイド

この論文は、量子コンピュータ時代に向けた新しいデジタル署名の仕組み「SQInstructor」について説明しています。既存の「SQIsign」という優れた署名方式を、より柔軟で強力な「レベル構造（Level Structures）」という概念を使って進化させたものです。

難しい数学用語を避け、日常の比喩を使ってこの研究の核心を解説します。

---

1. 背景：なぜ新しい署名が必要なのか？

従来の「SQIsign」とは？

まず、既存の「SQIsign」という署名方式を想像してください。これは、**「迷路の出口を見つけるゲーム」**のようなものです。

• 秘密鍵：迷路の入り口から出口への「隠された道（秘密のルート）」です。
• 公開鍵：迷路そのものです。
• 署名：誰かが「この迷路を解けるか？」と質問（チャレンジ）してきたとき、秘密の道を使って正解（回答）を返すことです。

SQIsign は非常にコンパクトで効率的ですが、その「秘密の道」を見つける計算が非常に複雑で、少し時間がかかるという弱点がありました。また、セキュリティ証明にも課題が残っていました。

今回の「SQInstructor」のアイデア

この論文の著者たちは、**「迷路の壁に、特定の『レベル』のマークをつける」というアイデアを導入しました。これを「レベル構造（Level Structure）」**と呼びます。

• 比喩：
  • 従来の SQIsign：「迷路の入り口から出口へ、ただ単に道を通れ」
  • 新しい SQInstructor：「入り口から出口へ通る道はいいが、『青い旗』が立っている場所を必ず通って、出口の『青い旗』に繋げなければならない』」

この「旗（レベル構造）」の制約を加えることで、計算がよりスムーズになり、セキュリティの証明も容易になるのです。

---

2. 核心：レベル構造とは何か？

「レベル構造」は、数学的には楕円曲線の「ねじれ部分群（torsion subgroup）」の基底を指しますが、ここでは**「迷路の特定のチェックポイント」**と考えると分かりやすいです。

• 1 次元の道（1D Isogenies）：
  昔ながらの方法で、迷路を一つずつ順番に解いていくスタイルです。
  • メリット：高度な機能（リング署名など）を作るのに使えます。
  • デメリット：少し遅いです。
• 高次元の道（2D Isogenies）：
  新しい方法で、迷路を立体的に、あるいは並列に解くスタイルです。
  • メリット：非常に高速で、現在の SQIsign と同等かそれ以上の性能があります。
  • デメリット：実装が少し複雑です。

SQInstructor は、この「レベル構造」の概念を**「旗の選び方」や「解く方法（1 次元か 2 次元か）」を自由に選べるようにする「汎用フレームワーク」**として提案しています。

---

3. 具体的な仕組み：どうやって動くのか？

このプロトコルは、3 つのステップで進行する「お見合い（識別）ゲーム」のようなものです。

1. コミットメント（約束）：
   証明者（署名する人）が、新しい迷路（コミットメント）を生成して、相手（検証者）に渡します。
2. チャレンジ（挑戦）：
   検証者が、その迷路に**「特定のレベル構造（例えば、赤い旗）」**を指定して、「この赤い旗を、あなたの秘密の道を使って、相手の迷路の『青い旗』に繋げてみせなさい！」と命令します。
3. レスポンス（回答）：
   証明者は、秘密鍵（隠された道）を使って、**「赤い旗から青い旗へ繋がる道」**を見つけ出し、それを証明します。

重要なポイント：
従来の SQIsign では、「道が特定の点（旗）を消滅させること」が求められていましたが、SQInstructor では**「ある旗を別の旗へ『移動』させること」**が求められます。この「移動」の自由度が、新しいセキュリティと効率性を生み出しています。

---

4. この研究の成果と貢献

この論文では、以下の 3 つの大きな成果を上げています。

1. 数学の一般化（Deuring 対応の拡張）：
   超ひも理論（数学の分野）と楕円曲線の関係を、単なる「曲線同士」だけでなく、「旗（レベル構造）付きの曲線同士」の関係にまで拡張しました。これにより、これまで難しかった大きな数の計算も、具体的なアルゴリズムで解けるようになりました。

2. 新しいアルゴリズムの開発：
   「旗の制約」を満たすような、効率的な道（アイソゲニー）を見つけるための新しい計算方法（制約付きノルム方程式の解法）を開発しました。

3. 実用的な実装：

   • 1 次元版：従来の SQIsign のような、リング署名などに応用できるバージョン。
   • 2 次元版：NIST（アメリカの規格化機関）が選定している最新の SQIsign と同等の速度とセキュリティを持つバージョン。

   実際の実験では、SQInstructor は SQIsign とほぼ同じ速度で動作し、署名サイズもほとんど変わらないことが確認されました。

---

5. まとめ：なぜこれが重要なのか？

SQInstructorは、単なる「新しい署名方式」ではなく、**「将来の暗号技術を柔軟に設計するための設計図（フレームワーク）」**です。

• 柔軟性：必要に応じて「1 次元の道」か「2 次元の道」かを選べます。
• 安全性：量子コンピュータに対しても強く、数学的な裏付けがより明確になりました。
• 応用：リング署名（誰が署名したか分からないようにする技術）や、他の高度な暗号技術に応用しやすい土台を提供します。

つまり、この研究は「暗号のレゴブロック」を、より多様で組み立てやすい形に作り変えたようなものです。これにより、量子コンピュータ時代でも安全に使える、より強力で便利なデジタル署名システムの実現が近づきました。

技術概要

論文「The SQInstructor: a guide to SQIsign and the Deuring Correspondence with level structures」の技術的サマリー

1. 概要と背景

本論文は、ポスト量子暗号の有力候補である等方性（Isogeny）に基づく暗号、特に NIST 標準化プロセスに参加している署名方式SQIsignの一般化と拡張を提案しています。

SQIsign は、超特異楕円曲線と四元数代数の間の**Deuring 対応（Deuring Correspondence）**を基盤としており、非常にコンパクトな署名サイズを実現しています。しかし、従来の SQIsign は、検証者のチャレンジとして「楕円曲線上の特定の点（ねじれ点）」を指定し、応答者がその点をゼロにする等方性（核を指定する等方性）を計算するという構造を持っていました。

本論文は、この「点をゼロにする」という制約を一般化し、**レベル構造（Level Structures）**を用いて、あるレベル構造を別のレベル構造へ「写す（マッピングする）」という新しい制約条件を導入することで、SQInstructorという新しい汎用フレームワークを提案しています。

2. 解決すべき課題

従来の SQIsign やその派生方式には、以下の課題や限界がありました。

1. 制約の柔軟性の欠如: 従来のプロトコルは、特定のねじれ点（またはその生成する部分群）を消滅させる（ゼロにする）等方性のみを扱っていました。これを「あるレベル構造を別のレベル構造へ写す」というより一般的な制約に拡張する理論的枠組みが不足していました。
2. Deuring 対応の一般化: 超特異楕円曲線にレベル構造（ねじれ部分群の基底の同値類）を付与した場合、四元数代数の部分環（Order）との対応関係がどのように変化するか、またそれをアルゴリズム的に明示的に計算する方法が完全には確立されていませんでした。
3. 制約付きノルム方程式の求解: 署名生成において、特定のレベル構造の制約を満たすような、滑らかなノルム（次数）を持つ等方性（または四元数体上のイデアル）を効率的に求めるアルゴリズムが必要でした。

3. 手法と主要な貢献

3.1 レベル構造を用いた Deuring 対応の一般化

著者らは、超特異楕円曲線にレベル構造（$\Gamma$-構造）を付与した系における Deuring 対応を一般化しました。

• 定義: 楕円曲線 $E$ の $N$-ねじれ部分群 $E[N]$ の基底の集合に対し、部分群 $\Gamma \subset GL_2(\mathbb{Z}/N\mathbb{Z})$ による同値関係を定義し、これを $\Gamma$-レベル構造とします（例：Borel 型、スカラー型、分裂カルタン型など）。
• 対応関係: 超特異楕円曲線とレベル構造の組 $(E, S)$ と、四元数代数 $B_{p,\infty}$ 内の特定の部分環（Order）$O(E, S)$ の間の対応を確立しました。
• イデアルと等方性: 等方性 $\phi: (E, S) \to (E', S')$ がレベル構造を保存する（$\phi(S) = S'$）条件は、四元数体上の左イデアルが特定の部分環に属するという条件として定式化されます。これにより、レベル構造の制約付きの等方性問題が、四元数体上の制約付きイデアル問題として扱えるようになりました。

3.2 SQInstructor プロトコルの提案

上記の一般化された対応関係に基づき、新しい識別プロトコル（および署名方式）SQInstructorを提案しました。

• プロトコルフロー:
  1. 鍵生成: 秘密鍵としてイデアル $I_{sk}$ を選び、公開鍵として $(E_{pk}, S_{pk})$ を設定します。
  2. コミットメント: 秘密イデアル $I_{com}$ を用いて曲線 $E_{com}$ を生成し、送信します。
  3. チャレンジ: 検証者が $E_{com}$ 上の新しいレベル構造 $S_{com}$ を選び、プロトコルに提示します。
  4. 応答: 証明者は、$S_{pk}$ を $S_{com}$ に写す等方性 $\phi_{rsp}$ を計算して送信します。
• 柔軟性: このフレームワークは、応答の計算に 1 次元の等方性（従来の SQIsign 風）を使用するか、2 次元以上の高次元等方性（HD）を使用するかを選択可能です。

3.3 アルゴリズム的貢献

• 制約付きノルム方程式の求解（1 次元の場合）:
  • 従来の KLPT アルゴリズムを拡張し、レベル構造の制約（特定の部分環への属する条件）を満たす滑らかなノルムを持つイデアルを計算するアルゴリズム（ScalarSigningKLPT, BorelSigningKLPT）を設計しました。
  • これにより、リング署名やチャメレオンハッシュなどの高度なプリミティブを 1 次元等方性で実現する道が開かれました。
• 高次元等方性による実装（2 次元の場合）:
  • 最新の SQIsign の技術（高次元等方性）を SQInstructor に適用し、効率的な署名生成と検証を実現しました。
  • 安全性証明（EUF-CMA）を、等方性オラクル（Isogeny Oracle）やヒント付きゼロ知識証明のモデル下で確立しました。

4. 結果と評価

4.1 実装とベンチマーク

著者らは、SQIsign のリファレンス実装をベースに SQInstructor を実装し、ベンチマークを行いました。

• 性能: 高次元等方性を用いた SQInstructor は、従来の SQIsign と比較して、鍵生成、署名、検証のすべての段階でほぼ同等の性能を示しました。
• サイズ: 署名サイズはわずかに増加しましたが（高次元等方性の表現による）、依然として非常にコンパクトです。
  • NIST Level I 基準で、公開鍵 65 バイト、署名 174 バイト（SQInstructor） vs 148 バイト（SQIsign）。
  • NIST Level V 基準で、公開鍵 129 バイト、署名 355 バイト（SQInstructor） vs 292 バイト（SQIsign）。
• 計算コスト: 検証時間はわずかに増加しましたが、実用上は許容範囲内です。

4.2 安全性

• 特殊な音明性（Special Soundness）: 異なるチャレンジに対する 2 つの応答から、非スカラーの自己準同型（Endomorphism）を構成できることを示し、レベル構造の制約付き Endomorphism 環問題の困難性に帰着されることを証明しました。
• ゼロ知識性: 高次元等方性を用いた場合、等方性オラクルモデル下で統計的なゼロ知識性を満たすことを示しました。

5. 意義と将来展望

1. 理論的統一: SQIsign の背後にある数学的構造を「レベル構造の写像」という観点から再解釈し、より広範なプロトコル設計の基盤を提供しました。
2. 高度なプリミティブへの適用: 1 次元等方性を用いたインスタンス化は、リング署名やチャメレオンハッシュなど、高次元等方性では実装が難しい（または未解決の）高度な暗号プリミティブを、レベル構造の制約付きで実現する可能性を開きました。
3. 実用性の維持: 理論的な一般化を行いながら、高次元等方性を用いた実装では既存の SQIsign と同等の実用性能を維持することに成功しました。これは、NIST 標準化に向けた候補方式の進化において重要なステップです。
4. 新しい数学的ツール: 超特異楕円曲線にレベル構造を付与した系における Deuring 対応の明示的な構成と、制約付きノルム方程式の効率的な求解アルゴリズムは、その後の研究において独立した価値を持つと考えられます。

結論として、SQInstructor は、SQIsign の柔軟性を高めつつ、その安全性と効率性を維持・拡張する画期的なフレームワークであり、ポスト量子署名技術の発展に大きく寄与するものです。