論文の概要: On the Complexity of Symmetric Boolean Functions in Multiparty Private Simultaneous Messages
- arxiv url: http://arxiv.org/abs/2610.21216v1
- Date: Thu, 15 Oct 2026 04:07:18 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-16 19:13:16.174227
- Title: On the Complexity of Symmetric Boolean Functions in Multiparty Private Simultaneous Messages
- Title（参考訳）: 多人数プライベートメッセージにおける対称性ブール関数の複雑さについて
- Abstract要約: すべての対称ブール関数に対して全通信$widetildeO(n3/2)$の完全プライベートPSMプロトコルを構築する。
また、サポートプライバシというより弱い概念も検討しています。
- 参考スコア（独自算出の注目度）: 2.5175734363501907
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Multiparty Private Simultaneous Messages (PSM), also known as Decomposable Randomized Encoding (DRE) or information-theoretic garbling, is a model for non-interactive secure computation. Each party encodes its input using shared randomness and sends a message to an evaluator who does not know that randomness. The evaluator must recover the function output without learning anything else about the inputs. Perfect privacy requires identical transcript distributions on inputs with the same output. We also study the weaker notion of support privacy, which requires only that these distributions have the same support. We study the communication complexity of symmetric Boolean functions when each of the $n$ parties holds one input bit. Lower bounds. We prove a superlinear lower bound for support-private PSM protocols computing $OR_n$. Our technique gives $Ω(n\log n)$ lower bounds for $MAJ_n$ and $EMAJ_n$ (with even $n$), and an $Ω(n\log q)$ lower bound for $MOD_q$ when $q\leq(1-c)n$ for a fixed constant $c>0$. Upper bounds. We construct perfectly private PSM protocols of total communication $\widetilde{O}(n^{3/2})$ for every symmetric Boolean function, improving on the known quadratic bound. For $MAJ_n$, known branching-program constructions yield an upper bound of $O(n\log^3 n\log\log n)$. For $EMAJ_n$ and $MOD_q$ with prime $q$, the lower bounds are tight up to constant factors in the stated regimes. Under support privacy, we obtain $\widetilde{O}(n)$ communication for every symmetric Boolean function. Earlier lower-bound techniques of Ball et al. (ITCS 2020) yield only trivial linear bounds for symmetric Boolean functions. Concurrent and independent work by Holmgren and Wu proves a $ω(n)$ lower bound for $OR_n$ using the same combinatorial core. Both works used AI assistance.
- Abstract（参考訳）: マルチパーティ・プライベート同時メッセージ(英: Multiparty Private Simultaneous Messages、PSM)は、非インタラクティブなセキュアな計算のモデルである。
各パーティは、その入力を共有ランダム性を使ってエンコードし、そのランダム性を知らない評価者にメッセージを送信する。
評価者は入力について何も学ばずに関数出力を回復しなければならない。
完全なプライバシは、同じ出力を持つ入力に対して、同じ書き起こしの配布を必要とする。
また、サポートプライバシというより弱い概念も検討しています。
対称ブール関数の通信複雑性について、各$n$パーティが1ビットの入力ビットを持つときに検討する。
下限。
サポートプライベートなPSMプロトコルを$OR_n$で計算する際の超線形な下限を証明します。
我々の手法は、$MAJ_n$に対して$Ω(n\log n)$low boundsと$EMAJ_n$($n$まで)を与え、$Ω(n\log q)$ lower bound for $MOD_q$ if $q\leq(1-c)n$ for a fixed constant $c>0$を与える。
上界。
我々は、すべての対称ブール関数に対して、全通信$\widetilde{O}(n^{3/2})$の完全プライベートなPSMプロトコルを構築し、既知の二次境界を改善する。
MAJ_n$の場合、既知の分岐プログラムの構成は$O(n\log^3 n\log n)$となる。
素数$q$の$EMAJ_n$と$MOD_q$の場合、下限は記述された規則の定数要素に固まる。
サポートプライバシの下では、すべての対称ブール関数に対する$\widetilde{O}(n)$通信を得る。
Ball et al (ITCS 2020) の初期の下界の手法は対称ブール関数に対して自明な線型境界しか得られない。
Holmgren と Wu の同時かつ独立な研究は、同じ組合せコアを使って$OR_n$ の $ω(n)$ 以下の境界を証明している。
どちらの作品もAIを利用した。
関連論文リスト
- Characterizing Quantum Advantage for Generalizations of the Boolean Hidden Matching Problem [5.457853441330696]
本稿では,$f$-Boolean Hidden 分割問題の一方的な通信複雑性について検討する。
古典的および量子的通信境界を$f$-Boolean Hidden Partitionに対して確立する。
論文 参考訳（メタデータ） (2026-10-05T17:48:13Z) - Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma [70.99943094379263]
有界ラディウス系におけるスパース半定値プログラムに対する最初の準時間古典的解法を与える。
我々の主な技術的貢献は、ハミルトンのギブス状態を同時に表す古典的な手続きである。
論文 参考訳（メタデータ） (2026-09-30T17:51:21Z) - Exponential lower bounds for low-degree strategies in position-based quantum cryptography [0.764671395172401]
非局所量子計算 (NLQC) は、2つの遠隔操作者による2部単位のU_AB$の実装に基づいている。
ユニタリな$U_AB$が存在するかどうかを知ることは、大きなオープンな問題である。
このような指数的下界は、位置ベースの量子暗号のセキュリティに不可欠である。
論文 参考訳（メタデータ） (2026-09-28T16:43:48Z) - Improved lower bounds for decomposable randomized encoding [1.4724626819957034]
関数 $f$ に対する分解可能なランダム化符号化 (DRE) は、個々の入力をローカルにエンコードする$n$を許容する。
OR に対する最初の超線型下界を証明し、より一般的にはすべての非周期対称函数に対して証明する。
論文 参考訳（メタデータ） (2026-09-16T02:17:11Z) - Ordered-Angle Coding for Exact Multiuser Unanimity Testing [0.0]
我々は、シリアル量子アーキテクチャにおいて、$n$変換のみのユーザ間でバイナリユニニミティテストのための順序角符号化を導入する。
加法的代数にはベルの絡み合いは必要ないが、すべての正直な試行において、旅行者は局所的に極大に混合される。
論文 参考訳（メタデータ） (2026-09-04T18:28:01Z) - Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
Lag $j$はスケール$r_j$の予測に影響を与え、$n_T,j=T-j+1$の予測ラウンドに入る。
すべての要約可能なエンベロープに対して、局所化された混合は$cR_T(r)leq C_T(r)$を証明する。
指数関数やエンベロープの場合、有限サンプル条件の下では、トープリッツ・デサインの逆は$cR_T(r)geq c_T(r)$である。
論文 参考訳（メタデータ） (2026-08-27T01:31:46Z) - Quantum Search With Generalized Wildcards [0.4310167974376404]
我々は、コスト$O(sqrtn log n)$の量子アルゴリズムと、ほぼ一致する$Omega(sqrtn)$の低い境界を示す。
以下に示すように、$calQ$が有界サイズセット、連続ブロック、プレフィックス、フルセットのみである場合に、ほぼタイトなバウンダリを表示する。
論文 参考訳（メタデータ） (2025-11-06T18:55:05Z) - The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。
目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
論文 参考訳（メタデータ） (2020-09-21T04:13:34Z) - 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) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。
同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文 参考訳（メタデータ） (2020-02-09T03:39:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。