Non‐stochastic hypothesis testing for privacy
Pages 754 - 763
Abstract
In this study, I consider privacy against hypothesis testing adversaries within a non‐stochastic framework. He developed a theory of non‐stochastic hypothesis testing by borrowing the notion of uncertain variables from non‐stochastic information theory. I define tests as binary‐valued mappings on uncertain variables and proved a fundamental bound on the best performance of the tests in non‐stochastic hypothesis testing. I provide parallels between stochastic and non‐stochastic hypothesis‐testing frameworks. I use the performance bound in non‐stochastic hypothesis testing to develop a measure of privacy. I then construct the reporting policies with the prescribed privacy and utility guarantees. The utility of a reporting policy is measured by the distance between the reported and original values. Finally, I present the notion of indistinguishability as a measure of privacy by extending the identifiability from the privacy literature to the non‐stochastic framework. I prove that the linear quantisers can indeed achieve identifiability for responding to linear queries on private datasets.
8. References
[1]
Warner S.L.: ‘Randomized response: a survey technique for eliminating evasive answer bias ’, J. Am. Stat. Assoc., 1965, 60, (309 ), pp. 63–69
[2]
Dwork C. Roth A.: ‘The algorithmic foundations of differential privacy ’, Found. Trends Theor. Comput. Sci., 2014, 9, (3–4 ), pp. 211–407
[3]
Duchi J.C. Jordan M.I. Wainwright M.J.: ‘Local privacy and statistical minimax rates ’. 2013 IEEE 54th Annual Symp. on Foundations of Computer Science (FOCS), Berkeley, CA, USA, 2013, pp. 429–438
[4]
Kairouz P. Oh S. Viswanath P.: ‘Extremal mechanisms for local differential privacy ’. Advances in Neural Information Processing Systems, Montreal, Canada, 2014, pp. 2879–2887
[5]
Machanavajjhala A. Kifer D. Abowd J. et al.: ‘Privacy: theory meets practice on the map ’. Proc. of the 2008 IEEE 24th Int. Conf. on Data Engineering, Cancun, Mexico, 2008, pp. 277–286
[6]
Wang W. Ying L. Zhang J.: ‘On the relation between identifiability, differential privacy, and mutual‐information privacy ’, IEEE Trans. Inf. Theory, 2016, 62, (9 ), pp. 5018–5029
[7]
Lee J. Clifton C.: ‘Differential identifiability ’. Proc. of the 18th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, Beijing, People's Republic of China, 2012, pp. 1041–1049
[8]
Bkakria A. Cuppens‐Boulahia N. Cuppens F.: ‘Linking differential identifiability with differential privacy ’. Int. Conf. on Information and Communications Security, Lille, France, 2018, pp. 232–247
[9]
Farokhi F. Nair G.: ‘Privacy‐constrained communication ’, IFAC‐PapersOnLine, 2016, 49, (22 ), pp. 43–48
[10]
Wainwright M.J. Jordan M.I. Duchi J.C.: ‘Privacy aware learning ’. Proc. of Advances in Neural Information Processing Systems (NIPS), Harrahs and Harveys, Lake Tahoe, NV, USA, 2012, pp. 1430–1438
[11]
Liang Y. Poor H.V. Shamai S.: ‘Information theoretic security ’, Found. Trends Commun. Inf. Theory, 2009, 5, (4–5 ), pp. 355–580
[12]
Lai L. Ho S.‐W. Poor H.V.: ‘Privacy–security trade‐offs in biometric security systems–part I: single use case ’, IEEE Trans. Inf. Forensics Sec., 2011, 6, (1 ), pp. 122–139
[13]
Li Z. Oechtering T.: ‘Privacy on hypothesis testing in smart grids ’. IEEE Information Theory Workshop (ITW) 2015, Jeju, Korea, 11–15 October 2015, pp. 337–341
[14]
Farokhi F. Sandberg H.: ‘Fisher information as a measure of privacy: preserving privacy of households with smart meters using batteries ’, IEEE Trans. Smart Grid, 2018, 9, (5 ), pp. 4726–4734
[15]
Sankar L. Rajagopalan S.R. Poor H.V.: ‘Utility‐privacy tradeoffs in databases: an information‐theoretic approach ’, IEEE Trans. Inf. Forensics Sec., 2013, 8, (6 ), pp. 838–852
[16]
Farokhi F. Milosevic J. Sandberg H.: ‘Optimal state estimation with measurements corrupted by Laplace noise ’. 2016 IEEE 55th Conf. on Decision and Control (CDC), Las Vegas, NV, USA, 2016, pp. 302–307
[17]
Bild R. Kuhn K.A. Prasser F.: ‘SafePub: a truthful data anonymization algorithm with strong privacy guarantees ’, Proc. Priv. Enhancing Technol., 2018, 2018, (1 ), pp. 67–87
[18]
Bambauer J. Muralidhar K. Sarathy R.: ‘Fool's gold: an illustrated critique of differential privacy ’, Vanderbilt J. Entertainment Technol. Law, 2013, 16, p. 701
[19]
Bhaskar R. Bhowmick A. Goyal V. et al.: ‘Noiseless database privacy ’. Int. Conf. on the Theory and Application of Cryptology and Information Security, Seoul, Republic of Korea, 2011, pp. 215–232
[20]
Nabar S.U. Marthi B. Kenthapadi K. et al.: ‘Towards robustness in query auditing ’. Proc. of the 32nd Int. Conf. on Very Large Data Bases, Seoul, Republic of Korea, 2006, pp. 151–162
[21]
Wyner A.D.: ‘The wire‐tap channel ’, Bell Syst. Tech. J., 1975, 54, (8 ), pp. 1355–1387
[22]
Courtade T.: ‘Information masking and amplification: the source coding setting ’. Proc. of the IEEE Int. Symp. on Information Theory Proc. (ISIT), Cambridge, Massachusetts, USA, 2012, pp. 189–193
[23]
Yamamoto H.: ‘A source coding problem for sources with additional outputs to keep secret from the receiver or wiretappers ’, IEEE Trans. Inf. Theory, 1983, 29, (6 ), pp. 918–923
[24]
Yamamoto H.: ‘A rate‐distortion problem for a communication system with a secondary decoder to be hindered ’, IEEE Trans. Inf. Theory, 1988, 34, (4 ), pp. 835–842
[25]
Samarati P.: ‘Protecting respondents identities in microdata release ’, IEEE Trans. Knowl. Data Eng., 2001, 13, (6 ), pp. 1010–1027
[26]
Sweeney L.: ‘k‐anonymity: a model for protecting privacy ’, Int. J. Uncertain. Fuzziness Knowl.‐Based Syst., 2002, 10, (5 ), pp. 557–570
[27]
Machanavajjhala A. Gehrke J. Kifer D. et al.: ‘ℓ‐diversity: privacy beyond k‐anonymity ’. 22nd Int. Conf. on Data Engineering (ICDE'06), Atlanta, GA, USA, 2006, pp. 24–24
[28]
Narayanan A. Shmatikov V.: ‘Robust de‐anonymization of large sparse datasets ’. IEEE Symp. on Security and Privacy, 2008. SP 2008, Oakland, California, USA, 2008, pp. 111–125
[29]
Su J. Shukla A. Goel S. et al.: ‘De‐anonymizing web browsing data with social networks ’. Proc. of the 26th Int. Conf. on World Wide Web, Perth, Australia, 2017, pp. 1261–1269
[30]
De Montjoye Y.‐A. Hidalgo C.A. Verleysen M. et al.: ‘Unique in the crowd: the privacy bounds of human mobility ’, Sci. Rep., 2013, 3, p.1376
[31]
Poulis G. Gkoulalas‐Divanis A. Loukides G. et al.: ‘SECRETA: a tool for anonymizing relational, transaction and rtdatasets ’, in Gkoulalas‐Divanis A. Loukides G. (Eds.): ‘Medical data privacy handbook ’ (Springer International Publishing, Switzerland, 2015 ), pp. 83–109
[32]
Dankar F.K. El Emam K.: ‘Practicing differential privacy in health care: a review ’, Trans. Data Priv., 2013, 6, (1 ), pp. 35–67
[33]
Mervis J.: ‘Researchers object to census privacy measure ’, Science, 2019, 363, (6423 ), pp. 114–114
[34]
Farokhi F.: ‘Development and analysis of deterministic privacy‐preserving policies using non‐stochastic information theory ’, IEEE Trans. Inf. Forensics Sec., 2019, 14, pp. 2567–2576
[35]
Hartley R.V.L.: ‘Transmission of information ’, Bell Syst. Tech. J., 1928, 7, (3 ), pp. 535–563
[36]
Kolmogorov A.N. Tikhomirov V.M.: ‘ɛ ‐entropy and ɛ ‐capacity of sets in function spaces ’, Usp. Mat. Nauk, 1959, 14, (2 ), pp. 3–86. English translation American Mathematical Society Translations, series 2, vol. 17, pp. 277–364
[37]
Renyi A.: ‘On measures of entropy and information ’. Proc. of the Fourth Berkeley Symp. on Mathematical Statistics and Probability, Berkeley, CA, USA, 1961, vol. 1, pp. 547–561
[38]
Nair G.N.: ‘A nonstochastic information theory for communication and state estimation ’, IEEE Trans. Autom. Control, 2013, 58, (6 ), pp. 1497–1510
[39]
Jagerman D.: ‘ɛ ‐entropy and approximation of bandlimited functions ’, SIAM J. Appl. Math., 1969, 17, (2 ), pp. 362–377
[40]
Nair G.N.: ‘A nonstochastic information theory for feedback ’. 2012 IEEE 51st Annual Conf. on Decision and Control (CDC), Maui, HI, USA, 2012, pp. 1343–1348
[41]
Duan P. Yang F. Shah S.L. et al.: ‘Transfer zero‐entropy and its application for capturing cause and effect relationship between variables ’, IEEE Trans. Control Syst. Technol., 2015, 23, (3 ), pp. 855–867
[42]
Wiese M. Johansson K.H. Oechtering T.J. et al.: ‘Uncertain wiretap channels and secure estimation ’. 2016 IEEE Int. Symp. on Information Theory (ISIT), Barcelona, Spain, 2016, pp. 2004–2008
[43]
Barber R.F. Duchi J.: ‘Privacy: a few definitional aspects and consequences for minimax mean‐squared error ’. 53rd IEEE Conf. on Decision and Control, Los Angeles, CA, USA, 2014, pp. 1365–1369
[44]
Katz J. Lindell Y.: ‘Introduction to modern cryptography ’, Chapman & Hall/CRC Cryptography and Network Security Series (Taylor & Francis, Boca Raton, FL, USA, 2014, 2nd edn. )
[45]
Farokhi F.: ‘Non‐stochastic hypothesis testing with application to privacy against hypothesis‐testing adversary ’. 2019 IEEE 58th Conf. on Proc. of the Decision and Control (CDC), Nice, France, 2019
[46]
Shingin H. Ohta Y.: ‘Disturbance rejection with information constraints: performance limitations of a scalar system for bounded and Gaussian disturbances ’, IFAC Proc. Vol., 2009, 42, (20 ), pp. 304–309
[47]
Farokhi F. Ding N.: ‘Measuring information leakage in non‐stochastic brute‐force guessing ’, arXiv preprint arXiv:2004.10911, 2020
[48]
Sason I. Verdú S.: ‘Arimoto–Rényi conditional entropy and Bayesian m‐ary hypothesis testing ’, IEEE Trans. Inf. Theory, 2017, 64, (1 ), pp. 4–25
[49]
Yu B.: ‘Assouad, Fano, and Le Cam ’, in Pollard D. Torgersen E. Yang G.L. (Eds.): ‘Festschrift for Lucien Le Cam: research papers in probability and statistics ’ (Springer New York, New York, NY, 1997 ), pp. 423–435
[50]
Billingsley P.: ‘Probability and measure ’ (John Wiley & Sons, Hoboken, NJ, USA, 1995, 3rd edn. )
[51]
Sabo M.: ‘Young people survey: explore the preferences, interests, habits, opinions, and fears of young people ’. Available at https://www.kaggle.com/miroslavsabo/young‐people‐survey, last visit: 8 March 2019
Recommendations
t-Closeness through Microaggregation: Strict Privacy with Enhanced Utility Preservation
Microaggregation is a technique for disclosure limitation aimed at protecting the privacy of data subjects in microdata releases. It has been used as an alternative to generalization and suppression to generate k-anonymous data sets, where the identity of ...
A Novel Differential Privacy Approach that Enhances Classification Accuracy
C3S2E '16: Proceedings of the Ninth International C* Conference on Computer Science & Software EngineeringIn the recent past, there has been a tremendous increase of large repositories of data, examples being in healthcare data, consumer data from retailers, and airline passenger data. These data are continually being shared with interested parties, either ...
Survey on Privacy-Preserving Techniques for Microdata Publication
The exponential growth of collected, processed, and shared microdata has given rise to concerns about individuals’ privacy. As a result, laws and regulations have emerged to control what organisations do with microdata and how they protect it. Statistical ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© 2020 The Institution of Engineering and Technology.
Publisher
John Wiley & Sons, Inc.
United States
Publication History
Published: 01 November 2020
Author Tags
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 08 Feb 2025