SLIDE: Shuffle Shamir Secret Shares Uniformly with Linear Online Communication and Guaranteed Output Delivery

• URL: http://arxiv.org/abs/2608.27129v1
• Date: Thu, 27 Aug 2026 13:44:17 GMT
• Title: SLIDE: Shuffle Shamir Secret Shares Uniformly with Linear Online Communication and Guaranteed Output Delivery
• Abstract summary: We propose two new shuffle protocols for Shamir secret sharing.<n>First protocol is concretely efficient, while the second achieves the best-known $O(nml)$ online communication and $O(n)$ rounds.<n> Experiments show significant improvements in online efficiency and total cost over prior work.
• Score: 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.

Related papers

• Single-Shuffle Full-Open Card-Based Protocols for Any Function [4.039245878626346]
  A textitsingle-shuffle full-open protocol is a minimal model of card-based secure computation.<n>We prove for the first time that every function admits a single-shuffle full-open protocol.
  arXiv  Detail & Related papers  (2025-10-20T08:52:23Z)
• Communication-Efficient Publication of Sparse Vectors under Differential Privacy [2.9123921488295768]
  We propose a differentially private algorithm for publishing matrices aggregated from sparse vectors.<n>Our algorithm significantly reduces this cost to $O(varepsilon m)$, where $varepsilon$ is the privacy budget.<n>We theoretically prove that our method yields results identical to those of randomized response.
  arXiv  Detail & Related papers  (2025-06-25T08:25:46Z)
• Breaking Free: Efficient Multi-Party Private Set Union Without Non-Collusion Assumptions [5.030459935922802]
  Multi-party private set union (MPSU) protocol enables $m$ $(m > 2)$ parties, each holding a set, to collectively compute the union of their sets. We propose the first MPSU protocol based on oblivious transfer and symmetric-key techniques in the standard semi-honest model. We show that our protocol requires only $4.4$ seconds in online phase for 3 parties with sets of $220$ items each.
  arXiv  Detail & Related papers  (2024-06-11T07:10:45Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  We revisit the input perturbations framework for differential privacy where noise is added to the input $Ain mathcalS$. We first design novel efficient algorithms to privately release pair-wise cosine similarities. We derive a novel algorithm to compute $k$-way marginal queries over $n$ features.
  arXiv  Detail & Related papers  (2024-06-07T12:07:16Z)
• Efficient unitary designs and pseudorandom unitaries from permutations [35.66857288673615]
  We show that products exponentiated sums of $S(N)$ permutations with random phases match the first $2Omega(n)$ moments of the Haar measure. The heart of our proof is a conceptual connection between the large dimension (large-$N$) expansion in random matrix theory and the method.
  arXiv  Detail & Related papers  (2024-04-25T17:08:34Z)
• Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transition [71.33787410075577]
  We study reinforcement learning with linear function approximation, unknown transition, and adversarial losses. We propose a new algorithm that attains an $widetildeO(dsqrtHS3K + sqrtHSAK)$ regret with high probability.
  arXiv  Detail & Related papers  (2024-03-07T15:03:50Z)
• A Construction of Evolving $k$-threshold Secret Sharing Scheme over A Polynomial Ring [55.17220687298207]
  The threshold secret sharing scheme allows the dealer to distribute the share to every participant that the secret is correctly recovered from a certain amount of shares. We propose a brand-new construction of evolving $k$-threshold secret sharing scheme for an $ell$-bit secret over a ring, with correctness and perfect security.
  arXiv  Detail & Related papers  (2024-02-02T05:04:01Z)
• Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation [77.09836892653176]
  We study multi-agent reinforcement learning in the setting of episodic Markov decision processes. We propose a provably efficient algorithm based on value that enable asynchronous communication. We show that a minimal $Omega(dM)$ communication complexity is required to improve the performance through collaboration.
  arXiv  Detail & Related papers  (2023-05-10T20:29:29Z)
• A Novel and Optimal Spectral Method for Permutation Synchronization [8.517406772939292]
  Permutation synchronization is an important problem in computer science that constitutes the key step of many computer vision tasks. In this paper, we propose a novel and statistically optimal spectral algorithm.
  arXiv  Detail & Related papers  (2023-03-21T17:43:26Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  We propose a class of novel distributed Adam-type algorithms (emphi.e., SketchedAMSGrad) utilizing sketching. Our new algorithm achieves a fast convergence rate of $O(frac1sqrtnT + frac1(k/d)2 T)$ with the communication cost of $O(k log(d))$ at each iteration.
  arXiv  Detail & Related papers  (2022-10-14T01:42:05Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.