Differential privacy has become a de facto standard for releasing data in a privacy-preserving way. Creating a differentially private algorithm is a process that often starts with a noise-free (non-private) algorithm. The designer then decides where
to add noise, and how much of it to add. This can be a non-trivial process -- if not done carefully, the algorithm might either violate differential privacy or have low utility. In this paper, we present DPGen, a program synthesizer that takes in non-private code (without any noise) and automatically synthesizes its differentially private version (with carefully calibrated noise). Under the hood, DPGen uses novel algorithms to automatically generate a sketch program with candidate locations for noise, and then optimize privacy proof and noise scales simultaneously on the sketch program. Moreover, DPGen can synthesize sophisticated mechanisms that adaptively process queries until a specified privacy budget is exhausted. When evaluated on standard benchmarks, DPGen is able to generate differentially private mechanisms that optimize simple utility functions within 120 seconds. It is also powerful enough to synthesize adaptive privacy mechanisms.
This work proposes a compact robotic limb, AugLimb, that can augment our body functions and support the daily activities. AugLimb adopts the double-layer scissor unit for the extendable mechanism which can achieve 2.5 times longer than the forearm le
ngth. The proposed device can be mounted on the users upper arm, and transform into compact state without obstruction to wearers. The proposed device is lightweight with low burden exerted on the wearer. We developed the prototype of AugLimb to demonstrate the proposed mechanisms. We believe that the design methodology of AugLimb can facilitate human augmentation research for practical use. see http://www.jaist.ac.jp/~xie/auglimb.html
The permute-and-flip mechanism is a recently proposed differentially private selection algorithm that was shown to outperform the exponential mechanism. In this paper, we show that permute-and-flip is equivalent to the well-known report noisy max algorithm with exponential noise.
Private selection algorithms, such as the Exponential Mechanism, Noisy Max and Sparse Vector, are used to select items (such as queries with large answers) from a set of candidates, while controlling privacy leakage in the underlying data. Such algor
ithms serve as building blocks for more complex differentially private algorithms. In this paper we show that these algorithms can release additional information related to the gaps between the selected items and the other candidates for free (i.e., at no additional privacy cost). This free gap information can improve the accuracy of certain follow-up counting queries by up to 66%. We obtain these results from a careful privacy analysis of these algorithms. Based on this analysis, we further propose novel hybrid algorithms that can dynamically save additional privacy budget.
Let $k$ be an algebraically closed field of characteristic $p>0$. Let $c,din mathbb{N}$ be such that $h=c+d>0$. Let $H$ be a $p$-divisible group of codimension $c$ and dimension $d$ over $k$. For $minmathbb{N}^ast$ let $H[p^m]=ker([p^m]:Hrightarrow H
)$. It is a finite commutative group scheme over $k$ of $p$ power order, called a Barsotti-Tate group of level $m$. We study a particular type of $p$-divisible groups $H_pi$, where $pi$ is a permutation on the set ${1,2,dots,h}$. Let $(M,varphi_pi)$ be the Dieudonne module of $H_pi$. Each $H_pi$ is uniquely determined by $H_pi[p]$ and by the fact that there exists a maximal torus $T$ of $GL_M$ whose Lie algebra is normalized by $varphi_pi$ in a natural way. Moreover, if $H$ is a $p$-divisible group of codimension $c$ and dimension $d$ over $k$, then $H[p]cong H_pi[p]$ for some permutation $pi$. We call these $H_pi$ canonical lifts of Barsotti-Tate groups of level $1$. We obtain new formulas of combinatorial nature for the dimension of $boldsymbol{Aut}(H_pi[p^m])$ and for the number of connected components of $boldsymbol{End}(H_pi[p^m])$.
Noisy Max and Sparse Vector are selection algorithms for differential privacy and serve as building blocks for more complex algorithms. In this paper we show that both algorithms can release additional information for free (i.e., at no additional pri
vacy cost). Noisy Max is used to return the approximate maximizer among a set of queries. We show that it can also release for free the noisy gap between the approximate maximizer and runner-up. This free information can improve the accuracy of certain subsequent counting queries by up to 50%. Sparse Vector is used to return a set of queries that are approximately larger than a fixed threshold. We show that it can adaptively control its privacy budget (use less budget for queries that are likely to be much larger than the threshold) in order to increase the amount of queries it can process. These results follow from a careful privacy analysis.
