論文の概要: Pseudorandom Permutations from Random Reversible Circuits
- arxiv url: http://arxiv.org/abs/2404.14648v1
- Date: Tue, 23 Apr 2024 00:50:57 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-24 15:41:14.979052
- Title: Pseudorandom Permutations from Random Reversible Circuits
- Title（参考訳）: ランダム可逆回路からの擬似乱数置換
- Authors: William He, Ryan O'Donnell,
- Abstract要約: 固定された最寄りのアーキテクチャにおいて,各層が$approx n/3$のランダムゲートからなる深さ$n cdot tildeO(k2)$のランダム回路がほぼ$k$の独立な置換をもたらすことを示す。
また、擬似乱数関数からの擬似乱数置換のLuby-Rack-off構成は可逆回路で実装可能であることを示す。
- 参考スコア（独自算出の注目度）: 1.9567015559455132
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: 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 $n \cdot \tilde{O}(k^2)$, with each layer consisting of $\approx n/3$ random gates in a fixed nearest-neighbor architecture, yields almost $k$-wise independent permutations. The main technical component is showing that the Markov chain on $k$-tuples of $n$-bit strings induced by a single random $3$-bit nearest-neighbor gate has spectral gap at least $1/n \cdot \tilde{O}(k)$. This improves on the original work of Gowers [Gowers96], who showed a gap of $1/\mathrm{poly}(n,k)$ for one random gate (with non-neighboring inputs); and, on subsequent work [HMMR05,BH08] improving the gap to $\Omega(1/n^2k)$ in the same setting. From the perspective of cryptography, 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. We also show that the Luby--Rackoff construction of pseudorandom permutations from pseudorandom functions can be implemented with reversible circuits. From this, we make progress on the complexity of the Minimum Reversible Circuit Size Problem (MRCSP), showing that block ciphers of fixed polynomial size are computationally secure against arbitrary polynomial-time adversaries, assuming the existence of one-way functions (OWFs).
- Abstract（参考訳）: 我々は、${0,1\}^n$上の置換の擬似ランダム性特性を、可逆な$$3$-bitゲート($\{0,1\}^3$上の置換)から得られるランダム回路で計算する。
我々の主な結果は深さ$n \cdot \tilde{O}(k^2)$のランダム回路であり、各層は固定された最寄りのアーキテクチャにおいて$\approx n/3$のランダムゲートで構成され、ほぼ$k$の独立な置換が得られることである。
主な技術的構成要素は、$k$-tuples of $n$-bit strings by a single random $3$-bit Near-nebor gate has gap at least $1/n \cdot \tilde{O}(k)$である。
これは、1/\mathrm{poly}(n,k)$が1つのランダムゲート(非隣接入力を持つ)に対して1/\mathrm{poly}(n,k)$のギャップを示していたGowers [Gowers96] の元々の作業を改善し、続く作業 [HMMR05,BH08] では、ギャップを同じ設定で$\Omega(1/n^2k)$に改善した。
暗号の観点では、我々の結果は特に単純で実践的なブロック暗号構造であり、数ラウンドで$k$〜input-outputペアにアクセスする攻撃者に対して、証明可能な統計的セキュリティを提供する。
また、擬似乱数関数からの擬似乱数置換のLuby-Rackoff構成は可逆回路で実装可能であることを示す。
そこで我々は, 最小可逆回路サイズ問題 (MRCSP) の複雑性を推し進め, 一方向関数 (OWF) の存在を前提として, 固定多項式サイズのブロック暗号が任意の多項式時間逆数に対して計算的に安全であることを示す。
関連論文リスト
- 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) - Simple constructions of linear-depth t-designs and pseudorandom unitaries [40.72668922727092]
一様ランダムなユニタリ、すなわちハール測度から引き出されたユニタリは、多くの有用な性質を持つが、効率的に実装することはできない。
$t-設計はハール測度の最初の$tモーメントを再現するランダムユニタリーであり、擬ランダムユニタリー(PRU)はハール測度と計算的に区別できないランダムユニタリーである。
論文 参考訳（メタデータ） (2024-04-19T06:13:02Z) - Crooked indifferentiability of the Feistel Construction [53.572703605492904]
Feistelの構築は擬似乱数置換とブロック暗号を構築するための基本的な技術である。
本稿では, アルゴリズム置換攻撃に対しても, 簡単な構成法が適用可能であることを示す。
論文 参考訳（メタデータ） (2024-04-15T04:29:24Z) - Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
スポンジハッシュは、広く使われている暗号ハッシュアルゴリズムのクラスである。
これまでのところ、不規則な置換は根本的なオープンな問題のままである。
ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要である。
論文 参考訳（メタデータ） (2024-03-07T18:46:58Z) - Classical simulation of peaked shallow quantum circuits [2.6089354079273512]
準ポリノミカルランタイム$nO(logn)$のアルゴリズムについて述べる。
我々のアルゴリズムは、浅い回路の出力確率を、与えられた逆多項式加法誤差の範囲内で推定することができる。
論文 参考訳（メタデータ） (2023-09-15T14:01:13Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳（メタデータ） (2023-05-09T20:53:27Z) - Post-Quantum Security of the Even-Mansour Cipher [14.141778162933013]
Even-Mansour暗号は古典的な攻撃に対して安全である。
偶数マンスールは、自然の「後量子」環境でも安全であることが証明できる。
論文 参考訳（メタデータ） (2021-12-14T16:43:34Z) - On Submodular Contextual Bandits [92.45432756301231]
作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。
Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
論文 参考訳（メタデータ） (2021-12-03T21:42:33Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。