PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Jiacheng Gao, Moyang Xie, Yuan Zhang, Sheng Zhong

arXiv:2608.27129v1cs.CR

TL;DR

Shamir-secret-sharing shuffles have lacked a combination of uniformity and efficient communication. This paper introduces permutation sharing and shuffle-correlation-based protocols, culminating in SLIDE with uniformity, O(nml) online communication, and guaranteed output delivery.

  • Problem

    Existing Shamir-secret-sharing shuffle constructions are either non-uniform or incur high communication and round complexity.

  • Method

    The paper introduces a permutation-sharing technique and combines it with shuffle correlation to construct uniform shuffles and extend them to guaranteed output delivery.

  • Results

    SLIDE simultaneously achieves uniformity, O(nml) online communication, and guaranteed output delivery.

  • Takeaways & Limitations

    The constructions improve the online efficiency of Shamir-based MPC shuffles and support practical shuffle-based MPC frameworks.

  • Takeaways & Limitations

    Shuffle1 can be preferable when overall cost matters more than online latency, particularly because it has simpler machinery and smaller concrete overheads in some settings.

Abstract

from arXiv · show

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.

1 Introduction

The paper addresses inefficient or non-uniform shuffling for Shamir secret sharing by introducing uniform protocols with improved online complexity and guaranteed output delivery.

  • Motivation: Existing Shamir-based shuffles either lack uniformity or require high communication and round complexity.Switching networks are non-uniform, sorting networks achieve uniformity only probabilistically, and prior uniform constructions remain costly.
  • Core technique: The paper introduces a permutation-sharing primitive for applying shared permutations to secret-shared vectors.The primitive supports a tunable parameter k that balances communication and computation.
  • Shuffle protocols: The first protocol sequentially applies independent uniformly random secret permutations shared during the offline phase.Its communication and round costs depend on the tunable parameter k.
  • Shuffle protocols: The second protocol uses shuffle correlation to achieve O(nml) online communication and O(n) rounds.Its offline communication improves on the previous best-known uniform bound of O(n^2ml log m).
  • Guaranteed output delivery: SLIDE extends the constructions to guaranteed output delivery while retaining uniformity and O(nml) online communication.It ensures honest parties obtain the correct output despite adversarial behavior.
  • Evaluation: The paper analyzes how k affects communication, computation, and round complexity to guide parameter selection.Experiments report improvements in online efficiency and total cost over prior work.

2 Related Works

Prior Shamir-secret-sharing shuffle approaches include decryption, switching, sorting, square-network, and permute-in-turn techniques, but existing methods face uniformity, efficiency, or online-complexity limitations.

  • Background: Decryption shuffles produce permuted plaintexts, whereas MPC shuffles must preserve secret-shared outputs for subsequent computation.This distinction limits the direct use of decryption shuffles in MPC tasks.
  • Secret-sharing gap: Additive-secret-sharing advances cannot be directly applied to Shamir sharing because Shamir shares must remain points on a low-degree polynomial.This prevents techniques such as PRG-based rerandomization from transferring directly.
  • Existing approaches: Switching-network shuffles achieve O(nml log m) communication but do not generate uniformly distributed permutations.Their gates randomly swap inputs, yet some resulting permutations occur with significantly different probabilities.
  • Existing approaches: Sorting-network shuffles obtain uniformity only with some probability and rely on heavy MPC sorting primitives.Designing suitable sorting networks is also difficult.
  • Existing approaches: Square networks approximate uniform permutations by composing smaller permutations, with computation depending on the number of layers q.The cited construction uses q=15 and incurs O(qn^2m^2l) total computation.
  • Online complexity: Existing protocols largely neglect online complexity because their offline phases prepare only basic randomness rather than data-independent shuffle work.Switching and sorting approaches require actual inputs before their main operations can proceed.
  • This work: The paper’s permutation-sharing technique creates a trade-off between permutation-sharing communication and application communication, while its later protocol reaches linear online complexity.The approach exploits low-communication inner products in Shamir sharing and integrates shuffle correlation.

3 Preliminaries

The paper models MPC over Shamir secret sharing with an honest-majority, malicious-adversary setting and modular secret-sharing primitives. Its notation supports shared vectors and matrices, while its security-with-abort constructions are later extended to guaranteed output delivery.

  • Setting and assumptions: The protocols operate with n parties over a finite field F of size greater than n, with fewer than n/2 corrupted parties.The corruption threshold is t < n/2, and publicly known distinct nonzero evaluation points are used for the parties.
  • Permutation notation: A permutation maps an m-element vector to a reordered vector, with its permutation matrix encoding the mapping between input and output positions.The matrix entry is 1 when the column equals the permutation image of the row and 0 otherwise.
  • Basic notation: Shamir shares represent secrets as evaluations of a degree-t polynomial with the secret at f(0), and vectors or matrices are shared entrywise.The notation writes shared vectors and matrices componentwise using brackets around each shared value.
  • Setting and assumptions: The paper assumes m is a power of 2 to use Beneš-network-based permutation decomposition, while smaller arrays can be handled using a shuffle for size m.The construction also assumes m and k are powers of 2 when both parameters are relevant.
  • Security model: The primary security goal is unconditional security with abort against static adversaries under an honest majority.If corrupted parties deviate, honest parties abort with overwhelming probability; the paper later replaces aborting primitives to obtain GOD.
  • Guaranteed output delivery: The GOD extension replaces security-with-abort primitives, uses dispute control to exclude corrupted parties, and relies on authentication tags.Dispute sets grow after failed checks, and communication between disputed parties is routed through relays rather than sent directly.
  • Shamir functionality: The abstract Shamir functionality provides sharing, addition, inner products, randomness, and public challenges, with operations assumed correct or causing abort.Most primitives use O(n) communication, while an inner product on length-m vectors uses O(n) communication and O(nm) computation.

4 Permutation Sharing Protocol and Shuffle Protocol

The paper shares permutations through smaller k × k permutation matrices and applies them to secret-shared vectors. This yields tunable communication trade-offs and efficient uniform shuffle protocols built from sequential secret permutations.

  • Shared permutation representation: The construction represents an m-permutation using many smaller k × k permutation matrices, interpolating between full-matrix sharing and permutation-network control bits.Sharing and applying these smaller matrices reduces the size of each matrix operation while retaining a tunable parameter k.
  • One-hot vectors: Well-formed shared permutation matrices are built from k distinct one-hot vectors whose validity can be checked before use.A k × k permutation matrix consists of k pairwise distinct one-hot vectors, so distinctness certifies the matrix structure.
  • Shared permutation definition: A k-shared m-permutation consists of s decomposition layers, each containing disjoint k-element tasks and secret-shared k-permutations whose composition induces the target permutation.The number of layers is s = O(log m / log k), and each task identifies the entries affected by its small permutation.
  • Permutation application: Once shared, a permutation is applied by extracting each task’s subvector, multiplying it by the corresponding shared k × k matrix, and writing the result back.When k = m, this reduces to multiplying one shared m × m permutation matrix directly by the vector.
  • One-hot generation: OneHot decomposes an index into log k bits, checks their binarity, and demultiplexes them into a length-k one-hot vector.The binary check detects invalid bits with probability at least 1 − d^-1, while demultiplexing uses O(k) multiplications in O(log log k) rounds.
  • Shared permutation representation: Task invariance lets parties agree which entries each small permutation handles without learning the original permutation.Because each task is independent of the original permutation, the affected positions can be fixed in advance.
  • Complexity analysis: The permutation-sharing protocol has O((k/log k)nm log m) communication and computation and O(log log k) rounds.The displayed theorem gives these asymptotic costs for SharePerm.
  • Complexity analysis: The first shuffle has offline communication O((k/log k)n^2m log m) and online communication O((l/log k)n^2m log m), with O(n log m) online rounds.Its larger-k trade-off reduces online communication and rounds but increases matrix-generation, application, and preprocessing costs.

5 Shuffle Protocol with Linear Online Communication

The second shuffle protocol uses shuffle correlation to move expensive permutation work offline while achieving low online communication, constant rounds, and improved latency. It offers strong online efficiency, while Shuffle1 remains simpler and can be preferable when overall cost matters more than online latency.

  • Construction: Shuffle2 leverages shuffle correlation to preserve shuffle security while moving most expensive permutation work to the offline phase.Online messages are masked by independently prepared random values, preserving input and permutation privacy.
  • Complexity: O(nm + n2) communication, O(n2m) computation, and O(n) rounds support vector shuffling; communication simplifies to O(nm) when n = O(m).
  • Complexity: O(nml + n2) online communication, O(n2ml) online computation, and O(n) online rounds are required for shuffling an m × l matrix.When n is much smaller than ml, online communication simplifies to O(nml).
  • Evaluation: 6 online rounds remain constant with m, compared with 180 for Shuffle1 and 350 for Keller and Scholl (2014) at m = 262,144.Shuffle2's online execution time also remains below 1 second at that scale, while other protocols require tens to hundreds of seconds.
  • Trade-offs: Shuffle1 can be preferable when online latency is relaxed and overall cost is prioritized because it avoids shuffle correlation and has smaller constant factors.This advantage is more relevant in malicious or GOD instantiations, where Shuffle1 incurs less additional overhead.

6 Guaranteed Output Delivery

The paper strengthens its shuffle protocols from security with abort to guaranteed output delivery by identifying corrupted parties or disputes and using authentication tags. These mechanisms allow honest parties to recover correct intermediate states rather than restarting after adversarial deviations.

  • Approach: GOD is obtained by replacing abort-only primitives with GOD-enabled counterparts for protocols built from standard MPC primitives.
  • Authentication tags: Authentication tags commit to shares produced within circuit segments, allowing honest parties to recover a correct intermediate state after adversarial deviations rather than restarting.Forgery succeeds with probability at most 2^-κ, and verifiers use tag checks and majority voting to identify a corrupted party.
  • Corruption identification: Corruption identification makes failures expose either a new corrupted party or a new disputing pair, enabling computation to continue without falsely identifying honest parties.Reported parties and disputing pairs must be new, so the corresponding sets strictly increase.
  • Corruption identification: The underlying protocols inherit corruption identification because they use basic MPC primitives, recursive subprotocols, and locally checked permutation sharing.This includes one-hot generation and the PermMat, PermCheck, SharePerm, and Permute protocols.
  • Result: All proposed protocols support corruption identification and can consequently be strengthened to achieve GOD with linear overhead.The construction applies because honest parties hold consistent shares at protocol termination.
  • Optimization: Selecting t + 1 active parties can reduce communication because t + 1 shares suffice to reconstruct a secret and at least one selected party is honest.

7 Conclusion

SLIDE is presented as the first shuffle protocol combining uniformity, O(nml) online communication, and guaranteed output delivery. It combines novel permutation sharing, shuffle correlation, and corruption-identification-based GOD techniques.

  • Conclusion: SLIDE simultaneously achieves uniform shuffling, O(nml) online communication, and guaranteed output delivery.
  • Conclusion: Its construction uses novel permutation sharing, integrates shuffle correlation for linear online complexity, and extends the result to guaranteed output delivery.The paper positions shuffling as a fundamental building block for many MPC protocols and primitives.

A Security Proofs

The security analysis argues that deviations are detected with overwhelming probability, while honest executions produce correct shares. Security of Shuffle2 follows from secure Permute and the composition theorem.

  • Proof strategy: The proof focuses on showing that adversarial deviations cause abort with overwhelming probability, using standard simulation-based security for Shamir secret sharing.
  • Proof strategy: Ideal functionalities provide strong guarantees, so errors in basic operations are detected and security follows through the composition theorem.
  • Security outcome: If the adversary misbehaves, the protocol aborts with overwhelming probability; if all parties behave honestly, honest parties receive correct shares.
  • Shuffle2 security: Security of Shuffle2off and Shuffle2on follows from secure implementation of Permute by the composition theorem.
  • Shuffle2 security: If corrupted parties misbehave, all parties abort with overwhelming probability.

A.1 Security of the One-Hot Protocol

The one-hot protocol securely produces a valid one-hot vector, while binary checks detect malformed inputs with overwhelming probability and protect an honest chooser’s index.

  • BinCheck aborts with overwhelming probability when any input is non-binary.
  • Demux securely constructs the one-hot vector indexed by 1 + the sum of the shared input bits when it does not abort.
  • The protocol outputs a valid one-hot vector with the index selected by the designated party upon successful termination.
  • If the designated party is honest, corrupted parties learn no information about the chosen index.
  • For malicious choices, non-binary submitted values are rejected, while valid binary choices correspond to an allowed index.

A.2 Security of the Permutation Protocol

The permutation protocols validate shared permutation matrices, preserve secrecy for an honest chooser, and either produce the intended shared permutation or abort under adversarial misbehavior.

  • PermCheck aborts with overwhelming probability when the shared one-hot vectors do not form a valid permutation matrix.
  • The permutation checks rely on opening a zero value for valid matrices and detecting a nonzero polynomial condition for invalid ones.
  • PermMat securely produces a valid shared permutation matrix when the designated party honestly chooses the permutation.
  • SharePerm shares the chooser’s permutation correctly when parties behave honestly and reveals no information about it when the chooser is honest.
  • Permute outputs a sharing of the permuted vector under honest execution, while adversarial misbehavior causes an abort with overwhelming probability.

A.3 Security of the Shuffle Protocol

Both shuffle protocol variants securely apply a uniformly random secret permutation, and both abort with overwhelming probability if the adversary misbehaves.

  • Shuffle1off and Shuffle1on abort with overwhelming probability under adversarial misbehavior.
  • Otherwise, Shuffle1off and Shuffle1on shuffle the shared data using a secret permutation uniformly random over all m-permutations.
  • Shuffle2off and Shuffle2on also abort with overwhelming probability if the adversary misbehaves.
  • Otherwise, Shuffle2off and Shuffle2on apply a secret permutation uniformly random over all m-permutations.

B.1 Proofs for Section 4.6

The complexity analysis bounds the costs of permutation sharing and application, then derives offline and online costs for the first shuffle protocol.

  • O(k log k nm log m) communication and O(k log k nm log m) computation are achieved by Permute, with its stated round bound.
  • O(n2d) communication and computation with O(log d) rounds characterize Demux, because its recursive calls parallelize.
  • O(nk) communication and computation with O(log log k) rounds characterize OneHot when d = log k.
  • O(nk2) communication and computation with O(log log k) rounds characterize PermMat, combining k parallel OneHot calls with PermCheck.
  • O(k log k nm log m) communication and computation, with O(log log k) rounds, are required by SharePerm.
  • For the first shuffle protocol, offline communication and computation are O(k log k n2m log m), while online costs scale with l and the stated round bound.

B.2 Proofs for Section 5.4

The section establishes complexity bounds for the shuffle protocols and explains the permutation-matrix sharing checks underlying their construction.

  • Complexity bounds: O(k log k n^2m log m) bounds Shuffle2off’s offline communication and computation, with O(log m / log k + log log k) rounds.The n calls to SharePerm and Permute on m × 3 matrices determine the bottleneck.
  • Complexity bounds: O(nm + n^2) communication, O(n^2m) computation, and O(n) rounds characterize Shuffle2on.When n = O(m), communication simplifies to O(nm).
  • Permutation-matrix checks: Permutation matrices are verified through binary entries and exactly-one conditions for every row and column when the field’s prime subfield satisfies p > m.The condition prevents modular overflow, allowing row and column sums to reflect the actual number of ones.
  • Permutation-matrix checks: When p ≤ m, modular overflow makes direct row and column checks unreliable, including an all-ones counterexample for m = p + 1.The construction therefore uses one-hot vectors in the general case, retaining O(nm^2) communication per permutation matrix.
  • Online efficiency: Online complexity matters because it determines user-facing latency and is multiplied across sequential shuffle invocations in applications such as radix sort.For 128-bit indices, radix sort requires 128 sequential shuffle calls, yielding at least R_off + 128 × R_on rounds.
  • Permutation sharing: The definition of k-shared permutations is asymptotically tight because their number must cover all m! distinct m-permutations.Stirling’s approximation gives log(m!) = Θ(m log m) and log(k!) = Θ(k log k).

C.4 Overhead of Malicious and GOD-Enabled Realizations

The section estimates the additional costs of malicious and GOD-enabled realizations beyond the semi-honest benchmarks, while distinguishing estimates from direct measurements.

  • Benchmark scope: The experiments benchmark only semi-honest Shamir implementations, while malicious and GOD costs are protocol-level estimates rather than separate measurements.Actual overhead may be higher depending on the backend and implementation details.
  • Malicious realization: A malicious Shuffle2 implementation is estimated to cost about 3× more offline and roughly twice the online payload than the semi-honest version.Additional correlated values, three-vector permutation, two-component corrections, and CorrCheck account for the increase.
  • GOD realization: GOD is expected to add a small backend-dependent constant-factor overhead in fault-free executions, but SLIDE’s end-to-end overhead may be larger.Dispute-control state and authentication tags add costs, while detected deviations can trigger relay communication and rollback.
  • Malicious realization: A malicious Shuffle1 implementation is estimated to increase costs by roughly 2× offline and 1.5× online without changing asymptotic complexity.The estimate includes well-formedness checks, secure multiplications, openings, and demultiplexing.
  • Round complexity under dispute control: A single GOD-enabled shuffle can reach O(n^2) rounds in the worst case because dispute-control rollbacks may add rounds.Within a full protocol, faulty parties are excluded after identification, so the shuffle’s stated round complexity remains O(n).
Loading 2608.27129v1…