論文の概要: Commitments are equivalent to one-way state generators
- arxiv url: http://arxiv.org/abs/2404.03220v2
- Date: Wed, 17 Apr 2024 10:29:25 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-18 18:31:46.742348
- Title: Commitments are equivalent to one-way state generators
- Title(参考訳): コミットは一方通行のステートジェネレータと等価です
- Authors: Rishabh Batra, Rahul Jain,
- Abstract要約: ワンウェイ状態発生器 (OWSG) は古典的なワンウェイ関数の自然な量子アナログである。
我々は、$Oleft(fracnlog(n)right)$-copy OWSGs が $poly(n)$-copy OWSG および量子コミットメントに等しいことを示す。
- 参考スコア(独自算出の注目度): 5.088702935364181
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: One-way state generators (OWSG) are natural quantum analogs to classical one-way functions. We show that $O\left(\frac{n}{\log(n)}\right)$-copy OWSGs ($n$ represents the input length) are equivalent to $poly(n)$-copy OWSG and to quantum commitments. Since known results show that $o\left(\frac{n}{\log(n)}\right)$-copy OWSG cannot imply commitments, this shows that $O\left(\frac{n}{\log(n)}\right)$-copy OWSGs are the weakest OWSGs from which we can get commitments (and hence much of quantum cryptography). Our construction follows along the lines of H\r{a}stad, Impagliazzo, Levin and Luby [HILL], who obtained classical pseudorandom generators (PRG) from classical one-way functions (OWF), however with crucial modifications. Our construction, when applied to the classical case, provides an alternative to the construction provided by [HILL]. Since we do not argue conditioned on the output of the one-way function, our construction and analysis are arguably simpler and may be of independent interest.
- Abstract(参考訳): ワンウェイ状態発生器 (OWSG) は古典的なワンウェイ関数の自然な量子アナログである。
我々は、$O\left(\frac{n}{\log(n)}\right)$-copy OWSGs(n$は入力長を表す)が$poly(n)$-copy OWSGと等価であり、量子コミットメントに等しいことを示す。
既知の結果は、$o\left(\frac{n}{\log(n)}\right)$-copy OWSG がコミットメントを示唆できないことを示しているので、$O\left(\frac{n}{\log(n)}\right)$-copy OWSG がコミットメントを得ることのできる最も弱い OWSG であることを示している。
H\r{a}stad, Impagliazzo, Levin, Luby [HILL] は古典的片方向関数 (OWF) から古典的擬似ランダム生成子 (PRG) を得たが、重要な修正を加えた。
我々の構成は、古典的な場合に適用すると、[HILL]が提供する構成の代替となる。
片方向関数の出力に条件づけられた議論はしないので、我々の構成と解析は間違いなく単純であり、独立した関心を持つかもしれない。
関連論文リスト
- Quantum One-Wayness of the Single-Round Sponge with Invertible
Permutations [55.2480439325792]
スポンジハッシュ(Spnge hashing)は、現在の国際ハッシュ関数標準SHA-3の基盤となる暗号ハッシュアルゴリズムの新たなクラスである。
ウンルーが提唱した「二重側ゼロ探索」予想を証明する。
また、ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要であることも示している。
論文 参考訳(メタデータ) (2024-03-07T18:46:58Z) - Deterministic identification over channels with finite output: a
dimensional perspective on superlinear rates [53.66705737169404]
有限出力であるが任意の入力アルファベットを持つメモリレスチャネルに対する一般性の問題を考える。
主な発見は、それによって特定可能なメッセージの最大数は、ブロック長が$n$の2R,nlog n$と超指数的にスケールすることです。
結果は、有限次元の出力量子系を持つ古典量子チャネルに直接一般化することが示されている。
論文 参考訳(メタデータ) (2024-02-14T11:59:30Z) - A Note on Output Length of One-Way State Generators and EFIs [8.988985347178424]
本研究では,一方向状態発生器(OWSG)の出力長,より弱い変種,EFIの出力長について検討する。
我々は、$O(log lambda)$-qubit出力を持つOWSGは存在しないことを示した。
また、$O(log lambda)$-qubit EFIが存在しないことも証明します。
論文 参考訳(メタデータ) (2023-12-26T12:27:10Z) - On the Computational Hardness of Quantum One-Wayness [3.5301990305960222]
Pseudorandom状態は、$n$bitsを$log n + 1$ qubitsに圧縮する。
一方向のステートジェネレータは、古典的に$rmPP$oracleにアクセスできる量子アルゴリズムによって破壊することができる。
我々の結果の興味深い意味は、すべての$t(n) = o(n/log n)$に対して、$t(n)$-copy 1-way状態生成器が無条件に存在することである。
論文 参考訳(メタデータ) (2023-12-13T18:56:03Z) - Ground State Preparation via Qubitization [0.0]
量子コンピュータ上でハミルトンの$H$の基底状態を作成するためのプロトコルについて述べる。
この方法は、いわゆる「量子化」の方法であるローとチュアンに依存している。
本稿では, 横フィールドイジングモデルと単一キュービット玩具モデルという2つのモデルについて述べる。
論文 参考訳(メタデータ) (2023-06-26T18:20:48Z) - Spacetime-Efficient Low-Depth Quantum State Preparation with
Applications [93.56766264306764]
任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。
我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
論文 参考訳(メタデータ) (2023-03-03T18:23:20Z) - One-Wayness in Quantum Cryptography [9.09597656634436]
本研究では,一方向関数の量子アナログである一方向状態発生器(OWSG)の特性について検討する。
量子デジタル署名はOWSGと等価であることを示す。
我々は、秘密に検証可能で統計的に可逆なOWSGと呼ばれるOWSGの変種を紹介する。
論文 参考訳(メタデータ) (2022-10-07T08:21:21Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳(メタデータ) (2022-06-07T18:00:01Z) - Quantum secure non-malleable-extractors [5.833272638548153]
我々はいくつかの明示的な量子安全な非可逆抽出器を構築した。
すべての量子安全な非可算抽出器は、Chattopadhyay, Goyal, Li による構成に基づいている。
論文 参考訳(メタデータ) (2021-09-07T13:56:24Z) - Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
計算・比較プログラム(Computer-and-compare program)として知られる回避関数のクラスに対する量子コピー保護スキームを導入する。
我々は,量子乱数オラクルモデル(QROM)において,完全悪意のある敵に対する非自明なセキュリティを実現することを証明した。
補完的な結果として、「セキュアソフトウェアリース」という,ソフトウェア保護の概念の弱さが示される。
論文 参考訳(メタデータ) (2020-09-29T08:41:53Z) - Quantum Differentially Private Sparse Regression Learning [132.1981461292324]
我々は、スパース回帰問題を解くために、効率的な量子微分プライベート(QDP)ラッソ推定器を考案する。
最後に、QDP Lasso はプライバシー保証付きで $tildeO(N-2/3)$ に近い最適ユーティリティを実現していることを示す。
論文 参考訳(メタデータ) (2020-07-23T10:50:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。