論文の概要: On the success probability of the quantum algorithm for the short DLP
- arxiv url: http://arxiv.org/abs/2309.01754v1
- Date: Mon, 4 Sep 2023 18:26:45 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-06 17:43:35.169801
- Title: On the success probability of the quantum algorithm for the short DLP
- Title（参考訳）: 短距離DLPにおける量子アルゴリズムの成功確率について
- Authors: Martin Eker{\aa}
- Abstract要約: 我々は,Ekeraa-Haastadのアルゴリズムが単一ランで短い$d$を回復する確率の低い境界を証明した。
私たちの限界によって、成功確率は、任意の短い$d$に対して1から1010$まで容易に押し付けられる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Eker{\aa} and H{\aa}stad have introduced a variation of Shor's algorithm for
the discrete logarithm problem (DLP). Unlike Shor's original algorithm,
Eker{\aa}-H{\aa}stad's algorithm solves the short DLP in groups of unknown
order. In this work, we prove a lower bound on the probability of
Eker{\aa}-H{\aa}stad's algorithm recovering the short logarithm $d$ in a single
run. By our bound, the success probability can easily be pushed as high as $1 -
10^{-10}$ for any short $d$. A key to achieving such a high success probability
is to efficiently perform a limited search in the classical post-processing by
leveraging meet-in-the-middle techniques. Asymptotically, in the limit as the
bit length $m$ of $d$ tends to infinity, the success probability tends to one
if the limits on the search space are parameterized in $m$. Our results are
directly applicable to Diffie-Hellman in safe-prime groups with short
exponents, and to RSA via a reduction from the RSA integer factoring problem
(IFP) to the short DLP.
- Abstract（参考訳）: Eker{\aa} と H{\aa}stad は離散対数問題 (DLP) に対する Shor のアルゴリズムのバリエーションを導入した。
Shorのアルゴリズムとは異なり、Eker{\aa}-H{\aa}stadのアルゴリズムは未知の順序の群で短いDLPを解く。
本研究では,eker{\aa}-h{\aa}stadのアルゴリズムが1回のランで短い対数$d$を回復する確率について,下限を証明した。
私たちの意見では、成功確率は、短い$d$の場合には、簡単に$110^{-10}$まで押し上げられます。
このような高い成功確率を達成する鍵は、ミート・イン・ザ・ミドルの技術を利用して、古典的な後処理において限られた探索を効率的に行うことである。
漸近的に、ビット長$m$の$d$が無限大の傾向にあるように、検索空間の極限が$m$でパラメータ化される場合、成功確率は1つになる。
我々の結果は、短い指数を持つ安全プリム群におけるディフィー・ヘルマンとRSA整数分解問題(IFP)から短いDLPへの還元を通じてRSAに直接適用できる。
関連論文リスト
- Efficient quantum algorithms for some instances of the semidirect
discrete logarithm problem [2.90985742774369]
SDLPは,いくつかの重要な症例においてさらに容易であることを示す。
SDLPのハードネスを前提としたセキュリティ仮定を前提としたSPDH-Signと類似の暗号系が量子攻撃に対して安全でないことを示す。
論文 参考訳（メタデータ） (2023-12-21T16:58:59Z) - Fast Minimization of Expected Logarithmic Loss via Stochastic Dual
Averaging [8.990961435218544]
本稿では,対数障壁を用いたB$-sample双対平均化法を提案する。
Poisson逆問題に対して、我々のアルゴリズムは$smashtildeO(d3/varepsilon2)$ timeで$varepsilon$解を得る。
量子状態トモグラフィーの最大線量推定を計算するとき、我々のアルゴリズムは $smashtildeO(d3/varepsilon2)$ time で $varepsilon$-optimal Solution を得る。
論文 参考訳（メタデータ） (2023-11-05T03:33:44Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - On the success probability of quantum order finding [0.0]
我々はShorのオーダーフィニングアルゴリズムが単一ランで$r$のオーダーを回復する確率の低い境界を証明した。
漸近的に、$r$が無限大の傾向にあるように、単一のランで$r$を回復する確率は1つになる。
論文 参考訳（メタデータ） (2022-01-19T18:58:18Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - Efficient Mean Estimation with Pure Differential Privacy via a
Sum-of-Squares Exponential Mechanism [16.996435043565594]
純微分プライバシーを受ける独立サンプルの共分散で$d$正確率分布の平均を推定するアルゴリズムを初めて与える。
我々の主な手法は、強力なSum of Squares法(SoS)を用いて微分プライベートアルゴリズムを設計する新しいアプローチである。
論文 参考訳（メタデータ） (2021-11-25T09:31:15Z) - Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。
O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。
さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
論文 参考訳（メタデータ） (2021-10-15T00:54:04Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-11T14:25:02Z) - Exponential Upper Bounds for the Runtime of Randomized Search Heuristics [9.853329403413701]
アルゴリズムの任意のランダム化ローカルサーチ,アルゴリズム,シミュレートされたアニーリング,および (1+1) 進化的アルゴリズムが,任意の擬ブール弱単調関数を最適化可能であることを示す。
また、OneMaxベンチマークにおいて、単純な遺伝的アルゴリズムの突然変異に基づくバージョンの実行時の指数的な上限を証明した。
論文 参考訳（メタデータ） (2020-04-13T00:24:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。