{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,3]],"date-time":"2026-05-03T10:59:49Z","timestamp":1777805989431,"version":"3.51.4"},"reference-count":63,"publisher":"SAGE Publications","issue":"2","license":[{"start":{"date-parts":[[2015,12,16]],"date-time":"2015-12-16T00:00:00Z","timestamp":1450224000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Journal of Computer Security"],"published-print":{"date-parts":[[2016,4,19]]},"abstract":"<jats:p>Garbled circuits provide a powerful tool for jointly evaluating functions while preserving the privacy of each user\u2019s inputs. While recent research has made the use of this primitive more practical, such solutions generally assume that participants are symmetrically provisioned with massive computing resources. In reality, most people on the planet only have access to the comparatively sparse computational resources associated with their mobile phones, and those willing and able to pay for access to public cloud computing infrastructure cannot be assured that their data will remain unexposed. We address this problem by creating a new SFE protocol that allows mobile devices to securely outsource the majority of computation required to evaluate a garbled circuit. Our protocol, which builds on the most efficient garbled circuit evaluation techniques, includes a new outsourced oblivious transfer primitive that requires significantly less bandwidth and computation than standard OT primitives and outsourced input validation techniques that force the cloud to prove that it is executing all protocols correctly. After showing that our extensions are secure in the malicious model, we conduct an extensive performance evaluation for a number of standard SFE test applications as well as a privacy-preserving navigation application designed specifically for the mobile use-case. Our system reduces execution time by 98.92% and bandwidth by 99.95% for the edit distance problem of size 128 compared to non-outsourced evaluation. These results show that even the least capable devices are capable of using large garbled circuits for secure computation.<\/jats:p>","DOI":"10.3233\/jcs-150540","type":"journal-article","created":{"date-parts":[[2016,4,19]],"date-time":"2016-04-19T12:25:32Z","timestamp":1461068732000},"page":"137-180","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":39,"title":["Secure outsourced garbled circuit evaluation for mobile devices"],"prefix":"10.1177","volume":"24","author":[{"given":"Henry","family":"Carter","sequence":"first","affiliation":[{"name":"School of Computer Science, Georgia Institute of Technology, Atlanta, GA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benjamin","family":"Mood","sequence":"additional","affiliation":[{"name":"School of Computer and Information Science and Engineering, University of Florida, Gainesville,\u00a0FL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Patrick","family":"Traynor","sequence":"additional","affiliation":[{"name":"School of Computer and Information Science and Engineering, University of Florida, Gainesville,\u00a0FL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kevin","family":"Butler","sequence":"additional","affiliation":[{"name":"School of Computer and Information Science and Engineering, University of Florida, Gainesville,\u00a0FL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2015,12,16]]},"reference":[{"key":"ref001","doi-asserted-by":"crossref","unstructured":"G.Asharov, Y.Lindell, T.Schneider and M.Zohner, More efficient oblivious transfer and extensions for faster secure computation, in: Proceedings of the ACM Conference on Computer and Communications Security, 2013.","DOI":"10.1145\/2508859.2516738"},{"key":"ref002","unstructured":"M.Bellare and S.Micali, Non-interactive oblivious transfer and applications, in: Advances in Cryptology\u00a0\u2013 CRYPTO, 1990."},{"key":"ref003","doi-asserted-by":"crossref","unstructured":"M.Ben-Or, S.Goldwasser and A.Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, in: Proceedings of the Annual ACM Symposium on Theory of Computing, 1988.","DOI":"10.1145\/62212.62213"},{"key":"ref004","doi-asserted-by":"crossref","unstructured":"R.Bendlin, I.Damg\u00e5rd, C.Orlandi and S.Zakarias, Semi-homomorphic encryption and multiparty computation, in: Proceedings of the Annual International Conference on Theory and Applications of Cryptographic Techniques, 2011.","DOI":"10.1007\/978-3-642-20465-4_11"},{"key":"ref005","doi-asserted-by":"crossref","unstructured":"J.Brickell and V.Shmatikov, Privacy-preserving graph algorithms in the semi-honest model, in: Proceedings of the International Conference on Theory and Application of Cryptology and Information Security, 2005.","DOI":"10.1007\/11593447_13"},{"key":"ref006","doi-asserted-by":"crossref","unstructured":"R.Canetti, Y.Lindell, R.Ostrovsky and A.Sahai, Universally composable two-party and multi-party secure computation, in: Proceedings of the Annual ACM Symposium on Theory of Computing, 2002.","DOI":"10.1145\/509978.509980"},{"key":"ref007","doi-asserted-by":"publisher","DOI":"10.1002\/sec.851"},{"key":"ref008","doi-asserted-by":"crossref","unstructured":"H.Carter, C.Lever and P.Traynor, Whitewash: Outsourcing garbled circuit generation for mobile devices, in: Proceedings of the Annual Computer Security Applications Conference (ACSAC), 2014.","DOI":"10.1145\/2664243.2664255"},{"key":"ref009","unstructured":"H.Carter, B.Mood, P.Traynor and K.Butler, Secure outsourced garbled circuit evaluation for mobile devices, in: Proceedings of the USENIX Security Symposium, 2013."},{"key":"ref010","doi-asserted-by":"crossref","unstructured":"D.Chaum, C.Cr\u00e9peau and I.Damgard, Multiparty unconditionally secure protocols, in: Proceedings of the Annual ACM Symposium on Theory of Computing, 1988.","DOI":"10.1145\/62212.62214"},{"key":"ref011","doi-asserted-by":"crossref","unstructured":"S.G.Choi, K.W.Hwang, J.Katz, T.Malkin and D.Rubenstein, Secure multi-party computation of Boolean circuits with applications to privacy in on-line marketplaces, in: RSA Cryptographers\u2019 Track, 2012.","DOI":"10.1007\/978-3-642-27954-6_26"},{"key":"ref012","doi-asserted-by":"crossref","unstructured":"S.G.Choi, J.Katz, R.Kumaresan and H.S.Zhou, On the security of the \u201cfree-xor\u201d technique, in: Proceedings of the International Conference on Theory of Cryptography, 2012.","DOI":"10.1007\/978-3-642-28914-9_3"},{"key":"ref013","doi-asserted-by":"crossref","unstructured":"I.Damg\u00e5rd and Y.Ishai, Scalable secure multiparty computation, in: Advances in Cryptology\u00a0\u2013 CRYPTO, 2006.","DOI":"10.1007\/11818175_30"},{"key":"ref014","doi-asserted-by":"crossref","unstructured":"I.Damg\u00e5rd and J.B.Nielsen, Scalable and unconditionally secure multiparty computation, in: Advances in Cryptology\u00a0\u2013 CRYPTO, 2007.","DOI":"10.1007\/11818175_30"},{"key":"ref015","doi-asserted-by":"crossref","unstructured":"I.Damgard, V.Pastro, N.Smart and S.Zakarias, Multiparty computation from somewhat homomorphic encryption, in: Advances in Cryptology\u00a0\u2013 CRYPTO, 2012.","DOI":"10.1007\/978-3-642-32009-5_38"},{"key":"ref016","doi-asserted-by":"crossref","unstructured":"C.Gentry, S.Halevi and N.P.Smart, Homomorphic evaluation of the aes circuit, in: Advances in Cryptology\u00a0\u2013 CRYPTO, 2012.","DOI":"10.1007\/978-3-642-32009-5_49"},{"key":"ref017","doi-asserted-by":"publisher","DOI":"10.1007\/BF00208001"},{"key":"ref018","unstructured":"V.Goyal, P.Mohassel and A.Smith, Efficient two party and multi party computation against covert adversaries, in: Advances in Cryptology\u00a0\u2013 EUROCRYPT, 2008."},{"key":"ref019","unstructured":"M.Green, S.Hohenberger and B.Waters, Outsourcing the decryption of abe ciphertexts, in: Proceedings of the USENIX Security Symposium, 2011."},{"key":"ref020","doi-asserted-by":"crossref","unstructured":"W.Henecka, S.K\u00f6gl, A.R.Sadeghi, T.Schneider and I.Wehrenberg, Tasty: Tool for automating secure two-party computations, in: Proceedings of the ACM Conference on Computer and Communications Security, 2010.","DOI":"10.1145\/1866307.1866358"},{"key":"ref021","unstructured":"J.Huang, Performance and power characterization of cellular networks and mobile application optimizations, PhD thesis, University of Michigan, 2013."},{"key":"ref022","unstructured":"Y.Huang, P.Chapman and D.Evans, Privacy-preserving applications on smartphones, in: Proceedings of the USENIX Workshop on Hot Topics in Security, 2011."},{"key":"ref023","unstructured":"Y.Huang, D.Evans and J.Katz, Private set intersection: Are garbled circuits better than custom protocols? in: Proceedings of the ISOC Symposium on Network and Distributed Systems Security, San Diego, CA, USA, 2012."},{"key":"ref024","doi-asserted-by":"crossref","unstructured":"Y.Huang, D.Evans, J.Katz and L.Malka, Faster secure two-party computation using garbled circuits, in: Proceedings of the USENIX Security Symposium, 2011.","DOI":"10.1007\/978-3-642-25560-1_2"},{"key":"ref025","doi-asserted-by":"crossref","unstructured":"Y.Huang, J.Katz and D.Evans, Quid-pro-quo-tocols: Strengthening semi-honest protocols with dual execution, in: Proceedings of the IEEE Symposium on Security and Privacy, 2012.","DOI":"10.1109\/SP.2012.43"},{"key":"ref026","doi-asserted-by":"crossref","unstructured":"Y.Huang, J.Katz and D.Evans, Efficient secure two-party computation using symmetric cut-and-choose, in: Advances in Cryptology\u00a0\u2013 CRYPTO, 2013.","DOI":"10.1007\/978-3-642-40084-1_2"},{"key":"ref027","doi-asserted-by":"crossref","unstructured":"A.Iliev and S.W.Smith, Small, stupid, and scalable: Secure computing with faerieplay, in: The ACM Workshop on Scalable Trusted Computing, 2010.","DOI":"10.1145\/1867635.1867643"},{"key":"ref028","doi-asserted-by":"crossref","unstructured":"Y.Ishai, J.Kilian, K.Nissim and E.Petrank, Extending oblivious transfers efficiently, in: Proceedings of the Annual International Cryptology Conference, 2003.","DOI":"10.1007\/978-3-540-45146-4_9"},{"key":"ref029","doi-asserted-by":"crossref","unstructured":"S.Jha, L.Kruger and V.Shmatikov, Towards practical privacy for genomic computation, in: Proceedings of the IEEE Symposium on Security and Privacy, 2008.","DOI":"10.1109\/SP.2008.34"},{"key":"ref030","unstructured":"S.Kamara, P.Mohassel and M.Raykova, Outsourcing multi-party computation, Report 2011\/272, Cryptology ePrint Archive, 2011, http:\/\/eprint.iacr.org\/."},{"key":"ref031","doi-asserted-by":"crossref","unstructured":"S.Kamara, P.Mohassel and B.Riva, Salus: A system for server-aided secure function evaluation, in: Proceedings of the ACM Conference on Computer and Communications Security, 2012.","DOI":"10.1145\/2382196.2382280"},{"key":"ref032","unstructured":"M.S.Kiraz, Secure and fair two-party computation, PhD thesis, Technische Universiteit Eindhoven, 2008."},{"key":"ref033","unstructured":"M.S.Kiraz and B.Schoenmakers, A protocol issue for the malicious case of Yao\u2019s garbled circuit construction, in: Proceedings of Symposium on Information Theory in the Benelux, 2006."},{"key":"ref034","doi-asserted-by":"crossref","unstructured":"V.Kolesnikov and R.Kumaresan, Improved OT extension for transferring short secrets, in: Advances in Cryptology\u00a0\u2013 CRYPTO, 2013.","DOI":"10.1007\/978-3-642-40084-1_4"},{"key":"ref035","unstructured":"V.Kolesnikov and T.Schneider, Improved garbled circuit: Free xor gates and applications, in: Proceedings of the International Colloquium on Automata, Languages and Programming, Part\u00a0II, 2008."},{"key":"ref036","unstructured":"B.Kreuter, B.Mood, a.shelat and K.Butler, PCF: A portable circuit format for scalable two-party secure computation, in: Proceedings of the USENIX Security Symposium, 2013."},{"key":"ref037","unstructured":"B.Kreuter, a.shelat and C.H.Shen, Billion-gate secure computation with malicious adversaries, in: Proceedings of the USENIX Security Symposium, 2012."},{"key":"ref038","doi-asserted-by":"crossref","unstructured":"L.Kruger, S.Jha, E.J.Goh and D.Boneh, Secure function evaluation with ordered binary decision diagrams, in: Proceedings of the ACM Conference on Computer and Communications Security, 2006.","DOI":"10.1145\/1180405.1180455"},{"key":"ref039","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-007-9015-5"},{"key":"ref040","doi-asserted-by":"crossref","unstructured":"Y.Lindell, Fast cut-and-choose based protocols for malicious and covert adversaries, in: Advances in Cryptology\u00a0\u2013 CRYPTO, 2013.","DOI":"10.1007\/978-3-642-40084-1_1"},{"key":"ref041","doi-asserted-by":"crossref","unstructured":"Y.Lindell and B.Pinkas, Privacy preserving data mining, in: Advances in Cryptology\u00a0\u2013 CRYPTO, 2000.","DOI":"10.1007\/3-540-44598-6_3"},{"key":"ref042","doi-asserted-by":"crossref","unstructured":"Y.Lindell and B.Pinkas, An efficient protocol for secure two-party computation in the presence of malicious adversaries, in: Advances in Cryptology\u00a0\u2013 EUROCRYPT, 2007.","DOI":"10.1007\/978-3-540-72540-4_4"},{"key":"ref043","doi-asserted-by":"crossref","unstructured":"Y.Lindell and B.Pinkas, Secure two-party computation via cut-and-choose oblivious transfer, in: Proceedings of the Conference on Theory of Cryptography, 2011.","DOI":"10.1007\/978-3-642-19571-6_20"},{"key":"ref044","doi-asserted-by":"crossref","unstructured":"A.L\u00f3pez-Alt, E.Tromer and V.Vaikuntanathan, On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption, in: Proceedings of the Symposium on Theory of Computing, 2012.","DOI":"10.1145\/2213977.2214086"},{"key":"ref045","doi-asserted-by":"crossref","unstructured":"L.Malka, Vmcrypt: Modular software architecture for scalable secure computation, in: Proceedings of the 18th ACM Conference on Computer and Communications Security, 2011.","DOI":"10.1145\/2046707.2046787"},{"key":"ref046","unstructured":"D.Malkhi, N.Nisan, B.Pinkas and Y.Sella, Fairplay\u00a0\u2013 A secure two-party computation system, in: Proceedings of the USENIX Security Symposium, 2004."},{"key":"ref047","unstructured":"T.Matsumoto, K.Kato and H.Imai, Speeding up secret computations with insecure auxiliary devices, in: Advances in Cryptology\u00a0\u2013 CRYPTO, 1988."},{"key":"ref048","doi-asserted-by":"crossref","unstructured":"P.Mohassel and M.Franklin, Efficiency tradeoffs for malicious two-party computation, in: Proceedings of the Public Key Cryptography Conference, 2006.","DOI":"10.1007\/11745853_30"},{"key":"ref049","doi-asserted-by":"crossref","unstructured":"B.Mood, D.Gupta, K.Butler and J.Feigenbaum, Reuse it or lose it: More efficient secure computation through reuse of encrypted values, in: Proceedings of the ACM Conference on Computer and Communications Security (CCS), 2014.","DOI":"10.1145\/2660267.2660285"},{"key":"ref050","doi-asserted-by":"crossref","unstructured":"B.Mood, L.Letaw and K.Butler, Memory-efficient garbled circuit generation for mobile devices, in: Proceedings of the IFCA International Conference on Financial Cryptography and Data Security, 2012.","DOI":"10.1007\/978-3-642-32946-3_19"},{"key":"ref051","doi-asserted-by":"crossref","unstructured":"M.Naor and B.Pinkas, Oblivious transfer and polynomial evaluation, in: Proceedings of the Annual ACM Symposium on Theory of Computing, 1999.","DOI":"10.1145\/301250.301312"},{"key":"ref052","unstructured":"M.Naor and B.Pinkas, Efficient oblivious transfer protocols, in: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2001."},{"key":"ref053","doi-asserted-by":"crossref","unstructured":"M.Naor, B.Pinkas and R.Sumner, Privacy preserving auctions and mechanism design, in: Proceedings of the ACM Conference on Electronic Commerce, 1999.","DOI":"10.1145\/336992.337028"},{"key":"ref054","doi-asserted-by":"crossref","unstructured":"J.B.Nielsen, P.S.Nordholt, C.Orlandi and S.S.Burra, A new approach to practical active-secure two-party computation, in: Advances in Cryptology\u00a0\u2013 CRYPTO, 2012.","DOI":"10.1007\/978-3-642-32009-5_40"},{"key":"ref055","doi-asserted-by":"crossref","unstructured":"N.Nipane, I.Dacosta and P.Traynor, \u201cMix-in-place\u201d anonymous networking using secure function evaluation, in: Proceedings of the Annual Computer Security Applications Conference, 2011.","DOI":"10.1145\/2076732.2076742"},{"key":"ref056","doi-asserted-by":"crossref","unstructured":"M.Osadchy, B.Pinkas, A.Jarrous and B.Moskovich, Scifi\u00a0\u2013 A system for secure face identification, in: Proceedings of the IEEE Symposium on Security and Privacy, 2010.","DOI":"10.1109\/SP.2010.39"},{"key":"ref057","unstructured":"C.Peikert, V.Vaikuntanathan and B.Waters, A framework for efficient and composable oblivious transfer, in: Advances in Cryptology\u00a0\u2013 CRYPTO, 2008."},{"key":"ref058","unstructured":"W.Rash, Dropbox password breach highlights cloud security weaknesses, 2012, available at: http:\/\/www.eweek.com\/c\/a\/Security\/Dropbox-Password-Breach-Highlights-Cloud-Security-Weaknesses-266215\/."},{"key":"ref059","doi-asserted-by":"crossref","unstructured":"T.Schneider and M.Zohner, GMW vs. Yao? Efficient secure two-party computation with low depth circuits, in: Proceedings of the IFCA International Conference on Financial Cryptography and Data Security, 2013.","DOI":"10.1007\/978-3-642-39884-1_23"},{"key":"ref060","doi-asserted-by":"crossref","unstructured":"a.shelat and C.H.Shen, Two-output secure computation with malicious adversaries, in: Advances in Cryptology\u00a0\u2013 EUROCRYPT, 2011.","DOI":"10.1007\/978-3-642-20465-4_22"},{"key":"ref061","unstructured":"K.Thomas, Microsoft cloud data breach heralds things to come, 2010, available at: http:\/\/www.pcworld.com\/article\/214775\/microsoft_cloud_data_breach_sign_of_future.html."},{"key":"ref062","doi-asserted-by":"crossref","unstructured":"D.P.Woodruff, Revisiting the efficiency of malicious two-party computation, in: Advances in Cryptology\u00a0\u2013 EUROCRYPT, 2007.","DOI":"10.1007\/978-3-540-72540-4_5"},{"key":"ref063","doi-asserted-by":"crossref","unstructured":"A.C.Yao, Protocols for secure computations, in: Proceedings of the Annual Symposium on Foundations of Computer Science, 1982.","DOI":"10.1109\/SFCS.1982.38"}],"container-title":["Journal of Computer Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/JCS-150540","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.3233\/JCS-150540","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/JCS-150540","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T20:44:57Z","timestamp":1777495497000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.3233\/JCS-150540"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12,16]]},"references-count":63,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,4,19]]}},"alternative-id":["10.3233\/JCS-150540"],"URL":"https:\/\/doi.org\/10.3233\/jcs-150540","relation":{},"ISSN":["0926-227X","1875-8924"],"issn-type":[{"value":"0926-227X","type":"print"},{"value":"1875-8924","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,12,16]]}}}