Trident: Efficient 4PC Framework for Privacy Preserving Machine Learning

In plain words

Several servers can each hold a random-looking piece of a patient record or a bank's data, and together they can train or query a machine-learning model without any one server seeing the data. This paper builds that kind of system for four servers, where at most one may misbehave on purpose.

Machine-learning code mixes three kinds of work. Some steps are plain adding and multiplying. Some are comparisons, such as checking whether a number is negative, which ReLU needs. Some are table-like lookups or divisions. Each kind is fastest with a different secure-computation toolkit, and switching between toolkits has a cost. The paper's framework, called Trident, handles all three and makes the switches cheaper. Most of the gain comes from the extra honest server: it allows a multiplication with one round of checking, a truncation step without the expensive circuits used before, and comparisons that take a fixed number of rounds instead of a number that grows with the bit width.

The authors compare their framework with ABY3, a three-server system, in their own benchmarks. They report large speedups for training and prediction on linear, logistic, neural-network and convolutional models. These numbers come from their setup, and the paper re-implements ABY3 because its code was not public.

TL;DR

• Four parties, at most one malicious; a verified multiplication costs 3 ring elements online per gate §3.2, §3.3.
• Mixed-world framework over a 64-bit ring: arithmetic, boolean and garbled sharings, with conversions between them §4.
• Truncation after multiplication uses no boolean circuit; ReLU and sigmoid take a constant number of rounds §5.1, §5.3.
• Author-reported: linear-regression training on LAN is up to 251.84x faster than malicious ABY3, and prediction latency is lower in most settings §1, §6.
• The source has inconsistent headline numbers; see Pitfalls.

Problem

Secure computation over three parties in the honest-majority setting, such as ABY3, is fast when all parties follow the protocol. Under malicious behaviour its dot products cost communication that grows with vector length, and its comparison, truncation and activation steps need rounds that grow with the ring size §1. Truncation is needed because fixed-point products grow in size. Earlier truncation methods were not safe with three or four parties, so a new approach was needed §1, §5.1. The paper's assumption is an extra honest party: four servers, at most one corrupted, with data secret-shared among them. Four servers, not three, also means extra cost to run, which the authors discuss as monetary cost §1, app. E.

Method

Sharing semantics §3.1

The paper's symbols are written as sqd, sgrd and shrd. This card names them:

• Additive share [x]: three values that sum to x, with P1, P2, P3 each holding one value §3.1.
• Replicated share <x>: the same three values, but each of P1, P2, P3 holds two of them in a cycle: P1 holds (x2, x3), P2 holds (x3, x1), P3 holds (x1, x2) §3.1.
• Masked share {x}: a public mask m = x + pad, known to P1, P2 and P3; the pad is replicated-shared among P1 to P3; P0 knows all three pad parts in clear §3.1.

Addition, and multiplication by a public constant, are local for all three sharings §3.1. The paper says the masked-share addition uses the same linearity §3.1.

Setup §2, app. A

Keys come from a setup functionality FSETUP that gives every pair of parties a key, every triple of parties a key, and all four parties one shared key. The keys seed a pseudorandom function (PRF) whose output is in Z_ℓ. Hashes are collision resistant and are used to save communication. The paper defers formal details to app. A.

Building blocks §3.2

• πSh: a party P_i shares a value. Offline, the pad is derived from the keys, so P_i learns it. Online, P_i sends the mask m = x + pad to P1–P3, who exchange hashes of it and abort on mismatch §3.2, πSh.
• πaSh: P0 shares a value additively in the offline phase. P0 chooses two random parts; the third part is minus the sum of the value and the two parts. P1 and P2 exchange a hash of that third part §3.2, πaSh. See Pitfalls on the sign.
• πRec: reconstruction. Each party receives its one missing share from one party and a hash of it from another, then recovers the value as the mask minus the three pads §3.2, πRec.
• πZero: a replicated sharing of zero, with parts A, B and Γ that sum to zero; built from keys and the PRF, adapted from a three-party protocol app. A, πZero.
• πMult: multiplication of two masked values. Offline, the parties compute the cross terms of the pads, using πZero for the randomising parts A, B and Γ, and exchange them with hashes §3.2, πMult. Online, each evaluator computes one term, receives a second term, and checks it with a hash. The product mask is the sum of the three terms plus the product of the input masks §3.2, πMult.

# Offline part of multiplication z = x * y  [§3.2, πMult] [app. A, πZero]
# A, B, Gamma are a zero sharing: A + B + Gamma = 0
def mult_offline_gamma(pad_x, pad_y, A, B, Gamma):
    # Each Gamma part uses only pad parts held by the two parties that get it
    gamma_B = pad_B_x * pad_B_y + pad_B_x * pad_C_y + pad_C_x * pad_B_y + A
    gamma_C = pad_C_x * pad_C_y + pad_C_x * pad_A_y + pad_A_x * pad_C_y + B
    gamma_A = pad_A_x * pad_A_y + pad_A_x * pad_B_y + pad_B_x * pad_A_y + Gamma
    return gamma_A, gamma_B, gamma_C

# Online part of multiplication z = x * y  [§3.2, πMult]
# Mask_z' = Mask_z - Mask_x * Mask_y; the three parts sum to Mask_z'
def mult_online(mask_x, mask_y, pad_z, gamma):
    # Each part is computed by two evaluators, sent by one, hashed by another
    part_1 = -pad_A_x * mask_y - pad_A_y * mask_x + gamma_A + pad_A_z
    part_2 = -pad_B_x * mask_y - pad_B_y * mask_x + gamma_B + pad_B_z
    part_3 = -pad_C_x * mask_y - pad_C_y * mask_x + gamma_C + pad_C_z
    # Verify the two received parts against their hashes, then add  [§3.2]
    mask_z = part_1 + part_2 + part_3 + mask_x * mask_y
    return mask_z

• Verified reconstruction and delayed checks: the hash exchanges of multiplication gates can be postponed to output reconstruction and combined into one hash, which gives an overall overhead of 3 ring elements §3.2.
• πfRec (fair reconstruction): P1 to P3 report whether all checks passed, P0 answers, and the parties decide by majority before exchanging missing shares. It takes 4 rounds §3.4, app. B.

Stages of the 4PC protocol §3.3

1. Input sharing: the owner of each input runs πSh on it.
2. Evaluation: gates are processed in topological order. Addition is local. Multiplication runs πMult.
3. Output reconstruction: πRec on each output.

Cost claims: offline 1 round and 3M ring elements, where M is the number of multiplication gates. Online input sharing 1 round and at most 3I elements, evaluation D rounds and 3M elements, output reconstruction 1 round and 3O elements, where I, O and D are the numbers of inputs, outputs and multiplicative depth §3.3, app. B. The paper says each multiplication gate costs 6 ring elements in total (3 offline, 3 online), against 4 online elements for Gordon et al. with the same total of 6 §1.

Garbled world §4.1

• The MRZ15 garbled-circuit scheme is used, with P1–P3 as garblers and P0 as the only evaluator. Free XOR, half gates and fixed-key AES garbling are used §4.1.
• πShG shares a bit: the garblers commit to both wire keys, and P0 checks the commitments. πvShG (verifiable garbled sharing) follows ABY3 §4.1, §4.2.
• AND gates use a garbled table sent by one garbler, with a hash from another §4.1.
• The paper states that no oblivious transfer is needed §4.1.

Verifiable sharing and dot product §4.2

• πvSh: two parties share a value; the second party sends a hash of the mask §4.2.
• πDotP: a dot product of two length-d vectors. The parties add the multiplication terms locally and exchange only once, so the communication does not depend on d: 3 ring elements offline and 3 online §4.2, app. B.

Sharing conversions §4.3, app. C

• πGB (garbled to boolean): P1 and P2 prepare a random value in both forms; P0 evaluates a XOR circuit and passes the result to P3 §4.3.
• πGA (garbled to arithmetic): the same, with a subtraction circuit §4.3.
• πBG (boolean to garbled): the bit is the XOR of two two-party masked parts, each shared with πvShG and combined by free XOR §4.3.
• πAG (arithmetic to garbled): the value is split as a difference of two values, shared with πvShG, and a garbled subtractor computes the result §4.3.
• πAB (arithmetic to boolean): same split, with a boolean subtractor circuit of log ℓ depth §4.3, app. C.
• πBitA (bit to arithmetic): P0 shares the random pad bit additively, all parties check it with a random ring element and random bit, then the mask bit is shared and multiplied §4.3, πBitA.
• πBA (boolean to arithmetic, version 2): each bit of the pad is turned into an additive sharing, then the masked bits are combined into three masked values §4.3, πBA.
• πBitInj (bit injection, bit times arithmetic value): the offline phase shares two pad products and checks them; the online phase computes a masked result with 3 ring elements §4.3, πBitInj.

Truncation and comparison §5.1, §5.2

Fixed-point numbers keep their last d bits as the fraction §5. After a multiplication, the parts are shifted right by d bits.

• πMultTr (multiplication with truncation): offline, parties sample random masks r1, r2, r3, sum them into r, truncate r to r_t, share r_t additively, and check the relation r = 2^d r_t + (low d bits of r) with one message and one hash. Online, the parties open z - r with the multiplication masks, truncate the result, and add r_t §5.1, πMultTr.
• Bit extraction (πBitExt): the sign bit of a masked value. The compiled text gives only the outline §5.2: P0 and P3 get a boolean sharing of PadA + PadB offline; P1 and P2 get a boolean sharing of Mask − PadC online; a parallel-prefix adder then yields the sign bit in boolean-shared form. The protocol box is in a LaTeX comment block, so the compiled text has no step-by-step box. The cost lemma describes an arithmetic multiplication and a reconstruction towards P0 and P3 in the online phase app. D, πBitExt.

# Multiplication with truncation  [§5.1, πMultTr]
# Offline, a random r and r_t = trunc(r) are shared; r_t is checked
def mult_trunc_online(z_minus_r, mask_x, mask_y, r_t_share):
    # Open z - r after the masked multiplication step  [§5.1]
    opened = open_sum(z_minus_r) + mask_x * mask_y
    # Truncate the opened value by d bits; a public, per-party step  [§5.1]
    truncated = opened >> d
    # Re-share the truncated value and add the offline share of r_t  [§5.1]
    share_z_t = share(truncated) + r_t_share
    return share_z_t

Activation functions §5.3

• ReLU: ReLU(x) = (1 xor b) * x, where b is the sign bit of x §5.3. The bit comes from bit extraction, and the product comes from bit injection §5.3.
• Sigmoid: a piecewise-linear approximation, not the logistic function. It is 0 below -1/2, x + 1/2 between -1/2 and 1/2, and 1 above 1/2 §5.3. It is computed as (1 xor b1) * b2 * (x + 1/2) + (1 xor b2), with b1 = [x + 1/2 < 0] and b2 = [x - 1/2 < 0] §5.3.

# ReLU  [§5.3]
def relu(x_shares):
    # Sign bit of x as boolean shares  [§5.2]
    b = bit_extract(x_shares)
    # Bit injection multiplies the negated sign bit with x  [§4.3, πBitInj]
    return bit_inject(1 xor b, x_shares)

# Sigmoid approximation  [§5.3]
def sigmoid(x_shares):
    # b1 is 1 below -1/2, b2 is 1 below +1/2  [§5.3]
    b1 = bit_extract(x_shares + 0.5)
    b2 = bit_extract(x_shares - 0.5)
    # Product of two bits, then one injection  [§5.3]
    inner = bit_inject((1 xor b1) * b2, x_shares + 0.5)
    return inner + (1 xor b2)

Training and prediction §6.1, §6.2

• Linear regression: one iteration updates the weight vector with mini-batch gradient descent, where the batch has B rows: W ← W − (α/B) Xᵀ(XW − Y) §6.1. All operations are additions and multiplications, so the update runs in the arithmetic sharing §6.1.
• Logistic regression: the same update, with the sigmoid approximation applied to XW §6.1.
• Neural network: two hidden layers of 128 ReLU nodes and an output layer of 10 nodes, trained by gradient descent. The output layer uses a softmax variant, ReLU(u_i) / Σ ReLU(u_j), with the division done in a garbled circuit §6.1. The output error is E = A − T §6.1.
• CNN: the convolution is replaced by a fully connected layer (an overestimate), with two hidden layers of 100 and 10 nodes §6.1.

# One gradient-descent iteration, linear regression  [§6.1]
def linear_regression_step(weights, batch_x, batch_y, lr, batch_size):
    # Forward pass on the mini-batch  [§6.1]
    predictions = batch_x @ weights
    # Backward pass: gradient of the squared error  [§6.1]
    error = predictions - batch_y
    weights = weights - (lr / batch_size) * (batch_x.T @ error)
    return weights

The same code, run under secret shares with the operations above, is the benchmarked algorithm.

Hyperparameters

WAN round-trip times (ms): P0–P1 274.83, P0–P2 174.13, P0–P3 219.45, P1–P2 152.3, P1–P3 60.19, P2–P3 92.63 §6.

Results

Author-reported. Setup: 64-bit ring, LAN and WAN as in Hyperparameters; ABY3 is the malicious version, re-implemented by the authors §6. Values are copied from the paper's tables; "This" is Trident.

Training, LAN (iterations per second) and WAN (iterations per minute), linear regression tab. 4

Training, logistic regression tab. 5

Training, neural network and CNN, d = 784 tab. 6

Units: LAN iterations per second; WAN iterations per minute.

Prediction, online latency, d = 784 tab. 7 (LAN in ms, WAN in s)

Online throughput, LAN (predictions per second) tab. 8

Bandwidth-limited throughput gain §6.2, bandwidth figure; not a numbered table: gain over ABY3 at 40, 30, 20, 10 Mbps: linear regression 74.73, 99.64, 149.46, 298.93; logistic regression 12.60, 16.80, 25.20, 50.39; NN 335.44 at all four; CNN 598.44 at all four.

Total online runtime, WAN, AES-128 circuit, seconds, against Gordon et al. app. E, tab. 11

Total online runtime, WAN, d = 784, B = 128, seconds, against malicious ABY3 app. E, tab. 12

Against semi-honest ABY3 (ABY3S), training app. E, tab. 13

Units: LAN it/s, WAN it/min.

Against semi-honest ABY3S, prediction latency app. E, tab. 14: LAN ms, ABY3S / This: linear 0.30 / 0.30, logistic 9.14 / 2.55, NN 480.81 / 17.17, CNN 1185.70 / 39.63. WAN s, ABY3S / This: linear 0.16 / 0.16, logistic 1.54 / 0.93, NN 4.07 / 2.31, CNN 4.47 / 2.31.

Against semi-honest ABY3S, throughput app. E, tab. 15: LAN queries per second, ABY3S / This: linear 106666.67 / 106666.67, logistic 3512.62 / 12549.02, NN 66.41 / 153.39, CNN 21.47 / 37.43. WAN queries per minute, ABY3S / This: linear 12488.62 / 12488.62, logistic 1248.86 / 2081.46, NN 211.18 / 368.13, CNN 51.54 / 89.84.

Conversion costs, offline and online app. C, tab. 9: rounds R and communication C in bits; ℓ = ring bits, κ = security parameter, |Dec|, |Sub|, |Add| = garbled-circuit sizes.

ML conversions app. D, tab. 10: d here is the caption's "number of features" (see Pitfalls).

Main-text cost claims §1, §3.3, §6.2: the text says linear-regression training LAN gains range over 4.88x to 251.84x; logistic LAN gains 5.95x to 67.88x; NN and CNN training gains 2.94x to 68.04x and 3.19x to 45.64x (abstract and §1). Prediction throughput gains: linear regression 26.16x to 145.18x and logistic 5.69x to 158.40x (§6.2). Bit-extraction comparison is 3 online rounds versus log ℓ (§5.2, app. D).

Paper vs code

No official code. The source names one software library, ENCRYPTO_utils, which is a third-party utility, not the authors' implementation. The arXiv abstract page lists no code link. A GitHub repository search for "trident+4PC", "trident+privacy+preserving+machine+learning" and "trident+mpc" returned zero repositories. Searches for the authors by name returned accounts with no name or affiliation shown, none tied to the paper, so none is used.

Pitfalls

• Sign convention in the additive sharing. πaSh sets the third part to minus the sum of the value and the other two parts, so under the paper's own definition the three parts sum to minus the value §3.2, πaSh. πMultTr uses the shares unchanged, which matches this reading §5.1. πBitA negates them, which does not match it §4.3, πBitA. Read literally, one of these steps is wrong. The card cannot tell which was intended, so pick one convention and test it.
• Headline numbers disagree. The abstract says training up to 187x and prediction up to 158x. The text gives LAN linear-regression training up to 251.84x §1, §6.1. From the table, 861.33 / 3.43 = 251.1, not 251.84, so rounding in the table may explain the gap. No table entry gives 187x. The 158x figure matches the logistic prediction throughput gain of 158.40x §6.2.
• B2A communication gain. The abstract claims 18x less communication for B2A. The conversion table gives online 3ℓ against 9ℓlogℓ+9ℓ for ABY3. At ℓ = 64 that is 192 against 4032, about 21x. The source of 18x is not stated.
• NN iteration rate. The text says 22.99 it/s and the table says 23.00 §6.1, tab. 6.
• ABY3 semi-honest baseline. §1 quotes ABY3 at 2.5 it/s for NN with batch 128, while the authors' own ABY3S measurement in tab. 13 is 1.01 it/s. Different sources, not reconciled.
• Who measured the baselines. ABY3 and MRZ15 code were not public, so the authors re-implemented them §6. The source of the Gordon et al. numbers is not stated.
• P0 is not always idle. The "P0 is idle online" claim §1, app. E holds for the arithmetic evaluation. P0 is the only evaluator of garbled circuits §4.1, so it does work in those steps.
• Truncation error. Truncation is probabilistic, as in SecureML, with an error in the least significant bit §6.2. The paper defers the bit-error analysis to SecureML and gives no bound of its own. The value of d is not stated.
• Caption ambiguity. The ML conversion table's caption says d is the number of features app. D, but §5 uses d for the number of fractional bits. The πMultTr cost formula contains d, and its meaning is not stated.
• Sigmoid is not the logistic function. It is a three-piece linear approximation §5.3. Implement it exactly as written if you want to match the benchmarks.
• Bit extraction is prose only. Its protocol box is inside a LaTeX comment block, so the compiled text has no step-by-step version §5.2. Cost lemmas for it are in app. D.
• Training details are missing. Learning rate, number of iterations, fractional-bit count and the NN loss are not stated in the compiled text. The NN cross-entropy appears only in a commented block. The softmax division circuit is not described §6.1.
• Bandwidth-limit method. The WAN throughput gains at lower bandwidth are measured by limiting bandwidth; the method is not stated §6.2.
• Security proof coverage. The proof handles corrupt P0 and corrupt P1 in detail. The paper says P2 and P3 are symmetric app. F. The zero-sharing πZero is adapted from a three-party protocol and its proof is omitted app. A. The security model is static malicious, in the FSETUP and FZERO hybrid model app. F.
• Late detection. Multiplication checks are postponed to output reconstruction, so a cheating party is caught late §3.2. Fair reconstruction needs 4 rounds app. B.
• Sharing soundness. The random-check soundness for the sharings of pads (πBitA, πMultTr) is not quantified §4.3, §5.1.
• Table numbers were taken from source order, not checked against the rendered PDF. Verify them before use.
• Version note. The paper's v2 says an improved version is at arXiv:2106.02850. That paper is not compiled here, and nothing from it is used.

Lineage

• Builds on: ABY3 [MR18] for the mixed-world framework and the truncation and comparison ideas; the Gordon et al. four-party protocol [GordonR018] for the masked evaluation; MRZ15 for the garbled world; SecureML [MohasselZ17] for the truncation problem. Only ABY3 and Gordon et al. are compared in the benchmarks.
• Compared against: ABY3 malicious and semi-honest, re-implemented by the authors; Gordon et al. 4PC for total online runtime on AES-128 app. E.
• Superseded by: the v2 note points to arXiv:2106.02850. No card for it exists yet.