Paper 2025/165

Shuffle Shamir Secret Shares Uniformly with Linear Online Communication

Jiacheng Gao, Nanjing University
Yuan Zhang, Nanjing University
Sheng Zhong, Nanjing University
Abstract

In this paper, we revisit shuffle protocol for Shamir secret sharing. Upon examining previous works, we observe that existing constructions either produce non-uniform shuffle or require large communication and round complexity, e.g. exponential in the number of parties. We propose two shuffle protocols, both of which shuffle uniformly within $O(\frac{k + l}{\log k}n^2m\log m)$ communication for shuffling rows of an $m\times l$ matrix shared among $n$ parties, where $k\leq m$ is a parameter balancing communication and computation. Our first construction is more concretely efficient, while our second construction requires only $O(nml)$ online communication within $O(n)$ round. In terms of overall communication and online communication, both shuffle protocols outperform current optimal shuffle protocols for Shamir secret sharing. At the core of our constructions is a novel permutation-sharing technique, which can be used to permute arbitrarily many vectors by computing matrix-vector products. Once shared, applying a permutation becomes much cheaper, which results in a faster online phase. Letting each party share one secret uniform permutation in the offline phase and applying them sequentially in the online phase, we obtain our first shuffle protocol. To further optimize online complexity and simplify the trade-off, we adopt the shuffle correlation proposed by Gao et al. and obtain the second shuffle protocol with $O(nml)$ online communication and $O(n^2ml)$ online computation. This brings an additional benefit that the online complexity is now independent of offline complexity, which reduces parameter optimization to optimizing offline efficiency. Our constructions require only most basic primitives in Shamir secret sharing scheme, and work for arbitrary field $\mathbb{F}$ of size larger than $n$. As shuffle is a frequent operation in algorithm design, we expect them to accelerate many other primitives in context of Shamir secret sharing MPC, such as sorting, oblivious data structure, etc.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
ShuffleMultiparty ComputationShamir Secret Sharing
Contact author(s)
jcgao @ smail nju edu cn
zhangyuan @ nju edu cn
zhongsheng @ nju edu cn
History
2025-02-05: approved
2025-02-04: received
See all versions
Short URL
https://ia.cr/2025/165
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/165,
      author = {Jiacheng Gao and Yuan Zhang and Sheng Zhong},
      title = {Shuffle Shamir Secret Shares Uniformly with Linear Online Communication},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/165},
      year = {2025},
      url = {https://eprint.iacr.org/2025/165}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.