Abstract: We study differentially private mechanisms for answering \emph{smooth} queries on databases consisting of data points in ${\mathbb{R}}^d$. A $K$-smooth query is specified by a function whose partial derivatives up to order $K$ are all bounded. We develop an $ϵ$-differentially private mechanism which for the class of $K$-smooth queries has accuracy $O({\left(\frac{1}{n}\right)}^{\frac{K}{2d+K}}/ϵ)$. The mechanism first outputs a summary of the database. To obtain an answer of a query, the user runs a public evaluation algorithm which contains no information of the database. Outputting the summary runs in time $O(n^{1+\frac{d}{2d+K}})$, and the evaluation algorithm for answering a query runs in time $\tilde{O}(n^{\frac{d+2+\frac{2d}{K}}{2d+K}})$. Our mechanism is based on $L_{\mathrm{\infty }}$-approximation of (transformed) smooth functions by low degree even trigonometric polynomials with small and efficiently computable coefficients.