Securely Tracking COVID-19 with Enya

World is going through Corona virus pandemic, and since we have limited resources and healthcare workers to minimize casualties and spread of the disease, scientists and doctors are searching for the ways to track the spread and distribute resources wisely, and ensuring privacy of the general public. 

So Enya, a start-up in Palo Alto, California that develops security and privacy technologies to protect consumers and patients, came up with a technique called "Secure Multiparty Computation (SMC)" and in this blog post we are gonna discuss the algorithm developed by Enya in its most simplified way.

Imagine you are a doctor who studies SARS-nCoV-2. One of the first things you might like to know are how old people with a positive SARS-nCoV-2 test are. To get that information, you could try to ask several million people for their date of birth but most people would be reluctant to tell you. Among other uses, banks use this information to verify a person's identity. Would you give your date of birth to someone who just contacted you by email? (Hopefully not!)

Here is another way – the doctor could ask everyone to add a random number between -100 to +100 to their age and submit the result. So if your age is 27 and your choice of random number is -12, you would subtract 12 from 27 and send the result, 15, to the doctor. The doctor would then not know your age, but she (or he) can still determine something very useful, which is the distribution of ages of people with a positive SARS-nCov-2 test result. To do this, the doctor would average over many responses.

Similar to how the mean displacement of a diffusing piece of dust is zero, the random terms would tend to cancel, gradually revealing a good estimate of the population’s true age structure.

This approach works well for research but there is an obvious problem – in a typical medical context, a patient expects their doctor to tell them something about their health and not just make abstract statements about global age demographics. Let’s add a few computational twists to the above approach. Here is a simplified example of secure multiparty computation.

Imagine a doctor has developed a new algorithm for estimating risk of infection. 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+ (wd - rd) + rp = age + (rp - rp) + (rd - rd). 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. The fact that both parties remember and do not disclose or share their noise terms (rp and rd, 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, 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, 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. If you have read to this point, you might be interested to learn more - here is the original 1991 publication on Beaver Triples (Efficient Multiparty Protocols Using Circuit Randomization).

Under the hood - how to securely investigate new COVID symptoms?

For example, a candidate symptom vector for the common cold could be {sneezing, runny nose} whereas a symptom vector for COVID could be {fever, blue toes, loss of sense of smell}. When someone contributes their symptoms to some tracking app(like Enya ), the first thing that happens is that their secrets (e.g. fever === true) are protected using SMC. Also using SMC, we then compute their mathematical (Hamming) distance to (currently) four different preconfigured symptom vectors, which represent "cold", "flu", "COVID-basic", and "COVID-neuro". When the computation completes, we are left with six numbers - the person's approximate location (e.g. "Delhi" or "Hong Kong"), their mathematical proximity to the four preconfigured symptom constellations, and a number representing {"no test", "negative test", "positive test"}. With this information, we can help others to investigate the extent to which different symptom constellations predict a negative or positive test result, and also to quantify whether different symptom constellations are able to discriminate among different diseases (e.g. "flu" vs. "COVID"). One anticipated long-term benefit of assembling this information is that public health officials will be able to better allocate scarce testing resources.

rd --> r_d   

Underlined text is sub-script.