Linear Secret-Shared Shuffle with Malicious Security

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.