論文の概要: Eidolon: A Practical Post-Quantum Signature Scheme Based on k-Colorability in the Age of Graph Neural Networks

• arxiv url: http://arxiv.org/abs/2602.02689v1
• Date: Mon, 02 Feb 2026 19:05:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-04 18:37:15.01984
• Title: Eidolon: A Practical Post-Quantum Signature Scheme Based on k-Colorability in the Age of Graph Neural Networks
• Title（参考訳）: Eidolon: グラフニューラルネットワーク時代におけるk-Colorabilityに基づく量子後署名の実践的スキーム
• Authors: Asmaa Cherkaoui, Ramon Flores, Delaram Kahrobaei, Richard Wilson,
• Abstract要約: エイドロン(Eidolon)は、NP完全k色性問題に基づく実用的な量子後シグネチャスキームである。 ランダムグラフの統計プロファイルを保存する「キート」カラーリングを植え込み、ハードインスタンスを生成する。
• 参考スコア（独自算出の注目度）: 0.5249805590164902
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose Eidolon, a practical post-quantum signature scheme based on the NP-complete k-colorability problem. Our construction generalizes the Goldreich-Micali-Wigderson zero-knowledge protocol to arbitrary k >= 3, applies the Fiat-Shamir transform, and uses Merkle-tree commitments to compress signatures from O(tn) to O(t log n). Crucially, we generate hard instances via planted "quiet" colorings that preserve the statistical profile of random graphs. We present the first empirical security analysis of such a scheme against both classical solvers (ILP, DSatur) and a custom graph neural network (GNN) attacker. Experiments show that for n >= 60, neither approach recovers the secret coloring, demonstrating that well-engineered k-coloring instances can resist modern cryptanalysis, including machine learning. This revives combinatorial hardness as a credible foundation for post-quantum signatures.
• Abstract（参考訳）: NP完全k色性問題に基づく実効的な量子後シグネチャスキームであるEidolonを提案する。 我々はGoldreich-Micali-Wigderson 0-knowledge プロトコルを任意の k >= 3 に一般化し、Fiat-Shamir 変換を適用し、O(tn) から O(t log n) へのシグネチャを圧縮するために Merkle-tree のコミットメントを利用する。 重要なことは、ランダムグラフの統計プロファイルを保存する「キート」カラーリングを植え込み、ハードインスタンスを生成する。 本稿では,古典的解法 (ILP, DSatur) とカスタムグラフニューラルネットワーク (GNN) の攻撃者に対する,このようなスキームの最初の経験的セキュリティ分析について述べる。 実験によると、n >= 60 の場合、どちらのアプローチも秘密の着色を回復せず、十分にエンジニアリングされたk-彩色インスタンスが機械学習を含む現代の暗号解析に抵抗できることが示されている。 このことは、結合の硬さを、量子後署名の信頼できる基盤として復活させる。

関連論文リスト

• Less is More: Towards Simple Graph Contrastive Learning [28.21633108265473]
  グラフコントラスト学習(GCL)は教師なしグラフ表現学習に対して強い期待を示しているが、ヘテロ親和性グラフに対する効果は限定的である。 既存の手法の多くは、複雑な拡張スキーム、複雑なエンコーダ、あるいは負のサンプリングに依存している。 グラフトポロジから構造的特徴を集約することでノード特徴雑音を緩和する。
  論文  参考訳（メタデータ） (2025-09-30T03:56:50Z)
• Bridging Continuous and Discrete Tokens for Autoregressive Visual Generation [85.82112629564942]
  本稿では,離散トークンのモデリングをシンプルに保ちながら,連続トークンの強力な表現能力を維持するTokenBridgeを提案する。 本稿では,各特徴次元を独立に離散化し,軽量な自己回帰予測機構と組み合わせた次元ワイド量子化戦略を提案する。 提案手法は,標準的なカテゴリー予測を用いて,連続的手法と同等に再現および生成品質を実現する。
  論文  参考訳（メタデータ） (2025-03-20T17:59:59Z)
• Discrete Graph Auto-Encoder [52.50288418639075]
  離散グラフオートエンコーダ(DGAE)という新しいフレームワークを導入する。 まず、置換同変オートエンコーダを用いてグラフを離散潜在ノード表現の集合に変換する。 2番目のステップでは、離散潜在表現の集合をソートし、特別に設計された自己回帰モデルを用いてそれらの分布を学習する。
  論文  参考訳（メタデータ） (2023-06-13T12:40:39Z)
• Randomized Message-Interception Smoothing: Gray-box Certificates for Graph Neural Networks [95.89825298412016]
  グラフニューラルネットワーク(GNN)のための新しいグレーボックス証明書を提案する。 我々はランダムにメッセージを傍受し、敵に制御されたノードからのメッセージがターゲットノードに到達する確率を分析する。 我々の証明書は、より遠くからの攻撃に対してより強力な保証を提供する。
  論文  参考訳（メタデータ） (2023-01-05T12:21:48Z)
• Efficient NIZKs and Signatures from Commit-and-Open Protocols in the QROM [10.5811404306981]
  コミット・アンド・オープンなSigma-protocolsは、非インタラクティブなゼロ知識引数とデジタル署名スキームを構築するための一般的なプロトコルのクラスである。 量子ランダムオラクルモデル(QROM)における厳密なオンライン抽出可能性を証明する。 この結果,デジタル署名方式であるPicnicの量子後セキュリティが向上した。
  論文  参考訳（メタデータ） (2022-02-28T12:51:51Z)
• Black-box Node Injection Attack for Graph Neural Networks [29.88729779937473]
  被害者のGNNモデルを回避するためにノードを注入する可能性について検討する。 具体的には,グラフ強化学習フレームワークGA2Cを提案する。 本稿では,既存の最先端手法よりもGA2Cの方が優れた性能を示す。
  論文  参考訳（メタデータ） (2022-02-18T19:17:43Z)
• Graph Coloring with Quantum Annealing [0.0]
  そこで我々は,D-Wave 2X を独立セットサンプリングとして用いたグラフカラー化近似アルゴリズムを開発した。 ランダムに生成された小さなグラフインスタンスのセットは、テストセットとして役立ちます。 我々の性能分析は、ハイブリッド量子古典アルゴリズムにおける量子優位性に限界があることを示唆している。
  論文  参考訳（メタデータ） (2020-12-08T15:08:22Z)
• Towards Sharper First-Order Adversary with Quantized Gradients [43.02047596005796]
  敵の訓練は最も成功した 敵の攻撃に対する防御だった 最先端の1次攻撃では、符号勾配を持つ逆例は各勾配成分の符号情報を保持するが、成分間の相対等級は捨てる。 勾配量子化は符号情報を保存するだけでなく、成分間の相対等級も保持する。
  論文  参考訳（メタデータ） (2020-02-01T14:33:51Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。