論文の概要: A New Approach to Post-Quantum Non-Malleability
- arxiv url: http://arxiv.org/abs/2207.05861v1
- Date: Tue, 12 Jul 2022 21:47:39 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-05 09:20:24.355604
- Title: A New Approach to Post-Quantum Non-Malleability
- Title(参考訳): ポスト量子非可視性の新しいアプローチ
- Authors: Xiao Liang, Omkant Pandey, Takashi Yamakawa
- Abstract要約: 量子完全同型暗号と誤りを伴う量子学習の難易度を$mathitpolynomial$で計算した最初の定ラウンドのセキュアなマルチパーティ計算を提供する。
応用として、量子完全同型暗号と誤りを伴う量子学習の難易度を$mathitpolynomial$で計算した。
- 参考スコア(独自算出の注目度): 10.946741355489157
- 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.
As an application, when combined with existing work, our results yield the
first constant-round post-quantum secure multiparty computation 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{polynomial}$ hardness の下で、最初の恒常的な量子後セキュアなマルチパーティ計算が得られる。
関連論文リスト
- Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳(メタデータ) (2024-02-06T15:39:09Z) - A polynomial-time dissipation-based quantum algorithm for solving the ground states of a class of classically hard Hamiltonians [4.500918096201963]
我々は、ハミルトン群の基底状態を解決するための量子アルゴリズムを与える。
我々のアルゴリズムに現れた指数的スピードアップのメカニズムは、オープン量子系における散逸に由来する。
論文 参考訳(メタデータ) (2024-01-25T05:01:02Z) - 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) - On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in
Constant Rounds [14.190389415911833]
我々は、$mathbfNPsubseteq mathbfBQP$ でない限り、$mathbfNP$ に対する定ラウンドのブラックボックスゼロ知識引数は存在しないことを示す。
また、$mathbfNP$ が$mathbfNPsubseteq mathbfBQP$ でない限り、$mathbfNP$ が存在しないことを証明する。
論文 参考訳(メタデータ) (2021-03-20T21:00:13Z) - Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
量子アルゴリズムの設計と回路下界の一般接続を確立する。
我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
論文 参考訳(メタデータ) (2020-12-03T14:03:20Z) - Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。
最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
論文 参考訳(メタデータ) (2020-03-04T07:36:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。