Paper 2025/2137 Original: eprint.iacr.org/2025/2137 ↗
Linear Secret-shared Shuffle with Malicious Security
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.
- History
- 2026-09-03: last updated
- 2025-11-21: published
- Short URL
- https://ia.cr/2025/2137
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}