Secret-Shared Shuffle with Malicious Security

Secret-Shared Shuffle with Malicious Security

Speakers: Xiangfu Song

Conference: NDSS Symposium

YouTube: (no public video)

Overview

This article delves into the critical advancements presented in the talk "Secret-Shared Shuffle with Malicious Security." Secret-Shared Shuffle (SSS) protocols are foundational primitives within secure multiparty computation (MPC), enabling multiple distrustful parties to collectively permute a vector of secret-shared data without revealing the individual secrets or the permutation itself. This capability is indispensable for privacy-preserving applications such as collaborative data analysis, anonymous communication systems like Mixnets and distributed-trust architectures (e.g., Mozilla's Prio), and enhancing differential privacy guarantees in the shuffle model.

The state-of-the-art semi-honest SSS protocol, known as CGP (Chase et al. in Asiacrypt 2020), is highly efficient, leveraging an offline correlation generation phase to facilitate a rapid online shuffle. Its simplicity and performance have led to widespread adoption. However, a significant limitation of the original CGP protocol is its security model: it is only secure against semi-honest adversaries, who follow the protocol but may try to learn information from legitimate messages. This level of security is often insufficient for real-world scenarios where adversaries might maliciously deviate from the protocol's specifications, potentially leading to privacy breaches or integrity violations.

The presented work directly addresses this critical gap. While prior attempts to enhance CGP with malicious security (e.g., by Eskandarian and Boneh in NDSS 2022, and Laud in CANS 2021) have been made, this research demonstrates that these existing protocols are flawed and vulnerable to specific attacks that allow malicious parties to learn private information. The speaker introduces a novel, robust, and efficient maliciously secure SSS protocol built upon the CGP framework. This is achieved through the integration of lightweight correlation checks and an innovative leakage reduction mechanism, ensuring privacy and correctness even in the presence of strong adversaries, with acceptable overhead compared to its semi-honest counterpart and superior performance against other state-of-the-art maliciously secure SSS protocols.

Background

[▶ Watch: Introduction and motivation for SSS protocols (0:00)]()

To understand the intricacies of maliciously secure SSS, it's essential to establish a foundation in the underlying cryptographic concepts and the semi-honest CGP protocol.

Notations and Permutations: Standard cryptographic notations are used, with G denoting an abelian group and F a finite field of l bits. Vectors are bold lowercase (e.g., x), and matrices are bold uppercase (e.g., M). A permutation π is a bijective function on n elements, mapping indices 0, ..., n-1 to 0, ..., n-1. Applying π to a vector x results in ỹ = (x_π(0), ..., x_π(n-1)).

Puncturable Pseudorandom Functions (PPRF): PPRFs are central to CGP. A PPRF F: K x X -> Y is a Pseudorandom Function (PRF) with a unique property: given a master key K and a specific "punctured" index a, a special punctured key K_a can be generated. An evaluator holding K_a can compute F(K, x) for any x ≠ a, but F(K, a) appears indistinguishable from a random element. PPRFs are typically constructed using the GGM tree method, which employs a length-doubling pseudorandom generator (PRG). The KeyGen algorithm samples an initial seed K. Puncture(K, a) computes intermediate keys layer by layer, retaining only those not on the path to a. Eval(K_a, x) reconstructs the path to x using K_a and the PRG. For malicious security, PPRF with key verification is required, allowing algorithms to check if a malicious key K is consistent with a set I. GGM PPRFs inherently support this.

Authenticated Secret Sharing (ASS): This work leverages additive linear secret sharing (LSS) over a finite field F. In LSS, a secret x is shared among parties P_i such that each P_i holds x_i, and the sum Σx_i = x. LSS offers perfect privacy against k-1 corrupted parties and supports local linear operations. Authenticated Secret Sharing (ASS) extends LSS by adding integrity guarantees, crucial for malicious security. It uses information-theoretic MACs (Message Authentication Codes). For a secret x, parties also share γ(x) = ξx for a secret MAC key ξ. An authenticated share (x) is then (x, γ(x)). The field size F must be sufficiently large (e.g., 2λ for statistical soundness). ASS also supports local linear operations and relies on ideal functionalities for operations like generating random secrets, sharing secrets known by one party, and generating multiplication triples (typical in SPDZ-family protocols).

Malicious SSS: Protocol Setting and Security Goals: The primary focus is on two parties (k=2) jointly holding an authenticated vector (x) and computing a re-randomized (ỹ) = π(x) using a random permutation π unknown to any party. The adversary is malicious, meaning it can arbitrarily deviate from the protocol, and can corrupt up to k-1 parties (a dishonest majority). The security goals are:

• Privacy: Ensuring the secrecy of shared values and the permutation π.
• Correctness: Guaranteeing the integrity of secrets and a correct shuffling, provided the protocol completes.
• Simulation-based security with abort: Formalized in Security Definition 4, this model states that a protocol is secure if a PPT (Probabilistic Polynomial Time) adversary in the real world cannot achieve more than a PPT simulator in an ideal world, with a negligible statistical error 2-λ + negl(κ). This implies that if a malicious party tries to learn extra information or cause incorrect computation, the protocol will detect this and abort, preventing the malicious party from gaining an advantage.

The Semi-honest CGP Protocol 1: The original CGP protocol builds upon specific correlations:

• Oblivious Punctured Vector (OPV): A sender P1 holds a vector v, and a receiver P0 holds (a, w) where w_i = v_i for i ≠ a and w_a = ⊥.
• Oblivious Punctured Matrix (OPM): An n-dimension OPM consists of n OPVs, with n punctured indices arranged according to a permutation π. P1 holds a matrix M, P0 holds π and a punctured matrix M*.
• Shuffle Tuple: An OPM correlation ((π, M), (M*)) can be non-interactively converted into a shuffle tuple ((π, Δ), (a, b)), where Δ = π(a) - b.
• Secret-shared Shuffle from Shuffle Tuples: P1 sends δ = x_1 - a to P0. P0 computes ỹ_0 = π(x_0 + δ) + Δ, and P1 sets ỹ_1 = b. Summing these shares recovers π(x). This is a one-sided shuffle (P0 knows π). For a fully secret-shared shuffle, the process is repeated with roles reversed.

Key Findings

[▶ Watch: Our solution: Lightweight correlation checks and leakage reduction (1:45)]()

The research presented makes several significant contributions, fundamentally advancing the state of maliciously secure Secret-Shared Shuffle protocols:

1. Insecurity of Existing Protocols: A thorough security analysis revealed critical flaws in prior maliciously secure CGP-like SSS protocols (e.g., from NDSS 2022 and CANS 2021). The talk demonstrates concrete selective failure attacks that allow malicious adversaries to learn sensitive information about the underlying permutations, shared secrets, and MACs, thereby violating privacy. This finding underscores the non-trivial challenges inherent in designing robust maliciously secure SSS protocols.

1. Lightweight Correlation Checks: The work introduces novel, lightweight correlation checks specifically designed for both Oblivious Punctured Vector (OPV) and Oblivious Punctured Matrix (OPM) correlations. These checks are crucial for verifying the well-formedness of the generated correlations in the offline phase, effectively preventing adversaries from exploiting incorrectly formed correlations to gain illicit information.

1. Sophisticated Leakage Reduction Mechanism: To combat the information leakage arising from selective failure attacks—both in the offline correlation generation and the online shuffle phases—a sophisticated leakage reduction mechanism was developed. This mechanism combines repeated, cascaded shuffle executions with a novel cut-and-choose bucketing strategy. A new combinatorial analysis method based on generating functions, coupled with a fast polynomial exponentiation algorithm (PolyExp), was introduced to compute the tightest security parameters (specifically, the number of required cascaded shuffles B) efficiently for a given statistical security level λ.

1. Robust Maliciously Secure SSS Protocol: By meticulously integrating these lightweight correlation checks, the innovative leakage reduction mechanism, and authenticated secret sharing (ASS), the researchers constructed a robust maliciously secure SSS protocol. This protocol guarantees privacy in all adversarial scenarios and ensures correctness if the protocol completes (i.e., malicious security with abort), while inheriting the efficiency benefits and optimizations of the original semi-honest CGP protocol.

1. Efficiency and Performance Leadership: Extensive implementation and evaluation of the new protocol demonstrated its practical viability and superior performance. The overhead introduced for achieving malicious security was shown to be acceptable, with the protocol outperforming existing maliciously secure SSS solutions, such as those found in the MP-SPDZ library, by significant margins (e.g., up to 15x faster in the offline phase and 7x faster in the online phase for specific configurations). This establishes a new state-of-the-art in efficient, maliciously secure secret-shared shuffling.

Technical Deep Dive

[▶ Watch: Background: Notations, Permutations, PPRFs explained (2:00)]()

The core of this research lies in identifying vulnerabilities in existing maliciously secure CGP-like SSS protocols and then designing sophisticated countermeasures.

Malicious Protocols & Online-phase Attacks:

Previous attempts to make CGP maliciously secure (e.g., works by Eskandarian and Boneh, and Laud) adapted the protocol to use authenticated secret sharings (ASS), packing authenticated shares (x)_i (from F x F) as elements of F2. However, the talk identified a Selective Failure Attack in the online phase.

A malicious sender P1 can deviate by sending an incorrect δ' = (x)_1 - a + ũ instead of the correct δ = (x)_1 - a, where ũ is an error vector with a non-zero element e at a specific position q. P1 then guesses that π(p) = q for some p.

• Case 1: P1 guesses correctly (π(p) = q). The error e is effectively "shuffled" into the correct position. The integrity of shuffled secrets and MACs remains preserved, and a post-execution check (like Π_MACCheck) outputs True. Crucially, P1 learns π(p) = q without being detected, violating privacy. This attack has a non-negligible success probability of 1/n.
• Case 2: P1 guesses incorrectly (π(p) ≠ q). The integrity is broken, the check detects the error, and P1 is caught.

This attack exploits the unauthenticated nature of the δ message, allowing P1 to probe information about π by observing the outcome of integrity checks.

Malicious Protocols & Offline-phase Attacks:

The correlation generation protocols for CGP are also vulnerable:

• OPV Attack (against [2]): During Oblivious Punctured Vector (OPV) generation, a malicious sender P1 can perform a selective failure attack. P1 generates a correct GGM tree but selectively corrupts one of the Oblivious Transfer (OT) messages for the first layer by adding an error e to guess α_1 = 0.
• Case 1: α_1 = 0 (correct guess). Parties still share a correct OPV correlation, and P1 learns α_1 = 0 undetected (1/2 success probability).
• Case 2: α_1 = 1 (incorrect guess). An erroneous OPV is shared, which will be detected later. This attack also breaks privacy.
• OPM Attack (against [2]): A malicious receiver P0 can break privacy during Oblivious Punctured Matrix (OPM) generation by choosing to puncture the same column for multiple rows. For instance, if P0 always punctures the fourth column, it learns (a_0, a_1, a_2) for free. Combined with P0's local share (x)_0 and the δ message from the online phase, P0 can fully recover (x_0, x_1, x_2) and their MACs, revealing shared secrets and MACs.

Countermeasures: Correlation Checks and Leakage Reduction:

To address these vulnerabilities, the work introduces a two-pronged approach:

1. Correlation Checks: These ensure the well-formedness of OPV and OPM correlations, primarily targeting receiver-side attacks.

• OPV Check: A consistency check for GGM trees, inspired by prior work [30, 41]. The GGM tree is expanded by an additional layer, mapping the punctured index a to its left child a0. P1 sends a hash of all right extended leaf nodes to P0. P0 computes its own hash and compares. Mismatches indicate an incorrect OPV correlation, leading to an abort. While it detects incorrect correlations, it doesn't prevent the sender's selective failure attack directly.
• OPM Check: This ensures the OPM receiver punctures honestly according to a valid permutation.
• An initial sacrifice-based OPM check was considered: if P0 punctures honestly, it should be able to recover the entire OPM matrix from P1. P1 sends column-wise sums, P0 recovers, both commit to their matrices, and check for equality. However, this destroys the correlation.
• To avoid destroying the correlation, an OPM extension trick is used: parties generate two OPM correlations embedded with identical puncture information. One is sacrificed for the check, the other used for the shuffle. This is done by extending the GGM PPRF's range to output (F2 x 0,1k) x 0,1k.
• Unfortunately, this OPM check introduced a new selective failure attack from a malicious sender P1, similar to the online attack. P1 can guess q = π(p), add an error e to the q-th column-wise sum. If the guess is correct, the check passes, and P1 learns q = π(p) without detection.

1. Leakage Reduction Mechanism: This mechanism specifically targets all selective failure attacks (offline OPV, offline OPM, and online post-execution), which are detectable with a certain probability.

• Reduce leakage via repeated execution: When a random shuffle is needed, parties perform B cascaded shuffle executions using B tuples (π_0), ..., (π_B-1). The final permutation is π = π_B-1 o ... o π_0. An adversary needs to guess correctly B times and pass all checks to learn information about π. If B is sufficiently large, the probability of undetected attacks becomes negligible.
• Cut-and-choose leakage reduction and analysis: To optimize B for batch correlation generation, a cut-and-choose bucketing strategy is employed. Parties generate NB tuples, randomly assign them into N buckets, each with B tuples. The goal is to ensure each bucket contains enough non-leaky tuples.
• A novel combinatorial analysis method using generating functions [43, 44] is developed to compute the tightest B given N, tuple dimension n, and statistical security parameter λ.
• To make this practical, a fast polynomial multiplication algorithm (PolyExp) is developed, leveraging the square-and-multiply trick to reduce complexity from O(N) to O(log N), further optimized by dropping high-degree coefficients irrelevant to λ. For N = 2^20, n = 2^10, and λ = 40, this analysis yields B = 7.

Concrete Protocols:

• GGM PPRF Instantiation: A GGM PPRF F' is instantiated with an extended range F' : {0,1}* x {0,1}^{h+1} -> (F2 x {0,1}^k) x {0,1}^k. This extends the h-th layer of the GGM tree, parsing each extended leaf node as ((m_0, m_1), β). β is for the OPV check, m_1 for the OPM check, and m_0 (an F2 element) for shuffle tuple generation.

• Offline Phase Protocol: OPV Setup with Check (IGenV): This protocol securely computes an ideal functionality F_GenV.

1. Sender S samples a random seed K.
2. S computes intermediate GGM keys.
3. For each layer, parties invoke maliciously secure OTs (Oblivious Transfers), where Receiver R inputs its choice bit a_i, and S inputs key pairs, R receiving the appropriate key.
4. R defines its punctured key path.
5. S computes extended leaf nodes using G' and calculates K_h+10 (XOR sum of s_h+1,j0) and a tag τ (hash of s_h+1,j1 and s_h+1,j2). S sends (K_h+10, τ) to R.
6. R computes its own tag τ' from its received keys and right leaf nodes.
7. R checks if τ = τ'. If not, R aborts.

Theorem 1 confirms I_GenV's security in the F_OT-hybrid model. Complexity: O(κ log n) communication, O(n) computation.

• Offline Phase Protocol: OPM Setup with Check (IGenM): This protocol computes F_GenM.

1. For each row i, R and S call F_GenV n times. R inputs π(i), S inputs K_i. R receives K_i*.
2. Parties locally parse the OPM correlation into two OPMs: (π)(0) (over F2) and (π)(1) (over {0,1}k).
3. Parties sacrifice (π)(1) for the OPM check: S computes column-wise sums w_j of M(1) and sends to R. R recovers M_j,π(j)(1). S computes a hash tag τ, R computes τ'. They invoke an equality check functionality F_eq and abort if τ ≠ τ'.

Theorem 2 confirms I_GenM's security in the (F_GenV, F_eq)-hybrid model. Complexity: O(κn log n + κn) communication, O(n^2) computation.

• Online Phase Protocol (I_OSSR): This implements F_OSS (a two-party one-sided secret-shared shuffle).
• Offline: Parties invoke F_GenM NB times (where R specifies NB permutations). They evaluate OPM keys to NB shuffle tuples, which are then shuffled with a public permutation ρ and divided into N buckets of B tuples.
• Online:

1. Initialize (x(0)) = (x).
2. Fetch B shuffle tuples from the next unused bucket.
3. For t = 0 to B-1 (cascaded shuffles):

• S parses (π_t)_S = (a(t), b(t)), sends δ(t) = (x(t))_S - a(t) to R. S sets (x(t+1))_S = b(t).
• R receives δ(t), parses (π_t)_R = (π_t, Δ(t)). R sets (x(t+1))_R = π_t((x(t))_R + δ(t)) + Δ(t).

1. Parties run Π_MACCheck over all intermediate shared vectors (x(1)), ..., (x(B)). Abort if check fails.
2. Output (x(B)).

Theorem 3 confirms I_OSSR's security with statistical error 2-λ, given F >= 2λ and proper B (from combinatorial analysis).

• Full SSS Protocol (I_SSS): For two parties, I_SSS is achieved by invoking I_OSSR twice with roles reversed, similar to the original CGP.

Extension and Optimizations:

• Multi-party Shuffle Protocols: The techniques extend to k parties using a pair-wise execution paradigm. This involves k^2 invocations of pair-wise CGP shuffle, leading to O(lk^2n) online communication and O(κk^2n log n) offline communication. More efficient multi-party protocols are future work.
• Trade-off using Generalized Benes Networks (GBN): To reduce the O(n^2) computation for large n, a permutation decomposition technique from [1] is borrowed. A permutation π ∈ S_n is decomposed into d = 2log n / log T - 1 smaller permutations π_i, each composed of n/T disjoint T x T permutations. Each T x T OPM costs O(T^2), making total offline computation O(dnT). T can be configured to balance computational overhead (smaller T) and online communication costs (larger T).

Demo / Proof of Concept

[▶ Watch: Malicious SSS: Protocol setting and security goals (4:00)]()

The talk includes a robust demonstration of the protocol's practicality and efficiency through a C++ implementation and extensive performance evaluations. This serves as the practical proof of concept for the theoretical advancements.

Experiment Settings:

• The implementation used fix-key AES for PRG and hash functions, and IKNP-type maliciously secure OT extension from the emp-toolkit.
• Tests were run on a desktop PC with an Intel Xeon Platinum 8163 CPU (2.50GHz, 16 cores, 32GB RAM) running Ubuntu 20.04 LTS.
• Network conditions were simulated using Linux tc:
• LAN: RTT 0.2 ms, 1 Gbps
• WAN: RTT 80 ms, 40 Mbps
• Cryptographic parameters: computational security κ = 128, statistical security λ = 40, and element size l = 128 bits.

Performance of Correlation Generation (Single Shuffle Tuple):

Measurements for generating one shuffle tuple, with n ranging from 2^6 to 2^12, revealed:

• Running time (Fig. 14): The maliciously secure protocol was 1.1-2.9x slower than the semi-honest CGP protocol in a LAN setting and 1.01-2.3x slower in a WAN setting. This overhead is attributed to malicious OTs and correlation checks. Notably, the protocol showed good network efficiency, being only 1.3-5.7x slower in WAN compared to LAN. For larger n, computation dominates runtime.
• Communication (Table I): The protocol incurred approximately 20% more communication than the semi-honest CGP, demonstrating that the lightweight correlation checks introduce low communication overhead.

Performance of Shuffle (Online Phase):

Online phase performance was evaluated for n from 2^10 to 2^20, using GBN decomposition with T = 2^d where d ∈ {4, 6, 8, 10}. The protocol was compared against the state-of-the-art maliciously secure SSS protocol from the MP-SPDZ library [4], which uses multiplication triples to evaluate a two-swap permutation network.

• Running time (Table II): The proposed protocol significantly outperformed MP-SPDZ [4] in both LAN and WAN. While comparable for T = 2^4, the efficiency gap widened for larger T. For n = 2^20 in a WAN setting, the protocol with T = 2^10 was approximately 6x faster than MP-SPDZ [4], showcasing excellent scalability for large-dimension vectors.

Amortized Offline Running Time (Table III):

Considering the cut-and-choose leakage reduction:

• In a LAN setting (computation-bound), using low-dimension tuples (T = 2^6) was optimal, with the protocol being about 15x faster than HE-based MP-SPDZ [4].
• In a WAN setting (communication-bound), T = 2^6 achieved the most balanced efficiency.

Amortized Communication (Table IV):

• The proposed protocol required significantly less communication than MP-SPDZ [4].
• For the offline phase, with T = 2^4, it required at least 7x less communication than HE-based MP-SPDZ [4] and two orders of magnitude less than OT-based MP-SPDZ [4].
• For the online phase, T = 2^10 required the least communication.
• The recommendation is to choose d such that d divides log_2 n to optimize offline communication.

Defensive Implications

[▶ Watch: Overview of the semi-honest CGP protocol (4:30)]()

The findings of this research have critical implications for practitioners and developers building privacy-preserving systems that rely on secret-shared shuffling:

1. Re-evaluate Existing Implementations: Organizations currently using CGP-like SSS protocols for malicious security should immediately re-evaluate their implementations. The demonstrated selective failure attacks against previously proposed malicious CGP variants confirm that these protocols do not achieve their claimed privacy guarantees. Assuming semi-honest security in a malicious environment is a critical vulnerability.

1. Adopt Robust Maliciously Secure Protocols: For applications involving sensitive data where adversaries are expected to be malicious, it is imperative to adopt protocols that are provably secure in the malicious model. The protocol presented in this talk offers a robust alternative, integrating lightweight correlation checks and a sophisticated leakage reduction mechanism to withstand arbitrary adversarial deviations.

1. Implement Correlation Checks Diligently: Any implementation of SSS based on OPV and OPM correlations must incorporate rigorous checks to ensure the well-formedness of these correlations. The OPV Check and OPM Check described are essential components to prevent adversaries from generating incorrect correlations that can later be exploited to learn sensitive information.

1. Incorporate Leakage Reduction for Selective Failure Attacks: Given the prevalence of selective failure attacks, relying solely on post-execution checks is insufficient. Implementing a leakage reduction mechanism (such as the proposed cascaded shuffles with cut-and-choose bucketing and combinatorial analysis) is crucial to reduce the probability of undetected information leakage to a negligible level. Developers must carefully choose security parameters B and N based on the provided analysis to ensure adequate security.

1. Consider Performance Trade-offs: While the new protocol offers superior performance, its efficiency can be further optimized by selecting appropriate parameters, especially for the Generalized Benes Networks (GBN) decomposition (T and d). For computation-bound environments (e.g., LAN), smaller T might be preferable for offline phases, while communication-bound environments (e.g., WAN) might benefit from specific T values or d choices that divide log_2 n to minimize communication. Understanding these trade-offs is key to deploying efficient and secure systems.

1. Stay Informed on Multi-Party Challenges: For multi-party SSS, the current extension involves k^2 pair-wise invocations, leading to high overhead. Defenders should be aware of this complexity and monitor ongoing research for more efficient multi-party CGP-like protocols as this remains an area for future work.

Key Takeaways

• Existing maliciously secure CGP-like Secret-Shared Shuffle (SSS) protocols are vulnerable to selective failure attacks, allowing malicious adversaries to learn sensitive information about permutations and shared secrets, thus failing to deliver claimed privacy.
• Lightweight correlation checks for Oblivious Punctured Vector (OPV) and Oblivious Punctured Matrix (OPM) are essential to ensure the well-formedness and integrity of cryptographic correlations generated in the offline phase.
• A novel leakage reduction mechanism, combining cascaded shuffles with a cut-and-choose bucketing strategy and a tight combinatorial analysis (using generating functions and PolyExp), is critical for mitigating information leakage from selective failure attacks across different protocol phases.
• The presented protocol successfully integrates these countermeasures with authenticated secret sharing (ASS) to achieve robust malicious security with abort, guaranteeing privacy and correctness, while inheriting efficiency benefits from the original semi-honest CGP.
• Implemented in C++, the new protocol demonstrates practical viability and significantly outperforms state-of-the-art maliciously secure SSS protocols like those in MP-SPDZ, achieving up to 15x faster offline phase and 7x faster online phase for large-scale shuffles.
• Future work should focus on more efficient leakage reduction mechanisms for the online phase and optimizing multi-party SSS protocols to reduce the k^2 complexity for a larger number of parties.

About the Speaker(s)

The talk "Secret-Shared Shuffle with Malicious Security" was presented by Xiangfu Song. The provided transcript and metadata do not contain further biographical details about the speaker, such as their title or affiliation.