論文の概要: Quantum secure non-malleable-extractors
- arxiv url: http://arxiv.org/abs/2109.03097v4
- Date: Sun, 28 May 2023 21:38:46 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-31 04:48:40.779526
- Title: Quantum secure non-malleable-extractors
- Title（参考訳）: 量子安全な非可逆抽出器
- Authors: Naresh Goud Boddu, Rahul Jain, Upendra Kapshikar
- Abstract要約: 我々はいくつかの明示的な量子安全な非可逆抽出器を構築した。
すべての量子安全な非可算抽出器は、Chattopadhyay, Goyal, Li による構成に基づいている。
- 参考スコア（独自算出の注目度）: 5.833272638548153
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We construct several explicit quantum secure non-malleable-extractors. All
the quantum secure non-malleable-extractors we construct are based on the
constructions by Chattopadhyay, Goyal and Li [2015] and Cohen [2015].
1) We construct the first explicit quantum secure non-malleable-extractor for
(source) min-entropy $k \geq \textsf{poly}\left(\log \left( \frac{n}{\epsilon}
\right)\right)$ ($n$ is the length of the source and $\epsilon$ is the error
parameter). Previously Aggarwal, Chung, Lin, and Vidick [2019] have shown that
the inner-product based non-malleable-extractor proposed by Li [2012] is
quantum secure, however it required linear (in $n$) min-entropy and seed
length.
Using the connection between non-malleable-extractors and privacy
amplification (established first in the quantum setting by Cohen and Vidick
[2017]), we get a $2$-round privacy amplification protocol that is secure
against active quantum adversaries with communication $\textsf{poly}\left(\log
\left( \frac{n}{\epsilon} \right)\right)$, exponentially improving upon the
linear communication required by the protocol due to [2019].
2) We construct an explicit quantum secure $2$-source non-malleable-extractor
for min-entropy $k \geq n- n^{\Omega(1)}$, with an output of size
$n^{\Omega(1)}$ and error $2^{- n^{\Omega(1)}}$.
3) We also study their natural extensions when the tampering of the inputs is
performed $t$-times. We construct explicit quantum secure
$t$-non-malleable-extractors for both seeded ($t=d^{\Omega(1)}$) as well as
$2$-source case ($t=n^{\Omega(1)}$).
- Abstract（参考訳）: 我々は、いくつかの明示的な量子セキュアな非可算抽出器を構成する。
私たちが構築した量子安全な非可算抽出子は、Chattopadhyay, Goyal and Li [2015] と Cohen [2015] による構成に基づいている。
1) (ソース) min-entropy $k \geq \textsf{poly}\left(\log \left( \frac{n}{\epsilon} \right)\right)$ (n$ はソースの長さであり、$\epsilon$ はエラーパラメータである)。
これまでaggarwal, chung, lin, vidick [2019] は、li [2012] が提案した内積ベースの非可算抽出器は量子安定であることを示したが、それは線形(n$)のミンエントロピーと種子長を必要とした。
非可算抽出元とプライバシ増幅(cohen and vidick [2017] による量子設定で最初に確立された)の接続を使って、[2019] のためにプロトコルが要求する線形通信によって指数関数的に改善される、[2019] による通信$\textsf{poly}\left(\log \left( \frac{n}{\epsilon} \right)\right)$ でアクティブな量子敵に対してセキュアな、2ドルのプライバシ増幅プロトコルが得られる。
2) ミンエントロピー$k \geq n-n^{\Omega(1)}$に対して、明示的な量子セキュアな2$2-ソース非可換抽出器を構築し、大きさが$n^{\Omega(1)}$と誤差が$2^{-n^{\Omega(1)}}$とする。
3) 入力の改ざんが$t$-times で行われる場合の自然拡張についても検討した。
我々は、シードされた(t=d^{\Omega(1)}$)および2$ソースケース(t=n^{\Omega(1)}$)に対して、明示的な量子セキュアな$t$-非可算抽出器を構築する。
関連論文リスト
- On estimating the trace of quantum state powers [2.637436382971936]
量子状態のトレースを推定する計算複雑性を、$n$-qubit混合量子状態$rho$に対して$texttr(rhoq)$で調べる。
我々の高速化は、正のパワー関数の計算可能な一様近似を量子特異値変換に効率よく導入することで達成される。
論文 参考訳（メタデータ） (2024-10-17T13:57:13Z) - Linear gate bounds against natural functions for position-verification [0.0]
量子位置検証スキームは、証明者の空間的位置を検証しようとする。
我々は、$f$-routing(英語版)と$f$-BB84(英語版)として知られる2つのよく研究された位置検証スキームを考える。
論文 参考訳（メタデータ） (2024-02-28T19:00:10Z) - Dimension Independent Disentanglers from Unentanglement and Applications [55.86191108738564]
両部非絡み込み入力から次元独立なk-パーティイトディジアンタングル(類似)チャネルを構築する。
NEXP を捉えるためには、$| psi rangle = sqrta | sqrt1-a | psi_+ rangle という形の非負の振幅を持つのに十分であることを示す。
論文 参考訳（メタデータ） (2024-02-23T12:22:03Z) - The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。
すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
論文 参考訳（メタデータ） (2022-09-04T10:01:39Z) - A Law of Robustness beyond Isoperimetry [84.33752026418045]
我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。
次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。
我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
論文 参考訳（メタデータ） (2022-02-23T16:10:23Z) - A direct product theorem for quantum communication complexity with
applications to device-independent cryptography [6.891238879512672]
我々は、$l$プレーヤの入力集合にまたがる分布である$p$に対して、任意の絡み合い支援量子通信プロトコルの成功確率は、$n$で指数関数的に低下することを示した。
また、デバイスが情報を漏らさないという仮定なしに、デバイス非依存(DI)量子暗号が可能であることも示している。
論文 参考訳（メタデータ） (2021-06-08T12:52:10Z) - 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) - 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) - Quantum Differentially Private Sparse Regression Learning [132.1981461292324]
我々は、スパース回帰問題を解くために、効率的な量子微分プライベート(QDP)ラッソ推定器を考案する。
最後に、QDP Lasso はプライバシー保証付きで $tildeO(N-2/3)$ に近い最適ユーティリティを実現していることを示す。
論文 参考訳（メタデータ） (2020-07-23T10:50:42Z) - Epsilon-nets, unitary designs and random quantum circuits [0.11719282046304676]
エプシロンネット(Epsilon-nets)は、量子情報や量子コンピューティングにおける多くの応用に関連するユニタリ演算の概念である。
固定された$d$に対して、$delta$-approx $t$-expanders を構成するユニタリが $epsilon$-nets for $tsimeqfracd5/2epsilon$ および $delta=left(fracepsilon3/2dright)d2$ となることを証明している。
近似tdesign が生成可能であることを示す。
論文 参考訳（メタデータ） (2020-07-21T15:16:28Z) - Capacity Approaching Coding for Low Noise Interactive Quantum
Communication, Part I: Large Alphabets [15.078027648304115]
ノイズの多いチャネル上での双方向の対話型量子通信を実現する際の問題点を考察する。
$mathrmpoly(n)$ sizeアルファベット上のノイズのないquditチャネルの場合、主な結果は2-theta(nepsilon)$未満の確率で失敗するシミュレーション手法である。
我々は、$sqrtepsilon$項の定数係数まで最適であると推測する。
論文 参考訳（メタデータ） (2020-01-09T02:48:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。