Secure sublinear time differentially private median computation

A system comprising:

• at least one processor;
• and
• a non-transitory computer-readable medium storing executable instructions that, when executed, cause the at least one processor to perform operations comprising:
• obtaining secret shares of a first dataset of a first entity, secret shares of a second dataset of a second entity, secret shares of gap values for the first dataset, secret shares of gap values for the second dataset, secret shares of probability mass values for the first dataset, and secret shares of probability mass values for the second dataset, the gap values for the first dataset comprising differences between adjacent data points in the first dataset, and the gap values for the second dataset comprising difference between adjacent data points in the second dataset;
• determining a differentially private median of a union of the first dataset and the second dataset using an inverse transform sampling algorithm based on the secret shares of the first dataset, the secret shares of the second dataset, the secret shares of the gap values for the first dataset, the secret shares of the gap values for the second dataset, the secret shares of the probability mass values for the first dataset, and the secret shares of the probability mass values for the second dataset, the determining the differentially private median being performed using a garbled circuit protocol;
• and
• performing a function of a networked computer system using the determined.

A non-transitory machine-readable storage medium, tangibly embodying a set of instructions that, when executed by at least one processor, causes the at least one processor to perform operations comprising:

• obtaining secret shares of a first dataset of a first entity, secret shares of a second dataset of a second entity, secret shares of gap values for the first dataset, secret shares of gap values for the second dataset, secret shares of probability mass values for the first dataset, and secret shares of probability mass values for the second dataset, the gap values for the first dataset comprising differences between adjacent data points in the first dataset, and the gap values for the second dataset comprising difference between adjacent data points in the second dataset;
• determining a differentially private median of a union of the first dataset and the second dataset using an inverse transform sampling algorithm based on the secret shares of the first dataset, the secret shares of the second dataset, the secret shares of the gap values for the first dataset, the secret shares of the gap values for the second dataset, the secret shares of the probability mass values for the first dataset, and the secret shares of the probability mass values for the second dataset, the determining the differentially private median being performed using a garbled circuit protocol;
• and
• performing a function of a networked computer system using the determined median.