“At first glance, MPC seems a bit like magic. The cool thing about working with it then, is that you get to be a magician,” as Louis Lindgaard put it when he finished his master’s thesis with us, on our Confidential Computing platform.
We probably all wish for better insights that can improve the health sector, but we also value our privacy, and wish to protect our data from breaches. Maybe you know that at Partisia, we work to solve this problem using Multi-Party Computation (MPC) and cryptography. Our Confidential Computing platform, which uses these techniques, allows researchers to analyse data while keeping it encrypted.
With Confidential Computing, we can run secure analyses on sensitive data from several parties, without copying the data, and without the parties revealing it to each other. In doing so, we must be vigilant in ensuring that no one can infer something they shouldn’t from the bits and pieces exposed along the way.
This is the problem Louis took on, and it is a subtle one. When you run analytics on encrypted health data, joining and filtering records can leak structure: not the values, which stay encrypted, but the order of the rows.
To mitigate this, data must be shuffled, like a deck of cards. The question was whether a brand-new linear-time shuffle could do it more cheaply for us in Confidential Computing.
In November a new paper was published. Within about a month it landed on a problem we had been looking at in the OSCAR DREAM project (supported by Innovation Fund Denmark), so Louis and the Confidential Computing team did the obvious thing. We put it to the test, to see whether it could make one of our privacy safeguards cheaper. The answer was not the one we expected, and that turned out to be the interesting part.
MPC: the thing privacy-preserving analytics has to get right
There is real value locked inside health records (which treatments work, for whom, what tends to happen next), and a real duty to protect the privacy of the people those records describe. MPC lets several organisations compute a shared answer over their combined data while each keeps its own records encrypted and in its own hands. The result comes out; the raw data never meets. That is what powers our Confidential Computing platform.
In the OSCAR and OSCAR DREAM projects we have worked to enable analysis across different hospitals and registers so researchers can put statistical questions to Danish health data without anyone handing over the underlying records. Much of that work has gone into safely merging those data sources. We must join tables, match records about the same person across sources, and then filter, keeping only the rows that meet some condition. And here is the sharp edge: joining and filtering can leak information even when every value stays encrypted.
Example: how structure can leak information
Picture two hospitals. Hospital A holds basic records keyed on the social security number. Hospital B holds the same patients with a sensitive field, their HIV status. A query joins the two and then keeps only the patients who are HIV-positive. Under MPC, every value (the IDs, the ages, the HIV flag) stays secret-shared and is never revealed in the clear.
Now watch what can still go wrong. Hospital A uploaded its rows in a known order, and the join keeps that order, so A can recognise the position of each of its own rows. The query is public, so everyone knows the filter keeps HIV-positive patients. When the filter removes the rows that fail, A sees which positions survived, and reads its answer off the order alone: these patients are HIV-positive, those are not. No value was decrypted. The encryption held the whole way. The leak came from the structure, from the order of the rows, not from the numbers inside them.
This matters because it is exactly the kind of inference that data regulations exist to prevent. A patient is entitled to seek care from a secondary provider without their primary doctor learning of it, and a system that quietly leaks that fact is not one you can run on a population. Confidential Computing is designed so this leak does not occur. The point of the work here was not to patch a hole, but to make the safeguard that prevents it cheaper, and to let the platform safely support more of these operations.
The fix is an old idea: shuffle the deck
The safeguard has an intuitive name. Shuffle the rows of each table by a hidden order before any joining or filtering, and the position of a row stops carrying information. A can no longer match a surviving row to its own patient, so the filter tells it nothing. The values were already encrypted; now the order is meaningless too.
The hard part is shuffling when no single party may see the data and one party might try to cheat. The approach Louis worked with does it as a half-shuffle: each party permutes the encrypted rows in turn, so that by the end neither side knows the combined order, while the protocol still catches a party that misbehaves. That last property has a name, active security, and it is the strong setting we want: correct, or it stops, even against a party that does not play by the rules.
The twist: you don’t get efficiency for free
Here is where the November result comes in, and where Louis’s thesis earns its keep. Building a secure shuffle the established way, as a circuit called a Waksman network, costs on the order of n log n work for n rows. In November, Dittmer, Nema and Ostrovsky published the first actively secure two-party shuffle that runs in linear time, by delegating the permutation to one party under homomorphic encryption instead of building a circuit. On paper, linear beats n log n.
However, an asymptotic win is not automatically a practical one. Because the homomorphic encryption that buys the linear bound is itself expensive, that cost can swallow the advantage at the input sizes you actually meet. The input size at which the new protocol becomes the better choice was an open question, and nobody had answered it. Louis did. His thesis is the first implementation study of that protocol. He built both it and the established Waksman shuffle into our Confidential Computing backend using the open-source FRESCO framework, and measured them against each other.
Here is what he found out: the cost of the homomorphic encryption dominates, so the established method stays faster for smaller input sizes, approximately up to the hundreds of thousands. When running queries on the populations of cities, the old method remains the better choice, but when analysing the entire population of Denmark, the new approach pulls ahead and makes a small but meaningful improvement.
Why we were eager, and why it still matters
Two things made this worth doing quickly. The timing was unusual: theoretical cryptography often waits a long time for practical use, and here a result from November met a concrete problem about a month after we had run into it. And a secure shuffle is not a one-query trick; it is a general building block that closes this class of structural leak and keeps working as the set of operations grows, which is why getting its cost right is worth the care.
The honest takeaway is the one we trust. We did not make our safeguards dramatically cheaper this time. We learned, precisely and on a real system, where a promising new method does and does not pay off, and we are the first to have done so. For a platform meant to run on sensitive data at the scale of a population, that kind of measured knowledge is worth more than a headline.
The person behind the work
Louis Godtfred Kastrup Lindgaard wrote his Computer Science thesis at Aarhus University, advised by Sophia Yakoubov, in partnership with Partisia and with support from Danil Annenkov, then team lead of Confidential Computing. The story of how it came together is a small lesson in luck meeting preparation: Sophia suggested a thesis on shuffling, the Confidential Computing team had a live problem waiting for exactly that, and the protocol that fit it had been published only weeks earlier. By his own account, Louis came to study MPC almost by accident, and stayed because he found it to be one of the most interesting things you can do with math and computers. We are glad he did.
Read further
- Samuel Dittmer, Rohit Nema, Rafail Ostrovsky, “Linear Secret-shared Shuffle with Malicious Security”, Cryptology ePrint Archive 2025/2137.
- Abraham Waksman, “A permutation network”, Journal of the ACM, 1968. The established circuit-based shuffle used as the baseline.
Want to explore what Confidential Computing could unlock from your own sensitive data, without ever exposing it?
