Enhanced robust input protocol for secure multi-party computation (MPC) via hierarchical pseudorandom secret sharing

1. A method comprising:

obtaining, by a server in a plurality of servers, a first set of replicated shares R A of a random or pseudorandom secret key R;

transmitting, by the server, the first set of replicated shares R A to a client that is configured to submit k private inputs X (1) , . . . , X (k) to the plurality of servers for use in a secure multi-party computation (MPC) protocol;

determining, by the server, k second sets of replicated shares R A (1) , . . . , R A (k) corresponding to k pseudorandom secret keys R (1) , . . . , R (k) , the determining being performed by applying pseudorandom secret sharing (PRSS) to the first set of replicated shares R A ;

receiving, by the server from the client, a public broadcast of k delta values Δ (1) , . . . , Δ (k) corresponding to the k private inputs X (1) , . . . , X (k) ;

determining, by the server, k third sets of replicated shares X A (1) , . . . , X A (k) corresponding to the k private inputs X (1) , . . . , X (k) based on the k delta values Δ (1) , . . . , Δ (k) and the k second sets of replicated shares R A (1) , . . . , R A (k) ; and

using, by the server, the k third sets of replicated shares X A (1) , . . . , X A (k) as part of a computation phase of the MPC protocol.

2. The method of claim 1 further comprising, prior to using the k third sets of replicated shares X A (1) , . . . , X A (k) :

converting the k third sets of replicated shares X A (1) , . . . , X A (k) into shares that conform to Shamir's secret sharing scheme.

3. The method of claim 1 wherein determining the k second sets of replicated shares R A (1) , . . . , R A (k) comprises:

computing a pseudorandom function ƒ(R A , i) for every share in the first set of replicated shares R A and for i=1, . . . , k.

4. The method of claim 1 wherein determining the k third sets of replicated shares X A (1) , . . . , X A (k) comprises:

computing Δ (i) +R A (i) for i=1, . . . , k.

5. The method of claim 1 wherein the first set of replicated shares R A are derived via PRSS from a master random secret key that is different from random or pseudorandom secret key R.

6. The method of claim 1 wherein the client determines the k delta values Δ (1) , . . . , Δ (k) by:

reconstructing the k pseudorandom secret keys R (1) , . . . , R (k) based on a complete replicated sharing [R] of the random or pseudorandom secret key R received from the plurality of servers; and

computing X (i) −R (i) for i=1, . . . , k.

7. The method of claim 6 wherein the client reconstructs the k pseudorandom secret keys R (1) , . . . , R (k) by:

deriving replicated sharings [R (1) ], . . . , [R (k) ] of the k pseudorandom secret keys R (1) , . . . , R (k) by computing a pseudorandom function ƒ(R j ,i) for every share R j in the complete replicated sharing [R] and for i=1, . . . , k; and

reconstructing the k pseudorandom secret keys R (1) , . . . , R (k) using the replicated sharings [R (1) ], . . . , [R (k) ].

8. A non-transitory computer readable storage medium having stored thereon program code executable by a server in a plurality of servers, the program code embodying a method comprising:

obtaining a first set of replicated shares R A of a random or pseudorandom secret key R;

transmitting the first set of replicated shares R A to a client that is configured to submit k private inputs X (1) , . . . , X (k) to the plurality of servers for use in a secure multi-party computation (MPC) protocol;

determining k second sets of replicated shares R A (1) , . . . , R A (k) corresponding to k pseudorandom secret keys R (1) , . . . , R (k) , the determining being performed by applying pseudorandom secret sharing (PRSS) to the first set of replicated shares R A ;

receiving, from the client, a public broadcast of k delta values Δ (1) , . . . , Δ (k) corresponding to the k private inputs X (1) , . . . , X (k) ;

determining k third sets of replicated shares X A (1) , . . . , X A (k) corresponding to the k private inputs X (1) , . . . , X (k) based on the k delta values Δ (1) , . . . , Δ (k) and the k second sets of replicated shares R A (1) , . . . , R A (k) ; and

using the k third sets of replicated shares X A (1) , . . . , X A (k) as part of a computation phase of the MPC protocol.

9. The non-transitory computer readable storage medium of claim 8 wherein the method further comprises, prior to using the k third sets of replicated shares X A (1) , . . . , X A (k) :

converting the k third sets of replicated shares X A (1) , . . . , X A (k) into shares that conform to Shamir's secret sharing scheme.

10. The non-transitory computer readable storage medium of claim 8 wherein determining the k second sets of replicated shares R A (1) , . . . , R A (k) comprises:

computing a pseudorandom function ƒ(R A , i) for every share in the first set of replicated shares R A and for i=1, . . . , k.

11. The non-transitory computer readable storage medium of claim 8 wherein determining the k third sets of replicated shares X A (1) , . . . , X A (k) comprises:

computing Δ (i) +R A (i) for i=1, . . . , k.

12. The non-transitory computer readable storage medium of claim 8 wherein the first set of replicated shares R A are derived via PRSS from a master random secret key that is different from random or pseudorandom secret key R.

13. The non-transitory computer readable storage medium of claim 8 wherein the client determines the k delta values Δ (1) , . . . , Δ (k) by:

reconstructing the k pseudorandom secret keys R (1) , . . . , R (k) based on a complete replicated sharing [R] of the random or pseudorandom secret key R received from the plurality of servers; and

computing X (i) −R (i) for i=1, . . . , k.

14. The non-transitory computer readable storage medium of claim 13 wherein the client reconstructs the k pseudorandom secret keys R (1) , . . . , R (k) by:

deriving replicated sharings [R (1) ], . . . , [R (k) ] of the k pseudorandom secret keys R (1) , . . . , R (k) by computing a pseudorandom function ƒ(R j , i) for every share R j in the complete replicated sharing [R] and for i=1, . . . , k; and

reconstructing the k pseudorandom secret keys R (1) , . . . , R (k) using the replicated sharings [R (1) ], . . . , [R (k) ].

15. A server in a plurality of servers, the server comprising:

a processor; and

a non-transitory computer readable medium having stored thereon program code that, when executed, causes the processor to:

obtain a first set of replicated shares R A of a random or pseudorandom secret key R;

transmit the first set of replicated shares R A to a client that is configured to submit k private inputs X (1) , . . . , X (k) to the plurality of servers for use in a secure multi-party computation (MPC) protocol;

determine k second sets of replicated shares R A (1) , . . . , R A (k) corresponding to k pseudorandom secret keys R (1) , . . . , R (k) , the determining being performed by applying pseudorandom secret sharing (PRSS) to the first set of replicated shares R A ;

receive, from the client, a public broadcast of k delta values Δ (1) , . . . , Δ (k) corresponding to the k private inputs X (1) , . . . , X (k) ;

determine k third sets of replicated shares X A (1) , . . . , X A (k) corresponding to the k private inputs X (1) , . . . , X (k) based on the k delta values Δ (1) , . . . , Δ (k) and the k second sets of replicated shares R A (1) , . . . , R A (k) ; and

use the k third sets of replicated shares X A (1) , . . . , X A (k) as part of a computation phase of the MPC protocol.

16. The server of claim 15 wherein the program code further causes the processor to, prior to using the k third sets of replicated shares X A (1) , . . . , X A (k) :

convert the k third sets of replicated shares X A (1) , . . . , X A (k) into shares that conform to Shamir's secret sharing scheme.

17. The server of claim 15 wherein the program code that causes the processor to determine the k second sets of replicated shares R A (1) , . . . , R A (k) comprises program code that causes the processor to:

compute a pseudorandom function ƒ(R A , i) for every share in the first set of replicated shares R A and for i=1, . . . , k.

18. The server of claim 15 wherein the program code that causes the processor to determine the k third sets of replicated shares X A (1) , . . . , X A (k) comprises program code that causes the processor to:

compute Δ (i) +R A (i) for i=1, . . . , k.

19. The server of claim 15 wherein the first set of replicated shares R A are derived via PRSS from a master random secret key that is different from random or pseudorandom secret key R.

20. The server of claim 15 wherein the client determines the k delta values Δ (1) , . . . , Δ (k) by:

reconstructing the k pseudorandom secret keys R (1) , . . . , R (k) based on a complete replicated sharing [R] of the random or pseudorandom secret key R received from the plurality of servers; and

computing X (i) −R (i) for i=1, . . . , k.

21. The server of claim 20 wherein the client reconstructs the k pseudorandom secret keys R (1) , . . . , R (k) by:

deriving replicated sharings [R (1) ], . . . , [R (k) ] of the k pseudorandom secret keys R (1) , . . . , R (k) by computing a pseudorandom function f(R j , i) for every share R j in the complete replicated sharing [R] and for i=1, . . . , k; and reconstructing the k pseudorandom secret keys R (1) , . . . , R (k) using the replicated sharings [R (1) ], . . . , [R (k) ].