Encrypted Push-Pull Without Homomorphic Division

Many real networks of learning devices, such as drone swarms, vehicles, and sensor grids, have one-way links: device A can hear device B, but B cannot hear A. Optimization algorithms for these directed networks exist. They are called push-sum and push-pull, and they correct the imbalance of one-way mixing by having each device divide its model by a running "mass" estimate. Everyone who has looked at encrypting these algorithms has run into the same problem. Practical homomorphic encryption, meaning encryption that lets you add numbers while they stay encrypted, cannot divide one encrypted number by another. Emulating division inside fully homomorphic encryption triggers bootstrapping, the costly noise-reset step that dominates encrypted computation.

This note argues that division is the wrong obstacle. Each device already holds its own model, so it may legitimately learn the sum of what its in-neighbors pushed to it and divide in plaintext. The real problem is narrower. The device must learn only that sum, even though it cannot talk back to the neighbors that sent it. We propose to solve this with a threshold decryption committee that is reached over multi-hop directed paths. Strong connectivity is what guarantees those paths exist, so the connectivity assumption turns into a cryptographic latency. We also propose an exact integer mass-splitting rule that keeps encrypted gradient tracking from drifting. The whole protocol uses only homomorphic additions, so it needs no bootstrapping and no multiplicative depth.

Core Claim

Encrypted optimization over directed, time-varying graphs can run at additive-encryption cost if three pieces are combined.

The first piece is receiver-side plaintext normalization. The in-neighbors of node $i$ encrypt their push messages under a public key belonging to $i$. Node $i$ adds the ciphertexts together, and after decryption divides by its mass variable in the clear.

The second piece is sum-only decryption. The secret key of node $i$ is split with Shamir secret sharing among a committee of $k$ other nodes. Node $i$ forwards only the aggregated ciphertext to the committee. At least $\tau$ members must return partial decryptions over directed paths back to $i$. The individual messages therefore never become decryptable by $i$ alone.

The third piece is exact integer mass splitting. Before encrypting, each sender quantizes its tracking vector with stochastic rounding. It then splits the resulting integer vector into integer shares that sum exactly to it, one share per out-neighbor. Column-stochastic mass conservation therefore holds bit-for-bit in the encrypted integer domain.

The price of this design is delay. The aggregate that node $i$ forms at round $t$ becomes usable at round $t + d_i$, where

$$d_i = \min_{C \subseteq \mathcal{C}_i,\, |C| = \tau}\; \max_{c \in C} \big(\mathrm{dist}(i,c) + \mathrm{dist}(c,i)\big).$$

Here $\mathcal{C}_i$ is the committee of node $i$, $\tau$ is the decryption threshold, and $\mathrm{dist}$ is directed hop distance. The formula says $d_i$ is the directed round-trip time to the $\tau$-th fastest committee member. Strong connectivity makes $d_i$ finite. Under joint connectivity over a window of $B$ rounds, $d_i$ inflates by at most a factor of order $B$ per hop, because each hop may have to wait for its link to reappear. The algorithmic question is whether push-pull still converges exactly when it runs on decryptions that are $d_i$ rounds stale. The systems question is what this costs compared with homomorphic division or symmetric-graph protocols.

Grounding in Prior Work

Four plaintext papers supply the optimization method. On the distributed optimization over directed networks introduces D-DGD, which cancels directional bias by adding an auxiliary variable to each node's state and dividing by it. SAB-TV introduces push-pull gradient tracking over time-varying directed graphs: models are pulled through row-stochastic weights and gradient trackers are pushed through column-stochastic weights. DSGTm-TV adds heavy-ball momentum and lets nodes use uncoordinated step sizes. We reuse the update rules from these papers unchanged, except that nodes see delayed aggregates. All four papers send states in plaintext, so any in-neighbor sees every model and gradient.

Compressed Push-Pull constrains our design. It shows that gradient tracking over directed graphs stays stable only under unbiased compression. Encryption-friendly quantizers such as BatchCrypt's clipping in BatchCrypt and the sign quantization in RSA are deterministic, which violates that condition. Our stochastic-rounding-then-exact-split rule satisfies both constraints: it is unbiased, and it is exact in integers.

The closest cryptographic work motivates the gap. D-MHE runs decentralized learning with multiparty BFV encryption and reports 91.18% on MNIST and 68.25% on CIFAR-10 at about 133 seconds per iteration. Its ciphertext conversion step is a two-party interaction, so it presumes that links work in both directions. RSA supplies the Shamir-threshold idea we borrow, which tolerates 50% dropouts, but RSA assumes a central server. mMFHE shows the failure mode we must avoid: multi-key decryption deadlocks if any single party is missing.

On overhead, Circuit Bootstrapping identifies bootstrapping as the dominant cost, and A Systematic Comparison of Encrypted ML reports 56 GB and about 549 seconds for a single HE-Transformer prediction. Together these explain why a division circuit evaluated at every node in every round is a non-starter. Our protocol avoids that circuit entirely instead of optimizing it.

Research Program

The first thread is the protocol itself. Setup is one-time. Each node $i$ generates a BFV key pair and publishes the public key by flooding it along directed paths. It picks a committee of $k$ nodes, preferring nodes with short directed round-trips. It then sends each member an encrypted Shamir share of its secret key along a directed path to that member.

Each online round $t$ proceeds as follows. Sender $j$ pushes to each out-neighbor $i$ an encryption, under $i$'s key, of its integer share of the tracking vector together with its mass share. Node $i$ adds whatever ciphertexts arrive that round. Because nothing has to cancel, a missing sender costs nothing. Node $i$ then forwards the single aggregate ciphertext toward its committee. Committee members return partial decryptions along return paths. Node $i$ combines any $\tau$ of them and applies the push-pull step using the aggregate from round $t - d_i$. BFV's slot packing, the technique from CryptoNets, carries whole parameter vectors in a few ciphertexts.

The second thread is analysis. We will extend the linear-rate argument of SAB-TV to push-pull with node-specific bounded delays $d_i$, treating the delays as extra virtual nodes in an augmented directed graph. We expect linear convergence to the same neighborhood, with a contraction factor that degrades as the maximum delay grows. We will derive a step-size bound that depends only on local quantities, namely $d_i$ and out-degree, which addresses the complaint that directed methods need global spectral constants. We will also prove that exact integer splitting keeps the network-wide sum of trackers equal to the sum of quantized gradients, so the only added error is zero-mean rounding noise.

The third thread is security. The threat model is honest-but-curious nodes. Node $i$ learns individual messages only if it colludes with at least $\tau$ of its committee. We will also measure the residual leakage from the aggregate itself. When a round delivers only one in-neighbor to $i$, the aggregate equals that neighbor's message. In that case the protocol withholds the partial decryptions and defers the aggregate to the next round, and the analysis must show that this deferral preserves convergence.

Baselines

The naive reference point is plaintext push-pull: SAB-TV and DSGTm-TV run with no privacy on the same graphs, data, and step-size grid. This gives the accuracy ceiling and the minimum communication and time. On MNIST digits 3 versus 7, SAB-TV reports over 97% test accuracy after 50 epochs. DSGTm-TV reports over 95% on 3 versus 5 in about 200 iterations. Our target is to land within 0.5 percentage points of these numbers at the same number of epochs, allowing extra rounds only equal to the delay.

The obvious encrypted competitor is homomorphic division. Every node's state stays encrypted under CKKS, which is approximate-arithmetic homomorphic encryption, and the reciprocal of the mass variable is computed by Newton iterations with bootstrapping. The ciphertext parameters and packing are identical to ours, and the Newton iteration count is tuned so that normalization error matches our quantization error. No reported result was found on Lacuna for encrypted push-sum or push-pull over directed graphs, so we will build this baseline ourselves. Beating it means at least an order-of-magnitude lower per-round wall-clock time at equal accuracy.

The strongest existing system is D-MHE, which reports 68.25% on CIFAR-10 at about 133 seconds per iteration and 56.7 MB per user on MNIST with 100 users. Because it needs two-way links, we run it on the symmetric subgraph, keeping only edges that exist in both directions, with the same model, data split, and tuning budget. On graphs where one-way edges are needed for connectivity, D-MHE either runs on a disconnected graph or requires those links to be made two-way. Beating it means matching its accuracy on graphs where it runs, while using all directed edges and tolerating time-varying links where it stalls.

The per-node pairwise-masking baseline is described under Why not just use pairwise masks? below. It uses zero-sum masks among the in-neighbors of each node, with seeds exchanged in setup, and runs on the same graphs. We also include plaintext push-pull with Gaussian noise added to the trackers, calibrated to a standard privacy budget, as the differential-privacy reference.

Three ablations isolate the key ingredients. The first replaces exact integer splitting with independent deterministic rounding of each share, to test the claim that this breaks mass conservation and causes tracking drift. The second sets the committee to $\tau = 1$ with the nearest node, which isolates how delay affects convergence. The third disables deferral of single-sender rounds, to measure the leakage-versus-speed trade.

Why not just…?

Why not just use pairwise masks, which are nearly free? Pairwise masks are a real threat on static directed graphs with reliable links. There, the in-neighbors of $i$ can share seeds during setup, and their masks cancel in the sum at no cryptographic cost. The scheme breaks when the set of senders that reach $i$ changes from round to round. Uncancelled masks then corrupt the aggregate. Repairing them requires telling the survivors who dropped, and that information must flow from $i$ back to its in-neighbors, which is exactly the missing direction. Our experiments sweep link-drop probability from 0 to 50%. We expect masking to win at 0% and fail as drops increase. If masking with delayed multi-hop repair turns out to match us at moderate drop rates, we will report the crossover honestly.

Why not just add differential-privacy noise? D-MHE reports 4 to 8 percentage-point accuracy drops for the differential-privacy baseline LEASGD relative to lossless encryption. In push-pull, noise injected into the trackers persists as a steady-state error floor, because the trackers sum up noise rather than averaging it away. Our differential-privacy baseline measures this floor directly on the same graphs.

Why not just symmetrize the graph or elect a coordinator? This would allow D-MHE or RSA to be used unchanged. Doing so discards one-way edges, and in range-limited or directional-antenna networks those edges are often what keeps the network connected. The experiment on symmetric subgraphs reports how often discarding them disconnects the network, and how much slower mixing becomes when it does not.

Proposed Experiments

The workloads are drawn from the file. We use synthetic logistic regression as in CPP, MNIST binary tasks as in SAB-TV and DSGTm-TV, and a small CIFAR-10 CNN matching D-MHE's setting, with 16 to 100 nodes. Topologies include random directed strongly connected graphs, geometric graphs with directional antennas, and time-varying graphs that are connected only jointly over windows of $B \in \{1, 5, 20\}$ rounds, plus independent link drops.

The metrics are optimality gap against rounds and against wall-clock time, test accuracy, bytes sent per node per round (including relay traffic along committee paths), measured decryption delay $d_i$ versus its predicted value, and the fraction of rounds deferred for leakage.

Three results decide the proposal. First, accuracy must stay within 0.5 points of plaintext SAB-TV and DSGTm-TV while per-round cost stays well below the homomorphic-division baseline. Second, the observed slowdown in convergence must track the predicted delay $d_i$ as $B$ grows. Third, the deterministic-rounding ablation must show tracking drift that exact splitting eliminates. If the delay penalty grows faster than linearly in $B$, the connectivity-as-latency view is wrong, and the protocol reduces to a static-graph method.