Robust input verification for secure multi-party computation (MPC) with clients
In one set of embodiments, each server executing a secure multi-party computation (MPC) protocol can receive shares of inputs to the MPC protocol from a plurality of clients, where each input is private to each client and where each share is generated from its corresponding input using a threshold secret sharing scheme. Each server can then verify whether the shares of the plurality of inputs are valid/invalid and, for each invalid share, determine whether a client that submitted the invalid share or a server that holds the invalid share is corrupted. If the client that submitted the invalid share is corrupted, each server can ignore the input of that corrupted client during a computation phase of the MPC protocol. Alternatively, if the server that holds the invalid share is corrupted, each server can prevent that corrupted server from participating in the computation phase.
1. A method comprising:
receiving, by each server in a plurality of servers executing a secure multi-party computation (MPC) protocol, shares of a plurality of inputs to the MPC protocol from a plurality of clients, wherein each input in the plurality of inputs is private to each client in the plurality of clients, and wherein each share is generated from its corresponding input using a threshold secret sharing scheme;
verifying, by said each server, whether the shares of the plurality of inputs are valid or invalid;
determining, by said each server based on the verifying, a set of clients in the plurality of clients that may be corrupted; and
sending, by said each server to each client in the set of clients, a request to resubmit the shares of the client's inputs using an alternative input scheme that is distinct from the threshold secret sharing scheme.
2. The method of claim 1 further comprising:
determining, for a share that is determined to be invalid, that a client that submitted the share is corrupted; and
ignoring the input of the client during a computation phase of the MPC protocol.
3. The method of claim 2 wherein determining that the client that submitted the share is corrupted comprises:
determining that an input sharing submitted by the client is not consistent.
4. The method of claim 1 further comprising:
determining, for a share that is determined to be invalid, that a server that holds the share is corrupted; and
preventing the server from participating in a computation phase of the MPC protocol.
5. The method of claim 4 wherein determining that the server that holds the share is corrupted comprises:
determining that the server holds more than a threshold number of invalid shares of consistent input sharings submitted by the plurality of clients.
6. The method of claim 1 wherein there are n servers in the plurality of servers and at most t<n/4 servers are corrupted, and
wherein there are N clients in the plurality of clients and at most (1−ρ)N clients are corrupted for 0<ρ≤1.
7. The method of claim 1 wherein the shares are verified together for all clients in the plurality of clients.
8. A non-transitory computer readable storage medium having stored thereon program code executable by each server in a plurality of servers executing a secure multi-party computation (MPC) protocol, the program code causing said each server to execute a method comprising:
receiving shares of a plurality of inputs to the MPC protocol from a plurality of clients, wherein each input in the plurality of inputs is private to each client in the plurality of clients, and wherein each share is generated from its corresponding input using a threshold secret sharing scheme;
verifying whether the shares of the plurality of inputs are valid or invalid;
determining, based on the verifying, a set of clients in the plurality of clients that may be corrupted; and
sending, to each client in the set of clients, a request to resubmit the shares of the client's inputs using an alternative input scheme that is distinct from the threshold secret sharing scheme.
9. The non-transitory computer readable storage medium of claim 8 wherein the method further comprises:
determining, for a share that is determined to be invalid, that a client that submitted the share is corrupted; and
ignoring the input of the client during a computation phase of the MPC protocol.
10. The non-transitory computer readable storage medium of claim 9 wherein determining that the client that submitted the share is corrupted comprises:
determining that an input sharing submitted by the client is not consistent.
11. The non-transitory computer readable storage medium of claim 8 wherein the method further comprises:
determining, for a share that is determined to be invalid, that a server that holds the share is corrupted; and
preventing the server from participating in a computation phase of the MPC protocol.
12. The non-transitory computer readable storage medium of claim 11 wherein determining that the server that holds the share is corrupted comprises:
determining that the server holds more than a threshold number of invalid shares of consistent input sharings submitted by the plurality of clients.
13. The non-transitory computer readable storage medium of claim 8 wherein there are n servers in the plurality of servers and at most t<n/4 servers are corrupted, and
wherein there are N clients in the plurality of clients and at most (1−ρ)N clients are corrupted for 0<ρ≤1.
14. The non-transitory computer readable storage medium of claim 8 wherein the shares are verified together for all clients in the plurality of clients.
15. A server among a plurality of servers executing a secure multi-party computation (MPC) protocol, the server comprising:
a processor; and
a non-transitory computer readable medium having stored thereon program code that, when executed, causes the processor to:
receive shares of a plurality of inputs to the MPC protocol from a plurality of clients, wherein each input in the plurality of inputs is private to each client in the plurality of clients, and wherein each share is generated from its corresponding input using a threshold secret sharing scheme;
verify whether the shares of the plurality of inputs are valid or invalid;
determine, based on the verifying, a set of clients in the plurality of clients that may be corrupted; and
send, to each client in the set of clients, a request to resubmit the shares of the client's inputs using an alternative input scheme that is distinct from the threshold secret sharing scheme.
16. The server of claim 15 wherein the program code further causes the processor to:
determine, for a share that is determined to be invalid, that a client that submitted the share is corrupted; and
ignore the input of the client during a computation phase of the MPC protocol.
17. The server of claim 16 wherein determining that the client that submitted the share is corrupted comprises:
determining that an input sharing submitted by the client is not consistent.
18. The server of claim 15 wherein the program code further causes the processor to:
determine, for a share that is determined to be invalid, that a server that holds the share is corrupted; and
prevent the server from participating in a computation phase of the MPC protocol.
19. The server of claim 18 wherein determining that the server that holds the share is corrupted comprises:
determining that the server holds more than a threshold number of invalid shares of consistent input sharings submitted by the plurality of clients.
20. The server of claim 15 wherein there are n servers in the plurality of servers and at most t<n/4 servers are corrupted, and
wherein there are N clients in the plurality of clients and at most (1−ρ)N clients are corrupted for 0<ρ≤1.
21. The server of claim 15 wherein the shares are verified together for all clients in the plurality of clients.