A system for executing a secret shuffle protocol, the system comprising a plurality of clients and a service provider, wherein each client comprises at least one computing device and the service provider comprises at least one server computing device, and wherein:
- each client is configured to:
- identify a client-specific secret input value;
- encrypt the client-specific secret input value;
- and
- send the encrypted client-specific secret input value to the service provider;
- and
- the service provider is configured to receive, from each client, the encrypted client-specific secret input value;
- and
- each client is further configured to:
- generate a client-specific random value;
- send the client-specific random value to each of the other clients;
- and
- receive, from each of the other clients, the client-specific random values of each of the other clients;
- and
- the service provider is further configured to select a service provider random value and send the service provider random value to each of the clients;
- and
- each client is further configured to receive the service provider random value from the service provider;
- and
- the service provider is further configured to randomly permute the encrypted client-specific secret input values using a random permutation;
- and
- each client is further configured to:
- generate a client-specific list of hashed values using each of the client-specific random values generated by each of the clients and the service provider random value;
- determine, using the client-specific list of hashed values, a client-specific random index that is different from client-specific random indices determined by the other clients;
- receive, from the service provider, a randomly-determined encrypted blinded input selected based on the client-specific random index;
- and
- the service provider is further configured to:
- provide a randomly-determined encrypted blinded input to each client, wherein each randomly-determined encrypted blinded input is selected based on the client-specific random index of the client;
- and
- provide, to each client, a client-specific encrypted first blinding value, wherein the client-specific encrypted first blinding value is an encryption of a client-specific first blinding value included in the randomly-determined encrypted blinded input received by the client;
- and
- each client is further configured to:
- receive, from the service provider, the client-specific first encrypted blinding value;
- rerandomize the randomly-determined encrypted blinded input to prevent the service provider from learning the client-specific random index of the client;
- send, to the service provider, a client-specific rerandomized encrypted blinded input;
- generate, using a client-specific second blinding value, a client-specific encrypted and blinded first blinding value;
- and
- send, to the service provider, a client-specific encrypted and blinded first blinding value;
- encrypt the client-specific second blinding value;
- and
- send, to the service provider, a client-specific encrypted second blinding value;
- and
- the service provider is further configured to:
- receive, from each client, the client-specific rerandomized encrypted blinded input, the client-specific encrypted and blinded first blinding value, and the client-specific encrypted second blinding value;
- and
- decrypt each client-specific encrypted and blinded first blinding value to generate a first client-specific intermediate plaintext for each client;
- multiply each first client-specific intermediate plaintext by negative one to generate a second client-specific intermediate plaintext for each client;
- encrypt each second client-specific intermediate plaintext to generate an intermediate ciphertext for each client;
- multiply, for each client, the intermediate ciphertext by the client-specific rerandomized encrypted blinded input and the client-specific encrypted second blinding value, to homomorphically remove the first blinding value and the second blinding value, to generate a client-specific rerandomized encrypted secret input value, wherein the client-specific rerandomized encrypted secret input values are generated in an order that is unmapped to an order of receipt, at the service provider, of the encrypted secret input values.