Cryptology ePrint Archive: Report 2022/177

The Power of the Differentially Oblivious Shuffle in Distributed Privacy Mechanisms

Mingxun Zhou and Elaine Shi

Abstract: 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.

Category / Keywords: cryptographic protocols / Differential Obliviousness

Date: received 16 Feb 2022, last revised 22 May 2022

Contact author: mingxunz at andrew cmu edu

Available format(s): PDF | BibTeX Citation

Version: 20220522:155800 (All versions of this report)

Short URL: ia.cr/2022/177


[ Cryptology ePrint archive ]