Imagine a doctor has developed a new algorithm for estimating cardiac risk. Let’s say it’s a simple addition, such as risk = age + 3. The patient, Alice, may wish to keep her age (= 27) secret and the doctor may wish to protect her algorithm (risk = age + 3). As shown in the figure, these two parties could agree to do the following. First, they could both subtract a random number from their secret (Step 1) and then share the differences (Step 2). Next, they could each add their random number to the other party’s share (Step 3) and then exchange the results of those calculations (Step 4). Finally, one (or both) parties could add the shares, revealing the patient’s risk (= 30) without, at any point, transmitting either the patient’s age or the doctor’s secret.
Mathematically, how does this work?
If you kept track of all the terms, you see that risk = (age – rp
) + rd
) + rp
= age + (rp
) + (rd
) + wd
The middle two terms evaluate to zero, simplifying the expression to the desired result, risk = age + wd.
Essentially, both parties inject noise into a communications protocol, the noisy signal undergoes previously agreed-upon linear mathematical operations, and then, the noise is removed at the very end. Since both parties only disclose/share the sums
of their noise terms (rp
, respectively) is what protects the secrets.
This simplified example omits details required to make such systems work in practice – most obviously, in this toy scheme with only one secret per side, the patient can immediately obtain the doctor’s secret, wd
, by inverting the algorithm (risk – 27 = 3). As soon as the secrets on both sides become more complex, such as by involving more than one term on each side, it becomes exceedingly difficult for either party to learn (or even estimate) the other party’s secrets. Multiplication requires additional steps such as mathematically-paired random numbers called Beaver Triples. Here is the original 1991 publication on Beaver Triples (Efficient Multiparty Protocols Using Circuit Randomization
If you have read to this point, you might be interested to learn more
, or, to come join us
in Palo Alto to build a foundation for secure and private computation.