Practical Universal Random Sampling

In our paper we modify and extend the line of research initiated in CRYPTO 2006 paper ([5]) on preserving privacy in statistical databases. Firstly we present a simpler approach giving the explicit formulas for the sampling probabilities. We show that in most cases our analysis gives substantially better results than those presented in the original paper. Additionaly we outline how the simplified approach can be used for constructing a protocol of privacy preserving sampling distributed databases. © 2010 Springer-Verlag.