論文の概要: The Parallel Reversible Pebbling Game: Analyzing the Post-Quantum
Security of iMHFs
- arxiv url: http://arxiv.org/abs/2110.04191v3
- Date: Tue, 11 Oct 2022 20:59:04 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-12 00:54:07.242299
- Title: The Parallel Reversible Pebbling Game: Analyzing the Post-Quantum
Security of iMHFs
- Title（参考訳）: 並列可逆ペブリングゲーム:imhfsの量子後安全性の解析
- Authors: Jeremiah Blocki and Blake Holman and Seunghoon Lee
- Abstract要約: 本稿では,量子コンピューティングにおけるNo-Deletion Theoremによる追加制約を捉える並列可逆ペブブリングゲームを提案する。
我々は、いくつかの重要なグラフの可逆空間時間複雑性を解析するために、新しい可逆ペブブリングゲームを適用した。
- 参考スコア（独自算出の注目度）: 6.305950347749109
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The classical (parallel) black pebbling game is a useful abstraction which
allows us to analyze the resources (space, space-time, cumulative space)
necessary to evaluate a function $f$ with a static data-dependency graph $G$.
Of particular interest in the field of cryptography are data-independent
memory-hard functions $f_{G,H}$ which are defined by a directed acyclic graph
(DAG) $G$ and a cryptographic hash function $H$. The pebbling complexity of the
graph $G$ characterizes the amortized cost of evaluating $f_{G,H}$ multiple
times as well as the total cost to run a brute-force preimage attack over a
fixed domain $\mathcal{X}$, i.e., given $y \in \{0,1\}^*$ find $x \in
\mathcal{X}$ such that $f_{G,H}(x)=y$. While a classical attacker will need to
evaluate the function $f_{G,H}$ at least $m=|\mathcal{X}|$ times a quantum
attacker running Grover's algorithm only requires $\mathcal{O}(\sqrt{m})$
blackbox calls to a quantum circuit $C_{G,H}$ evaluating the function
$f_{G,H}$. Thus, to analyze the cost of a quantum attack it is crucial to
understand the space-time cost (equivalently width times depth) of the quantum
circuit $C_{G,H}$. We first observe that a legal black pebbling strategy for
the graph $G$ does not necessarily imply the existence of a quantum circuit
with comparable complexity -- in contrast to the classical setting where any
efficient pebbling strategy for $G$ corresponds to an algorithm with comparable
complexity evaluating $f_{G,H}$. Motivated by this observation we introduce a
new parallel reversible pebbling game which captures additional restrictions
imposed by the No-Deletion Theorem in Quantum Computing. We apply our new
reversible pebbling game to analyze the reversible space-time complexity of
several important graphs: Line Graphs, Argon2i-A, Argon2i-B, and DRSample. (See
the paper for the full abstract.)
- Abstract（参考訳）: 古典的な(並列の)ブラックペブリングゲームは、静的データ依存グラフ$g$で関数を評価するのに必要なリソース(空間、時空、累積空間)を分析するのに有用な抽象化である。
特に暗号分野における関心は、データに依存しないメモリハード関数$f_{G,H}$であり、これは有向非巡回グラフ(DAG)$G$と暗号ハッシュ関数$H$によって定義される。
例えば、$y \in \{0,1\}^*$を$x \in \mathcal{X}$とすると、$f_{G,H}(x)=y$となる。
古典的攻撃者は関数 $f_{G,H}$ 少なくとも$m=|\mathcal{X}|$倍の時間でGroverのアルゴリズムを実行する量子攻撃者は$\mathcal{O}(\sqrt{m})$ Blackbox call to a quantum circuit $C_{G,H}$ evaluate the function $f_{G,H}$.
したがって、量子攻撃のコストを分析するためには、量子回路$C_{G,H}$の時空間コスト(同じ幅の時間深度)を理解することが不可欠である。
我々はまず、グラフ $g$ の合法的ブラックペブリング戦略は、必ずしも同等の複雑性を持つ量子回路の存在を意味するものではないことを観察する。
本研究の目的は,量子コンピューティングにおけるNo-Deletion Theoremが課す追加の制約を捉える並列可逆ペブブブリングゲームを導入することである。
線形グラフ, Argon2i-A, Argon2i-B, DRSample といった重要なグラフの可逆空間時間複雑性を解析するために, 新たな可逆ペブブブリングゲームを適用した。
(全文は論文を参照)。
関連論文リスト
- Implementation of Continuous-Time Quantum Walk on Sparse Graph [0.0]
連続時間量子ウォーク(CTQW)は、量子コンピューティングにおいて重要な役割を果たす。
CTQWを効率的に実装する方法は難しい問題である。
本稿では,スパースグラフ上でのCTQWの実装について検討する。
論文 参考訳（メタデータ） (2024-08-20T05:20:55Z) - Quantum advantage in zero-error function computation with side information [10.0060346233449]
本稿では,サイド情報を用いたゼロエラー関数計算の問題点について考察する。
Alice and Bob has correlation source $X,Y$ with joint p.m.f. $p_XY(cdot, cdot)$.
単一インスタンスの場合における量子アドバンテージの挙動と、混乱グラフのいくつかのクラスについて検討する。
論文 参考訳（メタデータ） (2024-02-02T16:41:36Z) - Universality of graph homomorphism games and the quantum coloring
problem [0.0]
量子グラフパラメータは、任意の同期非局所ゲームに対する勝利戦略をエンコードすることを示す。
同期ゲームにおける勝利戦略は、関連するグラフカラーゲームに対する勝利戦略に変換することができる。
論文 参考訳（メタデータ） (2023-05-29T14:28:28Z) - On the Unlikelihood of D-Separation [69.62839677485087]
解析的な証拠として、大きなグラフ上では、d-分離は存在が保証されたとしても珍しい現象である。
PCアルゴリズムでは、その最悪ケース保証がスパースグラフで失敗することが知られているが、平均ケースでも同じことが言える。
UniformSGSでは、既存のエッジに対してランニング時間が指数的であることが知られているが、平均的な場合、それは既存のほとんどのエッジにおいても期待されるランニング時間であることを示す。
論文 参考訳（メタデータ） (2023-03-10T00:11:18Z) - From Bit-Parallelism to Quantum String Matching for Labelled Graphs [0.0]
二次時間で解ける多くの問題は、ビットパラレルのスピードアップが$w$で、$w$はコンピュータワードサイズである。
このような制限されたグラフの族上の単純なビット並列アルゴリズムは、現実的な量子アルゴリズムに変換可能であることを示す。
論文 参考訳（メタデータ） (2023-02-06T15:14:34Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Beyond the Berry Phase: Extrinsic Geometry of Quantum States [77.34726150561087]
状態の量子多様体のすべての性質がゲージ不変のバーグマンによって完全に記述されることを示す。
偏光理論への我々の結果の即時適用について述べる。
論文 参考訳（メタデータ） (2022-05-30T18:01:34Z) - Quantum double aspects of surface code models [77.34726150561087]
基礎となる量子double $D(G)$対称性を持つ正方格子上でのフォールトトレラント量子コンピューティングの北エフモデルを再検討する。
有限次元ホップ代数$H$に基づいて、我々の構成がどのように$D(H)$モデルに一般化するかを示す。
論文 参考訳（メタデータ） (2021-06-25T17:03:38Z) - Quantum speedups for dynamic programming on $n$-dimensional lattice
graphs [0.11470070927586015]
複雑性を$widetilde O(T_Dn)$で表すと、$T_D D+1$となる。
最もよく知られている古典的アルゴリズムは $textpoly(m,n)log n T_Dn$ であるが、量子アルゴリズムの時間複雑性は $textpoly(m,n)log n T_Dn$ である。
論文 参考訳（メタデータ） (2021-04-29T14:50:03Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。