%AEugenio, Evercita%ALiu, Fang%D2021%I %K %MOSTI ID: 10311803 %PMedium: X %TConstruction of Differentially Private Empirical Distributions from a Low-Order Marginals Set Through Solving Linear Equations with 𝑙2 Regularization %XWe introduce a new algorithm, Construction of dIfferentially Private Empirical Distributions from a low-order marginal set tHrough solving linear Equations with 𝑙2 Regularization (CIPHER), that produces differentially private empirical joint distributions from a set of low-order marginals. CIPHER is conceptually simple and requires no more than decomposing joint probabilities via basic probability rules to construct a linear equation set and subsequently solve the equations. Compared to the full-dimensional histogram (FDH) sanitization, CIPHER has drastically lower requirements on computational storage and memory, which is practically attractive especially considering that the high-order signals preserved by the FDH sanitization are likely just sample randomness and rarely of interest. Our experiments demonstrate that CIPHER outperforms the multiplicative weighting exponential mechanism in preserving original information and has similar or superior cost-normalized utility to FDH sanitization at the same privacy budget. Country unknown/Code not availablehttps://doi.org/978-3-030-80129-8OSTI-MSA