COMMUNICATION-EFFICIENT SECRET SHUFFLE PROTOCOL FOR ENCRYPTED DATA BASED ON HOMOMORPHIC ENCRYPTION AND OBLIVIOUS TRANSFER

The present disclosure involves systems, software, and computer implemented methods for a communication-efficient secret shuffle protocol for encrypted data based on homomorphic encryption and oblivious transfer. A service provider and multiple clients participate in a secret shuffle protocol of randomly shuffling encrypted client-specific secret input values. The protocol includes generation and exchange of random numbers, random permutations and different blinding values, including use of an oblivious transfer mechanism. A last protocol step includes using homomorphism, for each client, to perform computations on intermediate encrypted data to homomorphically remove a first blinding value and a second blinding value, to generate a client-specific rerandomized encrypted secret input value. As a result, 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.