論文の概要: A compact QUBO encoding of computational logic formulae demonstrated on cryptography constructions

• arxiv url: http://arxiv.org/abs/2409.07501v1
• Date: Tue, 10 Sep 2024 18:46:26 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-13 20:40:16.931201
• Title: A compact QUBO encoding of computational logic formulae demonstrated on cryptography constructions
• Title（参考訳）: 暗号構造上で実証された計算論理公式のコンパクトQUBO符号化
• Authors: Gregory Morse, Tamás Kozsik, Oskar Mencer, Peter Rakyta,
• Abstract要約: 我々は,暗号アルゴリズムに焦点をあてて,準拘束的二項最適化の最先端を推し進めることを目指している。 AES-128/192/256、MD5、SHA1、SHA256など、最も広く使われている暗号アルゴリズムについて考察する。 これらの結果から,QUBO 行列のスパースと係数の大きさを低く保ちながら,これまでに公表した結果と比較して,QUBO のインスタンスを数千の論理変数で減らした。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We aim to advance the state-of-the-art in Quadratic Unconstrained Binary Optimization formulation with a focus on cryptography algorithms. As the minimal QUBO encoding of the linear constraints of optimization problems emerges as the solution of integer linear programming (ILP) problems, by solving special boolean logic formulas (like ANF and DNF) for their integer coefficients it is straightforward to handle any normal form, or any substitution for multi-input AND, OR or XOR operations in a QUBO form. To showcase the efficiency of the proposed approach we considered the most widespread cryptography algorithms including AES-128/192/256, MD5, SHA1 and SHA256. For each of these, we achieved QUBO instances reduced by thousands of logical variables compared to previously published results, while keeping the QUBO matrix sparse and the magnitude of the coefficients low. In the particular case of AES-256 cryptography function we obtained more than 8x reduction in variable count compared to previous results. The demonstrated reduction in QUBO sizes notably increases the vulnerability of cryptography algorithms against future quantum annealers, capable of embedding around $30$ thousands of logical variables.
• Abstract（参考訳）: 我々は,暗号アルゴリズムに焦点をあてて,準拘束的二項最適化の最先端を推し進めることを目指している。 最適化問題の線形制約の最小限のQUBOエンコーディングは、整数線形プログラミング(ILP)問題の解として現れるので、その整数係数に対する特別なブール論理式(ANFやDNF)を解くことで、正規形式やQUBO形式のマルチインプット AND、OR、XOR演算の置換を簡単に扱うことができる。 提案手法の効率性を示すため,AES-128/192/256,MD5,SHA1,SHA256などの暗号アルゴリズムについて検討した。 これらの結果から,QUBO 行列のスパースと係数の大きさを低く保ちながら,これまでに公表した結果と比較して,QUBO のインスタンスを数千の論理変数で減らした。 AES-256暗号関数の特定の場合、従来の結果と比較して変数数を8倍以上に削減した。 実証されたQUBOサイズの削減は、将来の量子アンニールに対する暗号アルゴリズムの脆弱性を顕著に増加させ、約30ドルの論理変数を埋め込むことができる。

関連論文リスト

• Encodings of the weighted MAX k-CUT on qubit systems [0.0]
  本稿では,重み付きMAX k-CUT問題の量子ビットシステム上での符号化法について検討する。 各種符号化方式について検討し,これらの手法の有効性について検討する。 重み付きおよび非重み付きグラフインスタンスの数値シミュレーションは、これらの符号化方式の有効性を実証する。
  論文  参考訳（メタデータ） (2024-11-13T13:21:35Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization [55.81991984375959]
  本研究では、以下の簡単な観察を通して、個別化されたプライバシ会計を解析する新しい手法を提案する。 我々は、分解可能な部分モジュラーおよびセットアルゴリズム被覆を含む、プライベート最適化問題に対するいくつかの改良されたアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-05-28T19:02:30Z)
• On efficient quantum block encoding of pseudo-differential operators [6.134067544403308]
  ブロック符号化は多くの既存の量子アルゴリズムの中核にある。 本稿では, 擬微分演算子 (PDO) を用いた高密度演算子のリッチファミリーのブロック符号化について述べる。
  論文  参考訳（メタデータ） (2023-01-21T07:18:57Z)
• 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)
• Alternatives to a nonhomogeneous partial differential equation quantum algorithm [52.77024349608834]
  Apsi(textbfr)=f(textbfr)$ という形の非等質線型偏微分方程式を解くための量子アルゴリズムを提案する。 これらの成果により、現代の技術に基づく量子アルゴリズムの実験的実装が容易になった。
  論文  参考訳（メタデータ） (2022-05-11T14:29:39Z)
• Gaussian Elimination versus Greedy Methods for the Synthesis of Linear Reversible Circuits [0.0]
  可逆回路は、量子コンピューティングに多くの応用がある可逆回路のサブクラスを表す。 ガウス除去アルゴリズムの最適化版と調整LU分解を用いて,任意の線形可逆作用素に対する新しいアルゴリズムを提案する。 全体として、我々のアルゴリズムは特定の問題サイズに対する最先端の手法を改善している。
  論文  参考訳（メタデータ） (2022-01-17T16:31:42Z)
• Finite-Bit Quantization For Distributed Algorithms With Linear Convergence [6.293059137498172]
  量子化された通信対象のメッシュネットワーク上での(強い凸)複合最適化問題に対する分散アルゴリズムについて検討する。 通信効率のよい符号化方式と結合した新しい量子化器を提案し, バイアス圧縮(BC-)ルールを効率的に実装した。 数値計算により,提案手法を応用した分散アルゴリズムは,既存の量子化規則を用いたアルゴリズムよりも,通信の複雑さが高いことが示された。
  論文  参考訳（メタデータ） (2021-07-23T15:31:31Z)
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
  この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。 我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。 標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
  論文  参考訳（メタデータ） (2021-07-09T16:04:24Z)
• Sparse Hashing for Scalable Approximate Model Counting: Theory and Practice [36.8421113576893]
  n 変数上の CNF 式 F が与えられたとき、モデルカウントや #SAT の問題は F の満足な割り当ての数を計算することである。 近年,効率的なアルゴリズム技術開発への取り組みが急増している。
  論文  参考訳（メタデータ） (2020-04-30T11:17:26Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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