Information Theoretic Approaches to Privacy-Preserving Information Access and Dissemination

doi:10.1017/9781316450840.018

17 - Information Theoretic Approaches to Privacy-Preserving Information Access and Dissemination

from Part IV - Data Systems and Related Applications

Published online by Cambridge University Press: 28 June 2017

G. Fanti and

Edited by

Ashish Khisti and

G. Fanti: Affiliation:
Department of Electrical Engineering and Computer Science, University of California, Berkeley
K. Ramchandran: Affiliation:
Department of Electrical Engineering and Computer Science, University of California, Berkeley
Rafael F. Schaefer: Affiliation:
Technische Universität Berlin
Holger Boche: Affiliation:
Technische Universität München
Ashish Khisti: Affiliation:
University of Toronto
H. Vincent Poor: Affiliation:
Princeton University, New Jersey

Book contents

Get access

Summary

The Internet has revolutionized the process of obtaining and sharing information. However, this functionality comes hand-in-hand with pervasive, often subtle, privacy violations. In this chapter, we discuss algorithmic approaches for accessing and disseminating information while protecting the privacy of network users. In particular, we focus on mechanisms that offer information theoretic privacy guarantees; that is, these mechanisms offer protection even against computationally unbounded adversaries. We provide a high-level overview of various classes of privacy-preserving algorithms, with concrete intuition-building examples.

Introduction

People today generate, share, and consume information with unprecedented efficiency. The Internet has enabled realities that seemed impossible a few decades ago: instantaneous global message dissemination, large-scale data storage at minimal cost, and lightning-fast information search and retrieval, to name a few. However, these advances come hand-in-hand with unique privacy threats, which were largely ignored in the push to develop seamless user experiences. Namely, the very information that users willingly consume and produce on the Internet can be deeply revealing about the users themselves. More problematically, leakage of this information poses a significant privacy risk, which can have serious societal repercussions, both psychological and physical [1,2]. In this chapter, we explore several privacy challenges and offer solutions associated with two key aspects of information flow: data dissemination and data access.

When people disseminate information – for instance, by posting a message on a social network – they can inadvertently reveal sensitive information about themselves. Sometimes, this information might be inherent to the content a user posts. For example, if Alice posts on Twitter that she is going to the cinema at 8 pm, then she is implicitly telling her contacts that she will not be home at 8 pm; in the worst case, this could facilitate a robbery. Such content-based data leakage is inevitable, and must be managed by educating users about the privacy implications of posting personal information. However, sometimes information dissemination can also cause unintentional leakage of metadata, or data that is not directly related to content. For example, if Alice posts a picture of her cats to a social network at 3 pm, and the social network includes her GPS location when it propagates the message to her contacts, then Alice's contacts could learn her location at 3 pm.

Type: Chapter
Information: Information Theoretic Security and Privacy of Information Systems , pp. 473 - 498

DOI: https://doi.org/10.1017/9781316450840.018 [Opens in a new window]

Publisher: Cambridge University Press

Print publication year: 2017

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Book purchase

Temporarily unavailable

References

[1] M. R., Lepper and D., Greene, “Turning play into work: Effects of adult surveillance and extrinsic rewards on children's intrinsic motivation,” J. Personality and Social Psychology, vol. 31, no. 3, p. 479, Mar. 1975.Google Scholar

[2] B. J., Alge, “Effects of computer surveillance on perceptions of privacy and procedural justice,” J. Applied Psychology, vol. 86, no. 4, p. 797, Aug. 2001.Google Scholar

[3] G., Greenwald. “XKeyscore: NSA tool collects ‘nearly everything a user does on the internet’,” The Guardian, Jul. 2014. [Online]. Available: www.theguardian.com/world/2013/jul/31/nsa-top-secret-program-online-data

[4] A., Nordrum. “Quantum computer comes closer to cracking RSA encryption,” IEEE Spectrum, Mar. 2016. [Online]. Available: http://spectrum.ieee.org/tech-talk/computing/hardware/encryptionbusting-quantum-computer-practices-factoring-in-scalable-fiveatomexperiment

[5] A., Shontell. “7 people who were arrested because of something they wrote on Facebook,” Jul. 2013. [Online]. Available: www.businessinsider.com/people-arrestedfor-facebook-posts-2013-7

[6] P. K., Smith, J., Mahdavi, M., Carvalho, S., Fisher, S., Russell, and N., Tippett, “Cyberbullying: Its nature and impact in secondary school pupils,” J. Child Psychology and Psychiatry, vol. 49, no. 4, pp. 376–385, Apr. 2008.Google Scholar

[7] D., Chaum, “The dining cryptographers problem: Unconditional sender and recipient untraceability,” J. Cryptology, vol. 1, no. 1, pp. 65–75, Jan. 1988.Google Scholar

[8] M., Waidner and B., Pfitzmann, “The dining cryptographers in the disco: Unconditional sender and recipient untraceability with computationally secure serviceability,” Lecture Notes in Computer Science, vol. 434, p. 690, 1989.Google Scholar

[9] P., Golle and A., Juels, “Dining cryptographers revisited,” Lecture Notes in Computer Science, vol. 3027, pp. 456–473, 2004.Google Scholar

[10] S., Goel, M., Robson, M., Polte, and E., Sirer, “Herbivore: A scalable and efficient protocol for anonymous communication,” Cornell University, Tech. Rep., 2003.

[11] H., Corrigan-Gibbs and B., Ford, “Dissent: Accountable anonymous group messaging,” in Proc. 17th ACM Conf. Computer and Communications Security, Chicago, IL, USA, Oct. 2010, pp. 340–350.

[12] D. I., Wolinsky, H., Corrigan-Gibbs, B., Ford, and A., Johnson, “Dissent in numbers: Making strong anonymity scale,” in Proc. 10th USENIX Conf. Operating Systems Design and Implementation, Hollywood, CA, USA, Oct. 2012, pp. 179–182.

[13] G., Fanti, P., Kairouz, S., Oh, and P., Viswanath, “Spy vs. spy: Rumor source obfuscation,” in Proc. 2015 ACM SIGMETRICS Int. Conf. Measurement and Modeling of Computer Systems, Portland, OR, USA, Jun. 2015, pp. 271–284.

[14] W., Luo, W. P., Tay, and M., Leng, “Rumor spreading and source identification: A hide and seek game,” in Proc. 2015 IEEE/ACM Int. Conf. Advances in Social Networks Analysis and Mining, Paris, France, Aug. 2015, pp. 186–193.

[15] P., Syverson, G., Tsudik, M., Reed, and C., Landwehr, “Towards an analysis of onion routing security,” in Proc. Int. Workshop Designing Privacy Enhancing Technologies: Design Issues in Anonymity and Unobservability, Berkeley, CA, USA, Jul. 2001, pp. 96–114.

[16] J., Feigenbaum, A., Johnson, and P., Syverson, “A model of onion routing with provable anonymity,” Lecture Notes in Computer Science, vol. 4886, pp. 57–71, 2007.Google Scholar

[17] M., Barbaro and T., Zeller. “A face is exposed for AOL searcher no. 4417749,” New York Times, Aug. 2006. [Online]. Available: www.nytimes.com/2006/08/09/technology/09aol.html

[18] D., McCullagh, “Verizon draws fire for monitoring app usage, browsing habits,” CNET, Oct. 2012. [Online]. Available: www.cnet.com/news/verizon-draws-firefor-monitoring-app-usage-browsing-habits/

[19] K., Hill. “Facebook will use your browsing and app history for ads (despite saying it wouldn't 3 years ago),” Forbes, Jun. 2014. [Online]. Available: www.forbes.com/sites/kashmirhill/2014/06/13/facebook-web-app-tracking-for-ads/

[20] R., Dingledine, N., Mathewson, and P., Syverson, “Tor: The second-generation onion router,” in Proc. 13th Conf. USENIX Security Symposium – Volume 13, San Diego, CA, USA, Aug. 2004, pp. 21–21.

[21] C., Gentry and Z., Ramzan, “Single-database private information retrieval with constant communication rate,” Lecture Notes in Computer Science, vol. 3580, pp. 803–815, 2005.Google Scholar

[22] F., Olumofin and I., Goldberg, “Revisiting the computational practicality of private information retrieval,” in Financial Cryptography and Data Security, ser. Lecture Notes in Computer Science, G., Danezis, Ed., Berlin, Heidelberg, 2012, vol. 7035, pp. 158–172.

[23] S., Papadopoulos, S., Bakiras, and D., Papadias, “pCloud: A distributed system for practical PIR,” IEEE Trans. Dependable Secure Computing, vol. 9, no. 1, pp. 115–127, Jan. 2012.Google Scholar

[24] B., Chor, O., Goldreich, E., Kushilevitz, and M., Sudan, “Private information retrieval,” in Proc. 36th Annual Symposium Foundations of Computer Science, Milwaukee, WI, USA, Oct. 1995, pp. 41–50.

[25] C., Devet and I., Goldberg, “The best of both worlds: Combining information-theoretic and computational PIR for communication efficiency,” Lecture Notes in Computer Science, vol. 8555, pp. 63–82. 2014.Google Scholar

[26] S., Yekhanin, “Towards 3-query locally decodable codes of subexponential length,” J. ACM, vol. 55, no. 1, pp. 1:1–1:16, Feb. 2008.

[27] K., Efremenko, “3-query locally decodable codes of subexponential length,” SIAM J. Comput., vol. 41, no. 6, pp. 1694–1703, 2012.Google Scholar

[28] Z., Dvir and S., Gopi, “2-server PIR with sub-polynomial communication,” J. ACM, vol. 63, no. 4, pp. 39:1–39:15, Sep. 2016.Google Scholar

[29] N. B., Shah, K. V., Rashmi, and K., Ramchandran, “One extra bit of download ensures perfectly private information retrieval,” in Proc. IEEE Int. Symp. Inf. Theory, Honolulu, HI, USA, Jul. 2014, pp. 856–860.

[30] A., Fazeli, A., Vardy, and E., Yaakobi, “PIR with low storage overhead: Coding instead of replication,” May 2015. [Online]. Available: http://arxiv.org/abs/1505.06241

[31] A., Beimel, Y., Ishai, and T., Malkin, “Reducing the servers' computation in private information retrieval: PIR with preprocessing,” J. Cryptology, vol. 17, no. 2, pp. 125–151, Mar. 2004.Google Scholar

[32] A., Beimel, Y., Ishai, and E., Kushilevitz, “General constructions for information-theoretic private information retrieval,” J. Computer and System Sciences, vol. 71, no. 2, pp. 213–247, Aug. 2005.Google Scholar

[33] I., Goldberg, “Improving the robustness of private information retrieval,” in IEEE Symp. Security Privacy, Oakland, CA, USA, May 2007, pp. 131–148.

[34] E., Yang, J., Xu, and K., Bennett, “Private information retrieval in the presence of malicious failures,” in Proc. 26th Annual Int. Comp. Software Appl. Conf., Oxford, UK, Aug. 2002, pp. 805–810.

[35] A., Shamir, “How to share a secret,” Commun. ACM, vol. 22, no. 11, pp. 612–613, Nov. 1979.Google Scholar

[36] M., Ben-Or, S., Goldwasser, and A., Wigderson, “Completeness theorems for non-cryptographic fault-tolerant distributed computation,” in Proc. Twentieth Annual ACM Symp. Theory of Comput., Chicago, IL, USA, 1988, pp. 1–10.

[37] C., Devet, I., Goldberg, and N., Heninger, “Optimally robust private information retrieval,” in Proc. 21st USENIX Conf. Security Symp., Bellevue, WA, USA, Aug. 2012, p. 13.

[38] A., Beimel and Y., Stahl, “Robust information-theoretic private information retrieval,” Lecture Notes in Computer Science, vol. 2576, pp. 326–341, 2003.Google Scholar

[39] A., Beimel and Y., Stahl, “Robust information-theoretic private information retrieval,” J. Cryptology, vol. 20, no. 3, pp. 295–321, 2007.Google Scholar

[40] I. S., Reed and G., Solomon, “Polynomial codes over certain finite fields,” J. Society Industrial and Applied Mathematics, vol. 8, no. 2, pp. 300–304, Jun. 1960.Google Scholar

[41] L. R., Welch and E. R., Berlekamp, “Error correction for algebraic block codes,” Dec. 1986, US Patent 4633470.

[42] V., Guruswami and M., Sudan, “Improved decoding of Reed–Solomon and algebraic–geometric codes,” in Proc. 39th Annual Symp. Found. Computer Science, Palo Alto, CA, USA, Nov. 1998, pp. 28–37.

[43] F., Parvares and A., Vardy, “Correcting errors beyond the Guruswami–Sudan radius in polynomial time,” in Proc. 46th Annual IEEE Symp. Found. Computer Science, Pittsburgh, PA, USA, Nov. 2005, pp. 285–294.

[44] V., Guruswami and A., Rudra, “Explicit codes achieving list decoding capacity: Error-correction with optimal redundancy,” IEEE Trans. Inf. Theory, vol. 54, no. 1, pp. 135–150, Jan. 2008.Google Scholar

[45] H., Cohn and N., Heninger, “Approximate common divisors via lattices,” The Open Book Series, vol. 1, no. 1, pp. 271–293, 2013.Google Scholar

[46] P., Mittal, F., Olumofin, C., Troncoso, N., Borisov, and I., Goldberg, “PIR-Tor: Scalable anonymous communication using private information retrieval,” in Proc. 20th USENIX Conf. Security, San Francisco, CA, USA, Aug. 2011, pp. 31–31.

[47] N., Borisov, G., Danezis, and I., Goldberg, “DP5: A private presence service,” Proc. Privacy Enhancing Technol., vol. 2015, no. 2, pp. 1–21, Jun. 2015.Google Scholar

[48] D., Rushe, “Lavabit founder refused FBI order to hand over email encryption keys,” The Guardian, Oct. 2013. [Online]. Available: www.theguardian.com/world/2013/oct/03/lavabit-ladar-levison-fbi-encryption-keys-snowden

[49] H., Corrigan-Gibbs, D., Boneh, and D., Mazières, “Riposte: An anonymous messaging system handling millions of users,” in IEEE Symp. Security and Privacy, San Jose, CA, USA, May 2015, pp. 321–338.

[50] P., Paillier, “Public-Key Cryptosystems Based on Composite Degree Residuosity Classes,” Lecture Notes in Computer Science, vol. 1592, pp. 223–238, 1999.Google Scholar

[51] R., Ostrovsky and W. E., Skeith, “Private searching on streaming data,” Lecture Notes in Computer Science, vol. 3621, pp. 223–240, 2005,Google Scholar

[52] J., Bethencourt, D., Song, and B., Waters, “New constructions and practical applications for private stream searching,” in Proc. IEEE Symp. Security Privacy, Oakland, CA, USA, May 2006, pp. 134–139.

[53] J., Bethencourt, D., Song, and B., Waters, “New techniques for private stream searching,” ACM Trans. Inf. System Security, vol. 12, no. 3, p. 16, Jan. 2009.Google Scholar

[54] G., Danezis and C., Diaz, “Space-efficient private search with applications to rateless codes,” Lecture Notes in Computer Science, vol. 4886, pp. 148–162, 2007.Google Scholar

[55] M., Finiasz and K., Ramchandran, “Private stream search at the same communication cost as a regular search: Role of LDPC codes,” in Proc. IEEE Int. Symp. Inf. Theory, Cambridge, MA, USA, Jul. 2012, pp. 2556–2560.

[56] F., Olumofin and I., Goldberg, “Privacy-preserving queries over relational databases,” Lecture Notes in Computer Science, vol. 6205, pp. 75–92, 2010.Google Scholar

[57] M., Bellare, A., Boldyreva, and A., O'Neill, “Deterministic and efficiently searchable encryption,” Lecture Notes in Computer Science, vol. 4622, pp. 535–552, 2007.Google Scholar

[58] J., Bethencourt, H., Chan, A., Perrig, E., Shi, and D., Song, “Anonymous multi-attribute encryption with range query and conditional decryption,” in Proc. IEEE Symp. Security Privacy, Oakland, CA, USA, May 2006.

[59] D., Boneh and B., Waters, “Conjunctive, subset, and range queries on encrypted data,” Lecture Notes in Computer Science, vol. 4392, pp. 535–554, 2007.Google Scholar

[60] A., Boldyreva, N., Chenette, and A., O'Neill, “Order-preserving encryption revisited: Improved security analysis and alternative solutions,” Lecture Notes in Computer Science, vol. 6841, pp. 578–595, 2011.Google Scholar

[61] R. A., Popa, C., Redfield, N., Zeldovich, and H., Balakrishnan, “CryptDB: Protecting confidentiality with encrypted query processing,” in Proc. 23rd ACM Symp. Operating Systems Principles, Cascais, Portugal, Oct. 2011, pp. 85–100.

[62] R. A., Popa, E., Stark, J., Helfer, S., Valdez, N., Zeldovich, M. F., Kaashoek, and H., Balakrishnan, “Building web applications on top of encrypted data using mylar,” in Proc. 11th USENIX Conf. Networked Systems Design Implementation, Seattle, WA, USA, Apr. 2014, pp. 157–172.

[63] G., Fanti and K., Ramchandran, “Efficient private information retrieval over unsynchronized databases,” in Proc. 52nd Annual Allerton Conf. Commun., Control, Computing,Monticello, IL, USA, Sep. 2014, pp. 1229–1239.