{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T08:02:25Z","timestamp":1758268945850},"reference-count":50,"publisher":"Privacy Enhancing Technologies Symposium Advisory Board","issue":"3","license":[{"start":{"date-parts":[[2017,7,1]],"date-time":"2017-07-01T00:00:00Z","timestamp":1498867200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/3.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017,7,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider privacy-preserving computation of big data using trusted computing primitives with limited private memory. Simply ensuring that the data remains encrypted outside the trusted computing environment is insufficient to preserve data privacy, for data movement observed during computation could leak information. While it is possible to thwart such leakage using generic solution such as ORAM [42], designing efficient privacy-preserving algorithms is challenging. Besides computation efficiency, it is critical to keep trusted code bases lean, for large ones are unwieldy to vet and verify. In this paper, we advocate a simple approach wherein many basic algorithms (e.g., sorting) can be made privacy-preserving by adding a step that securely scrambles the data before feeding it to the original algorithms. We call this approach<jats:italic>Scramble-then-Compute<\/jats:italic>(S<jats:sc>t<\/jats:sc>C), and give a sufficient condition whereby existing external memory algorithms can be made privacy-preserving via S<jats:sc>t<\/jats:sc>C. This approach facilitates code-reuse, and its simplicity contributes to a smaller trusted code base. It is also general, allowing algorithm designers to leverage an extensive body of known efficient algorithms for better performance. Our experiments show that S<jats:sc>t<\/jats:sc>C could offer up to 4.1\u00d7 speedups over known, application-specific alternatives.<\/jats:p>","DOI":"10.1515\/popets-2017-0026","type":"journal-article","created":{"date-parts":[[2017,7,8]],"date-time":"2017-07-08T10:01:47Z","timestamp":1499508107000},"page":"21-38","source":"Crossref","is-referenced-by-count":12,"title":["Privacy-Preserving Computation with Trusted Computing via Scramble-then-Compute"],"prefix":"10.56553","volume":"2017","author":[{"given":"Hung","family":"Dang","sequence":"first","affiliation":[{"name":"National University of Singapore"}]},{"given":"Tien Tuan Anh","family":"Dinh","sequence":"additional","affiliation":[{"name":"National University of Singapore"}]},{"given":"Ee-Chien","family":"Chang","sequence":"additional","affiliation":[{"name":"National University of Singapore"}]},{"given":"Beng Chin","family":"Ooi","sequence":"additional","affiliation":[{"name":"National University of Singapore"}]}],"member":"35752","published-online":{"date-parts":[[2017,7,6]]},"reference":[{"key":"2021040621523502839_j_popets-2017-0026_ref_001_w2aab2b8b9b1b7b1ab1ab1Aa","unstructured":"[1] Apache Spark. http:\/\/spark.apache.org\/."},{"key":"2021040621523502839_j_popets-2017-0026_ref_002_w2aab2b8b9b1b7b1ab1ab2Aa","unstructured":"[2] IBM 4764 PCI-X Cryptographic Coprocessor. http:\/\/www-03.ibm.com\/security\/cryptocards\/pcixcc\/overview.shtml."},{"key":"2021040621523502839_j_popets-2017-0026_ref_003_w2aab2b8b9b1b7b1ab1ab3Aa","unstructured":"[3] IBM PCIe Cryptographic Coprocessor Version 2 (PCIeCC2). http:\/\/www-03.ibm.com\/security\/cryptocards\/pciecc2\/overview.shtml."},{"key":"2021040621523502839_j_popets-2017-0026_ref_004_w2aab2b8b9b1b7b1ab1ab4Aa","unstructured":"[4] Software Guard Extensions Programming Reference. https:\/\/software.intel.com\/sites\/default\/files\/managed\/48\/88\/329298-002.pdf."},{"key":"2021040621523502839_j_popets-2017-0026_ref_005_w2aab2b8b9b1b7b1ab1ab5Aa","unstructured":"[5] WikiLeaks Publishes NSA Target List. https:\/\/www.schneier.com\/blog\/archives\/2016\/03\/wikileaks_publi.html."},{"key":"2021040621523502839_j_popets-2017-0026_ref_006_w2aab2b8b9b1b7b1ab1ab6Aa","doi-asserted-by":"crossref","unstructured":"[6] Ahmad, Muhammad Yousuf, and Kemme, Bettina 2015. Compaction management in distributed key-value datastores. In: PVLDB.","DOI":"10.14778\/2757807.2757810"},{"key":"2021040621523502839_j_popets-2017-0026_ref_007_w2aab2b8b9b1b7b1ab1ab7Aa","unstructured":"[7] Aiyer, Amitanand, Bautin, Mikhail, Chen, Guoqiang Jerry, Damania, Pritam, Khemani, Prakash, Muthukkaruppan, Kannan, Ranganathan, Karthik, Spiegelberg, Nicolas, Tang, Liyin, and Vaidya, Madhuwanti 2012. Storage infrastructure behind facebook messages using hbase at scale. Data Engineering Bulletin."},{"key":"2021040621523502839_j_popets-2017-0026_ref_008_w2aab2b8b9b1b7b1ab1ab8Aa","unstructured":"[8] Arasu, Arvind, Blanas, Spyros, Eguro, Ken, Kaushik, Raghav, Kossmann, Donald, Ramamurthy, Ravi, and Venkatesan, Ramaratnam 2013. Orthogonal Security With Cipherbase. In: CIDR."},{"key":"2021040621523502839_j_popets-2017-0026_ref_009_w2aab2b8b9b1b7b1ab1ab9Aa","unstructured":"[9] Arasu, Arvind, and Kaushik, Raghav 2013. Oblivious query processing. arXiv preprint arXiv:1312.4012."},{"key":"2021040621523502839_j_popets-2017-0026_ref_010_w2aab2b8b9b1b7b1ab1ac10Aa","doi-asserted-by":"crossref","unstructured":"[10] Bajaj, Sumeet, and Sion, Radu 2014. TrustedDB: A Trusted Hardware-Based Database with Privacy and Data Confidentiality. In: TKDE.","DOI":"10.1109\/TKDE.2013.38"},{"key":"2021040621523502839_j_popets-2017-0026_ref_011_w2aab2b8b9b1b7b1ab1ac11Aa","doi-asserted-by":"crossref","unstructured":"[11] Baumann, Andrew, Peinado, Marcus, and Hunt, Galen 2014. Shielding applications from an untrusted cloud with haven. In: OSDI.","DOI":"10.1145\/2799647"},{"key":"2021040621523502839_j_popets-2017-0026_ref_012_w2aab2b8b9b1b7b1ab1ac12Aa","doi-asserted-by":"crossref","unstructured":"[12] Blanton, Marina, Steele, Aaron, and Alisagari, Mehrdad 2013. Data-oblivious graph algorithms for secure computation and outsourcing. In: ASIACCS.","DOI":"10.1145\/2484313.2484341"},{"key":"2021040621523502839_j_popets-2017-0026_ref_013_w2aab2b8b9b1b7b1ab1ac13Aa","doi-asserted-by":"crossref","unstructured":"[13] Blum, Manuel, Floyd, Robert W, Pratt, Vaughan, Rivest, Ronald L, and Tarjan, Robert E 1973. Time bounds for selection. Journal of computer and system sciences.","DOI":"10.1016\/S0022-0000(73)80033-9"},{"key":"2021040621523502839_j_popets-2017-0026_ref_014_w2aab2b8b9b1b7b1ab1ac14Aa","unstructured":"[14] Boneh, Dan, Mazieres, David, and Popa, Raluca Ada 2011. Remote oblivious storage: Making oblivious RAM practical. MIT-CSAIL-TR-2011-018."},{"key":"2021040621523502839_j_popets-2017-0026_ref_015_w2aab2b8b9b1b7b1ab1ac15Aa","doi-asserted-by":"crossref","unstructured":"[15] Brakerski, Zvika, and Brakerski, Zvika 2011. Efficient Fully Homomorphic Encryption from (Standard) LWE. In: FOCS.","DOI":"10.1109\/FOCS.2011.12"},{"key":"2021040621523502839_j_popets-2017-0026_ref_016_w2aab2b8b9b1b7b1ab1ac16Aa","doi-asserted-by":"crossref","unstructured":"[16] Chaum, David L 1981. Untraceable electronic mail, return addresses, and digital pseudonyms. Communications of the ACM.","DOI":"10.1145\/358549.358563"},{"key":"2021040621523502839_j_popets-2017-0026_ref_017_w2aab2b8b9b1b7b1ab1ac17Aa","doi-asserted-by":"crossref","unstructured":"[17] Chen, Shuo, Wang, Rui, Wang, XiaoFeng, and Zhang, Kehuan 2010. Side-Channel Leaks in Web Applications: A Reality Today, a Challenge Tomorrow. In: IEEE S&P (Oakland).","DOI":"10.1109\/SP.2010.20"},{"key":"2021040621523502839_j_popets-2017-0026_ref_018_w2aab2b8b9b1b7b1ab1ac18Aa","unstructured":"[18] Chen, Yao, and Sion, Radu 2012. On securing untrusted clouds with cryptography. Data Engineering Bulletin."},{"key":"2021040621523502839_j_popets-2017-0026_ref_019_w2aab2b8b9b1b7b1ab1ac19Aa","unstructured":"[19] di Vimercati, Sabrina De Capitani, Foresti, Sara, Paraboschi, Stefano, Pelosi, Gerardo, and Samarati, Pierangela 2013. Distributed shuffling for preserving access confidentiality. In: ESORICS."},{"key":"2021040621523502839_j_popets-2017-0026_ref_020_w2aab2b8b9b1b7b1ab1ac20Aa","unstructured":"[20] Dinh, Tien Tuan Anh, Saxena, Prateek, Chang, Ee-Chien, Ooi, Beng Chin, and Zhang, Chunwang 2015. M2R: Enabling Stronger Privacy in MapReduce Computation. In: USENIX Security."},{"key":"2021040621523502839_j_popets-2017-0026_ref_021_w2aab2b8b9b1b7b1ab1ac21Aa","doi-asserted-by":"crossref","unstructured":"[21] ElGamal, Taher 1984. A public key cryptosystem and a signature scheme based on discrete logarithms. In: CRYPTO.","DOI":"10.1109\/TIT.1985.1057074"},{"key":"2021040621523502839_j_popets-2017-0026_ref_022_w2aab2b8b9b1b7b1ab1ac22Aa","doi-asserted-by":"crossref","unstructured":"[22] Gentry, Craig, et al. 2009. Fully homomorphic encryption using ideal lattices. In: STOC.","DOI":"10.1145\/1536414.1536440"},{"key":"2021040621523502839_j_popets-2017-0026_ref_023_w2aab2b8b9b1b7b1ab1ac23Aa","doi-asserted-by":"crossref","unstructured":"[23] Goldreich, Oded, and Ostrovsky, Rafail 1996. Software protection and simulation on oblivious RAMs. Journal of the ACM.","DOI":"10.1145\/233551.233553"},{"key":"2021040621523502839_j_popets-2017-0026_ref_024_w2aab2b8b9b1b7b1ab1ac24Aa","doi-asserted-by":"crossref","unstructured":"[24] Goodrich, Michael T. 2011. Data-oblivious External-memory Algorithms for the Compaction, Selection, and Sorting of Outsourced Data. In: SPAA.","DOI":"10.1145\/1989493.1989555"},{"key":"2021040621523502839_j_popets-2017-0026_ref_025_w2aab2b8b9b1b7b1ab1ac25Aa","doi-asserted-by":"crossref","unstructured":"[25] Goodrich, Michael T 2014. Zig-zag sort: A simple deterministic data-oblivious sorting algorithm running in o (n log n) time. In: STOC.","DOI":"10.1145\/2591796.2591830"},{"key":"2021040621523502839_j_popets-2017-0026_ref_026_w2aab2b8b9b1b7b1ab1ac26Aa","doi-asserted-by":"crossref","unstructured":"[26] Goodrich, Michael T., and Mitzenmacher, Michael 2010. Privacy-preserving access of outsourced data via oblivious RAM simulation. CoRR, abs\/1007.1259.","DOI":"10.1007\/978-3-642-22012-8_46"},{"key":"2021040621523502839_j_popets-2017-0026_ref_027_w2aab2b8b9b1b7b1ab1ac27Aa","unstructured":"[27] Goodrich, Michael T, Ohrimenko, Olga, and Tamassia, Roberto 2012. Data-oblivious graph drawing model and algorithms. arXiv preprint arXiv:1209.0756."},{"key":"2021040621523502839_j_popets-2017-0026_ref_028_w2aab2b8b9b1b7b1ab1ac28Aa","unstructured":"[28] Halevy, Alon, Rajaraman, Anand, and Ordille, Joann 2006. Data Integration: The Teenage Years. In: VLDB."},{"key":"2021040621523502839_j_popets-2017-0026_ref_029_w2aab2b8b9b1b7b1ab1ac29Aa","doi-asserted-by":"crossref","unstructured":"[29] Katz, Jonathan, and Lindell, Yehuda 2014. Introduction to modern cryptography. CRC Press.","DOI":"10.1201\/b17668"},{"key":"2021040621523502839_j_popets-2017-0026_ref_030_w2aab2b8b9b1b7b1ab1ac30Aa","doi-asserted-by":"crossref","unstructured":"[30] Klonowski, Marek, and Kuty\u0142owski, Miros\u0142aw 2005. Provable anonymity for networks of mixes. In: Information Hiding.","DOI":"10.1007\/11558859_3"},{"key":"2021040621523502839_j_popets-2017-0026_ref_031_w2aab2b8b9b1b7b1ab1ac31Aa","unstructured":"[31] Knuth, Donald Ervin 1998. The art of computer programming: sorting and searching, Vol. 3. Pearson Education."},{"key":"2021040621523502839_j_popets-2017-0026_ref_032_w2aab2b8b9b1b7b1ab1ac32Aa","doi-asserted-by":"crossref","unstructured":"[32] Lakshman, Avinash, and Malik, Prashant 2010. Cassandra: a decentralized structured storage system. Operating Systems Review, 44.","DOI":"10.1145\/1773912.1773922"},{"key":"2021040621523502839_j_popets-2017-0026_ref_033_w2aab2b8b9b1b7b1ab1ac33Aa","doi-asserted-by":"crossref","unstructured":"[33] Li, Feifei, Hadjieleftheriou, Marios, Kollios, George, and Reyzin, Leonid 2006. Dynamic authenticated index structure for outsourced databases. In: ACM SIGMOD.","DOI":"10.1145\/1142473.1142488"},{"key":"2021040621523502839_j_popets-2017-0026_ref_034_w2aab2b8b9b1b7b1ab1ac34Aa","doi-asserted-by":"crossref","unstructured":"[34] McCun, Jonathan M., Parno, Bryan, Perrig, Adrian, Reiter, Michael K., and Isozaki, Hiroshi 2008. Flicker: An Execution Infrastructure for TCB Minimization. In: EuroSys.","DOI":"10.1145\/1352592.1352625"},{"key":"2021040621523502839_j_popets-2017-0026_ref_035_w2aab2b8b9b1b7b1ab1ac35Aa","doi-asserted-by":"crossref","unstructured":"[35] McCune, J.M., Li, Y., Qu, N., Zhou, Z., Datta, A., Gligor, V., and Perrig, A. 2010. TrustVisor: Efficient TCB Reduction and Attestation. In: IEEE S&P (Oakland).","DOI":"10.1109\/SP.2010.17"},{"key":"2021040621523502839_j_popets-2017-0026_ref_036_w2aab2b8b9b1b7b1ab1ac36Aa","unstructured":"[36] Meng, Xiangrui, Bradley, Joseph, Yuvaz, B, Sparks, Evan, Venkataraman, Shivaram, Liu, Davies, Freeman, Jeremy, Tsai, D, Amde, Manish, Owen, Sean, et al. 2016. Mllib: Machine learning in apache spark. JMLR."},{"key":"2021040621523502839_j_popets-2017-0026_ref_037_w2aab2b8b9b1b7b1ab1ac37Aa","doi-asserted-by":"crossref","unstructured":"[37] Ohrimenko, Olga, Costa, Manuel, Fournet, Cedric, Gkantsidis, Christos, Kohlweiss, Markulf, and Sharma, Divya 2015. Observing and Preventing Leakage in MapReduce. In: CCS.","DOI":"10.1145\/2810103.2813695"},{"key":"2021040621523502839_j_popets-2017-0026_ref_038_w2aab2b8b9b1b7b1ab1ac38Aa","doi-asserted-by":"crossref","unstructured":"[38] Ohrimenko, Olga, Goodrich, Michael T, Tamassia, Roberto, and Upfal, Eli 2014. The Melbourne shuffle: Improving oblivious storage in the cloud. In: ICALP.","DOI":"10.1007\/978-3-662-43951-7_47"},{"key":"2021040621523502839_j_popets-2017-0026_ref_039_w2aab2b8b9b1b7b1ab1ac39Aa","unstructured":"[39] Ohrimenko, Olga, Schuster, Felix, Fournet, C\u00e9dric, Mehta, Aastha, Nowozin, Sebastian, Vaswani, Kapil, and Costa, Manuel 2016. Oblivious Multi-Party Machine Learning on Trusted Processors. In: USENIX Security."},{"key":"2021040621523502839_j_popets-2017-0026_ref_040_w2aab2b8b9b1b7b1ab1ac40Aa","unstructured":"[40] O\u2019Malley, Owen, and Murthy, Arun C 2009. Winning a 60 second dash with a yellow elephant. Tech. rep., Yahoo."},{"key":"2021040621523502839_j_popets-2017-0026_ref_041_w2aab2b8b9b1b7b1ab1ac41Aa","unstructured":"[41] Paillier, Pascal 1999. Public-key cryptosystems based on composite degree residuosity classes. In: EUROCRYPT."},{"key":"2021040621523502839_j_popets-2017-0026_ref_042_w2aab2b8b9b1b7b1ab1ac42Aa","doi-asserted-by":"crossref","unstructured":"[42] Pinkas, Benny, and Reinman, Tzachy 2010. Oblivious RAM revisited. In: CRYPTO.","DOI":"10.1007\/978-3-642-14623-7_27"},{"key":"2021040621523502839_j_popets-2017-0026_ref_043_w2aab2b8b9b1b7b1ab1ac43Aa","doi-asserted-by":"crossref","unstructured":"[43] Popa, Raluca Ada, Redfield, Catherine, Zeldovich, Nickolai, and Balakrishnan, Hari 2011. CryptDB: Protecting confidentiality with encrypted query processing. In: SOSP.","DOI":"10.1145\/2043556.2043566"},{"key":"2021040621523502839_j_popets-2017-0026_ref_044_w2aab2b8b9b1b7b1ab1ac44Aa","doi-asserted-by":"crossref","unstructured":"[44] Schuster, Felix, Costa, Manuel, Fournet, C\u00e9dric, Gkantsidis, Christos, Peinado, Marcus, Mainar-Ruiz, Gloria, and Russinovich, Mark 2014. VC3: Trustworthy DATA analytics in the cloud. In: IEEE S&P (Oakland).","DOI":"10.1109\/SP.2015.10"},{"key":"2021040621523502839_j_popets-2017-0026_ref_045_w2aab2b8b9b1b7b1ab1ac45Aa","doi-asserted-by":"crossref","unstructured":"[45] Stefanov, Emil, Van Dijk, Marten, Shi, Elaine, Fletcher, Christopher, Ren, Ling, Yu, Xiangyao, and Devadas, Srinivas 2013. Path ORAM: An extremely simple oblivious RAM protocol. In: CCS.","DOI":"10.1145\/2508859.2516660"},{"key":"2021040621523502839_j_popets-2017-0026_ref_046_w2aab2b8b9b1b7b1ab1ac46Aa","doi-asserted-by":"crossref","unstructured":"[46] Tu, Stephen, Kaashoek, M Frans, Madden, Samuel, and Zeldovich, Nickolai 2013. Processing analytical queries over encrypted data. In: PVLDB.","DOI":"10.14778\/2535573.2488336"},{"key":"2021040621523502839_j_popets-2017-0026_ref_047_w2aab2b8b9b1b7b1ab1ac47Aa","doi-asserted-by":"crossref","unstructured":"[47] Vimercati, Sabrina De Capitani Di, Foresti, Sara, Paraboschi, Stefano, Pelosi, Gerardo, and Samarati, Pierangela 2015. Shuffle index: efficient and private access to outsourced data. TOS.","DOI":"10.1007\/978-1-4939-2092-1_33"},{"key":"2021040621523502839_j_popets-2017-0026_ref_048_w2aab2b8b9b1b7b1ab1ac48Aa","doi-asserted-by":"crossref","unstructured":"[48] Wang, Shuhong, Ding, Xuhua, Deng, Robert H, and Bao, Feng 2006. Private information retrieval using trusted hardware. In: ESORICS.","DOI":"10.1007\/11863908_4"},{"key":"2021040621523502839_j_popets-2017-0026_ref_049_w2aab2b8b9b1b7b1ab1ac49Aa","doi-asserted-by":"crossref","unstructured":"[49] Xin, Reynold S, Gonzalez, Joseph E, Franklin, Michael J, and Stoica, Ion 2013. Graphx: A resilient distributed graph system on spark. In: GRADES.","DOI":"10.1145\/2484425.2484427"},{"key":"2021040621523502839_j_popets-2017-0026_ref_050_w2aab2b8b9b1b7b1ab1ac50Aa","unstructured":"[50] Zaharia, Matei, Chowdhury, Mosharaf, Franklin, Michael J, Shenker, Scott, and Stoica, Ion 2010. Spark: Cluster computing with working sets. HotCloud."}],"container-title":["Proceedings on Privacy Enhancing Technologies"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/content.sciendo.com\/view\/journals\/popets\/2017\/3\/article-p21.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.sciendo.com\/article\/10.1515\/popets-2017-0026","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,30]],"date-time":"2022-07-30T16:38:11Z","timestamp":1659199091000},"score":1,"resource":{"primary":{"URL":"https:\/\/petsymposium.org\/popets\/2017\/popets-2017-0026.php"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,7,1]]},"references-count":50,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2017,7,6]]},"published-print":{"date-parts":[[2017,7,1]]}},"alternative-id":["10.1515\/popets-2017-0026"],"URL":"https:\/\/doi.org\/10.1515\/popets-2017-0026","relation":{},"ISSN":["2299-0984"],"issn-type":[{"value":"2299-0984","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,7,1]]}}}