Protocol Review of SecureNN

On 21 March 2025 I finished reading SecureNN and wrote down five questions, one observation, and a postscript claiming the paper had a typo that broke security. This is that review, checked.

The version I read was eprint 2018/442, revision of 14 May 2018, titled SecureNN: Efficient and Private Neural Network Training, by Wagh, Gupta and Chandran.

The current version is the revision of 8 March 2019, which appeared at PETS 2019 and was retitled SecureNN: 3-Party Secure Computation for Neural Network Training. Three of my seven points were addressed in it. Four were not. I also checked everything against the reference implementation, which settled three things the paper alone could not.

Here is where each point landed. Click a row.

Question 1: the cost of "fresh" shares

How many bits of extra randomness are required to maintain this privilege? Is it cheaper (in terms of maintaining information-theoretic security) to group some protocols together?

The first half is just counting. Freshness is maintained by adding a pre-shared sharing of zero to each protocol's output. Walk one scalar ReLU and count them: one in Π_SC, one in Π_MSB, one in the 1×1 Π_MatMul inside Π_MSB, one in Π_DReLU, one in the Π_MatMul inside Π_ReLU, and one in Π_ReLU itself. Six, at ℓ bits each.

So the invariant is cheap. What is not cheap is the rest of the correlated randomness, and it is not the freshness masks: Π_PC needs ℓ multipliers s_i from Z₆₇^∗, ℓ more values u_i for a corner case, and a common permutation of 64 elements. That permutation alone is 296 bits, and Π_PC runs twice per DReLU. Add it up and one scalar ReLU consumes about 332 bytes of correlated randomness against 704 bytes on the wire.

Now the second half, which is where the question was better than I knew. I asked whether grouping is cheaper for information-theoretic security. That assumes these bits are information-theoretic. In the version I read, so did the paper, the abstract promised "three-party and four-party information-theoretically secure protocols," and Section 2.1 said "the adversary is not restricted to run in polynomial time (i.e., we provide information-theoretic security)."

The 2019 revision says something different. Section 3.4 now spells out how the zero-shares are made:

the two parties exchange a PRF key, k, and one party sets its share to z₀ = PRF_k(ctr), while the other sets its share to z₁ = −PRF_k(ctr)

and Section 1.1 adds a sentence that is not in the 2018 version at all:

All our protocols are fundamentally information-theoretically secure … However, in practice, we use pseudorandom functions to generate shared randomness as well as point-to-point secure channels between all pairs of parties thereby relying on computational assumptions for the implementation.

So the answer is: zero bits. The implementation spends PRF output, not randomness, and a PRF-keyed protocol is computationally secure however uniform its transcript looks. The 2018 abstract's distinction against SecureML, they are computationally secure, we are information-theoretic, does not reach the code, and the 2019 revision is the one that says so.

That also answers the grouping half. Merging protocols would drop the interior masks and save 4ℓ of the 6ℓ, about 4.5% of ReLU's communication, in exchange for the composition theorem that lets you build arbitrary networks from these pieces. Not worth it. There is a good reason to merge Π_SC and Π_MSB, but it is the one in Question 5, not this one.

One thing did get cheaper. The same PRF now generates the Beaver triples, and the 2019 table adds a row for it: matrix multiplication drops from 2(2mn + 2nv + mv)ℓ to (2mn + 2nv + mv)ℓ, exactly half. ReLU falls from about 96ℓ to 88ℓ.

Question 2: the excluded range

What is done when the value of a is in the excluded range? Do you clip the data into the very narrow range or do you abort training?

Neither. There is no clipping and no abort, and I checked the C++: the only assertions in Functionalities.cpp are about which party is calling and what the dimensions are. Nothing anywhere tests whether a value is in range.

I said "almost 100% of our integer a is excluded," which is arithmetically right, the safe set has 2^k+1 of 2⁶⁴ elements. But I was treating a as if it were uniform on Z_L, and it never is. It is a fixed-point number with thirteen fractional bits, so |a| < 2^k is really a bound of 2^k−13 on the real value.

The part I missed is that this range is not SecureNN's, and it is not really about DReLU. It is Theorem 1 of SecureML, which SecureNN cites for its truncation:

In field Z_2^l, let x ∈ [0, 2^l_x] ∪ [2^l − 2^l_x, 2^l), where l > l_x + 1 … Then with probability 1 − 2^l_x+1−l, Rec_A(⌊x⌋₀, ⌊x⌋₁) ∈ {⌊x⌋ − 1, ⌊x⌋, ⌊x⌋ + 1}.

Same set, same shape, same condition l > l_x + 1 that SecureNN writes as k < ℓ − 1. Every fixed-point multiply in the network already needs a value in that set or the local truncation of the shares fails, and it fails by roughly the size of the ring, not by one bit. DReLU inherits a constraint the arithmetic layer was already carrying, which is why nobody added a check for it.

So the range comes with a failure probability, and that is the number worth looking at. Below, the circle is Z_2⁶⁴ with zero at the top and the safe arcs shaded.

At k = 24 the safe arcs are invisible slivers and the expected number of failures across a whole training run is 0.004. At k = 62, where the arcs cover half the circle and the picture looks reassuring, every second multiply corrupts.

So ℓ = 64 is doing the work I thought it was, but for the truncation and not for DReLU. Union-bounding over the roughly 2.1 billion truncations in one Network A run pins k at 32 or below, a real-valued bound of about half a million. Comfortable for MNIST, and comfortable is the whole answer.

The 2019 revision did tighten the statement. Where the version I read wrote closed intervals, [0, 2^k] ∪ [2^ℓ − 2^k, 2^ℓ − 1], the current one writes them half-open: [0, 2^k) ∪ (2^ℓ − 2^k, 2^ℓ − 1]. That is a real correction to the endpoints and it changes nothing about the size of the set. What is still missing in both is a stated bound on activations, or an assertion, or a sentence telling an implementer how much headroom they have. Anyone porting this to a domain with a wider dynamic range gets no warning.

Question 3: FFT or NTT Beaver triples

I would be curious to hear if your team experimented with using discrete Fast Fourier Transform (FFT)-based Beaver's Triplets (or NTT since we start/end with shares of input/output values over a ring) for computing secure linear functions (matrix multiplications). Your C++ implementation uses the Eigen library.

They could not have, and the reason is the ring. An NTT of length n needs a primitive n-th root of unity, and it needs n to be invertible. The unit group of Z_2⁶⁴ is a 2-group:

Any n with an odd factor has no root of unity to use; any n that is a power of two is not invertible. There is no transform. You can work around it, Schönhage–Strassen uses Z_2^m+1, or you CRT across NTT-friendly primes, but both land you in a ring where the modulo is not free, which is the property the whole design exists to keep. The question and Question 4 have the same answer.

And a free transform would not have moved the number that matters anyway. Beaver's protocol communicates the openings of E = X − A and F = Y − B, which is set by the matrix dimensions, not by how you compute the products. The paper's own microbenchmarks show arithmetic is not the constraint: the 1×100×1 matrix multiplication does essentially no arithmetic and still costs 25.2 ms on the WAN against 0.33 ms on the LAN. That 25 ms is latency and nothing else. A faster multiply optimises the 0.33.

Where a transform would genuinely pay is convolutions, which SecureNN lowers to a much larger matrix multiplication by unrolling patches, that unrolling is why Conv2d costs (2m²f²i + 2f²oi + m²o)ℓ. A convolution theorem would attack communication, not just compute. But it needs a transform-friendly ring, and picking one costs the free modulo, which costs the GEMM.

Question 4: was ShareConvert forced by the ring?

Was F_SC only created because you are fixed on operating over the ring Z_2⁶⁴ (due to the practical optimizations C++ libraries make over rings of this size + you get modulo operations for FREE)?

Yes, and the paper says so almost in those words. From the version I read:

The ring size is set to Z_2⁶⁴ and we use the uint64_t native C++ datatype for all variables. As noted in [SecureML], compared to using a field … this has the benefit of implementing modulo operations for free.

and from Section 2 of the current one:

we could execute our protocol over the ring Z_N with N being odd. However doing so is fairly inefficient as matrix multiplication over the ring Z_2⁶⁴ … is much faster … Hence, we provide a protocol that converts values (≠ L − 1) that are secret shared over Z_L into shares over Z_L−1.

That is the whole reason Π_SC exists. The comparison trick needs MSB(a) = LSB(2a), which holds only over an odd ring, so the parties have to leave Z_2⁶⁴ and come back. Here is what the round trip costs.

304 of 664 bytes, and four of eight rounds. In the version I read the split was the same, 304 of 688. Either way, the ring choice costs about 45% of the operation that dominates the workload, the paper's own microbenchmarks put a 128×128 DReLU at 109.8 ms and 10.88 MB against 9.7 ms and 1.69 MB for their largest benchmarked matrix multiplication.

Neither version prints the counterfactual, and I think it should. Running everything over Z_2⁶⁴−1 costs you Eigen's native path, but reduction modulo a Mersenne number is a fold-and-add rather than a division, so what you lose is the vectorised library call, not the modulo. SecureNN optimised the layer that was already cheap and paid for it in the layer that was not. That trade is a day of work to measure and it has not been measured.

Question 5: why is ShareConvert its own function?

Can you comment on why F_SC was made into its own function? Wouldn't it be cleaner to have it be part of F_MSB which would now take inputs of secret shares over ⟨a⟩^L and output secret shares over ⟨a⟩^L also.

The premise checks out completely, and it checks out in the code too. In the paper, Π_SC is invoked exactly once, at step 2 of Algorithm 6, and Π_MSB exactly once, at step 3. Algorithm 6 is DReLU. There is no other caller of either, anywhere. In the implementation they sit in one function body with nothing between them:

void funcRELUPrime3PC(const vector<myType> &a, vector<myType> &b, size_t size)
{
    for (size_t i = 0; i < size; ++i)
        twoA[i] = (a[i] << 1);

    funcShareConvertMPC(twoA, size);
    funcComputeMSB3PC(twoA, b, size);
    ...
}

That is the whole case. Two functionalities, one caller each, the same caller, back to back, and the intermediate value twoA is never used for anything else.

You were right that Π_MSB is the only sub-protocol expecting Z_L−1, and right that the two are always used together. What I would add is why it matters, beyond tidiness. The paper's counter-argument is one clause, Π_SC "may be of independent interest", and that is fine for a reader but not for the analysis, because the seam is what creates the range condition in Question 2. DReLU has to compute c = 2a to satisfy Π_SC's a ≠ L − 1, and the doubling is what forces a into [0, 2^k) ∪ (2^ℓ − 2^k, 2^ℓ − 1]. That condition is proved in DReLU's lemma and then never restated: the ReLU lemma is given in the (F_DReLU, F_MATMUL)-hybrid model with no range condition attached, and Maxpool and Division do not mention it either.

Division shows what that costs. Algorithm 8 loops i from ℓ−1 down to 0 and calls DReLU on ⟨x⟩ − ⟨u_i+1⟩ − 2ⁱ⟨y⟩. At i = 63 that term has wrapped Z_2⁶⁴ for any y ≥ 2, so the value handed to DReLU no longer means what the comparison needs it to mean. The implementation does not do this. It runs for (looper = 1; looper < FLOAT_PRECISION+1; ++looper), thirteen iterations, not sixty-four, and it scales the divisor down with funcTruncate2PC instead of scaling it up, which never overflows. The cost table agrees with the code, at 10 l_D rounds. So this is the pseudocode being wrong rather than the system being broken, and it is exactly the kind of wrong you get when a precondition is proved at one level and not carried to its callers.

Fold the two together, give the result the signature ⟨a⟩^L → ⟨MSB(a)⟩^L, and the doubling and its range condition become internal to one functionality, stated once, where they can be enforced.

The thought: a communication budget

I guess the real benefits (in communication efficiency) come from achieving better accuracies with fewer epochs since we do the same number of secure operations per epoch. Network A stood out to me because it was an outlier in that it did not achieve good accuracy at lower epochs. The "communication budget" is something we should keep track of.

Network A is an outlier and the paper says so: it is left out of the epoch sweep because it "does not achieve good accuracy for smaller epochs." But putting the two training tables next to each other turns up something better than that. Epochs are the wrong knob.

Two runs hit exactly 99.15%. Network C at fifteen epochs and batch 128 takes 29.95 LAN hours. Network B at five epochs and batch 4 takes 9.98. Same accuracy, 3.0× the budget, and the two numbers sit in different tables so the comparison is never made.

The marginal rates say it too. On Network B, tripling the epochs buys 0.83 accuracy points for 11.6 LAN hours, 0.072 points per hour. Dropping the batch from 128 to 4 buys 1.21 points for 4.18 hours, 0.289, four times better. On Network C it is 0.050 against 0.275.

Then switch to WAN and the ranking flips. Network B at batch 4 costs 112.71 WAN hours against Network C's 91.99, because a smaller batch means more iterations and every iteration pays the round complexity of every protocol in it against a 58 ms ping. So the budget has two dimensions. Bytes per epoch are fixed by the architecture, so on a LAN you buy accuracy with batch size, Network B from batch 128 to 4 costs 1.7× the time. Rounds per epoch scale with iteration count, so on a WAN that identical purchase costs 6.3×.

Neither version tracks this. The 2019 revision actually made it harder to see: it dropped the cleartext-baseline and 4PC columns, so the two tables now share fewer axes than they did in the version I read.

P.S.: the four-party typo

This totally breaks security! It should be P₁ sends ⟨Y⟩^L₁ to P₂ and ⟨X⟩^L₁ to P₃ (shown correctly in Algorithm 6).

Correct, and confirmed three ways.

Section 3.2 of the version I read says P₀ sends ⟨X⟩₀ to P₂ and ⟨Y⟩₀ to P₃, "similarly, P₁ sends ⟨X⟩₁ to P₂ and ⟨Y⟩₁ to P₃." Algorithm 6, fourteen lines below, says P₁ sends ⟨Y⟩₁ to P₂ and ⟨X⟩₁ to P₃, your correction, verbatim.

Two things break, not one. Under the prose P₂ holds ⟨X⟩₀ and ⟨X⟩₁, whose sum is X, and P₃ reconstructs Y the same way, so security against a single semi-honest corruption, the entire threat model, is gone without anyone deviating. But the prose also cannot compute anything: P₂ needs ⟨X⟩₀·⟨Y⟩₁ and P₃ needs ⟨X⟩₁·⟨Y⟩₀ for the four terms to sum to XY, and neither can build a cross term out of two shares of the same matrix.

The code agrees with you rather than with the prose, and it names the swap. In funcMatMulMPC, the 4PC branch sends X in "NATURAL" order and Y in "UNNATURAL" order, and "UNNATURAL" is defined as exactly the crossover:

if (partyNum == PARTY_A)  sendVector<T>(vec, PARTY_D, size);
if (partyNum == PARTY_B)  sendVector<T>(vec, PARTY_C, size);

With partner(PARTY_A) = PARTY_C, P₂ ends up with ⟨X⟩₀ and ⟨Y⟩₁ and P₃ with ⟨X⟩₁ and ⟨Y⟩₀. Algorithm 6, exactly.

The typo is gone from the current version, but only because the four-party construction went with it. The 2019 revision drops the 4PC protocols, the 4PC complexity table, and the 4PC columns from every experimental table, and the phrase "four-party" does not appear in it once. The 2018 revision is still served by the archive and still cited.

What ties it together

Four of the five questions turn out to be the same question, which is Question 4.

Z_2⁶⁴ was chosen for the linear layers, where the cost is 9.7 ms and 1.69 MB. It forced Π_SC into existence, which is 45.8% of DReLU, where the cost is 109.8 ms and 10.88 MB. It put a seam between two functionalities that have one caller each and it is the same caller. It created a range condition that is proved in DReLU and never propagated. And it ruled out the transform-domain idea in Question 3, since a 2-group has no roots of unity to build one from.

None of that makes the choice wrong. It makes it unpriced. The paper argues for the ring in one paragraph about GEMM performance and then pays for it in four places without totalling the bill, and the counterfactual, everything over Z_2⁶⁴−1, no Π_SC, one functionality with a clean signature, is still not in either version.

Questions written 21 March 2025 against the May 2018 revision. Verified September 2026 against both published revisions and the reference implementation at commit 5496fd5 (2022-10-08). Every number here is recomputed from those sources, so it can be checked or contradicted.