IACR News item: 13 September 2013
Jalaj Upadhyay
ePrint ReportWe show that the technique of Blocki et al. (FOCS2012) ({\\sf BBDS}) can be adapted to preserve {\\sf DP} for answering cut-queries on sparse graphs, with an asymptotically efficient sanitizer than~{\\sf BBDS}. We use this as the base technique to construct an efficient sanitizer for arbitrary graphs. In particular, we use a preconditioning step that preserves the spectral properties (and therefore, size of any cut is preserved), and then apply our basic sanitizer. We first prove that our sanitizer preserves {\\sf DP} for graphs with high conductance. We then carefully compose our basic technique with the modified sanitizer to prove the result for arbitrary graphs. In certain sense, our approach is complementary to the Randomized sanitization for answering cut queries (Gupta, Roth, and Ullman, TCC 2012): we use graph sparsification, while Randomized sanitization uses graph densification.
Our sanitizers almost achieves the best of both the worlds with the same privacy guarantee, i.e., it is almost as efficient as the most efficient sanitizer and it has utility guarantee almost as strong as the utility guarantee of the best sanitization algorithm.
We also make some progress in answering few open problems by {\\sf BBDS}. We make a combinatorial observation that allows us to argue that the sanitized graph can also answer $(S,T)$-cut queries with same asymptotic efficiency, utility, and {\\sf DP} guarantee as our sanitization algorithm for $S, \\bar{S}$-cuts. Moreover, we achieve a better utility guarantee than Gupta, Roth, and Ullman (TCC 2012). We give further optimization by showing that fast Johnson-Lindenstrauss transform of Ailon and Chazelle~\\cite{AC09} also preserves {\\sf DP}.
Additional news items may be found on the IACR news page.