Metraipolis › archive › dc_caf855172fa7

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

Source: arXiv (en)
Original: https://arxiv.org/abs/2608.27129
License (as archived): CC0-1.0
Archived: 2026-10-17T15:55:08.295Z
SHA-256 of the archived text: 42530c378bb96efb4eb8bfbda6a153431760aac5f0342268ab0dea3bdc6a1c57
Stable URL of this page: https://metraipolis.com/documento/dc_caf855172fa7

How to cite

SLIDE: Shuffle Shamir Secret Shares Uniformly with Linear Online Communication and Guaranteed Output Delivery — arXiv:2608.27129 — arXiv (en), https://arxiv.org/abs/2608.27129 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_caf855172fa7 (Metraipolis archive dc_caf855172fa7, sha256 42530c378bb96efb4eb8bfbda6a153431760aac5f0342268ab0dea3bdc6a1c57)

BibTeX

@misc{dccaf855172fa7,
  title = {SLIDE: Shuffle Shamir Secret Shares Uniformly with Linear Online Communication and Guaranteed Output Delivery — arXiv:2608.27129},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.27129},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_caf855172fa7; sha256 42530c378bb96efb4eb8bfbda6a153431760aac5f0342268ab0dea3bdc6a1c57},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.27129. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: fiducia digitale e crittografia (retro-catalogo arXiv: annunci del 2026-08-28 in cs.CR).
Categorie arXiv: Cryptography and Security (cs.CR).
Pagina del lavoro: https://arxiv.org/abs/2608.27129 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T15:31:38.277Z dalla pagina https://arxiv.org/catchup/cs.CR/2026-08-28?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).