One-sided linkage: what leaks, the alternatives, and why simple looks right for now

Status: resolved - the send-everything pole this note explored shipped as the opt-in single-pass linkage strategy (the cascade stays the default). Its mechanism and disclosure are now normatively specified in PROTOCOL.md and summarized in EXCHANGE_REFERENCE.md; this note is kept for the rationale behind that choice and for the alternatives that were weighed but not built. See docs/notes/README.md.

When only one party is entitled to the result of a linkage, the other party still has to help compute it, and that help leaks a little about which of the helper's own records matched. This note maps what leaks, walks the realistic alternatives and what each of them leaks instead, and lays out why the approach that shipped, simple by design, is a defensible default.

It is design rationale. The mechanism it decided on is specified elsewhere (the links above); this note records the reasoning so the question does not have to be reworked from scratch the next time someone asks it. The discussion stays high level on purpose - the goal is to make the tradeoffs clear, not to re-specify any one mechanism.

The setup

Two roles matter. The receiver is the party that gets the result. The sender is the helper: it contributes its records so the receiver can find the matches, but it is not itself entitled to the answer.

A linkage runs as a sequence of rounds, one per linkage key, from the most precise key to the least. A key is a combined identifier - several pieces of personally identifying information concatenated together (name, date of birth, part of an SSN, and so on) - chosen to be precise enough that a match on it can be treated as definitive. When a record matches on a strong key it is set aside so it is not compared again on the weaker ones; the unmatched records "carry forward" to the next round. Setting matched records aside is an efficiency win, and it is also a privacy win for the receiver: it never sees that an already-matched record would also have matched on some weaker key.

Two facts hold throughout and are worth fixing in mind:

• The system assumes honest-but-curious partners operating under signed data-sharing agreements (the threat model the project adopts). They are not expected to tamper, but we still try to minimise what each side can learn.
• The size of each party's dataset is always revealed. So "the sender learns nothing" never means literally nothing - it means nothing about which records matched.

What the protocol offers today

There are two ways to run a one-sided exchange, and they leak in opposite directions.

The clean cascade. The sender is told which of its records have already matched, so it can drop them from the later rounds. The receiver gets a clean, minimised result. The sender learns which of its own records matched and - because the rounds run in a publicly agreed precision order - roughly how strong each match was. It never learns which of the receiver's records they matched to.

Naming precisely what leaks here matters, because it is easy to guard the wrong thing. The sensitive disclosure is membership: the sender knows its own record is, say, "Jane Doe," so "my record matched" tells it that the receiver also holds Jane Doe. The final association table - the pairing of the sender's records to the receiver's row numbers - adds almost nothing on top of that, because the receiver's row numbers are opaque integers that mean nothing without payload or identifiers attached, and a one-sided exchange withholds both from the helper (the withholdings and their fail-closed enforcement are specified in PROTOCOL.md and FILE_SYNC.md). So withholding the association table protects the least sensitive layer; the membership disclosure has already happened, round by round, and is intrinsic to dropping matched records. (The map does hold some signal in a few narrow cases - two of the sender's records mapping to one receiver row reveals the sender's own duplicates; row numbers that encode sort order leak rank; stable row numbers reused across exchanges can be correlated - but those are second-order.)

Send-everything. The sender is told nothing and simply contributes all of its records every round; the receiver tracks the one-to-one mapping itself. The sender learns nothing about matches - only the receiver's dataset size. The price is twofold: the full dataset moves across the wire every round, and the receiver sees more of the match structure within the overlap than it strictly needs - for example, that one of its records is also "close enough," under the agreed weaker rules, to additional sender records that the cascade would have suppressed.

The send-everything pole shipped as the opt-in single-pass linkage strategy (the cascade stays the default). It batches every key into one exchange, so the number of round trips stays the same no matter how many keys there are, and both parties must agree to use it, so they both consent to the extra receiver-side disclosure before any data moves. Its wire shape and disclosure are specified in PROTOCOL.md and summarized in EXCHANGE_REFERENCE.md; the analysis below describes the ideal this note weighed, and the shipped strategy realizes it in the one case where it is achievable.

The one place single-pass improves on the "sender learns nothing" ideal changes which of the leaks below is closable. For the sender to enrich its disclosed payload, or to receive its result in the both-output case, the receiver must return the sender its half of the association table - so those cases still disclose the helper's membership. But a non-receiving helper that discloses no payload needs nothing back, and there single-pass closes the leak at the wire: the receiver withholds the table so the helper's process never receives, and so never learns, its own membership. PROTOCOL.md owns exactly how; this note only records why that one case is closable and the others are not. The membership disclosure remains intrinsic and threat-model-accepted for the clean cascade (the helper must learn its matches to drop them) and for a payload-disclosing helper under single-pass (it needs its matched rows to enrich the overlap); in those, enforced non-output (below) keeps the tool from emitting the table but does not blind the helper at the wire.

That wire-level blindness also depends on the receiver holding its set size constant across rounds, since a shrinking set would let the sender read the per-round match counts straight off the size. That condition is necessary but not sufficient on its own -- the table withholding above is what completes it -- and it is specified with the strategy in PROTOCOL.md.

Why you can't just shuffle the leak away

There is a tempting shortcut worth heading off. A cardinality-only exchange looks as though it could hide which records are shared by having the sender shuffle the receiver's data before returning it, so the receiver counts matches but cannot identify them. (The count-only algorithm as specified works this way: psi-c's sender reorders the receiver's data under one permutation it keeps for the whole exchange, so the receiver counts matches it cannot attribute from the response order - psi-c-count-only.md has the construction.) The natural question is whether such a shuffle could hide which of the sender's records matched - keeping the clean cascade without ever telling the sender anything.

It cannot, for two reasons. First, in a full linkage the receiver is supposed to learn which records matched; a shuffle it could not see through would hide the answer from the receiver too, collapsing the linkage back into a cardinality count. Second, and more fundamentally, the leak we want to close is on the sender's side, and the sender owns both its records and its key. The matching encryption is deterministic by necessity - that is how equal records are recognised - so the sender can always re-encrypt any of its records and recognise it again, no matter how the pile is shuffled. Shuffling a party's own data in front of that same party hides nothing from it. The implementation already leans on this in the ordinary case: the sender permutes its own records before sending and reverses the permutation locally, unremarkable precisely because a party can always undo a permutation of its own data. Nor is there a salt that escapes it -- anything that stopped the sender recognising its own record would change the encrypted value, breaking matching for everyone.

The structural fork

Set the shuffle aside; the real obstacle is simpler. A clean later round requires that an already-matched record not appear in it, and only the owner of a record can leave that record out of its own input. So for the sender's matched records to be absent from the later rounds, the sender has to leave them out - which means it has to know which matched.

That is a fork with no free middle:

• Keep the clean cascade, and the sender necessarily learns which of its records matched, and roughly on which precision tier.
• Keep the sender blind, and nobody can drop its matched records, so it sends everything every round and the receiver sees the weaker matches the cascade would have suppressed.

You can sit anywhere between these - drop some tiers and not others - but every point trades one leak for the other in proportion. There is no point that is clean for the receiver and blind for the sender at the same time, as long as the protocol works by encrypting records and comparing them. That last clause is the whole constraint: the gating decision ("has this record already matched?") is computed from match results, and in an encrypt-and-compare design, acting on a result means someone has seen it.

Alternatives, and what each leaks instead

Taking heavyweight secure computation as a known fallback (described below), the space between the two poles holds more than "pick your leak direction." There are three levers: re-choreograph the same encryption engine, move the trust, or swap the primitive.

Approach	What the sender learns	The receiver's extra disclosure	Cost / trust
Clean cascade	membership + rough tier	none (minimised)	cheap
Send-everything	dataset size only in the ideal; the shipped single-pass returns the sender its table unless it is a non-receiving helper disclosing no payload, whose table is withheld at the wire	fuller match structure in the overlap	high bandwidth
Send-everything + receiver self-censor*	dataset size only	contention only	medium bandwidth
Batched / coarsened drops	membership + coarse tier	none	cheap
Both-sided + enforced discard	the result, then discards it	none	cheapest; trust is policy
Homomorphic-encryption PSI	next to nothing	contention only	heavy compute
Trusted hardware (enclave)	nothing beyond output + size	none	cheap compute; trust is hardware
Secure computation (circuit-PSI / MPC)	nothing	nothing	very heavy

* Worked out in discussion; should be validated before being relied on.

Re-choreograph the same engine.

• Receiver self-censor (with chaff). The receiver drops its own already-matched records from the later rounds and pads back to a constant size with records that match nothing. The sender stays blind (the size never moves), and the receiver stops learning the redundant weaker matches for records it has already matched. A residual remains - a still-unmatched receiver record colliding, under a weak rule, with a sender record already claimed by a stronger match - which cannot be removed without dropping the sender's record, and that takes us back to the cascade leak. This appears to narrow the receiver's disclosure substantially for only a bandwidth cost; because it was reasoned out rather than implemented, it should be validated before being relied on. The construction, in full:

  Round 1 (strongest key): the receiver sends all N records and learns its matches. Round 2 (a weaker key): the receiver wants to find matches for its still-unmatched records without re-learning anything about the ones already matched, so it sends the weak-key values of the unmatched records plus chaff padded up to N, where the chaff is constructed to match nothing. The sender, seeing N records both rounds, learns only the constant size. The receiver no longer sees the redundant weaker matches for its already-matched records. What remains is the "contention" case: a still-unmatched receiver record R' that matches, under the weak rule, a sender record already claimed by a stronger match to a different receiver record. R' is unmatched (so the receiver would not have dropped it) and the claimed sender record is the sender's to drop (so the receiver cannot remove it), which is why this residual cannot be closed without returning to the clean-cascade leak. The contention signal is largely about near-duplicates and data quality, arguably the least sensitive thing on the menu.

  Chaff needs care in general: chaff that can never match noises only the input sizes, not the match counts, while chaff that does match has to be constructed so it never corrupts the real result. This construction relies only on the safe, never-matching kind.

• Batched or coarsened drops. Tell the sender to drop in lumps rather than strictly round-by-round, or combine identifiers into fewer, stronger keys so there are fewer rounds. This keeps the cheap cascade but blurs the secondary "which tier" part of the leak.

Move the trust.

• Enforced discard - "the tool is the trust boundary." Run the exchange so the sender's software simply never writes or exposes the result. Data-sharing agreements are written about what software persists and exposes, not about what could in principle be inferred from memory, so "the shipped tool produces no sender-side output" is a control a compliance reviewer can actually evaluate. Paired with the idealized send-everything pole there would be genuinely nothing in the sender's memory to discover; the shipped single-pass reaches that ideal for a non-receiving helper disclosing no payload -- its table half is withheld at the wire, so there is genuinely nothing in its memory either -- but for a payload-disclosing helper, or the clean cascade, it returns the sender its own half of the association table, so like the clean cascade it there leans on the operator not inspecting transient state. Either way the residual sits on the malicious side of the honest-but-curious line, which the threat model already excludes.
• Trusted third party or trusted hardware. Hand the matching to a mutually trusted party, or to a hardware enclave neither side can see into. Both relocate the trust rather than removing it.

Swap the primitive.

• Homomorphic-encryption PSI. The receiver queries under encryption and the sender computes blind, learning next to nothing - not even the receiver's exact dataset size. It is tuned for the lopsided shape a one-sided exchange often has (a small querying side, a large helping side).
• Secure computation (circuit-PSI / MPC). The matching and the running "already matched?" bookkeeping happen inside a computation neither side can see into. Done fully, the sender learns nothing about which of its records matched, and with dummy padding not even how many. This is the only approach that genuinely removes the leak rather than relocating or blurring it - and it is a different engine, not an addition to the current one. The project already records this direction as the route for threshold and weighted matching (DESIGN.md); the same core would address this disclosure at the same kind of cost.

The deployment envelope prunes the list

Several of those alternatives do not survive the project's own constraints. The tool is meant to run in a standard browser, on hardware agencies already have, using software already commonly approved - and on datasets large enough (up to the tens of millions of records the design targets) that the in-browser budget is already tight.

Under that envelope:

• Trusted hardware is out. A browser has no access to an enclave, and enclaves need specific silicon and an attestation chain.
• Homomorphic-encryption PSI and full secure computation are not feasible in the browser at this scale today. Both are heavy, and the available libraries still demand expert tuning rather than dropping in.

So the heavyweight fixes are not merely more than the current threat model warrants - in the browser they are simply off the table. What fits the envelope is exactly the in-engine choreographies plus the policy and operational controls: which cascade, how much to blur, and enforced non-output backed by the agreement.

The binding constraint is the browser, not the project as a whole. The command-line and container path has native compute and no sandbox, so if the threat model ever hardened to a malicious adversary, a heavier crypto core would more plausibly live there - at the cost of splitting behaviour between the two front ends.

The decision that was taken

Under the honest-but-curious model the project adopts, the residual leak in the clean-cascade approach is accepted - a helper learning which of its own records matched, and roughly how strongly, is a modest disclosure between agencies that have already agreed to share the overlap. The clean cascade is the implementation's default; the send-everything pole ships as the opt-in single-pass strategy described above, chosen when its fixed round-trip count is worth the extra receiver-side disclosure. Combined with the deployment envelope - which rules the heavyweight alternatives out in the browser regardless - the chosen approach is the simple in-engine one, with the live levers being the choreography choice, the blurring measures, and enforced non-output on the helper's side. The secure-computation route, already scoped for threshold and weighted matching, is where to look if the model ever hardens - most plausibly in the command-line path rather than the browser.

The mechanism that resulted is specified in PROTOCOL.md and shown to operators through EXCHANGE_REFERENCE.md; the send-gate that enforces non-output is in FILE_SYNC.md. What remains in this note is the rationale behind that choice and the alternatives that were weighed but not built (self-censor, the heavyweight fixes), kept so they need not be reconstructed if the threat model changes.

A partial run is a disclosure, not just a worse result

Everything above weighs what a complete run discloses. A run that goes ahead on only some of the agreed linkage keys is a separate question, and it came out differently: it is refused outright, on every path, rather than warned about.

The reason is that the shortfall is not private to the party that has it. The rounds are lockstep, so an agreed key runs whether or not this party can populate it, and a key it populates for no record is a round it enters with an empty contribution. That is a different shape on the wire from a key that ran with values and matched nothing - one is an empty set, the other a populated set with no matches - and the two are distinguishable by the partner's software, in both directions, per key. The single-pass strategy sharpens it further: its index table is per-record, so an under-covered sender hands the receiver exactly which rows it had nothing for on which key. So the partner does not merely get a thinner result; it learns which of the agreed identifiers this party could not supply, at whatever granularity the strategy allows. That is a fact about this party's own data holdings, and nothing in the agreed terms, the consent facts, or the invitation declares it or asks the operator to consent to it.

There is a compliance half as well. The exchange record's matchingBasis is derived from the agreed terms, so a partial run would write a disclosure record naming identifier fields this party never contributed a value for. The record's existing over-claim rationale covers fields the terms do not reference; it does not cover fields the input never populated.

The record build therefore takes the fields the run contributed as an input of its own and refuses to write a record whose basis reaches past them, on whatever path assembled that build (EXCHANGE_RECORD.md). Two alternatives were weighed and left. Narrowing the basis to the contribution keeps a record for every run, but the contributions are per-party and asymmetric, so the two parties' records would then state different bases for one agreed set of keys - a term of the agreement turned into a per-party fact. A second refusal at the run boundary would stop the run itself, which the partner sees, for a local artifact the partner never reads. Refusing the build alone costs nothing the run needs: the record is a secondary artifact, built after the exchange has fully succeeded, and its failure leaves the result and the receipt untouched and reports the loss.

Why a warning cannot cover either half:

• Consent. The linkageKeys consent fact states that the agreed keys are what the run computes. A partial run does not honour it, and the operator warned about the shortfall is not the party whose consent is at stake - the partner is, and the partner sees no warning. Warn-and-proceed puts the choice with the wrong side.
• Unattended runs. A recurring exchange is a scheduled job. A warning on stderr in a discarded log does not reach anyone before the data moves, so the only tier that binds an unattended run is a refusal.
• The remedy is out of band anyway. A file that cannot fulfil the agreed terms needs new terms, and terms are agreed on between the parties, not adjusted locally. Since the fix is a conversation with the partner, letting the run proceed buys nothing except an exchange neither party agreed to. Once built, the in-band terms change decided for payload will hold that conversation through the run itself: the changed terms will reach the partner on the terms exchange, and the partner will confirm or apply them before any data moves (payload-as-agreed-terms.md).

The rule that resulted is one line - a run is refused unless the agreed terms declare at least one linkage key and the input can satisfy every one of them, none declaring cleaning that drops every record - and it is graded in one place in @alcove/core, enforced at the pre-send boundary every front end passes through, so no surface holds a threshold of its own. Its operator-facing form is in CLI.md and COMMUNICATION.md.

Two consequences are deliberate. A run that becomes unrunnable because the data drifted (a column dropped from a recurring feed) fails rather than degrading quietly, which is the intended trade: a silently narrowed linkage is worse than a stopped one. Once built, the payload columns a recurring exchange includes will be held to the same trade through the agreed terms rather than through a record of their own: a column added or dropped on either side will be a terms mismatch refused before any data moves (payload-as-agreed-terms.md). And the check is over column shape, so it cannot catch a field whose every row cleans to empty - that residual stays with the runtime coverage sweep, which is why the sweep is worth keeping beside this rule.

See also

• payload-as-agreed-terms.md - the payload column set held as agreed terms, compared at the handshake, with no separate record.
• DESIGN.md - the secure-computation extension already scoped for threshold and weighted matching, which would also address this disclosure.