論文の概要: SLIDE: Shuffle Shamir Secret Shares Uniformly with Linear Online Communication and Guaranteed Output Delivery
- arxiv url: http://arxiv.org/abs/2608.27129v1
- Date: Thu, 27 Aug 2026 13:44:17 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-28 16:30:58.421659
- Title: SLIDE: Shuffle Shamir Secret Shares Uniformly with Linear Online Communication and Guaranteed Output Delivery
- Title（参考訳）: SLIDE: Shuffle Shamirシークレットがリニアオンラインコミュニケーションと保証されたアウトプット配信を均一に共有
- Abstract要約: シャミル秘密共有のための2つの新しいシャッフルプロトコルを提案する。
第1のプロトコルは具体的に効率的で、第2のプロトコルはよく知られた$O(nml)$オンライン通信と$O(n)$ラウンドを達成する。
実験は、事前の作業よりもオンラインの効率と総コストを大幅に改善したことを示している。
- 参考スコア（独自算出の注目度）: 7.706875592040788
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We revisit shuffle protocols for Shamir secret sharing. Existing constructions either produce non-uniform shuffles or incur high communication and round complexity, sometimes exponential in the number of parties. We propose two new shuffle protocols that achieve uniform shuffling with communication complexity $O((k+l)n^2m\log m/\log k)$ for an $m$-by-$l$ matrix shared among $n$ parties, where $k\leq m$ is a tunable parameter. The first protocol is concretely efficient, while the second achieves the best-known $O(nml)$ online communication and $O(n)$ rounds. Experiments show significant improvements in online efficiency and total cost over prior work. Our key technical ingredient is a novel permutation sharing technique that represents permutations using smaller permutation matrices, making their application significantly more efficient. The first protocol applies independent secret permutations sequentially, while the second builds on shuffle correlation to achieve optimal online complexity. We further extend shuffle correlation to support guaranteed output delivery with linear online communication, yielding SLIDE, the first protocol to achieve both $O(nml)$ online communication and guaranteed output delivery. Our constructions rely only on basic Shamir secret sharing over any field of size greater than $n$. As shuffling is a fundamental primitive for MPC tasks such as sorting and oblivious data structures, our results enable more efficient and scalable secure computation in practice.
- Abstract（参考訳）: シャミール秘密共有のためのシャッフルプロトコルを再検討する。
既存の構成では、一様でないシャッフルを発生させるか、高いコミュニケーションと円周の複雑さを発生させる。
通信複雑性と一様シャッフルを実現する2つの新しいシャッフルプロトコルについて提案する。$O((k+l)n^2m\log m/\log k)$ for a $m$-by-$l$ matrix shared with $n$ parties, where $k\leq m$ is a tunable parameters。
第1のプロトコルは具体的に効率的で、第2のプロトコルは最もよく知られている$O(nml)$オンライン通信と$O(n)$ラウンドを達成する。
実験は、事前の作業よりもオンラインの効率と総コストを大幅に改善したことを示している。
我々の重要な技術要素は、より小さい置換行列を用いた置換を表現する新しい置換共有技術であり、それらの応用をはるかに効率的にする。
第1のプロトコルは独立した秘密置換を順次適用し、第2のプロトコルはシャッフル相関に基づいて最適なオンライン複雑性を実現する。
我々はさらにシャッフル相関を拡張し、線形オンライン通信による保証出力配信をサポートし、$O(nml)$オンライン通信と保証出力配信の両方を達成する最初のプロトコルであるSLIDEを提供する。
私たちの構築物は、$n$以上のあらゆる大きさのフィールドについて、基本的なShamirの秘密共有にのみ依存しています。
シャッフルはデータ構造をソートしたり隠したりといったMPCタスクの基本的なプリミティブであるため,本研究の結果はより効率的でスケーラブルなセキュアな計算を実現することができる。
関連論文リスト
- Single-Shuffle Full-Open Card-Based Protocols for Any Function [4.039245878626346]
textitsingle-shuffle full-open protocolは、カードベースのセキュアな計算の最小限のモデルである。
我々は、すべての関数が単一シャッフルのフルオープンプロトコルを持つことを初めて証明する。
論文 参考訳（メタデータ） (2025-10-20T08:52:23Z) - Communication-Efficient Publication of Sparse Vectors under Differential Privacy [2.9123921488295768]
スパースベクトルから集約された行列をパブリッシュするための微分プライベートアルゴリズムを提案する。
我々のアルゴリズムは、このコストを$O(varepsilon m)$に大幅に削減し、$varepsilon$はプライバシー予算である。
理論的には,本手法がランダム化応答と同一の結果をもたらすことを証明している。
論文 参考訳（メタデータ） (2025-06-25T08:25:46Z) - Breaking Free: Efficient Multi-Party Private Set Union Without Non-Collusion Assumptions [5.030459935922802]
マルチパーティ・プライベート・セット・ユニオン(MPSU)プロトコルにより、$m$$(m > 2)$パーティがそれぞれセットを保持し、集合のユニオンをまとめて計算することができる。
本稿では,標準半高次モデルにおいて,暗黙の転送と対称鍵技術に基づく最初のMPSUプロトコルを提案する。
当社のプロトコルでは,それぞれ220ドルのアイテムをセットした3つのパーティに対して,オンラインフェーズで4.4ドル秒しか必要としない。
論文 参考訳（メタデータ） (2024-06-11T07:10:45Z) - Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - Efficient unitary designs and pseudorandom unitaries from permutations [35.66857288673615]
実測値の最初の2Omega(n)$モーメントと無作為位相によるS(N)$置換の指数和が一致することを示す。
我々の証明の核心は、ランダム行列理論における大次元(大きな=N$)展開と方法の間の概念的接続である。
論文 参考訳（メタデータ） (2024-04-25T17:08:34Z) - Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit
Feedback and Unknown Transition [71.33787410075577]
線形関数近似,未知遷移,および逆損失を用いた強化学習について検討した。
我々は高い確率で$widetildeO(dsqrtHS3K + sqrtHSAK)$ regretを実現する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-03-07T15:03:50Z) - A Construction of Evolving $k$-threshold Secret Sharing Scheme over A Polynomial Ring [55.17220687298207]
閾値秘密共有方式により、ディーラーは、秘密が一定量の株式から正しく回収されたことをすべての参加者に分配することができる。
我々は、リング上の$ell$-bitシークレットのための、進化する$k$-thresholdシークレット共有スキームを、正確性と完全なセキュリティで新たに構築することを提案する。
論文 参考訳（メタデータ） (2024-02-02T05:04:01Z) - Cooperative Multi-Agent Reinforcement Learning: Asynchronous
Communication and Linear Function Approximation [77.09836892653176]
マルコフ決定過程の設定におけるマルチエージェント強化学習について検討した。
本稿では非同期通信が可能な値に基づく証明可能な効率的なアルゴリズムを提案する。
我々は、コラボレーションによってパフォーマンスを改善するために、最小の$Omega(dM)$通信の複雑さが必要であることを示す。
論文 参考訳（メタデータ） (2023-05-10T20:29:29Z) - A Novel and Optimal Spectral Method for Permutation Synchronization [8.517406772939292]
置換同期はコンピュータ科学において重要な問題であり、多くのコンピュータビジョンタスクの重要なステップを構成する。
本稿では,新しい,統計的に最適なスペクトルアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-03-21T17:43:26Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳（メタデータ） (2022-10-14T01:42:05Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。