HyperFrog 暗号システム：構造化された秘密分散のための連結グラフのサイクルランク

技術的サマリー（日本語）

本論文は、実験的なポスト量子鍵封入メカニズム（KEM）である「HyperFrog」の改訂版（v36.0 対応）を提案するものです。従来の LWE（Learning With Errors）ベースの KEM とは異なり、秘密鍵の分布を「連結されたボクセル占有場（voxel occupancy field）」の生成プロセスに依存させるという、構造化された秘密分布を採用しています。本稿では、以前のドラフトで混同されていた「形式的な定義」と「工学的な実装」を明確に分離し、ベンチマークの解釈を厳密化することに重点を置いています。

1. 解決しようとする問題と背景

ポスト量子暗号の標準化が進む中、格子ベース、符号ベース、等方性ベースなど成熟した KEM が存在します。しかし、設計の異なる部分のみを変更して実験的な構成を研究することは、新しい秘密分布の特性や攻撃ベクトルを理解する上で重要です。
HyperFrog は、従来の LWE 方式の代数コア（行列展開、公開鍵方程式など）はそのまま維持しつつ、秘密鍵の生成方法を革新しようとする試みです。

• 従来の課題: 以前のドラフトでは、秘密鍵の生成が「トポロジカルな物語（種数 genus など）」と「実用的なマイニング（コード内の工学的な簡易化）」が曖昧に混在しており、形式的な秘密法則（Secret Law）が明確でなかった。
• 本稿の課題: 秘密鍵の分布を数学的に厳密に定義し、実装モード（形式的マイナー vs 工学的マイナー）を明確に区別することで、セキュリティ主張の透明性とベンチマーク結果の解釈可能性を高めること。

2. 手法とシステム設計

HyperFrog は以下の 3 つの層で構成されます。

A. 秘密生成器（連結フロント成長プロセス）

16×16×16 のボクセルグリッド（全 4096 点）上で、秘密鍵（2048 ビットの占有ベクトル）を生成します。

• 形式的マイナー（Formal Miner）: 本論文で主張する秘密法則です。
  1. 4096 個のグリッドから 1 点を均一に選択し、占有状態とします。
  2. 現在の占有ボクセルの「隣接する未占有ボクセル（フロント）」から 1 点を均一に選び、占有状態に追加します。
  3. 占有ボクセル数が厳密に 2048 個になるまでこのプロセスを繰り返します。
  4. 生成された形状の**グラフサイクルランク（Graph Cycle Rank, $\beta_1$）**を計算し、ユーザー指定の閾値 $\tau$ 以上であれば採用します。
  • 特徴: 連結性が保証され、占有重みが厳密に固定され、ランダムなフロント拡張に基づく明確な確率分布を形成します。
• 工学的マイナー（Practical Miner）: コードには存在しますが、実験やテスト用として形式的主張からは除外されます。ランダムなビットセットから最大連結成分を抽出するなどの簡易的なアプローチを取ります。

B. 公開鍵と KEM コア（LWE ベース）

• パラメータ: $N=4096$, $M=2048$, 法 $q=2^{16}$, 鍵長 $k=256$ ビット。
• 公開鍵: シードから ChaCha20 を用いて行列 $A$ を展開し、$b = As + e \pmod q$ を計算（$s$ は上記で生成された秘密鍵、$e$ は中心二項分布ノイズ）。
• 暗号化: 256 ビットのメッセージに対し、各ビットごとに 64 行のランダムな行を選択して和を計算し、$u$ ベクトルと $v$ スカラーを生成します。
• 復号: Fujisaki-Okamoto (FO) 変換を適用し、選択的暗号文攻撃（CCA）耐性を実現します。

C. 実装とベンチマーク

• ファイル暗号化には AES-256-GCM を使用。
• 秘密鍵ファイルのパスワード保護には Argon2id を使用。
• ベンチマークでは、「秘密鍵のアンロック時間（パスワード解読）」と「暗号学的復号時間」を明確に分離して計測します。

3. 主な貢献

1. トポロジカル不変量の厳密化: 「種数（genus）」という曖昧な用語を廃止し、グラフ理論における**サイクルランク（$\beta_1 = |E| - |V| + C$）**という明確な数学的指標に統一しました。
2. 形式マイナーと工学的マイナーの分離: 論文の主張（形式マイナー）と実装の便利機能（工学的マイナー）を明確に区別し、セキュリティ評価の対象を限定しました。
3. 厳密な重み制御: 秘密鍵の占有ボクセル数を「2048 個」と厳密に固定することで、ノイズ分散の解析を簡潔化し、分布の特性を明確にしました。
4. ベンチマーク手法の改善: 鍵生成の診断情報、復号の正しさを記録するだけでなく、パスワードによる鍵アンロックコストと暗号処理コストを分離して報告し、パフォーマンス評価の透明性を高めました。

4. 実験結果

提出されたベンチマークコーパス（1670 件の形式サンプル）における結果は以下の通りです。

• 安定性: 1670 件中 1670 件で鍵生成に成功し、タイムアウトは 0 件でした。
• 構造的一貫性: すべてのサンプルで占有重みが厳密に 2048、連結成分数が 1 でした。
• サイクルランク: 観測されたサイクルランクは 2315〜2856 の範囲に分布し、平均は 2687.3 でした（閾値 $\tau$ は 6〜12 程度で設定されていたため、閾値によるフィルタリングは実際には行われていませんでした）。
• 復号成功率: 1670 件中 1670 件で復号の正しさが確認されました。
• パフォーマンス:
  • 鍵生成は非常に高速（平均 0.2ms 未満）。
  • 暗号化・復号は、ファイルサイズに比例してスケーリングしますが、パスワード保護された秘密鍵の場合、Argon2id によるアンロック時間が全体の復号時間の大部分を占めることが判明しました。
  • スレッド数 32 本ではオーバーヘッドが発生し、16 本が最適でした。

5. 意義と限界

意義:
本論文は、実験的なポスト量子暗号において、**「何を実装しているか（秘密分布）」と「何を主張できるか（セキュリティ）」**を誠実に区別するモデルケースを提供しています。特に、形式定義と実装コードの整合性を高め、ベンチマーク結果の解釈における誤解（例：パスワード解読コストを暗号コストと混同するなど）を防ぐための枠組みを確立しました。

限界と今後の課題:

• セキュリティ証明の欠如: 連結グラフ条件付きの秘密分布に対する LWE の困難性に関する削減証明（reduction）は存在しません。この分布が標準的な LWE と同等の安全性を持つかは未解決です。
• 帯域幅: 暗号文サイズが約 2.10 MB と非常に大きく、実用化には非効率です。
• 閾値の較正: 現在のベンチマークでは、設定されたサイクルランク閾値が非常に緩く、マイナーが「難しい条件」を満たす必要がないため、厳密な受入確率の較正は行われていません。
• サイドチャネル: 完全なサイドチャネル監査は行われていません。

結論:
HyperFrog は、ポスト量子暗号の新たな秘密分布を研究するための「透明な実験プラットフォーム」として再定義されました。完全な製品ではなく、構造化された秘密鍵が LWE に対してどのような影響を与えるかを検証するための研究対象として、その定義と実装が明確に記述されています。