Pretzel: Email encryption and provider-supplied functions are compatible

ABSTRACT

Emails today are often encrypted, but only between mail servers---the vast majority of emails are exposed in plaintext to the mail servers that handle them. While better than no encryption, this arrangement leaves open the possibility of attacks, privacy violations, and other disclosures. Publicly, email providers have stated that default end-to-end encryption would conflict with essential functions (spam filtering, etc.), because the latter requires analyzing email text. The goal of this paper is to demonstrate that there is no conflict. We do so by designing, implementing, and evaluating Pretzel. Starting from a cryptographic protocol that enables two parties to jointly perform a classification task without revealing their inputs to each other, Pretzel refines and adapts this protocol to the email context. Our experimental evaluation of a prototype demonstrates that email can be encrypted end-to-end and providers can compute over it, at tolerable cost: clients must devote some storage and processing, and provider overhead is roughly 5x versus the status quo.

References

1. http://openpgp.org/.
2. https://keybase.io.
3. http://spamprobe.sourceforge.net/.
4. http://spambayes.sourceforge.net/.
5. http://spamassassin.apache.org/.
6. http://scikit-learn.org/stable/.
7. http://www.cs.waikato.ac.nz/ml/weka/.
8. https://support.google.com/ads/answer/2842480?hl=en.
9. https://www.gnupg.org/software/gpgme/index.html.
10. https://www.sqlite.org/fts3.html.
11. https://www.cs.cmu.edu/~./enron/.
12. http://qwone.com/~jason/20Newsgroups/.
13. http://www.daviddlewis.com/resources/testcollections/reuters21578/.
14. http://email.about.com/od/emailstatistics/f/What_is_the_Average_Size_of_an_Email_Message.htm.
15. http://www.gossamer-threads.com/lists/spamassassin/users/151578.
16. http://users.spamassassin.apache.narkive.com/d6ppUDfw/large-scale-global-bayes-tuning.
17. http://spamassassin.apache.org/full/3.4.x/doc/Mail_SpamAssassin_Conf.html.
18. A survey on ring-LWE cryptography, Feb. 2016. https://www.microsoft.com/en-us/research/video/a-survey-on-ring-lwe-cryptography/.
19. P. Aditya, R. Sen, P. Druschel, S. J. Oh, R. Benenson, M. Fritz, B. Schiele, B. Bhattacharjee, and T. T. Wu. I-Pic: A platform for privacy-compliant image capture. In MobiSys, 2016.
20. C. Aguilar-Melchor, J. Barrier, L. Fousse, and M.-O. Killijian. XPIR: Private Information Retrieval for Everyone. In PETS, 2016.
21. A. Amirbekyan and V. Estivill-Castro. A new efficient privacy-preserving scalar product protocol. In Australasian conference on Data mining and analytics (AusDM), 2007.
22. I. Androutsopoulos, J. Koutsias, K. Chandrinos, G. Paliouras, and C. Spyropoulos. An evaluation of Naive Bayesian anti-spam filtering. In Workshop on Machine Learning in the New Information Age, 2000.
23. Apple. Our Approach to Privacy. http://www.apple.com/privacy/approach-to-privacy/.
24. M. L. G. at National Taiwan University. LIBLINEAR--A library for large linear classification. https://www.csie.ntu.edu.tw/~cjlin/liblinear/.
25. M. J. Atallah and W. Du. Secure multi-party computational geometry. In Workshop on Algorithms and Data Structures (WADS). 2001.
26. M. Ball, T. Malkin, and M. Rosulek. Garbling gadgets for boolean and arithmetic circuits. In ACM CCS, 2016.
27. D. Beeby. Rogue tax workers snooped on ex-spouses, family members. Toronto Star, June 2010. https://www.thestar.com/news/canada/2010/06/20/rogue_tax_workers_snooped_on_exspouses_family_members.html.
28. E. Betters. What is Google Assistant, how does it work, and when can you use it?, Sept. 2016. http://www.pocket-lint.com/news/137722-what-is-google-assistant-how-does-it-work-and-when-can-you-use-it.
29. B. Biggio, I. Corona, D. Maiorca, B. Nelson, N. Šrndić, P. Laskov, G. Giacinto, and F. Roli. Evasion attacks against machine learning at test time. In ECML-PKDD, 2013.
30. M. Blanton and P. Gasti. Secure and efficient protocols for iris and fingerprint identification. In ESORICS, 2011.
31. J. Bonneau. EthIKS: Using Ethereum to audit a CONIKS key transparency log. In FC, 2016.
32. B. E. Boser, I. M. Guyon, and V. N. Vapnik. A training algorithm for optimal margin classifiers. In Wkshp on Computational Learning Theory (COLT), 1992.
33. R. Bost, R. A. Popa, S. Tu, and S. Goldwasser. Machine learning classification over encrypted data. In NDSS, 2014.
34. Z. Brakerski and V. Vaikuntanathan. Fully homomorphic encryption from ring-LWE and security for key dependent messages. In CRYPTO, 2011.
35. L. Breiman, J. Friedman, C. J. Stone, and R. A. Olshen. Classification and regression trees. CRC press, 1984.
36. J. Bringer, O. El Omri, C. Morel, and H. Chabanne. Boosting GSHADE capabilities: New applications and security in malicious setting. In Symposium on Access Control Models and Technologies (SACMAT), 2016.
37. J. Callas, L. Donnerhacke, H. Finney, D. Shaw, and R. Thayer. OpenPGP message format. RFC 4880, IETF, 2007.
38. Y.-T. Chiang, D.-W. Wang, C.-J. Liau, and T.-s. Hsu. Secrecy of two-party secure computation. In IFIP DBSec. 2005.
39. P. Ciano. How to use Google Now, Mar. 2014. https://paulciano.org/2014/03/getting-google-now/.
40. M. Cohen. Web storage overview. https://developers.google.com/web/fundamentals/instant-and-offline/web-storage/.
41. K. Conger. Google engineer says he'll push for default end-to-end encryption in Allo, May 2016. https://techcrunch.com/2016/05/19/google-engineer-says-hell-push-for-default-end-to-end-encryption-in-allo/.
42. K. Conger. Google's Allo won't include end-to-end encryption by default, May 2016. https://techcrunch.com/2016/05/18/googles-allo-wont-include-end-to-end-encryption-by-default/.
43. J. Corbet. The grumpy editor's guide to bayesian spam filters, 2006. https://lwn.net/Articles/172491/.
44. G. V. Cormack. TREC 2007 spam track overview. In TREC, 2007.
45. C. Cortes and V. Vapnik. Support-vector networks. Machine Learning, 20(3):273--297, 1995.
46. R. De Clercq, S. S. Roy, F. Vercauteren, and I. Verbauwhede. Efficient software implementation of ring-LWE encryption. In Design, Automation & Test in Europe (DATE), 2015.
47. T. Dierks and E. Rescorla. The transport layer security (TLS) protocol version 1.2. RFC 5246, Network Working Group, 2008.
48. W. Diffie and M. Hellman. New directions in cryptography. IEEE transactions on Information Theory, 22(6):644--654, 1976.
49. J. Dizon. Gmail can now automatically put flight, hotel, ticket, or restaurant info on Google calendar, Aug. 2015. http://www.techtimes.com/articles/79380/20150826/gmail-can-now-automatically-put-flight-hotel-ticket-or-restaurant-info-on-google-calendar.htm.
50. Y. Dodis, R. Gennaro, J. Håstad, H. Krawczyk, and T. Rabin. Randomness extraction and key derivation using the CBC, cascade and HMAC modes. In CRYPTO, 2004.
51. C. Dong and L. Chen. A fast secure dot product protocol with application to privacy preserving association rule mining. In PAKDD, 2014.
52. W. Du and M. J. Atallah. Protocols for secure remote database access with approximate matching. In E-Commerce Security and Privacy, 2001.
53. W. Du and Z. Zhan. Building decision tree classifier on private data. In Intl. Conf. on Data Mining Wkshp on Privacy, Security and Data Mining (PSDM), 2002.
54. W. Du and Z. Zhan. A practical approach to solve secure multi-party computation problems. In New security paradigms workshop (NSPW), 2002.
55. T. Duong. Security and privacy in Google Allo, May 2016. https://vnhacker.blogspot.com/2016/05/security-and-privacy-in-google-allo.html.
56. Z. Durumeric, D. Adrian, A. Mirian, J. Kasten, E. Bursztein, N. Lidzborski, K. Thomas, V. Eranti, M. Bailey, and J. A. Halderman. Neither snow nor rain nor MITM...: An empirical analysis of email delivery security. In IMC, 2015.
57. R.-E. Fan, K.-W. Chang, C.-J. Hsieh, X.-R. Wang, and C.-J. Lin. LIBLINEAR: A library for large linear classification. JMLR, 9(Aug):1871--1874, 2008.
58. L. Franceschi-Bicchierai. Even the inventor of PGP doesn't use PGP, 2015. http://motherboard.vice.com/read/even-the-inventor-of-pgp-doesnt-use-pgp.
59. C. Gentry, S. Halevi, and N. P. Smart. Homomorphic evaluation of the AES circuit. In CRYPTO. 2012.
60. B. Goethals, S. Laur, H. Lipmaa, and T. Mielikäinen. On private scalar product computation for privacy-preserving data mining. In Intl. Conf. on Information Security and Cryptology (ICISC). 2004.
61. O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game. In STOC, 1987.
62. J. Goodman and W.-t. Yih. Online discriminative spam filter training. In Conf. on Email and Anti-Spam (CEAS), 2006.
63. Google. https://github.com/google/end-to-end.
64. Google. Google transparency report. https://www.google.com/transparencyreport/userdatarequests/US/.
65. Google. How Gmail ads work. https://support.google.com/mail/answer/6603?hl=en.
66. S. D. Gordon, J. Katz, V. Kolesnikov, F. Krell, T. Malkin, M. Raykova, and Y. Vahlis. Secure two-party computation in sublinear (amortized) time. In ACM CCS, 2012.
67. J. Gould. The natural history of Gmail data mining. Gmail isn't really about email---it's a gigantic profiling machine. Medium, June 2014. https://medium.com/@jeffgould/the-natural-history-of-gmail-data-mining-be115d196b10.
68. P. Graham. A plan for spam, 2002. http://www.paulgraham.com/spam.html.
69. P. Graham. Better Bayesian filtering, 2003. http://www.paulgraham.com/better.html.
70. T. Gupta, H. Fingler, L. Alvisi, and M. Walfish. Pretzel: Email encryption and provider-supplied functions are compatible (extended version). arXiv preprint arXiv:1612.04265, 2016.
71. J. Huang, J. Lu, and C. X. Ling. Comparing Naive Bayes, decision trees, and SVM with AUC and accuracy. In Intl. Conf. on Data Mining (ICDM), 2003.
72. Y. Huang, D. Evans, J. Katz, and L. Malka. Faster secure two-party computation using garbled circuits. In USENIX Security, 2011.
73. Y. Huang, J. Katz, and D. Evans. Quid-pro-quo-tocols: Strengthening semi-honest protocols with dual execution. In IEEE S&P, 2012.
74. Y. Huang, Z. Lu, et al. Privacy preserving association rule mining with scalar product. In International Conference on Natural Language Processing and Knowledge Engineering (NLP-KE), 2005.
75. Y. Huang, L. Malka, D. Evans, and J. Katz. Efficient privacy-preserving biometric identification. In NDSS, 2011.
76. I. Ioannidis, A. Grama, and M. Atallah. A secure protocol for computing dot-products in clustered and distributed environments. In International Conference on Parallel Processing (ICPP), 2002.
77. Y. Ishai, J. Kilian, K. Nissim, and E. Petrank. Extending oblivious transfers efficiently. In CRYPTO, 2003.
78. T. Joachims. Text categorization with Support Vector Machines: Learning with many relevant features. In ECML, 1998.
79. C. Kaleli and H. Polat. Providing Naïve Bayesian classifier-based private recommendations on partitioned data. In PKDD, 2007.
80. J.-S. Kang and D. Hong. On fast private scalar product protocols. In Security Technology (SecTech). 2011.
81. M. Keller, E. Orsini, and P. Scholl. Actively secure OT extension with optimal overhead. In CRYPTO, 2015.
82. A. Khedr, G. Gulak, and V. Vaikuntanathan. SHIELD: Scalable homomorphic implementation of encrypted data-classifiers. IEEE Transactions on Computers, 65(9):2848--2858, 2014.
83. B. Kreuter, A. Shelat, and C.-H. Shen. Billion-gate secure computation with malicious adversaries. In USENIX Security, 2012.
84. S. Laur and H. Lipmaa. On private similarity search protocols. In Nordic Workshop on Secure IT Systems (NordSec), 2004.
85. D. D. Lewis, Y. Yang, T. G. Rose, and F. Li. RCV1: A new benchmark collection for text categorization research. JMLR, 5(Apr):361--397, 2004.
86. C.-J. Lin, R. C. Weng, and S. S. Keerthi. Trust region Newton method for logistic regression. JMLR, 9(Apr):627--650, 2008.
87. Y. Lindell. Fast cut-and-choose-based protocols for malicious and covert adversaries. Journal of Cryptology, 29(2):456--490, 2016.
88. Y. Lindell and B. Pinkas. A proof of security of Yao's protocol for two-party computation. Journal of Cryptology, 22(2):161--188, 2009.
89. X. Liu, R. Lu, J. Ma, L. Chen, and B. Qin. Privacy-preserving patient-centric clinical decision support system on Naive Bayesian classification. IEEE Journal of Biomedical and Health Informatics, 20(2):655--668, 2016.
90. V. Lyubashevsky, C. Peikert, and O. Regev. On ideal lattices and learning with errors over rings. In EUROCRYPT, 2010.
91. V. Lyubashevsky, C. Peikert, and O. Regev. A toolkit for ring-LWE cryptography. In EUROCRYPT, 2013.
92. A. McCallum, K. Nigam, et al. A comparison of event models for Naive Bayes text classification. In AAAI workshop on learning for text categorization, 1998.
93. M. S. Melara, A. Blankstein, J. Bonneau, E. W. Felten, and M. J. Freedman. CONIKS: Bringing key transparency to end users. In USENIX Security, 2015.
94. R. C. Merkle. Secure communications over insecure channels. Communications of the ACM, 21(4):294--299, Apr. 1978.
95. V. Metsis, I. Androutsopoulos, and G. Paliouras. Spam filtering with Naive Bayes--which Naive Bayes? In Conf. on Email and Anti-Spam (CEAS), 2006.
96. T. Meyer. No warrant, no problem: How the government can get your digital data. ProPublica, June 2014. https://www.propublica.org/special/no-warrant-no-problem-how-the-government-can-still-get-your-digital-data/.
97. Microsoft. Law enforcement requests report. https://www.microsoft.com/about/csr/transparencyhub/lerr/.
98. A. Y. Ng and M. I. Jordan. On discriminative vs. generative classifiers: A comparison of logistic regression and naive Bayes. In NIPS, 2001.
99. P. Paillier. Public-key cryptosystems based on composite degree residuosity classes. In EUROCRYPT, 1999.
100. M. A. Pathak, M. Sharifi, and B. Raj. Privacy preserving spam filtering. arXiv preprint arXiv:1102.4021, 2011.
101. C. Peikert. How (not) to instantiate ring-LWE. In Conference on Security and Cryptography for Networks (SCN), 2016.
102. S. Perez. Microsoft's Cortana can now create reminders from your emails, Feb. 2017. https://techcrunch.com/2017/02/09/microsofts-cortana-can-now-create-reminders-from-your-emails/.
103. K. Poulsen. Five IRS employees charged with snooping on tax returns. Wired, May 2008. https://www.wired.com/2008/05/five-irs-employ/.
104. G. Robinson. A statistical approach to the spam problem. Linux Journal, Mar. 2003. http://www.linuxjournal.com/article/6467.
105. S. S. Roy, F. Vercauteren, N. Mentens, D. D. Chen, and I. Verbauwhede. Compact ring-LWE cryptoprocessor. In International Workshop on Cryptographic Hardware and Embedded Systems (CHES), 2014.
106. A.-R. Sadeghi, T. Schneider, and I. Wehrenberg. Efficient privacy-preserving face recognition. In Intl. Conf. on Information Security and Cryptology (ICISC), 2009.
107. A.-R. Sadeghi, T. Schneider, and I. Wehrenberg. Efficient privacy-preserving face recognition (full version). Cryptology ePrint Archive, Report 507, 2009.
108. D. Sculley and G. Wachman. Relaxed online SVMs in the TREC spam filtering track. In TREC, 2007.
109. D. Sculley and G. M. Wachman. Relaxed online SVMs for spam filtering. In ACM SIGIR Conference, 2007.
110. R. Shaltiel. Recent developments in explicit constructions of extractors. Bulletin of the European Association for Theoretical Computer Science (EATCS), 77(67-95):10, 2002.
111. M. Shaneck and Y. Kim. Efficient cryptographic primitives for private data mining. In Hawaii Intl. Conf. on System Sciences (HICSS), 2010.
112. C. Soghoian. Two honest Google employees: our products don't protect your privacy, Nov. 2011. http://paranoia.dubfire.net/2011/11/two-honest-google-employees-our.html.
113. S. Somogyi. Making end-to-end encryption easier to use. Google Security Blog, June 2014. https://security.googleblog.com/2014/06/making-end-to-end-encryption-easier-to.html.
114. E. M. Songhori, S. U. Hussain, A.-R. Sadeghi, T. Schneider, and F. Koushanfar. TinyGarble: Highly compressed and scalable sequential garbled circuits. In IEEE S&P, 2015.
115. A. Stamos. User-focused security: End-to-end encryption extension for Yahoo Mail. Yahoo Tumblr Blog, Mar. 2015. https://yahoo.tumblr.com/post/113708033335/user-focused-security-end-to-end-encryption.
116. B. Tang, S. Kay, and H. He. Toward optimal feature selection in Naive Bayes for text categorization. IEEE Transactions on Knowledge and Data Engineering, 28(9):2508--2521, 2016.
117. F. Tramèr, F. Zhang, A. Juels, M. K. Reiter, and T. Ristenpart. Stealing machine learning models via prediction APIs. In USENIX Security, 2016.
118. D. Trincă and S. Rajasekaran. Fast cryptographic multi-party protocols for computing boolean scalar products with applications to privacy-preserving association rule mining in vertically partitioned data. In Data Warehousing and Knowledge Discovery (DaWaK). 2007.
119. S. Tu, M. F. Kaashoek, S. Madden, and N. Zeldovich. Processing analytical queries over encrypted data. PVLDB, 6(5):289--300, Mar. 2013.
120. J. Vaidya and C. Clifton. Privacy preserving association rule mining in vertically partitioned data. In KDD, 2002.
121. J. Vaidya, M. Kantarcıoğlu, and C. Clifton. Privacy-preserving Naive Bayes classification. The VLDB Journal, 17(4):879--898, 2008.
122. J. Vaidya, B. Shafiq, A. Basu, and Y. Hong. Differentially private Naive Bayes classification. In IEEE/WIC/ACM International Joint Conferences on Web Intelligence (WI) and Intelligent Agent Technologies (IAT), 2013.
123. J. Vaidya, H. Yu, and X. Jiang. Privacy-preserving SVM classification. Knowledge and Information Systems, 14(2):161--178, 2008.
124. L. Vanderkam. Stop checking your email, now. Fortune, Oct. 2012. http://fortune.com/2012/10/08/stop-checking-your-email-now/.
125. N. Šrndic and P. Laskov. Practical evasion of a learning-based classifier: A case study. In IEEE S&P, 2014.
126. WhatsApp. WhatsApp FAQ - End-to-End Encryption. https://www.whatsapp.com/faq/en/general/28030015.
127. Wikipedia. 2016 Democratic National Committee email leak, 2014. https://en.wikipedia.org/wiki/2016_Democratic_National_Committee_email_leak.
128. Wikipedia. Sony pictures hack, 2014. https://en.wikipedia.org/wiki/Sony_Pictures_hack.
129. R. Wright and Z. Yang. Privacy-preserving Bayesian network structure computation on distributed heterogeneous data. In KDD, 2004.
130. Yahoo! https://github.com/yahoo/end-to-end.
131. Yahoo! Transparency report: Overview. https://transparency.yahoo.com/.
132. Z. Yang, S. Zhong, and R. N. Wright. Privacy-preserving classification of customer data without loss of accuracy. In SIAM International Conference on Data Mining (SDM), 2005.
133. A. C. Yao. Protocols for secure computations. In Symposium on Foundations of Computer Science (SFCS), 1982.
134. X. Yi and Y. Zhang. Privacy-preserving Naive Bayes classification on distributed data via semi-trusted mixers. Info. Systems, 34(3):371--380, 2009.
135. H. Yu, X. Jiang, and J. Vaidya. Privacy-preserving SVM using nonlinear kernels on horizontally partitioned data. In ACM Symposium on Applied Computing (SAC), 2006.
136. H. Yu, J. Vaidya, and X. Jiang. Privacy-preserving SVM classification on vertically partitioned data. In PAKDD, 2006.
137. S. Zahur and D. Evans. Obliv-C: A language for extensible data-oblivious computation. Cryptology ePrint Archive, Report 1153, 2015.
138. S. Zahur, M. Rosulek, and D. Evans. Two halves make a whole. In EUROCRYPT. 2015.
139. S. Zahur, X. Wang, M. Raykova, A. Gascón, J. Doerner, D. Evans, and J. Katz. Revisiting square-root ORAM efficient random access in multi-party computation. In IEEE S&P, 2016.
140. K. Zetter. Ex-Googler allegedly spied on user e-mails, chats, Sept. 2010. https://www.wired.com/2010/09/google-spy/.
141. H. Zhang. The optimality of Naive Bayes. AA, 1(2):3, 2004.
142. P. Zhang, Y. Tong, S. Tang, and D. Yang. Privacy preserving Naive Bayes classification. In Advanced Data Mining and Applications (ADMA). 2005.
143. Y. Zhu, Z. Wang, B. Hassan, Y. Zhang, J. Wang, and C. Qian. Fast secure scalar product protocol with (almost) optimal efficiency. In Collaborative Computing: Networking, Applications, and Worksharing (CollaborateCom). 2015.
144. P. R. Zimmermann. The official PGP user's guide. MIT press, 1995.

Index Terms

• Information systems

  • World Wide Web

    • Web applications

      • Internet communications tools

        • Email

• Security and privacy

  • Cryptography

  • Security services

    • Privacy-preserving protocols