Linear Secret-shared Shuffle with Malicious Security

Samuel Dittmer; Rohit Nema; Rafail Ostrovsky

Paper 2025/2137

Linear Secret-shared Shuffle with Malicious Security

Samuel Dittmer

, Stealth Software Technologies, Inc.

Rohit Nema

, Stanford University

Rafail Ostrovsky

, University of California, Los Angeles

Abstract

Securely shuffling a secret-shared list is a vital sub-protocol in numerous applications, including secure sorting, secure list merging, secure graph processing, oblivious RAM, and anonymous broadcast. We demonstrate how to convert the folklore constant-round protocol for secure shuffling, which employs a delegated Fisher-Yates shuffle using rerandomizable encryption, into a maliciously secure constant-round protocol. This gives the first ever protocol that has linear end-to-end time and communication for a two-party secret-shared shuffle with malicious security. We prove the security of our protocol under the ``linear targeted malleability'' assumption on the homomorphic encryption system, as well as the natural assumptions of efficient ciphertext validity checks and rerandomizability. We also introduce a novel assumption, which we call weak predicability, and show that it is sufficient for security.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: Secret-shared Shuffle Malicious Security Homomorphic Encryption
Contact author(s): sam @ stealthsoftwareinc com
rnema @ cs stanford edu
rafail @ cs ucla edu
History: 2026-02-23: last of 2 revisions; 2025-11-21: received; See all versions
Short URL: https://ia.cr/2025/2137
License: CC BY

BibTeX

@misc{cryptoeprint:2025/2137,
      author = {Samuel Dittmer and Rohit Nema and Rafail Ostrovsky},
      title = {Linear Secret-shared Shuffle with Malicious Security},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/2137},
      year = {2025},
      url = {https://eprint.iacr.org/2025/2137}
}