Systems and methods for secure multi-party computation protocol execution using check points
An encryption system and method are provided that provide the ability to execute a secure multi-party computation (SMPC) protocol to compute a large function using check points. At each checkpoint, respective parties to the computation write out some encrypted data that can be used to initiate the next stage of the computation between the present check point and the next check point. In this manner, if any participating party experiences a failure, such as a network outage, system crash, disk corruption, etc., during the protocol execution, there is no need to re-start the entire protocol from scratch. This allows for large functions to be practically computed using SMPC.
1 . A method comprising:
a) establishing a communication link between a first party device and a second party device;
b) jointly dividing a function to be computed into a multi-staged function by the first party device and the second party device;
c) jointly choosing an encryption function E by the first party and second party devices;
d) jointly constructing a multi-stage Secure Multi-Party Computation (SMPC)-compatible function, by the first party device and the second party device, such that each stage of the multi-stage SMPC-compatible function is compatible with a corresponding stage of the multi-staged function;
e) jointly executing a multi-stage SMPC protocol to jointly compute the multi-stage SMPC-compatible function by the first party device and the second party device;
f) triggering a checkpoint event upon separately determining a failure in the joint computation of the multi-stage SMPC-compatible function at a current stage of execution; and
g) restarting the multi-stage SMPC protocol from the current stage of execution in response to the checkpoint event.
2 . The method of claim 1 , wherein executing the multi-stage SMPC protocol to jointly compute the multi-stage SMPC-compatible function by the first party device and the second party device, at a first stage of the multi-stage SMPC protocol comprises:
generating an encryption key k 0 , by the first party device;
jointly computing an encrypted output Out 0 of the first stage of the multi-stage SMPC protocol, using a first stage of the multi-stage SMPC-compatible function and the generated encryption key ko as inputs to the computation;
receiving, by the second party device, the encrypted output Out 0 ;
saving, by the second party device, the encrypted output Out 0 to a local storage of the second party device;
saving, by the first party device, the encryption key k 0 , to a local storage of the first party device;
saving a current state of circuit execution to the local storage of the first party device; and
saving the current state of circuit execution to the local storage of the second party device.
3 . The method of claim 1 , wherein executing the multi-stage SMPC protocol to jointly compute the multi-stage SMPC-compatible function by the first party device and the second party device at one or more intermediate stages in between a first stage and a final stage comprises:
loading, by the second party device, an encrypted output Out i-1 from a local storage of the second party device;
generating an encryption key k i , by the first party device;
loading, by the first party device, an encryption key k i-1 from a local storage of the first party device;
jointly decrypting the encrypted output Out i-1 loaded from the local storage of the second party device, using the encryption key k i-1 loaded from the local storage of the first party device to generate plaintext intermediate data from a prior intermediate stage;
jointly computing, by the first party device and the second party device, a current encrypted intermediate stage output Out i , using a current stage of the multi-stage SMPC-compatible function, the generated plaintext intermediate data and the generated encryption key k i ;
receiving, by the second party device, the encrypted output Out i ,
saving, by the second party device, the encrypted output Out i , provided by the first party device, to the local storage of the second party device;
saving, by the first party device, the encryption key k i , to the local storage of the first party device; and
saving a parameter to the local storage of the first party device and the second party device indicating a current state of circuit execution completion.
4 . The method of claim 1 , wherein executing the multi-stage SMPC protocol to jointly compute the multi-stage SMPC-compatible function by the first party device and the second party device at a final stage comprises:
loading, by the second party device, an encrypted output Out i-1 from a local storage of the second party device;
loading, by the first party device, an encryption key k i-1 from a local storage of the first party device;
jointly decrypting the encrypted output Out i-1 loaded from the local storage of the second party device, using the encryption key k i-1 loaded from the local storage of the first party device to generate a decrypted output; and
receiving, by the first party device, the decrypted output.
5 . The method of claim 1 , further comprising, upon triggering the checkpoint event;
re-establishing a communication link between the first party device and the second party device prior to restarting the multi-stage SMPC protocol; and
obtaining a joint agreement between the first party device and the second party device over the re-established communication link to restart the multi-stage SMPC protocol prior to restarting the multi-stage SMPC protocol from the current stage of execution in response to the checkpoint event.
6 . The method of claim 1 , wherein the chosen encryption function E is based on a pre-determined encryption algorithm compatible with the multi-stage SMPC protocol.
7 . The method of claim 1 , wherein a message authentication code (MAC) algorithm is incorporated as part of a pre-determined encryption algorithm.
8 . The method of claim 7 , wherein the MAC algorithm is added to an output of each stage of the multi-stage SMPC protocol.
9 . The method of claim 8 , wherein a validation of the MAC algorithm is added to the output of each stage of the multi-stage SMPC protocol.
10 . The method of claim 1 , wherein the function to be computed is jointly divided into the multi-staged function to minimize an amount of intermediate outputs carried between stages.
11 . A system comprising:
a memory; and
a processor communicatively coupled to the memory, the memory storing instructions executable by the processor to:
a) establish a communication link between a first party device and a second party device;
b) jointly divide a function to be computed into a multi-staged function by the first party device and the second party device;
c) jointly choose an encryption function E by the first party and second party devices;
d) jointly construct a multi-stage Secure Multi-Party Computation (SMPC)-compatible function, by the first party device and the second party device, such that each stage of the multi-stage SMPC-compatible function is compatible with a corresponding stage of the multi-staged function;
e) jointly execute a multi-stage SMPC protocol to jointly compute the multi-stage SMPC-compatible function by the first party device and the second party device;
f) trigger a checkpoint event upon separately determining a failure in the joint computation of the multi-stage SMPC-compatible function at a current stage of execution; and
g) restart the multi-stage SMPC protocol from the current stage of execution in response to the checkpoint event.
12 . The system of claim 11 , wherein the processor, at a first stage of computation of the multi-stage SMPC protocol, is configured to:
generate an encryption key k 0 , by the first party device;
jointly compute an encrypted output Out 0 of the first stage of the multi-stage SMPC protocol, using a first stage of the multi-stage SMPC-compatible function and the generated encryption key k 0 as inputs to the computation;
receive, by the second party device, the encrypted output Out 0 ;
save, by the second party device, the encrypted output Out 0 to a local storage of the second party device;
save, by the first party device, the encryption key k 0 , to a local storage of the first party device;
save a current state of circuit execution to the local storage of the first party device; and
save the current state of circuit execution to the local storage of the second party device.
13 . The system of claim 11 , wherein the processor, at an intermediate stage of operation of the multi-stage SMPC protocol, is configured to:
load, by the second party device, an encrypted output Out i-1 from a local storage of the second party device;
generate an encryption key k i , by the first party device;
load, by the first party device, an encryption key k i-1 from a local storage of the first party device;
jointly decrypt the encrypted output Out i-1 loaded from the local storage of the second party device, using the encryption key k i-1 loaded from a local storage of the first party device to generate plaintext intermediate data from a prior intermediate stage;
jointly compute, by the first party device and the second device, a current encrypted intermediate stage output Out i , using a current stage of the multi-stage SMPC-compatible function, the generated plaintext intermediate data and the generated encryption key k i ,
receive, by the second party device, the encrypted output Out i ;
save, by the second party device, the encrypted output Out i , provided by the first party device, to the local storage of the second party device;
save, by the first party device, the encryption key k i , to the local storage of the first party device; and
save a parameter to the local storage of the first party device and the second party device indicating a current state of circuit execution completion.
14 . The system of claim 11 , wherein the processor, at a final stage of operation of the multi-stage SMPC protocol, is configured to:
load, by the second party device, an encrypted output Out i-1 from a local storage of the second party device;
load, by the first party device, an encryption key k i-1 from a local storage of the first party device;
jointly decrypt the encrypted output Out i-1 loaded from the local storage of the second party device, using the encryption key k i-1 loaded from the local storage of the first party device to generate a decrypted output; and
receive, by the first party device, the decrypted output.
15 . The system of claim 11 , wherein upon triggering the checkpoint event, the processor is configured to:
re-establish a communication link between the first party device and the second party device prior to restarting the multi-stage SMPC protocol; and
obtain a joint agreement between the first party device and the second party device over the re-established communication link to restart the multi-stage SMPC protocol prior to restarting the multi-stage SMPC protocol from the current stage of execution in response to the checkpoint event.
16 . The system of claim 11 , wherein the chosen encryption function E is based on a pre-determined encryption algorithm compatible with the multi-stage SMPC protocol.
17 . The system of claim 11 , wherein a message authentication code (MAC) algorithm is incorporated as part of a pre-determined encryption algorithm.
18 . The system of claim 17 , wherein the MAC algorithm is added to an output of each stage of the multi-stage SMPC protocol.
19 . The system of claim 18 , wherein a validation of the MAC algorithm is added to the output of each stage of the multi-stage SMPC protocol.
20 . The system of claim 11 , wherein the function to be computed is jointly divided into the multi-staged function to minimize an amount of intermediate outputs carried between stages.