SIMD interactive comparison using garbled circuits and interactive bootstrapping for homomorphic encryption

1 . A computer implemented method for executing an interactive multi-party Single-Instruction/Multiple-Data (SIMD) program using a garbled circuit under a fully homomorphic encryption (FHE) protocol, the method comprising:

storing, in a garbler device, in communication with an evaluator device, in a system of two or more parties, a unique garbler secret key share of a shared secret key, a ciphertext of one or more values encrypted in a SIMD FHE protocol, and a shared public key encrypting the ciphertext;

partially decrypting, in the garbler device, the ciphertext using the unique garbler secret key share to generate a unique garbler data share that is non-linear;

linearizing, in the garbler device, the unique garbler data share that is non-linear to generate a linear unique garbler data share configured to be combined with other parties' shares at compact size; and

sending, from the garbler device to the evaluator device, a garbled circuit configured to perform an operation on the one or more values, a garbling of the linear unique garbled data share, and garbled potential wires into which the evaluator device is adapted to garble a linear unique evaluator data share by oblivious transfer,

wherein the garbled circuit is adapted to be evaluated by the evaluator device using a SIMD execution that combines, in parallel, multiple indices of the garbling of the linear unique garbled data share and an evaluator unique data share to generate an encrypted result of the operation of the garbled circuit on the one or more encrypted values.

2 . The method of claim 1 , wherein the operation is iteratively executed pair-wise between pairs of parties in a linked sequence of more than two parties, wherein in each iterative pair-wise execution, the evaluator device from a previous iteration is reset to be the garbler device in a current iteration and a third party of the more than two parties is set to be the evaluator device in the current iteration.

3 . The method of claim 2 , wherein each iterative pair-wise execution operates under a different shared secret key combining the unique the garbler secret key share of the garbler device and the evaluator secret key share of the evaluator device in a current iteration.

4 . The method of claim 2 , wherein the garbler device in the previous and current iterative pair-wise executions send different or the same garbled circuits to the evaluator device.

5 . The method of claim 1 , wherein the garbler device linearizes the unique garbler data share by distributed rounding.

6 . The method of claim 1 comprising, at the garbler device, reducing a size of the linear share to the compact size by modulo p, where p is the plaintext modulus of each of the one or more unencrypted values.

7 . The method of claim 1 , wherein the garbler device sends the garbled circuit that combines the two parties' unique data shares under a mask.

8 . A garbler device, in communication with an evaluator device, in a system of two or more parties, the garbler device comprising:

one or more memories configured to store a unique garbler secret key share of a shared secret key, a ciphertext of one or more values encrypted in a SIMD FHE protocol, and a shared public key encrypting the ciphertext; and

one or more processors configured to:

partially decrypt the ciphertext using the unique garbler secret key share s i to generate a unique garbler data share,

linearize the unique garbler data share that is non-linear to generate a linear unique garbler data share to be combined with other parties' shares at compact size, and

generate, and send to the evaluator device, a garbled circuit configured to perform an operation on the one or more values, a garbling of the linear unique garbled data share, and garbled potential wires into which the evaluator device is adapted to garble a linear unique evaluator data share by oblivious transfer,

wherein the garbled circuit is adapted to be evaluated by the evaluator device using a SIMD execution that combines, in parallel, multiple indices of the garbling of the linear unique garbled data share and an evaluator unique data share to generate an encrypted result of the operation of the garbled circuit on the one or more encrypted values.

9 . The garbler device of claim 8 , wherein the operation is iteratively executed pair-wise between pairs of parties in a linked sequence of more than two parties, wherein in each iterative pair-wise execution, the evaluator device from a previous iteration is reset to be the garbler device in a current iteration and a third party of the more than two parties is set to be the evaluator device in the current iteration.

10 . The garbler device of claim 8 , wherein the one or more processors are configured to linearize the unique garbler data share by distributed rounding.

11 . The garbler device of claim 8 , wherein the one or more processors are configured to reduce a size of the linear share to the compact size by modulo p, where p is the plaintext modulus of each of the one or more unencrypted values.

12 . The garbler device of claim 8 , wherein the one or more processors are configured to send the garbled circuit that combines the two parties' unique data shares under a mask.