2019/10/29 by Farhad Farokhi, Farokhi, Farhad
Computer Science · Engineering · Mathematics · #Cryptography and Data Security #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Electrical engineering #Information Retrieval (cs.IR) #Information Theory (cs.IT) #Privacy-Preserving Technologies in Data #Signal Processing (eess.SP) #Systems and Control (eess.SY) #Wireless Communication Security Techniques #cs.CR #cs.IR #cs.IT #cs.SY #eess.SP #eess.SY #electronic engineering #information engineering #math.IT
paper · pdf · doi:10.48550/arxiv.1910.13027
arxiv created 2019/10/29 · openalex publication_date 2019/10/29 · arxiv updated 2019/10/30 · openalex created_date 2022/08/30 · openalex updated_date 2026/07/28
In this paper, we define noiseless privacy, as a non-stochastic rival to differential privacy, requiring that the outputs of a mechanism (i.e., function composition of a privacy-preserving mapping and a query) can attain only a few values while varying the data of an individual (the logarithm of the number of the distinct values is bounded by the privacy budget). Therefore, the output of the mechanism is not fully informative of the data of the individuals in the dataset. We prove several guarantees for noiselessly-private mechanisms. The information content of the output about the data of an individual, even if an adversary knows all the other entries of the private dataset, is bounded by the privacy budget. The zero-error capacity of memory-less channels using noiselessly private mechanisms for transmission is upper bounded by the privacy budget. The performance of a non-stochastic hypothesis-testing adversary is bounded again by the privacy budget. Finally, assuming that an adversary has access to a stochastic prior on the dataset, we prove that the estimation error of the adversary for individual entries of the dataset is lower bounded by a decreasing function of the privacy budget. In this case, we also show that the maximal information leakage is bounded by the privacy budget. In addition to privacy guarantees, we prove that noiselessly-private mechanisms admit composition theorem and post-processing does not weaken their privacy guarantees. We prove that quantization operators can ensure noiseless privacy if the number of quantization levels is appropriately selected based on the sensitivity of the query and the privacy budget. Finally, we illustrate the privacy merits of noiseless privacy using multiple datasets in energy and transport.