Charles Lin

1. Consider this SQL query running without Opaque's oblivious mode, but only encryption mode.

SELECT patients.name, diseases.treatment FROM patients, diseases WHERE patients.disease=diseases.disease;

This joins the tables "patients" (with fields "name" and "disease") and
"diseases" (with fields "disease" and "treatment") by the attribute "disease", in order to fetch for each patient the treatment.

Consider the same threat model as in Opaque.
Give an example of a sensitive information that the attacker could learn by watching the distributed computation. Say what side information you assume your attacker has about the data and explain why it is reasonable that some attacker could have this side information.

P.S.: The syntax above is SQL, so if you need some help understanding it, the MySQL documentation is a good guide. This class assumes some basic understanding of SQL queries.


If the query was executed using a hash join, then the traffic patterns would leak which rows and how many rows are going to which machines. Combined with prior knowledge of disease distributions, which an attacker can have since it is public, the attacker can know which machines represent which diseases, and thus which rows have which diseases by following the traffic backwards. Finally, if the attacker had circumstantial information from a prior attack, such as knowing that patient A is in some range of rows, then the attacker would be able to determine which disease A has.


2. Assume each disease has a unique entry in the patients "table" (in fact, it is a unique key). Sketch an algorithm that computes this join obliviously. It does not have to be optimal, it only has to be oblivious.

If disease is a unique key in the patients table, then the join can be computed by doing a union on the patients table and diseases table, and doing an oblivious sort on the disease attribute. Then, for each patient, emit the joined row, and for each disease, emit a dummy row. Oblivious sort again to push the dummy values to the bottom and filter them out.