論文の概要: Pseudorandomness Properties of Random Reversible Circuits

• arxiv url: http://arxiv.org/abs/2502.07159v1
• Date: Tue, 11 Feb 2025 00:54:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-12 14:05:33.647879
• Title: Pseudorandomness Properties of Random Reversible Circuits
• Title（参考訳）: ランダム可逆回路の擬似性特性
• Authors: William Gay, William He, Nicholas Kocurek, Ryan O'Donnell,
• Abstract要約: 固定された2次元近辺アーキテクチャにおいて,各層が$Theta(n)$ランダムゲートからなる深さ$sqrtn cdot tildeO(k3)$のランダム回路により,およそ$k$の独立置換が得られることを示す。 我々の結果は、数ラウンドで$k$input-outputペアにアクセスする攻撃者に対して、証明可能な統計的セキュリティを提供する、特に単純で実践的なブロック暗号構築と見なすことができる。
• 参考スコア（独自算出の注目度）: 1.593690982728631
• License:
• Abstract: Motivated by practical concerns in cryptography, we study pseudorandomness properties of permutations on $\{0,1\}^n$ computed by random circuits made from reversible $3$-bit gates (permutations on $\{0,1\}^3$). Our main result is that a random circuit of depth $\sqrt{n} \cdot \tilde{O}(k^3)$, with each layer consisting of $\Theta(n)$ random gates in a fixed two-dimensional nearest-neighbor architecture, yields approximate $k$-wise independent permutations. Our result can be seen as a particularly simple/practical block cipher construction that gives provable statistical security against attackers with access to $k$~input-output pairs within few rounds. The main technical component of our proof consists of two parts: 1. We show that the Markov chain on $k$-tuples of $n$-bit strings induced by a single random $3$-bit one-dimensional nearest-neighbor gate has spectral gap at least $1/n \cdot \tilde{O}(k)$. Then we infer that a random circuit with layers of random gates in a fixed one-dimensional gate architecture yields approximate $k$-wise independent permutations of $\{0,1\}^n$ in depth $n\cdot \tilde{O}(k^2)$ 2. We show that if the $n$ wires are layed out on a two-dimensional lattice of bits, then repeatedly alternating applications of approximate $k$-wise independent permutations of $\{0,1\}^{\sqrt n}$ to the rows and columns of the lattice yields an approximate $k$-wise independent permutation of $\{0,1\}^n$ in small depth. Our work improves on the original work of Gowers, who showed a gap of $1/\mathrm{poly}(n,k)$ for one random gate (with non-neighboring inputs); and, on subsequent work improving the gap to $\Omega(1/n^2k)$ in the same setting.
• Abstract（参考訳）: 暗号における実用上の懸念から、$${0,1\}^n$上の置換の擬似ランダム性について、可逆な$$3$-bitゲート($$\{0,1\}^3$上の置換)で計算したランダム回路を用いて研究する。 我々の主な結果は、深さ$\sqrt{n} \cdot \tilde{O}(k^3)$のランダム回路であり、固定された2次元近傍のアーキテクチャにおいて、各層が$\Theta(n)$ランダムゲートで構成され、およそ$k$の独立な置換が得られることである。 我々の結果は、数ラウンドで$k$~input-outputペアにアクセスする攻撃者に対して、証明可能な統計的セキュリティを提供する、特に単純で実践的なブロック暗号構築と見なすことができる。 1) 1 つのランダムな 3 ビットの1-次元近傍ゲートによって誘導される$n$-bit 文字列の$k$-tuples 上のマルコフ連鎖が、少なくとも 1/n \cdot \tilde{O}(k)$ のスペクトルギャップを持つことを示す。 すると、固定された一次元ゲートアーキテクチャにおけるランダムゲートの層を持つランダム回路は、$k$ の独立置換を$\{0,1\}^n$ in depth $n\cdot \tilde{O}(k^2)$ 2. とすると、$n$のワイヤがビットの2次元格子上にレイアウトされている場合、$k$ の独立置換を$\{0,1\}^{\sqrt n} の行と列に繰り返し交互に印加すると、その格子は$\{0,1\}^n$ の独立置換を$k$ の独立置換を$\{0,1\}^n$ の小さな深さで行うことを示す。 本研究は,1/\mathrm{poly}(n,k)$を1つのランダムゲート(非隣り合う入力を持つ)に対して有意なギャップを示したGowersのオリジナルの作業を改善するとともに,そのギャップを同じ設定で$\Omega(1/n^2k)$に改善した。

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Incompressibility and spectral gaps of random circuits [2.359282907257055]
  可逆回路と量子回路は、交互群 $mathrmAlt (2n)$ とユニタリ群 $mathrmSU (2n)$ のランダムウォークを形成する。 ランダム可逆回路のギャップは、すべての$tgeq 1$に対して$Omega(n-3)$であり、ランダム量子回路のギャップは$Omega(n-3)$ for $t leq Theta(2n/2)$であることを示す。
  論文  参考訳（メタデータ） (2024-06-11T17:23:16Z)
• Efficient unitary designs and pseudorandom unitaries from permutations [35.66857288673615]
  実測値の最初の2Omega(n)$モーメントと無作為位相によるS(N)$置換の指数和が一致することを示す。 我々の証明の核心は、ランダム行列理論における大次元(大きな=N$)展開と方法の間の概念的接続である。
  論文  参考訳（メタデータ） (2024-04-25T17:08:34Z)
• Pseudorandom Permutations from Random Reversible Circuits [1.9567015559455132]
  固定された最寄りのアーキテクチャにおいて,各層が$approx n/3$のランダムゲートからなる深さ$n cdot tildeO(k2)$のランダム回路がほぼ$k$の独立な置換をもたらすことを示す。 また、擬似乱数関数からの擬似乱数置換のLuby-Rack-off構成は可逆回路で実装可能であることを示す。
  論文  参考訳（メタデータ） (2024-04-23T00:50:57Z)
• On the average-case complexity of learning output distributions of quantum circuits [55.37943886895049]
  統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。 この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
  論文  参考訳（メタデータ） (2023-05-09T20:53:27Z)
• On the moments of random quantum circuits and robust quantum complexity [0.0]
  我々は、ロバスト量子回路の複雑さの増大に新たな低い境界を証明した。 局所ゲートを持つランダム量子回路に対して、$SU(4)$の部分群から引き出された2つの境界を示す。
  論文  参考訳（メタデータ） (2023-03-29T18:06:03Z)
• Random matrices in service of ML footprint: ternary random features with no performance loss [55.30329197651178]
  我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。 3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。 提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
  論文  参考訳（メタデータ） (2021-10-05T09:33:49Z)
• An Algorithm for Reversible Logic Circuit Synthesis Based on Tensor Decomposition [0.0]
  可逆論理合成のためのアルゴリズムを提案する。 写像は階数 ($2n-2$) テンソルのテンソル積と 2 倍の恒等行列のテンソル積と書くことができる。
  論文  参考訳（メタデータ） (2021-07-09T08:18:53Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
  離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。 我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。 次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
  論文  参考訳（メタデータ） (2020-06-02T16:38:36Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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