Paper 2023/1794

Secret-Shared Shuffle with Malicious Security

Xiangfu Song, National University of Singapore
Dong Yin, Ant Group
Jianli Bai, University of Auckland
Changyu Dong, Guangzhou University
Ee-Chien Chang, National University of Singapore

A secret-shared shuffle (SSS) protocol permutes a secret-shared vector using a random secret permutation. It has found numerous applications, however, it is also an expensive operation and often a performance bottleneck. Chase et al. (Asiacrypt'20) recently proposed a highly efficient semi-honest two-party SSS protocol known as the CGP protocol. It utilizes purposely designed pseudorandom correlations that facilitate a communication-efficient online shuffle phase. That said, semi-honest security is insufficient in many real-world application scenarios since shuffle is usually used for highly sensitive applications. Considering this, recent works (CANS'21, NDSS'22) attempted to enhance the CGP protocol with malicious security over authenticated secret sharings. However, we find that these attempts are flawed, and malicious adversaries can still learn private information via malicious deviations. This is demonstrated with concrete attacks proposed in this paper. Then the question is how to fill the gap and design a maliciously secure CGP shuffle protocol. We answer this question by introducing a set of lightweight correlation checks and a leakage reduction mechanism. Then we apply our techniques with authenticated secret sharings to achieve malicious security. Notably, our protocol, while increasing security, is also efficient. In the two-party setting, experiment results show that our maliciously secure protocol introduces an acceptable overhead compared to its semi-honest version and is more efficient than the state-of-the-art maliciously secure SSS protocol from the MP-SPDZ library.

Note: Full version.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. NDSS 2024
Secret-shared ShuffleAttacks and AnalysisMalicious Security
Contact author(s)
songxf @ comp nus edu sg
dybean1994 @ gmail com
jbai795 @ aucklanduni ac nz
changyu dong @ gmail com
changec @ comp nus edu sg
2024-06-13: last of 2 revisions
2023-11-21: received
See all versions
Short URL
No rights reserved


      author = {Xiangfu Song and Dong Yin and Jianli Bai and Changyu Dong and Ee-Chien Chang},
      title = {Secret-Shared Shuffle with Malicious Security},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1794},
      year = {2023},
      doi = {10.14722/ndss.2024.24021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.