Linear Secret-Shared Shuffle with Malicious Security
Samuel Dittmer, Rohit Nema, Rafail Ostrovsky
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 protocol that has a 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 scheme, as well as the natural assumptions of efficient ciphertext validation and rerandomization. We also introduce an even weaker assumption (than linear targeted malleability) and show that this weaker assumption on the encryption scheme is also sufficient for proving security.
comment:
CRYPTO (8) 2026: 296-328
Fetch PDF file of the paper