Sampling from a remote dataset with a private criterion

1. A data sampling system for obtaining a sample of records from a remote dataset satisfying a private criterion using multi-party computation, the data sampling system comprising a data sampling device and a plurality of sample providing devices, each of the plurality of sample providing devices storing a respective subdataset of the remote dataset, the data sampling device comprising:

a communication interface configured for digital communication with at least one of the plurality of sample providing devices; and

a processor configured to:

determine a candidate size for the sample providing device, the candidate size being smaller than the size of the subdataset of the sample providing device;

request the sample providing device determine a candidate sample of the candidate size from the subdataset of the sample providing device;

perform a multi-party computation with the sample providing device to obtain a set of indices of records from the candidate sample satisfying the private criterion, wherein the multi-party computation comprises a private function evaluation, a private function of the private function evaluation comprising a function for evaluating the private criterion;

sample a subset of the set of indices; and

obtain from the sample providing device records of the candidate sample corresponding to the subset of the set of indices.

2. A data sampling device as in claim 1 , the processor being further configured to determine a total candidate size such that a sample of records of the remote dataset with size equal to the total candidate size is likely to contain at least a target number of records satisfying the private criterion according to a probability distribution, the candidate size for the sample providing device being determined from the total candidate size.

3. A data sampling device as in claim 2 , wherein determining the total candidate size comprises:

requesting the sample providing device to determine an initial sample of an initial size from the subdataset of the sample providing device;

performing a multi-party computation with the sample providing device to obtain a number of records from the initial sample satisfying the private criterion; and

determining the total candidate size at least in part based on the number of records from the initial sample satisfying the private criterion.

4. A data sampling device as in claim 2 , wherein determining the candidate size from the total candidate size comprises:

sampling an index sample of indices of records of the remote dataset, the size of the index sample being the total candidate size, and counting a number of indices in the index sample corresponding to the subdataset of the sample providing device; and

sampling the subset of the set of indices comprises iteratively selecting a subdataset corresponding to an index of the index sample and, if the selected subdataset is the subdataset of the sample providing device, selecting an index of a record from the candidate sample and adding the record to the subset if the selected index is in the set of indices.

5. A data sampling device as in claim 1 , wherein obtaining from the sample providing device records corresponding to the subset of the set of indices comprises performing a multi-party computation with the sample providing device, the subset of the set of indices being a private input to the multi-party computation of the data sampling device, records of the candidate sample being private inputs to the multi-party computation of the sample providing device.

6. A data sampling device as in claim 5 , wherein the multi-party computation to obtain records corresponding to the subset is an oblivious transfer.

7. A data sampling device as in claim 5 , wherein the multi-party computation to obtain records corresponding to the subset additionally comprises checking that the subset input by the data sampling device is a subset of the set of indices.

8. A data sampling device as in claim 1 , wherein performing the multi-party computation to obtain the set of indices of records satisfying the private criterion comprises evaluating the private criterion on a first set of attributes of a record and obtaining records of the candidate sample comprises obtaining a second set of attributes of the record, at least one attribute from the first set of attributes not being comprised in the second set of attributes.

9. A data sampling device as in claim 1 , wherein the size of the subset of the set of indices is determined based on a proportion of indices of records from the candidate sample that satisfy the private criterion.

10. A data sampling device as in claim 1 , wherein the processor is further configured to, if a number of obtained records is smaller than a target number of records, repeat one or more of the determining, the requesting, the performing, the sampling, and the obtaining.

11. A sample providing device for providing to a data sampling device a sample of records from a remote dataset satisfying a private criterion using multi-party computation, the sample providing device comprising:

a communication interface configured for digital communication with the data sampling device;

a storage configured to store a subdataset of the remote dataset; and

a processor configured to:

determine, at a request of the data sampling device, a candidate sample of a candidate size from the subdataset, the candidate size being smaller than the size of the subdataset;

perform a multi-party computation with the data sampling device to let the data sampling device obtain a set of indices of records from the candidate sample satisfying the private criterion, wherein the multi-party computation comprises a private function evaluation, a private function of the private function evaluation comprising a function for evaluating the private criterion; and

provide to the data sampling device records of the candidate sample corresponding to a subset of the set of indices sampled by the data sampling device.

12. A sample providing device as in claim 11 , wherein the processor is configured to, at a further request of the data sampling device, determine a further candidate sample of a further candidate size from the subdataset, the further candidate sample being disjoint from the candidate sample.

13. A data sampling method for obtaining a sample of records from a remote dataset satisfying a private criterion using multi-party computation, one or more sample providing devices storing respective subdatasets of the remote dataset, the data sampling method comprising:

establishing digital communication with a sample providing device from the one or more sample providing devices;

determining a candidate size for the sample providing device, the candidate size being smaller than the size of the subdataset of the sample providing device;

requesting the sample providing device to determine a candidate sample of the candidate size from the subdataset of the sample providing device;

performing a multi-party computation with the sample providing device to obtain a set of indices of records from the candidate sample satisfying the private criterion, wherein the multi-party computation comprises a private function evaluation, a private function of the private function evaluation comprising a function for evaluating the private criterion;

sampling a subset of the set of indices; and

obtaining from the sample providing device records of the candidate sample corresponding to the subset of the set of indices and store the records in a memory.

14. A data sampling method as in claim 13 , wherein the one or more sample providing devices comprise multiple sample providing devices.

15. A sample providing method for providing to a data sampling device a sample of records from a remote dataset satisfying a private criterion using multi-party computation, the sample providing method comprising:

establishing digital communication with the data sampling device;

providing a subdataset of the remote dataset;

determining, at a request of the data sampling device, a candidate sample of a candidate size from the subdataset, the candidate size being smaller than the size of the subdataset;

performing a multi-party computation with the data sampling device to let the data sampling device obtain a set of indices of records from the candidate sample satisfying the private criterion, wherein the multi-party computation comprises a private function evaluation, a private function of the private function evaluation comprising a function for evaluating the private criterion; and

providing to the data sampling device records of the candidate sample corresponding to a subset of the set of indices sampled by the data sampling device.

16. A non-transitory computer-readable medium comprising data representing instructions to cause a processor system to perform a data sampling method for obtaining a sample of records from a remote dataset satisfying a private criterion using multi-party computation, one or more sample providing devices storing respective subdatasets of the remote dataset, the data sampling method comprising:

establishing digital communication with a sample providing device from the one or more sample providing devices;

determining a candidate size for the sample providing device, the candidate size being smaller than the size of the subdataset of the sample providing device;

requesting the sample providing device to determine a candidate sample of the candidate size from the subdataset of the sample providing device;

performing a multi-party computation with the sample providing device to obtain a set of indices of records from the candidate sample satisfying the private criterion, wherein the multi-party computation comprises a private function evaluation, a private function of the private function evaluation comprising a function for evaluating the private criterion;

sampling a subset of the set of indices; and

obtaining from the sample providing device records of the candidate sample corresponding to the subset of the set of indices and store the records in a memory.

17. A non-transitory computer-readable medium as in claim 16 , wherein the one or more sample providing devices comprise multiple sample providing devices.

18. A non-transitory computer-readable medium comprising transitory or non-transitory data representing instructions to cause a processor system to perform a sample providing method for providing to a data sampling device a sample of records from a remote dataset satisfying a private criterion using multi-party computation, the sample providing method comprising:

establishing digital communication with the data sampling device;

providing a subdataset of the remote dataset;

determining, at a request of the data sampling device, a candidate sample of a candidate size from the subdataset, the candidate size being smaller than the size of the subdataset;

performing a multi-party computation with the data sampling device to let the data sampling device obtain a set of indices of records from the candidate sample satisfying the private criterion, wherein the multi-party computation comprises a private function evaluation, a private function of the private function evaluation comprising a function for evaluating the private criterion; and

providing to the data sampling device records of the candidate sample corresponding to a subset of the set of indices sampled by the data sampling device.