With the growing volume of data in society, the need for privacy protection in data analysis also rises. In particular, private selection tasks, wherein the most important information is retrieved under differential privacy are emphasized in a wide range of contexts, including machine learning and medical statistical analysis. However, existing mechanisms use global sensitivity, which may add larger amount of perturbation than is necessary. Therefore, this study proposes a novel mechanism for differentially private selection using the concept of smooth sensitivity and presents theoretical proofs of strict privacy guarantees. Simultaneously, given that the current state-of-the-art algorithm using smooth sensitivity is still of limited use, and that the theoretical analysis of the basic properties of the noise distributions are not yet rigorous, we present fundamental theorems to improve upon them. Furthermore, new theorems are proposed for efficient noise generation. Experiments demonstrate that the proposed mechanism can provide higher accuracy than the existing global sensitivity-based methods. Finally, we show key directions for further theoretical development. Overall, this study can be an important foundational work for expanding the potential of smooth sensitivity in privacy-preserving data analysis. The Python implementation of our experiments and supplemental results are available at https://github.com/ay0408/Smooth-Private-Selection.

With the increasing amount of data in society, privacy concerns in data sharing have become widely recognized. Particularly, protecting personal attribute information is essential for a wide range of aims from crowdsourcing to realizing personalized medicine. Although various differentially private methods based on randomized response have been proposed for single attribute information or specific analysis purposes such as frequency estimation, there is a lack of studies on the mechanism for sharing individuals’ multiple categorical information itself. The existing randomized response for sharing multi-attribute data uses the Kronecker product to perturb each attribute information in turn according to the respective privacy level but achieves only a weak privacy level for the entire dataset. Therefore, in this study, we propose a privacy-optimized randomized response that guarantees the strongest privacy in sharing multi-attribute data. Furthermore, we present an efficient heuristic algorithm for constructing a near-optimal mechanism whose time complexity is ${\mathcal{O}}\left({{k^2}}\right)$, where k is the number of attributes. The experimental results demonstrate that both of our methods provide significantly stronger privacy guarantees for the entire dataset than the existing method. Overall, this study is an important step toward trustworthy sharing and analysis of multi-attribute data.

With the recent increase in the medical data and health awareness, the use of genomic data to promote personalized medicine has been widely considered. Simultaneously, privacy concerns have arisen with the publication of statistics obtained from large-scale genomic statistical analysis such as GWAS. All existing differentially private methods for GWAS statistics protect privacy by adding noise based on global sensitivity, considering the worst-case scenario of possible datasets. However, the amount of noise required in practical cases is considerably smaller, and these methods do not achieve the desired accuracy in private statistics. In this study, we propose a privacy-preserving method for publishing much more accurate statistics using smooth sensitivity, which generates tailored noise for each dataset. We first introduce a more rigorous theorem on the properties of the noise distribution than was known previously and propose a new ϵ-differentially private method for publishing GWAS statistics. We also provide theoretical proof of the privacy guarantee. Thereafter, we present novel theorems for computing the smooth sensitivity significantly faster than conventional approaches. This enables the application of smooth sensitivity to GWAS statistics, which would otherwise be impossible because of the exceedingly high computational complexity. Based on these theorems, we performed detailed analyses of key GWAS statistics and developed efficient algorithms to obtain their smooth sensitivities. Experimental results demonstrate that our proposed methods achieve at least 3 times higher accuracy than existing global sensitivity-based methods. Furthermore, the execution time is sufficiently short, and the accuracy increases when the dataset becomes larger, suggesting that our methods are suitable for the publication of statistics in large-scale analysis. Because our method is expected to be applicable to other general statistics, this study is an important step toward highly accurate statistical analysis using smooth sensitivity. The supplemental materials are available at https://github.com/ay0408/SS-based-Stats.

As the amount of data containing human genome information increases, these data will be further utilized in medicine. However, if the statistics obtained from large-scale analyses are released unchanged, there is a risk of identifying individuals. Although there are several privacy-preserving techniques to release and utilize genomic statistics, most have the problem of poor accuracy at high privacy levels and do not provide correct results especially with an increased number of outputs. In addition, existing methods with relatively high accuracy are computationally intensive and hardly applicable to a large cohort such as those containing 106SNPs. In this paper, we propose innovative differentially private methods with both efficiency and high accuracy to release the top K significant SNPs based on genomic statistics data. First, we enhance the Fourier perturbation algorithm (FPA), which was proposed in the context of histogram publication, for use with genomic statistics. Then, we propose a new extended FPA with more accurate privacy guarantees and provide a proof that this method achieves ε-differential privacy. Furthermore, we present novel methods combining DFT with the Laplace and exponential mechanisms. These methods take only $\mathcal{O}(m{\text{log}}m)$ time for a dataset containing m SNPs. We also theoretically guarantee that the value of sensitivity for these methods is smaller than that for existing methods and therefore can provide more accurate outputs. In fact, our proposed algorithms can be conducted in less than 20 seconds even for a large cohort, and our experiments using real data show that our methods can achieve 1.5 to 8 times higher accuracy than state-of-the-art methods especially when K is large. Because retrieving multiple significant SNPs from large cohorts in genomic analysis is preferred, our proposed methods are remarkably advisable rather than existing methods. Supplementary materials and the Python implementation of our experiments are available at https://github.com/ay0408/DP-DFT.

Statistical analyses of datasets containing genomic information is essential for personalized medicine. However, when the statistics are released as they are, there is a risk of identifying individuals. In this study, we propose efficient a nd practical privacy-preserving methods using the concept of differential privacy for linkage analysis with a transmission disequilibrium test (TDT). We focus on the case of two affected children in one family, and present differentially private data sharing methods based on three statistics, which are the TDT statistic, haplotype-based statistic, and combined statistic of these two. First, we show the sensitivities of each statistic and present the algorithm using the Laplace mechanism. Then, for the exponential mechanism, we adopt the shortest Hamming distance score as the score function and propose exact and approximation algorithms to find the scores. In our experiments, we measure the run time of each algorithm to show that it is feasible even on a large dataset containing 106SNPs. Supplementary materials are available at https://github.com/ay0408/DP-linkage-analysis-TDT.