Carry the Ciphertext, Not the Data: Encrypted Mobile Agents for Cross-Silo Private Synthetic Tables

When the attributes of one population are split across institutions, such as diagnoses held by a hospital, claims by an insurer, and income by a tax office, nobody can build a realistic synthetic table without learning how those attributes co-vary across sites. Today there are two ways to get that joint information. One is to pool the raw records, which the law often forbids. The other is to upload everything, encrypted, to a cloud server that computes on ciphertexts. The second route is expensive because encrypted data is orders of magnitude larger than plaintext and encrypted multiplication is slow. We propose a third route. A small program, a mobile agent (code that carries its own state from machine to machine and resumes execution at each stop), travels from silo to silo. At each silo it combines the encrypted columns it is carrying with that silo's own columns, which stay in plaintext and never leave. The result is the statistics a differentially private synthesizer needs, and no party ever sees another party's data.

The central observation is that moving the code to the data changes the cost of the cryptography. In a centralized encrypted pipeline every attribute is encrypted and every cross-attribute count is a ciphertext-times-ciphertext product. When the agent computes at the silo that owns an attribute, that attribute can stay in plaintext, and the product becomes ciphertext-times-plaintext. That operation is cheaper, avoids the key-switching step, and does not have to ship the large attribute at all. The question is therefore which silo should encrypt, which should compute, and in what order the agent should visit them. We treat this as a planning problem that simultaneously controls bytes moved, encryption depth consumed, and privacy budget spent.

Core Claim

Consider data that is vertically partitioned: silos hold different columns of the same aligned records. For this setting, a migrating agent can compute the marginal statistics used by the adaptive marginal-selection synthesizer AIM (AIM) using only ciphertext-plaintext products and additions. It encrypts only the lower-cardinality side of each cross-silo marginal and orders the hops so that the encrypted state it carries stays small. We claim this matches the synthetic-data quality of the fully encrypted centralized approach. We also expect it to reduce ciphertext traffic and runtime by a factor that grows with the cardinality imbalance between silos. It should also make high-cardinality attributes feasible, which is where encrypted marginal synthesis currently struggles.

The cost model is simple. Let attribute $a$ with domain size $|a|$ live at silo $A$ and attribute $b$ with domain size $|b|$ live at silo $B$, over $n$ aligned records, with $s$ slots per ciphertext (the number of values packed into one encrypted vector). Computing the $a \times b$ marginal by encrypting $a$ at $A$ and multiplying by $B$'s plaintext indicators costs

$$ \text{traffic} \approx |a| \cdot \lceil n/s \rceil \ \text{ciphertexts}, \qquad \text{work} \approx |a|\cdot|b|\cdot\lceil n/s\rceil \ \text{ciphertext-plaintext products}. $$

The encrypted side should therefore be the small-domain side. A 50-value zip-code bin at $B$ costs nothing in traffic, whereas a centralized design pays for $|a|+|b|$ encrypted columns and ciphertext-ciphertext products. The traffic term follows from one-hot encoding with column-wise packing, the layout FHAIM uses.

Relation to Prior Work

The closest work is FHAIM. It runs AIM's select, measure and generate phases on CKKS-encrypted one-hot records held by a single data owner, on a single untrusted server. It supplies three techniques we reuse directly. The first is replacing AIM's absolute-value selection score with a squared L2 score, so selection needs no high-degree polynomial approximation of absolute value. The second is having the owner pre-sample and encrypt the privacy noise. The third is a restricted decryption oracle that reveals only the index of the selected marginal. FHAIM reports training in roughly 11 to 30 minutes on Breast Cancer, COMPAS and Diabetes, with utility comparable to plaintext AIM at $\epsilon=1$ (FHAIM summary). FHAIM has no notion of multiple owners, of partitioned columns, or of computing at the data. Our contribution is exactly the part that multiple silos make possible: plaintext computation at the owner, and the resulting encrypt-or-compute assignment and visit order.

AIM defines the selection loop we run and reports a 1.6x average error reduction over the next best mechanism. It also names the limitation that motivates us: marginal methods degrade on high-cardinality attributes. Under encryption that limitation is sharper, because every domain value is another encrypted column.

The migration side supplies execution machinery but no privacy. Matrix passes a serialized orchestrator state between stateless workers and reports 2.1x to 15.4x throughput gains from removing the central scheduler. It does so inside a trusted cluster, with plaintext state any host can read. We keep the state-passing design and encrypt the state. Bartocci and colleagues' fire-and-forget agent workflows (Hermes/UBioLab) motivate the asynchronous execution model, in which silos need not be online together.

Liu et al.'s disjoint itinerary planning (DMAIP-E) shows that ignoring the return distance to the sink is costly: first node death moves from round 280 to round 650 once that distance is modeled. We adapt this lesson. Our "sink" is the decryption party, and our cost includes the encrypted state that grows along the route. That growth is the state-bloat problem the migration literature leaves open.

Two works constrain the design. Fu and Xu's constraint models for agent execution (Fu and Xu) highlight that hosts can tamper with agents. We therefore state an honest-but-curious host assumption and treat integrity as out of scope. HEMET shows that designs which reduce raw operation counts can still lose under encryption if they deepen the chain of multiplications; that is, "mobile" in HEMET refers to mobile network architectures, not agents. This warns us that hop order, not just hop count, determines depth.

Research Program

System. The agent's state consists of the synthesizer's current model estimate, the list of candidate marginals, the privacy accountant, and a bag of encrypted indicator columns. Records are assumed aligned across silos by a prior private join, which is standard in vertically partitioned learning; we will state this assumption rather than solve it.

One marginal, step by step. To compute a marginal whose attributes span silos $A \rightarrow B \rightarrow C$, the agent proceeds as follows. At $A$, it encrypts $A$'s indicator columns. At $B$, it multiplies them slot-wise by $B$'s plaintext indicators. At $C$, it multiplies by $C$'s plaintext indicators, sums across slots with rotations, and adds pre-encrypted noise.

Depth. Each ciphertext-plaintext product consumes one rescaling level. A $k$-silo marginal therefore needs $k-1$ levels plus the reduction. For the 2- and 3-way marginals AIM favors, this fits within a leveled CKKS budget with no bootstrapping.

Selection. Selection scores are computed from the encrypted marginals with FHAIM's squared L2 score and decrypted through a restricted oracle. We will compare two decryption arrangements: a single oracle as in FHAIM, and a threshold key shared by the silos.

Planning. For each selected marginal, the planner chooses which silo encrypts and the order of the remaining hops. For a batch of marginals in one round, it chooses a route. Its objective is traffic plus weighted computation, subject to the level budget. Intermediate products of $|a|\cdot|b|$ columns are the bloat we must control, so the planner prefers to multiply in the largest-domain silo last. We will prove the cost model for the two-silo case, give a greedy ordering rule for longer chains, and measure how far greedy is from exhaustive search on small instances.

Privacy analysis. Hosts see only ciphertexts. The oracle sees only noisy scores and indices. The released marginals carry Gaussian noise accounted exactly as in AIM, so the end-to-end differential privacy guarantee is unchanged from AIM's. We will spell out the collusion cases, for example the final host colluding with the oracle, and what each case reveals.

Baselines

The naive reference point is independent local synthesis. Each silo runs plaintext AIM on its own columns at the same $\epsilon$, and the synthetic columns are concatenated with no cross-silo correlation. This sets the floor that any cross-silo method must beat on cross-silo marginal error.

The upper reference is plaintext AIM on the pooled table with a trusted curator. It is run with the same workload, the same $\epsilon$ in {0.3, 1, 3}, the same attribute binning, and AIM's default annealing. Our method should approach this line, not exceed it.

The strongest competitor is FHAIM extended to multiple owners in the most direct way. Every silo encrypts all its one-hot columns under a shared key and uploads them to one server, which computes cross-silo marginals by ciphertext-ciphertext products and runs FHAIM's selection and measurement. We will reimplement it in the same CKKS library, on the same hardware, with the same parameter-selection procedure, so any difference comes from the architecture and not the implementation. The reported number to beat on runtime is FHAIM's 11 to 30 minutes of training on Breast Cancer, COMPAS and Diabetes (FHAIM). Per-dataset accuracy was not reported on Lacuna, so we will measure utility ourselves. Beating this baseline means three things together: workload error within the confidence interval of centralized FHAIM, at least a 2x reduction in total ciphertext bytes moved, and lower wall-clock time on vertically partitioned Adult and Census Income. The gap should widen as a high-cardinality column is added.

Two ablations isolate the key ingredients. The first keeps migration but encrypts both sides of every marginal; this removes the plaintext-at-owner advantage. The second keeps plaintext-at-owner but uses a random encrypt-or-compute assignment and a random hop order; this removes the planner. For vertical data, federated diffusion synthesis (DP-FedTabDiff) addresses horizontally split clients rather than split columns, so it is not a like-for-like competitor. We will report it only on the horizontal control described below.

Why not just…?

Why not just have each silo send encrypted marginals to a server and add them? For horizontally partitioned data this is correct and simpler. Marginals of disjoint record sets simply add, so no agent and no multiplication is needed. We therefore restrict the claim to vertical partitions, where a cross-silo count is a sum of products of indicators held by different parties and cannot be formed by adding locally computed counts. We will include a horizontal control in which we expect encrypted aggregation to be as good as our method, which confirms the scope boundary.

Why not just use FHAIM centrally? This alternative is a real threat on small, low-cardinality tables, where uploading every encrypted column may cost only minutes. The cost model predicts our advantage grows with the domain-size imbalance between silos and vanishes when all domains are tiny. The cardinality sweep in our experiments is designed to show where the crossover lies rather than assume it. If the crossover sits at cardinalities nobody uses, the method is not worth adopting, and we will report that.

Why not just use secure multi-party computation or vertical federated learning? Multi-party protocols need all silos online and many interactive rounds per multiplication, which is the objection FHAIM itself raises. Encrypted vertical federated learning in the OARF benchmark reports estimated training times of hundreds of hours (OARF). Our agent needs one pass per marginal batch and tolerates silos being offline between hops. We will measure message count and required concurrent availability against an additive-secret-sharing implementation of the same marginal computation, on a simulated wide-area link.

Why not just synthesize locally and join? Independent synthesis loses every cross-silo correlation by construction, and small silos drown in noise. That is why it appears as the floor baseline rather than a competitor.

Proposed Experiments

Data and splits. We will vertically split Adult and the other AIM suite tables (AIM), Census Income and Credit Default from the DP-FedTabDiff suite (DP-FedTabDiff), and COMPAS, Diabetes and Breast Cancer from FHAIM's evaluation. Columns will be assigned to 2, 3 and 4 simulated silos, with attribute placement chosen to create cardinality imbalance.

Metrics. Utility is measured as AIM's average workload error on all 3-way marginals, reported separately for marginals that cross silos. Downstream utility is the accuracy of a classifier trained on synthetic data and tested on real data. Cost is measured as ciphertext bytes moved, wall-clock time, and levels consumed per marginal.

Decisive checks. The first check is the cardinality sweep. We re-bin one attribute from 10 to 1000 values and plot bytes and time for our method against centralized FHAIM. The cost model predicts linear growth in the encrypted-side domain for our method and in the total domain for the baseline. If the measured curves do not separate, the core claim fails. The second check is planner value. The planner should beat the random-assignment ablation on bytes and time with no change in error; if random is as good, the planning contribution is unnecessary. The third check is the horizontal control, where our method should show no advantage over encrypted aggregation. The fourth is a robustness check under high-latency simulated links, confirming that the one-pass agent keeps its advantage over the interactive multi-party baseline as round-trip time grows.