In this paper, we study differentially private mechanisms for functions whose outputs lie in a Euclidean Jordan algebra. Euclidean Jordan algebras capture many important mathematical structures and form the foundation of linear programming, second-order cone programming, and semidefinite programming. Our main contribution is a generic Gaussian mechanism for such functions, with sensitivity measured in ℓ2, ℓ1, and ℓ∞ norms. Notably, this framework includes the important case where the function outputs are symmetric matrices, and sensitivity is measured in the Frobenius, nuclear, or spectral norm. We further derive private algorithms for solving symmetric cone programs under various settings, using a combination of the multiplicative weights update method and our generic Gaussian mechanism. As an application, we present differentially private algorithms for semidefinite programming, resolving a major open question posed by [Hsu, Roth, Roughgarden, and Ullman, ICALP 2014].
Figures & tables
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Algebra J
Rank r
Peirce constant d
kC=d(r−1)+1
r×r real symmetric matrices
r
1
r
r×r complex Hermitian matrices
r
2
2r−1
r×r quaternionic Hermitian matrices
r
4
4r−3
spin factor R×Rn , n≥2
2
n−1
n
Albert algebra
3
8
17
Appendix
Table 1: Five types of simple Jordan algebras, their rank r , their Peirce constant d , and the dimension kC of the cone C of scaled primitive idempotents.
We give a gap-free (ε,δ)-differentially private algorithm for the principal component analysis (PCA) problem with Gaussian data. The algorithm is based on a private variant of the power iteration method, and it is computationally efficient.
Alina Ene, Huy L. Nguyen
Department of Computer Science, Boston University · Khoury College of Computer and Information Science, Northeastern University
We design a class of additive noise mechanisms that satisfy (ε,δ)-differential privacy (DP) for scalar, real-valued query functions with known sensitivities, with a particular focus on moderate and low-privacy regimes. These mechanisms, which we call mixture mechanisms, are constructed by mixing multiple Gaussian distributions that share the same variance but differ in their means and mixture weights. The resulting distributions can be interpreted as convex combinations of a zero-mean Gaussian (as used in the analytic Gaussian mechanism) and additional Gaussians whose means depend on the sensitivity of the query function. We derive tight conditions on the variances required for (ε,δ)-DP and provide efficient algorithms to compute them. Compared to the analytic Gaussian mechanism, our mechanisms yield substantially lower expected noise amplitudes (l1-loss) and variances (l2-loss for zero-mean distributions). In the low-privacy regime that motivates our design, our mechanisms approach optimality, mitigating nearly all of the optimality gap of the analytic Gaussian mechanism.
Huikang Liu, Aras Selvi, Wolfram Wiesemann
1Shanghai Jiao Tong University · 2UCL School of Management · 3Imperial Business School
We present the dithered Gaussian mechanism, an alternative to the discrete Gaussian mechanism for differential privacy that discretizes the private output rather than the noise distribution itself. By interpreting this discretization as post-processing of the Gaussian mechanism, our construction directly inherits the privacy guarantees of the standard Gaussian mechanism while avoiding vulnerabilities caused by finite-precision floating-point outputs. In addition, the mechanism is provably randomness-efficient: by sampling the discretized output values directly, the number of high-quality random bits required for privacy can be reduced significantly and made independent of the noise level. This is achieved by separating the randomness into two sources: a high-quality source used for the privacy-critical sampling step, and a high-performance public source, possibly known to the adversary, that supplies the additional randomness needed for randomized discretization. This separation enables the use of cryptographically secure randomness without substantial performance loss. As an application, we study model training with DP-SGD and show that cryptographically secure noise generation with reduced exposure to floating-point vulnerabilities can be achieved with modest practical overhead.
Nikita P. Kalinin, Rasmus Pagh
Institute of Science and Technology Austria · BARC University of Copenhagen