The present disclosure involves systems, software, and computer implemented methods for a verifiable communication-efficient secret shuffle protocol for encrypted data based on homomorphic encryption. 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, different blinding values, and use of random secret-shares. A protocol step includes homomorphic operations to shuffle encrypted secret input values so that resulting encrypted secret input values are rerandomized and in a shuffled sequence that is unmapped to an order of receipt by the service provider of the encrypted secret input values.