Secure multiparty computation of shuffle, sort, and set operations

1. A method for performing secure computations on records, comprising:

receiving a request to apply a computation on a record;

assigning a respective partial record of a plurality of partial records of the record to each of a plurality of computational processes;

instructing each of the plurality of computational processes to perform a computation scheme comprising:

applying one of a plurality of semi honest multiparty computations on the partial record;

iteratively repeating a predetermined number of times:

using a secure multiparty arithmetic computation to generate random terms;

using the secure multiparty arithmetic computation to assign the random terms and an outcome of the application to at least one predetermined equation;

verifying an integrity of at least one application of the semi honest multiparty computations by comparison of the assignments to the at least one predetermined equation to at least one constant; and

when the detected integrity is valid, calculating a response to the request by combining the applications of the semi honest multiparty computations on the partial records;

wherein the record and each partial record comprise a matrix of predetermined size comprising elements of a finite algebraic field;

wherein the secure multiparty arithmetic computation comprises a plurality of the following operations:

a multiplication of an input by a scalar,

a summation of two inputs,

a multiplication of two inputs, and

a comparison between two inputs;

wherein the random terms are generated as randomly generated elements of the finite algebraic field and summations of randomly generated elements of the finite algebraic field multiplied by matrix entries of respective partial records;

wherein the computation scheme comprises a sorting multiparty computation as follows:

applying a semi honest multiparty sorting computation on the partial record according to the preassigned index such that the sorting computation performs a sorting of matrix rows of the record according to a preassigned column index;

iteratively repeating a predetermined number of times:

using the secure multiparty arithmetic computation to generate random terms;

assigning the random terms and an outcome of the application to a predetermined polynomial and a predetermined logical term; and

verifying an integrity of at least one application of the semi honest multiparty computations by comparing the assignments to the predetermined polynomial to a first constant and by comparing the assignments to the predetermined logical term to a second constant.

2. The method of claim 1 , wherein the computation scheme comprises a shuffle multiparty computation as follows:

applying a semi honest multiparty shuffle computation on the partial record such that the shuffle computation permutes between respective partial record matrix entries of all computational processes;

iteratively repeating a predetermined number of times:

using the secure multiparty arithmetic computation to generate random terms;

using the secure multiparty arithmetic computation to assign the random terms and an outcome of the application to a polynomial equation; and

verifying an integrity of at least one application of the semi honest multiparty computations by comparing the assignments to the polynomial equation to a constant.

3. The method of claim 2 , wherein the computation requested to be applied on the record is a distinct multiparty computation performed as follows:

using the secure multiparty arithmetic computation to generate random terms according to a predetermined set of indices;

assigning the random terms to respective matrix rows;

applying the sorting multiparty computation on the partial record according to the assigned random terms;

using the secure multiparty arithmetic computation to replace all combined assigned random terms with a first constant in a case that a consecutive combined random term is of equal value, and with a second constant in a case that a consecutive combined random term is of different value;

applying the shuffle multiparty computation to the outcome of the application of the sorting multiparty computation with respective replaced assigned random terms to obtain an intermediate partial record;

using the secure multiparty arithmetic computation to combine assigned random terms in the intermediate partial record;

discarding all rows in the intermediate partial record for which respective combined random terms are equal to the first constant; and

using the secure multiparty arithmetic computation to output a combination of intermediate partial records.

4. The method of claim 3 , wherein the computation requested to be applied on the record comprising two matrices is a union multiparty computation performed as follows:

using the secure multiparty arithmetic computation to combine the two matrices into a combined matrix;

using the distinct multiparty computation on the combined matrix; and

outputting the outcome of the distinct multiparty computation.

5. The method of claim 4 , wherein the computation requested to be applied on the record is an intersect multiparty computation, and each partial record comprises a first matrix and a second matrix, performed as follows:

applying a semi honest multiparty intersect computation on the partial record to obtain a third matrix;

using the distinct multiparty computation on the first matrix;

using the distinct multiparty computation on the second matrix;

using the union multiparty computation on the first and second matrices to obtain a fourth matrix;

applying a concatenate operation to an outcome of the distinct multiparty computation on the first matrix and an outcome of the distinct multiparty computation on the second matrix to obtain a fifth matrix;

applying a concatenate operation to the third matrix and the fourth matrix to obtain a sixth matrix; and

verifying an integrity by using the fifth matrix and the sixth matrix as respective input and output in the shuffle multiparty computation.

6. The method of claim 5 , wherein the computation requested to be applied on the record is an except multiparty computation, and each partial record comprises a first matrix and a second matrix, performed as follows:

applying a semi honest multiparty except computation on the partial record to obtain a third matrix;

using the distinct multiparty computation on the second matrix;

using the union multiparty computation on the first and second matrices to obtain a fourth matrix;

applying a concatenate operation to the third matrix and an outcome of the distinct multiparty computation on the second matrix to obtain a fifth matrix;

applying a concatenate operation to the third matrix and the fourth matrix to obtain a sixth matrix; and

verifying an integrity by using the fourth matrix and the fifth matrix as respective input and output in the shuffle multiparty computation.

7. A system for performing secure computations on records, comprising:

at least one electronic circuitry adapted to perform the following:

receiving a request to apply a computation on a record;

assigning a respective partial record of a plurality of partial records of the record to each of a plurality of computational processes;

instructing each of the plurality of computational processes to perform a computation scheme comprising:

applying one of a plurality of semi honest multiparty computations on the partial record;

iteratively repeating a predetermined number of times:

using a secure multiparty arithmetic computation to generate random terms;

using the secure multiparty arithmetic computation to assign the random terms and an outcome of the application to at least one predetermined equation;

verifying an integrity of at least one application of the semi honest multiparty computations by comparison of the assignments to the at least one predetermined equation to at least one constant; and

when the detected integrity is valid, calculating a response to the request by combining the applications of the semi honest multiparty computations on the partial records;

wherein the record and each partial record comprise a matrix of predetermined size comprising elements of a finite algebraic field;

wherein the secure multiparty arithmetic computation comprises a plurality of the following operations:

a multiplication of an input by a scalar,

a summation of two inputs,

a multiplication of two inputs, and

a comparison between two inputs;

wherein the random terms are generated as randomly generated elements of the finite algebraic field and summations of randomly generated elements of the finite algebraic field multiplied by matrix entries of respective partial records;

wherein the computation scheme comprises a sorting multiparty computation as follows:

applying a semi honest multiparty sorting computation on the partial record according to the preassigned index such that the sorting computation performs a sorting of matrix rows of the record according to a preassigned column index;

iteratively repeating a predetermined number of times:

using the secure multiparty arithmetic computation to generate random terms;

assigning the random terms and an outcome of the application to a predetermined polynomial and a predetermined logical term; and

verifying an integrity of at least one application of the semi honest multiparty computations by comparing the assignments to the predetermined polynomial to a first constant and by comparing the assignments to the predetermined logical term to a second constant.