Abstract

We study differentially private mechanisms for answering smooth queries on databases consisting of data points in 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 K accuracy   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 and the evaluation algorithm for answering a query runs in time Our mechanism is based on -approximation of (transformed) smooth functions by low degree even trigonometric polynomials with small and efficiently computable coefficients.