Paper 2022/177

The Power of the Differentially Oblivious Shuffle in Distributed Privacy Mechanisms

Mingxun Zhou
Elaine Shi

The shuffle model has been extensively investigated in the distributed differential privacy (DP) literature. For a class of useful computational tasks, the shuffle model allows us to achieve privacy-utility tradeoff similar to those in the central model, while shifting the trust from a central data curator to a ``trusted shuffle'' which can be implemented through either trusted hardware or cryptography. Very recently, several works explored cryptographic instantiations of a new type of shuffle with relaxed security, called {\it differentially oblivious (DO) shuffles}. These works demonstrate that by relaxing the shuffler's security from simulation-style secrecy to differential privacy, we can achieve asymptotical efficiency improvements. A natural question arises, can we replace the shuffler in distributed DP mechanisms with a DO-shuffle while retaining a similar privacy-utility tradeoff? In this paper, we prove an optimal privacy amplification theorem by composing any locally differentially private (LDP) mechanism with a DO-shuffler, achieving parameters that tightly match the shuffle model. Moreover, we explore multi-message protocols in the DO-shuffle model, and construct mechanisms for the real summation and histograph problems. Our error bounds approximate the best known results in the multi-message shuffle-model up to sub-logarithmic factors. Our results also suggest that just like in the shuffle model, allowing each client to send multiple messages is fundamentally more powerful than restricting to a single message. As an application, we derive the result of using repeated DO-shuffling for privacy-preserving time-series data aggregation.

Available format(s)
Cryptographic protocols
Publication info
Differential Obliviousness
Contact author(s)
mingxunz @ andrew cmu edu
2022-11-02: last of 3 revisions
2022-02-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Mingxun Zhou and Elaine Shi},
      title = {The Power of the Differentially Oblivious Shuffle in Distributed Privacy Mechanisms},
      howpublished = {Cryptology ePrint Archive, Paper 2022/177},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.