論文の概要: A New Approach to Post-Quantum Non-Malleability
- arxiv url: http://arxiv.org/abs/2207.05861v3
- Date: Sat, 4 Nov 2023 06:29:10 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-08 01:39:54.734117
- Title: A New Approach to Post-Quantum Non-Malleability
- Title（参考訳）: ポスト量子非可視性の新しいアプローチ
- Authors: Xiao Liang, Omkant Pandey, Takashi Yamakawa
- Abstract要約: 我々は、最初の$mathitconstant$-$mathitround$のポスト量子非有理コミットメントの構築を提供する。
コミットメントに関して、非適合性の標準概念を達成します。
- 参考スコア（独自算出の注目度）: 8.859667450008452
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: We provide the first $\mathit{constant}$-$\mathit{round}$ construction of
post-quantum non-malleable commitments under the minimal assumption that
$\mathit{post}$-$\mathit{quantum}$ $\mathit{one}$-$\mathit{way}$
$\mathit{functions}$ exist. We achieve the standard notion of non-malleability
with respect to commitments. Prior constructions required
$\Omega(\log^*\lambda)$ rounds under the same assumption.
We achieve our results through a new technique for constant-round
non-malleable commitments which is easier to use in the post-quantum setting.
The technique also yields an almost elementary proof of security for
constant-round non-malleable commitments in the classical setting, which may be
of independent interest.
When combined with existing work, our results yield the first constant-round
quantum-secure multiparty computation for both classical and quantum
functionalities $\mathit{in}$ $\mathit{the}$ $\mathit{plain}$ $\mathit{model}$,
under the $\mathit{polynomial}$ hardness of quantum fully-homomorphic
encryption and quantum learning with errors.
- Abstract（参考訳）: 我々は、最初の$\mathit{constant}$-$\mathit{round}$ が、$\mathit{post}$-$\mathit{quantum}$$$\mathit{one}$-$$\mathit{way}$$$$\mathit{functions}$という最小限の仮定の下で、ポスト量子化後の非可算コミットメントの構成を提供する。
コミットメントに関して、非適合性の標準概念を達成する。
以前の構成では同じ仮定で$\Omega(\log^*\lambda)$ラウンドが必要だった。
我々は,ポスト量子環境において使用しやすい非可算コミットメントのための新しい手法により,結果を得る。
この手法はまた、古典的設定において、一定周期の非可算なコミットメントに対するセキュリティのほぼ初歩的な証明を与える。
既存の研究と組み合わせると、我々の結果は古典関数と量子関数の両方に対して最初の定ラウンドの量子セキュアなマルチパーティ計算($\mathit{in}$ $\mathit{the}$ $\mathit{plain}$ $\mathit{model}$, $\mathit{polynomial}$ hardness of quantum full-homomorphic encryption and quantum learning with error)が得られる。
関連論文リスト
- Slow Mixing of Quantum Gibbs Samplers [47.373245682678515]
一般化されたボトルネック補題を用いて、これらのツールの量子一般化を示す。
この補題は、古典的なハミング距離に類似する距離の量子測度に焦点を当てるが、一意に量子原理に根ざしている。
サブ線形障壁でさえも、ファインマン・カック法を用いて古典的から量子的なものを持ち上げて、厳密な下界の$T_mathrmmix = 2Omega(nalpha)$を確立する。
論文 参考訳（メタデータ） (2024-11-06T22:51:27Z) - Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth [8.66267734067296]
制限しきい値関数を演算する境界を持つ定数深さ回路のクラスについて検討する。
十分大きな$mathsfbPTFC0[k]$の場合、$mathsfbPTFC0[k]は$mathsfTC0[k]を含む。
論文 参考訳（メタデータ） (2024-08-29T09:40:55Z) - The $φ^n$ trajectory bootstrap [1.8855270809505869]
我々は、$langlephinrangle$ または $langle(iphi)nrangle$ の非整数 $n$ 結果が、波動関数アプローチの値と一致することを示す。
$mathcalPT$不変の場合、$langle(iphi)nrangle$と非整数$n$の存在は、非整数パワーで非エルミート理論をブートストラップすることができる。
論文 参考訳（メタデータ） (2024-02-08T16:09:06Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower
bounds [1.3927943269211591]
本研究は、$mathsfPH$の量子検証に基づく3つの一般化を研究する。
まず、[GSSSY22] から、崩壊定理と$mathsfQCPH$に対するカルプ・リプトンの定理を含むいくつかの開問題を解く。
我々は、$mathsfpureQPH$に対する一方の誤り低減と、これらの量子変量$mathsfPH$に関する最初の境界を示す。
論文 参考訳（メタデータ） (2024-01-03T09:12:25Z) - Parity vs. AC0 with simple quantum preprocessing [0.0]
我々は、$mathsfAC0$が$mathsfQNC0$回路の測定結果に作用するハイブリッド回路モデルについて検討する。
私たちは、$mathsfQNC0$が、タスクの検索とサンプリングに驚くほど強力なのに対して、その出力のグローバルな相関において、そのパワーは"ロックアウト"されていることに気付きました。
論文 参考訳（メタデータ） (2023-11-22T20:27:05Z) - Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。
我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
論文 参考訳（メタデータ） (2022-07-28T17:50:53Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
量子アルゴリズムの設計と回路下界の一般接続を確立する。
我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
論文 参考訳（メタデータ） (2020-12-03T14:03:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。