More Web Proxy on the site http://driver.im/

research-article

MrCrypt: static analysis for secure cloud computations

Authors:

Sai Deep Tetali,

Rupak Majumdar,

Todd MillsteinAuthors Info & Claims

OOPSLA '13: Proceedings of the 2013 ACM SIGPLAN international conference on Object oriented programming systems languages & applications

Pages 271 - 286

https://doi.org/10.1145/2509136.2509554

Published: 29 October 2013 Publication History

Abstract

In a common use case for cloud computing, clients upload data and computation to servers that are managed by a third-party infrastructure provider. We describe MrCrypt, a system that provides data confidentiality in this setting by executing client computations on encrypted data. MrCrypt statically analyzes a program to identify the set of operations on each input data column, in order to select an appropriate homomorphic encryption scheme for that column, and then transforms the program to operate over encrypted data. The encrypted data and transformed program are uploaded to the server and executed as usual, and the result of the computation is decrypted on the client side. We have implemented MrCrypt for Java and illustrate its practicality on three standard benchmark suites for the Hadoop MapReduce framework. We have also formalized the approach and proven several soundness and security guarantees.

References

[1]

F. Ahmad, S. Lee, M. Thottethodi, and T. Vijaykumar. Puma: Purdue mapreduce benchmarks suite. Technical Report TR-ECE-12--11, School of Electrical and Computer Engineering, Purdue University, 2012. URL http://docs.lib.purdue.edu/ecetr/437/.

[2]

O. Baudron, D. Pointcheval, and J. Stern. Extended notions of security for multicast public key cryptosystems. In phICALP '00, volume 1853 of phLecture Notes in Computer Science, pages 499--511. Springer, 2000.

Digital Library

[3]

M. Bellare, T. Kohno, and C. Namprempre. Authenticated encryption in ssh: provably fixing the ssh binary packet protocol. In phCCS '02, pages 1--11. ACM, 2002.

Digital Library

[4]

M. Bellare, T. Ristenpart, P. Rogaway, and T. Stegers. Format-preserving encryption. In phSelected Areas in Cryptography, volume 5867 of phLecture Notes in Computer Science, pages 295--312. Springer, 2009.

Digital Library

[5]

A. Boldyreva, N. Chenette, Y. Lee, and A. O'Neill. Order-preserving symmetric encryption. In phEUROCRYPT, volume 5479 of phLecture Notes in Computer Science, pages 224--241. Springer, 2009.

Digital Library

[6]

A. Boldyreva, N. Chenette, and A. O'Neill. Order-preserving encryption revisited: Improved security analysis and alternative solutions. In phCRYPTO, volume 6841 of phLecture Notes in Computer Science, pages 578--595. Springer, 2011.

Digital Library

[7]

C. Castelluccia, E. Mykletun, and G. Tsudik. Efficient aggregation of encrypted data in wireless sensor networks. In phProceedings of the The Second Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services, MOBIQUITOUS '05, pages 109--117, Washington, DC, USA, 2005. IEEE Computer Society. ISBN 0--7695--2375--7. 10.1109/MOBIQUITOUS.2005.25. URL http://dx.doi.org/10.1109/MOBIQUITOUS.2005.25.

Digital Library

[8]

J. Daemen and V. Rijmen. phThe design of Rijndael: AES-the advanced encryption standard. Springer, 2002.

Digital Library

[9]

J. Dean and S. Ghemawat. MapReduce: a flexible data processing tool. phCommun. ACM, 53 (1): 72--77, 2010.

Digital Library

[10]

T. ElGamal. A public-key cryptosystem and a signature scheme based on discrete logarithms. phIEEE Transactions on Information Theory, 31 (4): 469--472, 1985.

Digital Library

[11]

J. Foster, R. Johnson, J. Kodumal, and A. Aiken. Flow-insensitive type qualifiers. phACM Trans. Program. Lang. Syst., 28 (6): 1035--1087, Nov. 2006.

Digital Library

[12]

C. Fournet, J. Planul, and T. Rezk. Information-flow types for homomorphic encryptions. In phProceedings of the 18th ACM conference on Computer and communications security, CCS '11, pages 351--360. ACM, 2011.

Digital Library

[13]

T. Ge and S. Zdonik. Answering aggregation queries in a secure system model. In phProceedings of the 33rd international conference on Very large data bases, pages 519--530. VLDB Endowment, 2007.

Digital Library

[14]

C. Gentry. Fully homomorphic encryption using ideal lattices. In phSTOC 09: Symposium on Theory of Computing. ACM, 2009.

Digital Library

[15]

C. Gentry. Computing arbitrary functions of encrypted data. phCommun. ACM, 53 (3): 97--105, 2010.

Digital Library

[16]

C. Gentry and S. Halevi. Implementing Gentry's fully-homomorphic encryption scheme. In phEUROCRYPT 11, volume 6632 of phLecture Notes in Computer Science, pages 129--148. Springer, 2011.

Digital Library

[17]

S. Goldwasser and S. Micali. Probabilistic encryption. phJ. Computer and Systems Sciences, 28: 270--299, 1984.

[18]

S. Halevi and P. Rogaway. A tweakable enciphering mode. phAdvances in Cryptology-CRYPTO 2003, pages 482--499, 2003.

[19]

M. Hirt and K. Sako. Efficient receipt-free voting based on homomorphic encryption. In phProceedings of the 19th international conference on Theory and application of cryptographic techniques, EUROCRYPT'00, pages 539--556, Berlin, Heidelberg, 2000. Springer-Verlag. ISBN 3--540--67517--5. URL http://dl.acm.org/citation.cfm?id=1756169.1756222.

Digital Library

[20]

E. Kowalski. Insider threat study: Illicit cyber activity in the information technology and telecommunications sector. Technical report, Technical report, U.S. Secret Service and Carnegie Mellon University, 2008. URL http://www.secretservice.gov/$\sim$ntac/final\_it\_sector\_2008\_0109.pdf.

[21]

M. Lesani, R. Majumdar, T. Millstein, and S. Tetali. MrCrypt: Static analysis for secure cloud computations (technical report). Technical Report 130012, UCLA Computer Science Department, July 2013.

[22]

J. Li, M. Krohn, D. Mazières, and D. Shasha. Secure untrusted data repository (sundr). In phOSDI 04: Operating Systems Design and Implementation, pages 91--106. ACM, 2004.

Digital Library

[23]

P. Mahajan, S. Setty, S. Lee, A. Clement, L. Alvisi, M. Dahlin, and M. Walfish. Depot: Cloud storage with minimal trust. In phOSDI 10: Operating Systems Design and Implementation. ACM, 2010.

Digital Library

[24]

J. Mitchell, R. Sharma, D. Stefan, and J. Zimmerman. Information-flow control for programming on encrypted data. In phComputer Security Foundations Symposium (CSF), 2012 IEEE 25th, pages 45--60. IEEE, 2012.

Digital Library

[25]

M. Naehrig, K. Lauter, and V. Vaikuntanathan. Can homomorphic encryption be practical? In phProceedings of the 3rd ACM workshop on Cloud computing security workshop, CCSW '11, pages 113--124, New York, NY, USA, 2011. ACM. ISBN 978--1--4503--1004--8. 10.1145/2046660.2046682. URL http://doi.acm.org/10.1145/2046660.2046682.

Digital Library

[26]

N. Nystrom, M. Clarkson, and A. Myers. Polyglot: An extensible compiler framework for java. In phCompiler Construction, pages 138--152. Springer, 2003.

Digital Library

[27]

C. Olston, B. Reed, U. Srivastava, R. Kumar, and A. Tomkins. Pig latin: a not-so-foreign language for data processing. In phProceedings of the 2008 ACM SIGMOD international conference on Management of data, SIGMOD '08, pages 1099--1110, New York, NY, USA, 2008. ACM. ISBN 978--1--60558--102--6. 10.1145/1376616.1376726. URL http://doi.acm.org/10.1145/1376616.1376726.

Digital Library

[28]

P. Ørbæk and J. Palsberg. Trust in the λ-calculus. phJournal of Functional Programming, 7 (6): 557--591, Nov. 1997.

Digital Library

[29]

P. Paillier. Public-key cryptosystems based on composite degree residuosity classes. In phEUROCRYPT 99: Theory and Applications of Cryptographic Techniques, 1999.

Digital Library

[30]

B. Parno, J. McCune, D. Wendlandt, D. Andersen, and A. Perrig. CLAMP: Practical prevention of large-scale data leaks. In phProceedings of the 2009 30th IEEE Symposium on Security and Privacy, SP '09, pages 154--169, Washington, DC, USA, 2009. IEEE Computer Society. ISBN 978-0--7695--3633-0. 10.1109/SP.2009.21. URL http://dx.doi.org/10.1109/SP.2009.21.

Digital Library

[31]

A. Pavlo, E. Paulson, A. Rasin, D. Abadi, D. DeWitt, S. Madden, and M. Stonebraker. A comparison of approaches to large-scale data analysis. In phProceedings of the 35th SIGMOD international conference on Management of data, pages 165--178. ACM, 2009.

Digital Library

[32]

R. Popa, C. Redfield, N. Zeldovich, and H. Balakrishnan. CryptDB: protecting confidentiality with encrypted query processing. In phProceedings of the Twenty-Third ACM Symposium on Operating Systems Principles, pages 85--100. ACM, 2011.

Digital Library

[33]

M. Raykova, B. Vo, S. Bellovin, and T. Malkin. Secure anonymous database search. In phCCSW 09: Cloud Computing Security Workshop, pages 115--126. ACM, 2009.

Digital Library

[34]

R. Rivest, L. Adleman, and M. Dertouzos. On data banks and privacy homomorphisms. In phFoundations of Secure Computation, pages 169--179. Academic Press, 1978.

[35]

I. Roy, S. Setty, A. Kilzer, V. Shmatikov, and E. Witchel. Airavat: Security and privacy for MapReduce. In phNSDI, pages 297--312. USENIX, 2010.

Digital Library

[36]

A. Sabelfeld and A. C. Myers. Language-based information-flow security. phIEEE Journal on Selected Areas in Communications, 21 (1): 5--19, 2003.

Digital Library

[37]

T. Sander, A. Young, and M. Yung. Non-interactive cryptocomputing for NC$^1$. In phFOCS 99: Foundations of Computer Science. IEEE, 1999.

Digital Library

[38]

N. Santos, R. Rodrigues, K. Gummadi, and S. Saroiu. Policy-sealed data: A new abstraction for building trusted cloud services. In phUsenix Security Symposium. USENIX Association, 2012.

Digital Library

[39]

B. Schneier. Description of a new variable-length key, 64-bit block cipher (blowfish). In phFast Software Encryption, pages 191--204. Springer, 1994.

Digital Library

[40]

B. Schneier. phApplied cryptography. Wiley, 2nd edition, 1996.

[41]

J. Vaughan. Auraconf: a unified approach to authorization and confidentiality. In phProceedings of the 7th ACM SIGPLAN workshop on Types in language design and implementation, TLDI '11, pages 45--58, New York, NY, USA, 2011. ACM. ISBN 978--1--4503-0484--9. 10.1145/1929553.1929563. URL http://doi.acm.org/10.1145/1929553.1929563.

Digital Library

[42]

A. Wright and M. Felleisen. A syntactic approach to type soundness. phInformation and Computation, 115 (1): 38--94, 1994.

Digital Library

[43]

A. Yao. How to generate and exchange secrets. In phFOCS 86: Foundations of Computer Science, pages 162--167. IEEE, 1986.

Digital Library

Cited By

Mangipudi SChuprikov PEugster PViering MSavvides S(2023)Generalized Policy-Based Noninterference for Efficient Confidentiality-PreservationProceedings of the ACM on Programming Languages10.1145/35912317:PLDI(267-291)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591231
Al Azad MSarwar STaki SMastorakis S(2023)The Case for the Anonymization of Offloaded Computation2023 IEEE 16th International Conference on Cloud Computing (CLOUD)10.1109/CLOUD60044.2023.00019(84-95)Online publication date: Jul-2023
https://doi.org/10.1109/CLOUD60044.2023.00019
Fischer AFuhry BKußmaul JJanneck JKerschbaum FBodden E(2022)Computation on Encrypted Data Using Dataflow AuthenticationACM Transactions on Privacy and Security10.1145/351300525:3(1-36)Online publication date: 19-May-2022
https://dl.acm.org/doi/10.1145/3513005
Show More Cited By

Index Terms

MrCrypt: static analysis for secure cloud computations
1. Software and its engineering
  1. Software creation and management
    1. Software post-development issues
      1. Software reverse engineering
  2. Software notations and tools
    1. Formal language definitions
2. Theory of computation
  1. Formal languages and automata theory

Recommendations

MrCrypt: static analysis for secure cloud computations
OOPSLA '13

In a common use case for cloud computing, clients upload data and computation to servers that are managed by a third-party infrastructure provider. We describe MrCrypt, a system that provides data confidentiality in this setting by executing client ...
A Pairing-based Homomorphic Encryption Scheme for Multi-User Settings

A new method is presented to privately outsource computation of different users. As a significant cryptographic primitive in cloud computing, homomorphic encryption HE can evaluate on ciphertext directly without decryption, thus avoid information ...
Publicly verifiable searchable symmetric encryption based on efficient cryptographic components

Public verifiability is an interesting feature that cryptographic protocols, such as those used in cloud computing applications, may support. By public verifiability, the client can delegate the verification process to a third party auditor without ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

OOPSLA '13: Proceedings of the 2013 ACM SIGPLAN international conference on Object oriented programming systems languages & applications

October 2013

904 pages

ISBN:9781450323741

DOI:10.1145/2509136

Co-chair:
Antony Hosking
Purdue University, USA
,
General Chair:
Patrick Eugster
Purdue University, USA
,
Program Chair:
Cristina V. Lopes
University of California, Irvine, USA

ACM SIGPLAN Notices Volume 48, Issue 10
OOPSLA '13
October 2013
867 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2544173
Editor:
Mark W. Bailey
Hamilton College, Clinton, NY
Issue’s Table of Contents

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 October 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SPLASH '13

Sponsor:

SIGPLAN

SPLASH '13: Conference on Systems, Programming, and Applications: Software for Humanity

October 29 - 31, 2013

Indiana, Indianapolis, USA

Acceptance Rates

OOPSLA '13 Paper Acceptance Rate 50 of 189 submissions, 26%;

Overall Acceptance Rate 268 of 1,244 submissions, 22%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

56
Total Citations
View Citations
551
Total Downloads

Downloads (Last 12 months)13
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Mangipudi SChuprikov PEugster PViering MSavvides S(2023)Generalized Policy-Based Noninterference for Efficient Confidentiality-PreservationProceedings of the ACM on Programming Languages10.1145/35912317:PLDI(267-291)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591231
Al Azad MSarwar STaki SMastorakis S(2023)The Case for the Anonymization of Offloaded Computation2023 IEEE 16th International Conference on Cloud Computing (CLOUD)10.1109/CLOUD60044.2023.00019(84-95)Online publication date: Jul-2023
https://doi.org/10.1109/CLOUD60044.2023.00019
Fischer AFuhry BKußmaul JJanneck JKerschbaum FBodden E(2022)Computation on Encrypted Data Using Dataflow AuthenticationACM Transactions on Privacy and Security10.1145/351300525:3(1-36)Online publication date: 19-May-2022
https://dl.acm.org/doi/10.1145/3513005
Wu PLi QNing JHuang XWu W(2022)Differentially Oblivious Data Analysis With Intel SGX: Design, Optimization, and EvaluationIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2021.310631719:6(3741-3758)Online publication date: 1-Nov-2022
https://doi.org/10.1109/TDSC.2021.3106317
Wu PNing JLuo WHuang XHe D(2021)Exploring Dynamic Task Loading in SGX-based Distributed ComputingIEEE Transactions on Services Computing10.1109/TSC.2021.3123511(1-1)Online publication date: 2021
https://doi.org/10.1109/TSC.2021.3123511
Sobati-Moghadam S(2021)Efficient information-theoretically secure schemes for cloud data outsourcingCluster Computing10.1007/s10586-021-03344-x24:4(3591-3606)Online publication date: 1-Dec-2021
https://dl.acm.org/doi/10.1007/s10586-021-03344-x
Mallaiah KGandhi RRamachandram S(2021)Stateless Key Management Scheme for Proxy-Based Encrypted DatabasesComputer Networks, Big Data and IoT10.1007/978-981-16-0965-7_43(557-584)Online publication date: 22-Jun-2021
https://doi.org/10.1007/978-981-16-0965-7_43
Fischer AFuhry BKerschbaum FBodden E(2020)Computation on Encrypted Data using Dataflow AuthenticationProceedings on Privacy Enhancing Technologies10.2478/popets-2020-00022020:1(5-25)Online publication date: 7-Jan-2020
https://doi.org/10.2478/popets-2020-0002
Sharma SBurtsev AMehrotra S(2020)Advances in Cryptography and Secure Hardware for Data Outsourcing2020 IEEE 36th International Conference on Data Engineering (ICDE)10.1109/ICDE48307.2020.00173(1798-1801)Online publication date: Apr-2020
https://doi.org/10.1109/ICDE48307.2020.00173
Fan YLiu STan GQiao F(2020)Fine-grained access control based on Trusted Execution EnvironmentFuture Generation Computer Systems10.1016/j.future.2018.05.062109(551-561)Online publication date: Aug-2020
https://doi.org/10.1016/j.future.2018.05.062
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents