論文の概要: Improved Dual Attack and Trapdoor Sampling via Quantum Rejection Sampling
- arxiv url: http://arxiv.org/abs/2605.24798v1
- Date: Sun, 24 May 2026 01:01:43 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-26 19:50:18.451117
- Title: Improved Dual Attack and Trapdoor Sampling via Quantum Rejection Sampling
- Title（参考訳）: 量子リジェクションサンプリングによるデュアルアタックとトラップドアサンプリングの改善
- Authors: Cong Ling, Hao Yan, Nicholas Zhao,
- Abstract要約: 格子ガウスサンプリング項は二重攻撃とGPVトラップドアサンプリングにおいて重要なボトルネックとなる。
このサンプリングステップは、下界の Wang と Ling の Klein のアルゴリズム解析を組み合わせることで、量子的に加速できることを示す。
このサンプルをデュアルアタックフレームワークに置き換えると、全体的なアタックコストの見積が削減される。
- 参考スコア（独自算出の注目度）: 10.490991694116127
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work, we revisit the dual attack and GPV trapdoor sampling, focusing on the lattice Gaussian sampling term, which can be a significant bottleneck in the overall complexity. We show that this sampling step can be quantumly accelerated by combining the lower bound underlying Wang and Ling's analysis of Klein's algorithm with the quantum rejection sampling (QRS) framework proposed by Ozols et al. Specifically, this lower bound gives precisely the pointwise domination condition required for quantum rejection sampling when given coherent oracle access to a truncated Klein proposal distribution, which yields a quantum procedure for preparing the truncated dual $q$-ary lattice Gaussian with a quadratic reduction in the sampling complexity. The truncation radius is chosen so that the truncated distribution is negligibly close to the full lattice Gaussian in total variation distance. Substituting this sampler into the dual attack framework results in reduced overall attack-cost estimates. Compared with Pouly and Shen's modern dual attack under the same parameter choices, our estimates reduce the attack cost by \(9\), \(4\), and \(13\) bits for Kyber-512, Kyber-768, and Kyber-1024, respectively. We also report the corresponding estimates with modulus switching. Finally, by replacing the Markov chain Monte Carlo (MCMC) sampler with the QRS algorithm, we achieve a similar quadratic speedup in the GPV signing process.
- Abstract（参考訳）: 本研究では,2重攻撃とGPVトラップドアサンプリングを再考し,格子ガウスサンプリング項に着目した。
Ozolsらによって提案された量子リジェクションサンプリング(QRS)フレームワークと、量子リジェクションサンプリング(QRS)フレームワークを組み合わせることで、このサンプリングステップを量子的に加速できることを示す。具体的に、この下限は、与えられたコヒーレントなオラクルが、トランキャットされたクライン提案分布にアクセスできるときに、量子リジェクションサンプリングに必要なポイントワイドな支配条件を与える。
トラルニケート半径は、トラルニケート分布が全変分距離においてフル格子ガウスに無視的に近いように選択される。
このサンプルをデュアルアタックフレームワークに置き換えると、全体的なアタックコストの見積が削減される。
同じパラメータ選択下でのPouly と Shen の2重攻撃と比較すると,Kyber-512,Kyber-768,Kyber-1024 の攻撃コストは,それぞれ \(9\), \(4\), \(13\) となる。
また,弾性率の変動に伴う推定値についても報告する。
最後に、マルコフ連鎖モンテカルロ(MCMC)サンプリング器をQRSアルゴリズムに置き換えることで、GPV署名プロセスにおいて同様の2次高速化を実現する。
関連論文リスト
- Ancilla-Efficient QSAMPLE Preparation for Reversible Markov Chains [0.0]
作業レジスタに1つのアシラキュービットしか必要としない新しいエンドツーエンドフレームワークを提案する。
重要な技術的要素は、1つのアンシラ量子ビットを用いた選択位相コンパイラ回路である。
直接応用として,ギブスQSAMPLEの作成に量子アルゴリズムを適用し,厳密な複雑性解析を求める。
論文 参考訳（メタデータ） (2026-05-22T09:55:28Z) - Stratified Sampling for Quasi-Probability Decompositions [0.0]
準確率分解(QPD)は多くの量子アルゴリズムやプロトコルにおいて必須であることが証明されている。
我々は,この分散を考慮し,低減するための幅広い枠組みを構築している。
典型的なQPDの数値シミュレーションは、全体分散の定数要素の減少を示す。
論文 参考訳（メタデータ） (2026-02-11T17:46:40Z) - Large Language Monkeys: Scaling Inference Compute with Repeated Sampling [81.34900892130929]
モデルから候補解を繰り返しサンプリングする簡単な手法を用いて、推論計算をスケーリングのための別の軸として検討する。
複数のタスクやモデルにまたがって、カバレッジは4桁以上のサンプル数でスケールする。
コードや形式的証明のようなドメインでは、回答が自動的に検証されるので、カバレッジの増加は直接的にパフォーマンスの向上につながります。
論文 参考訳（メタデータ） (2024-07-31T17:57:25Z) - Faster Sampling via Stochastic Gradient Proximal Sampler [28.422547264326468]
非log-concave分布からのサンプリングのための近位サンプリング器 (SPS) について検討した。
対象分布への収束性は,アルゴリズムの軌道が有界である限り保証可能であることを示す。
我々は、Langevin dynamics(SGLD)とLangevin-MALAの2つの実装可能な変種を提供し、SPS-SGLDとSPS-MALAを生み出した。
論文 参考訳（メタデータ） (2024-05-27T00:53:18Z) - Stochastic Quantum Sampling for Non-Logconcave Distributions and
Estimating Partition Functions [13.16814860487575]
非対数確率分布からサンプリングする量子アルゴリズムを提案する。
f$ は有限和 $f(x):= frac1Nsum_k=1N f_k(x)$ と書くことができる。
論文 参考訳（メタデータ） (2023-10-17T17:55:32Z) - Importance sampling for stochastic quantum simulations [68.8204255655161]
我々は、係数に応じてハミルトン式からサンプリングしてランダムな積公式を構築するqDriftプロトコルを導入する。
サンプリング段階における個別のシミュレーションコストを考慮し、同じ精度でシミュレーションコストを削減可能であることを示す。
格子核効果場理論を用いて数値シミュレーションを行った結果, 実験結果が得られた。
論文 参考訳（メタデータ） (2022-12-12T15:06:32Z) - A Proximal Algorithm for Sampling [14.909442791255042]
我々は、滑らかさに欠けるポテンシャルに関連する問題を研究する。
ポテンシャルは凸か非滑らかである。
本アルゴリズムは, 拒絶サンプリングの特殊な事例に基づく。
論文 参考訳（メタデータ） (2022-02-28T17:26:09Z) - Sampling Overhead Analysis of Quantum Error Mitigation: Uncoded vs.
Coded Systems [69.33243249411113]
パウリの誤差は、多数の現実的な量子チャネルの中で最も低いサンプリングオーバーヘッドをもたらすことを示す。
我々はQEMと量子チャネル符号化を併用する手法を考案し、純粋なQEMと比較してサンプリングオーバーヘッドの低減を解析する。
論文 参考訳（メタデータ） (2020-12-15T15:51:27Z) - Revisiting the Sample Complexity of Sparse Spectrum Approximation of
Gaussian Processes [60.479499225746295]
本稿では,ガウス過程に対して,パラメータ空間全体に対して同時に保持可能な保証付きスケーラブルな近似を導入する。
我々の近似は、スパーススペクトルガウス過程(SSGP)のための改良されたサンプル複雑性解析から得られる。
論文 参考訳（メタデータ） (2020-11-17T05:41:50Z) - On Thompson Sampling with Langevin Algorithms [106.78254564840844]
多武装バンディット問題に対するトンプソンサンプリングは理論と実践の両方において良好な性能を享受する。
計算上のかなりの制限に悩まされており、反復ごとに後続分布からのサンプルを必要とする。
本稿では,この問題に対処するために,トンプソンサンプリングに適した2つのマルコフ連鎖モンテカルロ法を提案する。
論文 参考訳（メタデータ） (2020-02-23T22:35:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。