論文の概要: The Round Complexity of Black-Box Post-Quantum Secure Computation

• arxiv url: http://arxiv.org/abs/2502.13830v1
• Date: Wed, 19 Feb 2025 15:45:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-20 14:00:35.083144
• Title: The Round Complexity of Black-Box Post-Quantum Secure Computation
• Title（参考訳）: ブラックボックスポスト量子セキュア計算のラウンド複雑度
• Authors: Rohit Chatterjee, Xiao Liang, Omkant Pandey, Takashi Yamakawa,
• Abstract要約: 量子後状態におけるセキュアマルチパーティ計算(MPC)のラウンド複雑性について検討する。 私たちの焦点は、完全にブラックボックスの設定であり、建設とセキュリティの削減の両方がブラックボックスであることです。 各種の量子後プリミティブを用いて、マルチパーティ設定において、最初のブラックボックス、コンスタントラウンド構成を提案する。
• 参考スコア（独自算出の注目度）: 7.683672647857481
• License:
• Abstract: We study the round complexity of secure multi-party computation (MPC) in the post-quantum regime. Our focus is on the fully black-box setting, where both the construction and security reduction are black-box. Chia, Chung, Liu, and Yamakawa [FOCS'22] demonstrated the infeasibility of achieving standard simulation-based security within constant rounds unless $\mathbf{NP} \subseteq \mathbf{BQP}$. This leaves crucial feasibility questions unresolved. Specifically, it remains unknown whether black-box constructions are achievable within polynomial rounds; also, the existence of constant-round constructions with respect to $\epsilon$-simulation, a relaxed yet useful alternative to standard simulation, remains unestablished. This work provides positive answers. We introduce the first black-box construction for PQ-MPC in polynomial rounds, from the minimal assumption of post-quantum semi-honest oblivious transfers. In the two-party scenario, our construction requires only $\omega(1)$ rounds. These results have already been applied in the oracle separation between classical-communication quantum MPC and $\mathbf{P} = \mathbf{NP}$ in Kretschmer, Qian, and Tal [STOC'25]. As for $\epsilon$-simulation, Chia, Chung, Liang, and Yamakawa [CRYPTO'22] resolved the issue for the two-party setting, leaving the multi-party case open. We complete the picture by presenting the first black-box, constant-round construction in the multi-party setting, instantiable using various standard post-quantum primitives. En route, we obtain a black-box, constant-round post-quantum commitment achieving a weaker version of 1-many non-malleability, from post-quantum one-way functions. Besides its role in our MPC construction, this commitment also reduces the assumption used in the quantum parallel repetition lower bound by Bostanci, Qian, Spooner, and Yuen [STOC'24]. We anticipate further applications in the future.
• Abstract（参考訳）: 量子後状態におけるセキュアマルチパーティ計算(MPC)のラウンド複雑性について検討する。 私たちの焦点は、完全にブラックボックスの設定であり、建設とセキュリティの削減の両方がブラックボックスであることです。 Chia, Chung, Liu, and Yamakawa [FOCS'22] は、$\mathbf{NP} \subseteq \mathbf{BQP}$でない限り、一定のラウンドで標準シミュレーションベースのセキュリティを達成することができないことを示した。 このことは、重要な実現可能性に関する疑問を未解決のまま残している。 具体的には、ブラックボックス構造が多項式ラウンド内で達成可能かどうかは不明であるが、標準シミュレーションの緩和された有用な代替品である$\epsilon$-simulationに関する定数ラウンド構成の存在は、まだ確立されていない。 この研究は肯定的な答えを与える。 多項式ラウンドにおけるPQ-MPCの最初のブラックボックス構成は、量子後半正直な移動の最小限の仮定から導入する。 両者のシナリオでは、我々の構成は$\omega(1)$のラウンドしか必要としない。 これらの結果は Kretschmer, Qian, Tal [STOC'25] における古典通信量子 MPC と $\mathbf{P} = \mathbf{NP}$ のオラクル分離に既に適用されている。 $\epsilon$-simulationについては、Chia、Chung、Liang、および山川(CryPTO'22)が2党設定の問題を解決し、複数党の訴訟は解決した。 様々な量子後プリミティブを用いて、マルチパーティ設定で、最初のブラックボックス、コンスタントラウンドの構成をインスタンス化して、画像を完成させる。 提案手法では,量子後片道関数から1個の非可逆性の弱いバージョンを実現するため,ブラックボックス,定数ラウンドのポスト量子コミットメントを得る。 我々のMPC構築におけるその役割に加えて、このコミットメントは、ボスタンチ、カイアン、スプーナー、ユアン(STOC'24)による量子並列反復の下限で使われる仮定を減少させる。 我々は将来さらなる応用を期待する。

関連論文リスト

• The Black-Box Simulation Barrier Persists in a Fully Quantum World [9.887919546667598]
  我々は、$mathbfBQP$の言語のみが、定ラウンド$textitfully-quantum$ BBZKを許容していることを示す。 量子ゼロ知識の性質を照らし、量子領域で将来のプロトコルを設計するための貴重な洞察を提供する。
  論文  参考訳（メタデータ） (2024-09-10T08:17:17Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。 特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
  論文  参考訳（メタデータ） (2024-02-29T01:35:46Z)
• On black-box separations of quantum digital signatures from pseudorandom states [1.9254132307399263]
  我々は、$textitdoes not$が存在し、量子デジタル署名スキームのブラックボックス構造が存在することを示す。 この結果は,古典署名付き$textitone-time$ secure QDSスキームを記述した森前と山川(2022年)を補完するものである。
  論文  参考訳（メタデータ） (2024-02-13T03:36:35Z)
• On sampling determinantal and Pfaffian point processes on a quantum computer [49.1574468325115]
  DPPは1970年代の量子光学のモデルとしてマッキによって導入された。 ほとんどのアプリケーションはDPPからのサンプリングを必要としており、その量子起源を考えると、古典的なコンピュータでDPPをサンプリングするのは古典的なものよりも簡単かどうか疑問に思うのが自然である。 バニラサンプリングは、各コスト$mathcalO(N3)$と$mathcalO(Nr2)$の2つのステップから構成される。
  論文  参考訳（メタデータ） (2023-05-25T08:43:11Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  浅量子回路の計算能力と古典計算の組合せを包括的に評価する。 いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
  論文  参考訳（メタデータ） (2022-10-12T17:54:02Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。 3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
  論文  参考訳（メタデータ） (2021-08-03T17:49:09Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。 本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
  論文  参考訳（メタデータ） (2021-07-05T17:45:41Z)
• A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Rounds [12.525959293825318]
  我々は,統計音性およびブラックボックス$epsilon$-zero-knowledgeを満たすNPのラウンド・インタラクティブ証明を構築した。 我々の研究の核心は、シミュレーターが悪意のある検証者のコミットメッセージを抽出できる新しい量子巻き戻し技術である。
  論文  参考訳（メタデータ） (2020-11-05T05:40:05Z)
• Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
  古典的アリス(Alice)と量子的ボブ(Quantum Bob)が古典的なチャネルを通してのみ通信できるような設定を考える。 悪質な量子逆数の場合,ブラックボックスシミュレーションを用いた2次元量子関数を実現することは,一般に不可能であることを示す。 我々は、QMA関係Rの古典的量子知識(PoQK)プロトコルを入力として、古典的当事者によって検証可能なRのゼロ知識PoQKを出力するコンパイラを提供する。
  論文  参考訳（メタデータ） (2020-10-15T17:55:31Z)
• Post-Quantum Multi-Party Computation [32.75732860329838]
  我々は、悪質な時間量子敵に対するセキュリティを備えた古典的機能(平易なモデル)のマルチパーティ計算について研究する。 誤差付き学習における超ポリノミカル量子硬度(LWE)とLWEに基づく円形セキュリティ仮定の量子硬度を仮定する。 その過程で、私たちは独立した関心を持つ可能性のある暗号プリミティブを開発します。
  論文  参考訳（メタデータ） (2020-05-23T00:42:52Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。