論文の概要: Verified Pythagorean Composition for Adaptive Cryptographic Games: Noise Flooding in Homomorphic Encryption
- arxiv url: http://arxiv.org/abs/2608.13846v1
- Date: Fri, 14 Aug 2026 00:40:29 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-17 20:14:29.228028
- Title: Verified Pythagorean Composition for Adaptive Cryptographic Games: Noise Flooding in Homomorphic Encryption
- Title（参考訳）: 適応暗号ゲームのための検証されたピタゴラス構成:同型暗号化におけるノイズ洪水
- Abstract要約: ノイズフラッディングは、近似同型暗号に対する復号攻撃に対する標準的な防御である。
本稿では,SSProveのセマンティクス上に新たなリレーショナル・プログラム・ロジックを構築した。
- 参考スコア（独自算出の注目度）: 45.00791460144501
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Noise flooding is a standard defense against decryption attacks on approximate homomorphic encryption, but its security proof is unusually sensitive to composition. Replacing each of $q$ adaptive decryption answers with a statistically close simulation and applying an ordinary hybrid argument loses linearly in $q$. The cryptographic proof instead accumulates conditional Kullback-Leibler (KL) costs and converts to statistical distance once, giving the parameter-critical square-root loss. We machine-check this argument using Rocq and SSProve. Given any fully homomorphic encryption scheme that is approximately correct and IND-CPA secure, we formalize a reduction for every $q$-query IND-CPAD adversary and prove \[ \Pr[\mathsf{IND\text{-}CPAD}_{\mathsf{NF}}^{\mathcal A}=1] \leq β_{\mathsf{CPA}}(\mathcal B_{\mathcal A,q}) + \frac{\sqrt{qn}}{2γ}. \] where $n$ is the plaintext dimension and $γ$ is the flooding-width multiplier. Our proof constructs a new relational program logic over SSProve semantics. Its Pythagorean judgment composes conditional KL budgets without converting them to statistical distance, and a verified trace compiler lifts a local oracle rule to arbitrary adaptive programs with a single final conversion.
- Abstract（参考訳）: ノイズフラッディングは、ほぼ同型暗号に対する復号攻撃に対する標準的な防御法であるが、そのセキュリティ証明は構成に異常に敏感である。
それぞれの$q$適応復号解を統計的にクローズドなシミュレーションで置き換え、通常のハイブリッド引数を適用すると、$q$で線形に失われる。
暗号証明は代わりに条件付きKullback-Leibler (KL) のコストを蓄積し、パラメータクリティカルな平方根の損失を与える統計距離に変換する。
我々は、RocqとSSProveを使ってこの引数をマシンでチェックする。
ほぼ正当かつIND-CPAセキュアな完全同型暗号スキームが与えられた場合、$q$-query IND-CPAD の逆数に対する還元を形式化し、 \[ \Pr[\mathsf{IND\text{-}CPAD}_{\mathsf{NF}}^{\mathcal A}=1] \leq β_{\mathsf{CPA}}(\mathcal B_{\mathcal A,q}) + \frac{\sqrt{qn}}{2γ} を証明する。
$n$ は平文次元、$γ$ はフラッディング幅乗算器です。
本稿では,SSProveのセマンティクス上に新たなリレーショナル・プログラム・ロジックを構築した。
ピタゴラスの判断は、統計的距離に変換することなく条件付きKL予算を構成し、検証されたトレースコンパイラは、局所オラクルルールを1つの最終変換を持つ任意の適応プログラムに持ち上げる。
関連論文リスト
- A Complexity-Theoretic Approach to Proofs of Space [5.160781170457704]
我々は、デランドマイズ仮定と暗号仮定の組み合わせからPoSを構築するための基本的な暗号フレームワークを提供する。
ほぼ最適なパラメータと相互作用パターンを持つPoSは、(a)上の仮定と(c)$mathsfP$に対するSNARGから従う。
論文 参考訳（メタデータ） (2026-08-10T01:28:01Z) - The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
AxiotisとSviridenkoは[AS21]において、凸最適化における制限条件数への線形依存はスパース時間アルゴリズムでは改善できないと推測した。
我々は、最小二乗目的に対する予想下界を確立し、ランダム化された完全体積小セット展開仮説に基づく条件付けを行う。
論文 参考訳（メタデータ） (2026-08-03T17:57:01Z) - Optimizing Explicit Unit-Distance Lower-Bound Certificates [0.0]
2026年のエルツの単位距離予想とサウィンの量的洗練の反証は、固定正の$varepsilon$に対して、n$平面点の間の単位距離の最大値$u(n)$が$n1+varepsilon$を超えることを示す。
本稿では、Sawinのパラメータ選択を非線形整数最適化問題として扱い、素集合$T$と$S_Q$を含む証明書のためのオープンソースのPythonパイプラインを開発する。
論文 参考訳（メタデータ） (2026-06-02T10:05:23Z) - Scaling Federated Linear Contextual Bandits via Sketching [49.12000877146222]
本稿では,FSCLB(Federated Sketch Contextual Linear Bandits)を提案する。
合成と実世界の両方のデータセットの実験では、FSCLBは計算と通信のコストを90%以上削減している。
論文 参考訳（メタデータ） (2026-05-01T08:22:06Z) - Cryptanalysis of the Legendre Pseudorandom Function over Extension Fields [0.0]
レジェンドレット擬似関数(Regendre Pseudorandom Function、PRF)は、レジェンドレットシンボル上に構築された高効率な暗号プリミティブである。
最近の関心は拡張フィールドの$mathbbF_pr$よりもインスタンス化に移行している。
本稿では, 1 度レジェンダー PRF を $mathbbF_pr$ で動作させる, 包括的な暗号解析手法を提案する。
論文 参考訳（メタデータ） (2026-04-06T16:35:32Z) - Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterization [85.91302339486673]
我々は、s-正方形および非正方形不確実性集合の下で、一般的な政策パラメータ化を伴うロバストマルコフ決定過程(RMDP)について検討する。
無限状態空間に拡張する一般政策パラメタライゼーションに対する新しいリプシッツ・リプシッツ・スムースネス特性を証明した。
本研究では,S-正方形不確かさに対する勾配降下アルゴリズムと非正方形不確かさに対するFrank-Wolfeアルゴリズムを設計する。
論文 参考訳（メタデータ） (2026-02-11T21:44:20Z) - Cryptographic transformations over polyadic rings [3.0860863056832826]
暗号システムは、グループ、リング、フィールド内のバイナリ操作に依存する。
我々は、高アリティの操作を許すことで古典環を一般化する多進環へのシフトを提案する。
この構造を利用する2つの具体的な暗号化手順を提案する。
論文 参考訳（メタデータ） (2025-12-14T07:15:55Z) - Compile-Time Fully Homomorphic Encryption of Vectors: Eliminating Online Encryption via Algebraic Basis Synthesis [1.3824176915623292]
暗号文は、事前計算された暗号化ベースベクターとランタイムスケールの0の暗号化を組み合わせた構成である。
ランダム化された$mathbbZ_t$-加群として定式化し、標準仮定の下でIND-CPAセキュリティを満たすことを証明した。
ゼロのランダムな暗号のプールを必要とする以前の設計とは異なり、我々の構成は実行時に新しいスカラーによって乗算された1つのゼロ暗号文を用いて等価なセキュリティを実現する。
論文 参考訳（メタデータ） (2025-05-19T00:05:18Z) - Post-quantum encryption algorithms of high-degree 3-variable polynomial congruences: BS cryptosystems and BS key generation [0.0]
本稿では,3変数のBeal-Schurコングルースに基づく量子後暗号アルゴリズムを構築する。
この結果を用いて、単純でセキュアな量子後暗号アルゴリズムを生成する。
論文 参考訳（メタデータ） (2024-08-14T14:19:46Z) - Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。
逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
論文 参考訳（メタデータ） (2021-10-25T02:53:24Z) - Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
計算・比較プログラム(Computer-and-compare program)として知られる回避関数のクラスに対する量子コピー保護スキームを導入する。
我々は,量子乱数オラクルモデル(QROM)において,完全悪意のある敵に対する非自明なセキュリティを実現することを証明した。
補完的な結果として、「セキュアソフトウェアリース」という,ソフトウェア保護の概念の弱さが示される。
論文 参考訳（メタデータ） (2020-09-29T08:41:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。