論文の概要: On the (Quantum) Communication Complexity of Secure MPC from a Random Oracle

• arxiv url: http://arxiv.org/abs/2611.04052v1
• Date: Mon, 02 Nov 2026 22:46:56 GMT
• ステータス: 情報取得中
• システム内更新日: 2026-11-04 17:41:15.131425
• Title: On the (Quantum) Communication Complexity of Secure MPC from a Random Oracle
• Title（参考訳）: ランダムOracleからのセキュアMPCの(量子)通信複雑性について
• Abstract要約: 情報理論 MPC ($n$ parties with $t$ corruptions) は、$O(|C| cdot t/(n-t)$オンライン通信を伴う回路$C$を安全に評価することができる。 我々は、$n = O(log )$のとき、次数-2s(内積を含む)の新たな構成で一致する、$(|C|)$の通信下界を示す。 まず、量子通信(および前処理)を用いた情報理論プロトコルは、従来のプロトコルに比べて通信を減少させることができないことを証明します。
• 参考スコア（独自算出の注目度）: 57.20693707878285
• License:
• Abstract: Information-theoretic MPC among $n$ parties with $t$ corruptions can securely evaluate a circuit $C$ with $O(|C| \cdot t/(n-t))$ online communication in the preprocessing model and $O(|C| \cdot t/(n-2t))$ communication in the honest majority setting. Damgård, Larsen and Nielsen (CRYPTO 2019) showed that both communication bounds are tight for inner products. Fully homomorphic encryption and other assumptions known to imply public-key cryptography beat both communication bounds, but the communication complexity with symmetric-key cryptography alone is less understood. For MPC with preprocessing, we prove that the same $Ω(|C| \cdot t/(n-t))$ lower bound holds in the random oracle model, so a random oracle cannot reduce the online communication. For honest majority MPC relative to a random oracle, we present an $Ω(|C|)$ communication lower bound that is matched by a new construction for degree-2 polynomials (including inner products) when $n = O(\log λ)$, beating the information-theoretic bound. We also study quantum MPC. First, we prove that information-theoretic protocols with quantum communication (and preprocessing) cannot reduce communication compared to their classical counterparts. Furthermore, we extend our lower bound for MPC with preprocessing to protocols with a quantum-accessible random oracle, but use only classical communication. In contrast, with both quantum communication and a post-quantum one-way function, we present a simple two-party protocol that evaluates the two-party instance of these circuits with $\mathrm{poly}(λ, \log |C|)$ communication, beating these lower bounds. Finally, such communication savings do not come for free. We prove that there exist circuits $C$ such that every blackbox protocol with $o(|C|)$ quantum communication must perform $Ω(|C|)$ cryptographic operations.
• Abstract（参考訳）: 汚職のある$n$政党間の情報理論的MPCは、$O(|C| \cdot t/(n-t))$前処理モデルにおけるオンライン通信と$O(|C| \cdot t/(n-2t))$コミュニケーションの正直な多数決で$C$を確実に評価することができる。 Damgård氏、Larsen氏、Nielsen氏(CRYPTO 2019)は、両方の通信境界が内部製品にとって厳密であることを示した。 完全同型暗号や公開鍵暗号で知られている仮定は、両方の通信境界を破るが、対称鍵暗号だけでの通信の複雑さは理解されていない。 事前処理を伴うMPCの場合、同じ$Ω(|C| \cdot t/(n-t))$下界がランダムなオラクルモデルに成り立つことが証明されるので、ランダムなオラクルはオンライン通信を減らすことはできない。 ランダムなオラクルに対する正直な多数 MPC に対して、$n = O(\log λ)$ のとき、次数2多項式(内部積を含む)の新たな構成によって一致する$Ω(|C|)$ の通信下界が情報理論境界を破る。 量子MPCも研究している。 まず、量子通信(および前処理)を用いた情報理論プロトコルは、従来のプロトコルに比べて通信を低減できないことを示す。 さらに、MPCの下位境界を、量子アクセス可能なランダムオラクルを持つプロトコルにプリプロセッシングすることで拡張するが、古典的な通信のみを使用する。 これとは対照的に、量子通信と後量子片方向関数の両方で、これらの回路の2パーティのインスタンスを$\mathrm{poly}(λ, \log |C|)$通信で評価し、これらの下位境界を破る単純な2パーティプロトコルを提案する。 最後に、このようなコミュニケーションの節約は無料ではない。 我々は、$o(|C|)$量子通信を持つすべてのブラックボックスプロトコルが$Ω(|C|)$暗号演算を行うように、$C$が存在することを証明している。

関連論文リスト

• A distillation-teleportation protocol for fault-tolerant QRAM [95.99192129224721]
  本稿では,論理量子乱数アクセスメモリ(QRAM)をフォールトトレラント実装するためのプロトコルを提案する。 古典的メモリサイズ2n$をコヒーレントにアクセスするために、我々のプロトコルは、フォールトトレラントな量子リソースをわずか$mathrmpoly(n)$で消費する。
  論文  参考訳（メタデータ） (2025-05-26T17:42:56Z)
• A Quantum Approach For Reducing Communications in Classical Secure Computations with Long Outputs [2.3465488122819123]
  我々は、2つの当事者が長い出力でセキュアな計算を行いたいという古典的な暗号問題について研究する。 本研究では,セキュリティを近似したセキュアな関数サンプリングを実現するために,まず量子暗号プロトコルを設計する。
  論文  参考訳（メタデータ） (2023-10-08T16:07:46Z)
• Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation [77.09836892653176]
  マルコフ決定過程の設定におけるマルチエージェント強化学習について検討した。 本稿では非同期通信が可能な値に基づく証明可能な効率的なアルゴリズムを提案する。 我々は、コラボレーションによってパフォーマンスを改善するために、最小の$Omega(dM)$通信の複雑さが必要であることを示す。
  論文  参考訳（メタデータ） (2023-05-10T20:29:29Z)
• Communication complexity of entanglement assisted multi-party computation [11.820804392113294]
  プレーヤが2ドル、ドットが2ドル、n$が1に適切な情報を伝達する必要がある場合、プレーヤが$n$のマルチパーティ計算問題を考える。 量子プロトコル(複雑性$(n-1)log n$ bits)と古典的プロトコル(複雑性$(n-1)2(log n2$)ビット)を示す。 これは、我々の量子プロトコルが古典的プロトコルよりも厳密に優れていることを示している。
  論文  参考訳（メタデータ） (2023-05-08T03:10:08Z)
• 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)
• Communication Complexity of Private Simultaneous Quantum Messages Protocols [0.609170287691728]
  本稿では、量子通信の利点と、プライベート同時量子メッセージモデルの事前絡み合いについて検討する。 プライバシ条件は,PSQMモデルの通信コストを必然的に増大させることを示す。 また,共有絡み合った状態と共有ランダム文字列を持つPSQMプロトコルの通信複雑性の指数的差を示す。
  論文  参考訳（メタデータ） (2021-05-15T03:08:01Z)
• Fault-tolerant Coding for Quantum Communication [71.206200318454]
  ノイズチャネルの多くの用途でメッセージを確実に送信するために、回路をエンコードしてデコードする。 すべての量子チャネル$T$とすべての$eps>0$に対して、以下に示すゲートエラー確率のしきい値$p(epsilon,T)$が存在し、$C-epsilon$より大きいレートはフォールトトレラント的に達成可能である。 我々の結果は、遠方の量子コンピュータが高レベルのノイズの下で通信する必要があるような、大きな距離での通信やオンチップでの通信に関係している。
  論文  参考訳（メタデータ） (2020-09-15T15:10:50Z)
• Quantum Communication Complexity of Distribution Testing [114.31181206328276]
  2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。 目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。 この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
  論文  参考訳（メタデータ） (2020-06-26T09:05:58Z)
• Communication Cost of Quantum Processes [49.281159740373326]
  分散コンピューティングにおける一般的なシナリオは、リモートコンピュータ上で計算を実行するようサーバに要求するクライアントである。 重要な問題は、所望の計算を指定するのに必要な最小限の通信量を決定することである。 クライアントが選択した量子処理を正確に実行するために、サーバが必要とする(古典的および量子的)通信の総量を分析する。
  論文  参考訳（メタデータ） (2020-02-17T08:51:42Z)

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

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