Abstract
Data encryption is a common approach to protect the confidentiality of users' data. However, when computation is required, the data must be decrypted before processing. The decryption-for-processing approach causes critical threats. For instance, a compromised server may lead to the leakage of data or cryptographic keys. On the other hand, data owners are concerned since the data is beyond their control. Thus, they look for mechanisms to achieve strong data protection. Accordingly, alternatives for protecting data become essential. Consequently, the trend of processing over encrypted data starts to arise along with a rapidly growing literature. This paper surveys applications, tools, building blocks, and approaches that can be used to directly process encrypted data (i.e., without decrypting it). The purpose of this survey is to provide an overview of existing systems and approaches that can be used to process encrypted data, discuss commercial usage of such systems, and to analyze the current developments in this area
- M. Abadi, J. Feigenbaum, and J. Kilian. On hiding information from an oracle. In ACM Symp. on Theory of Computing, New York, USA, 1987. Google ScholarDigital Library
- R. Agrawal, J. Kiernan, R. Srikant, and Y. Xu. Order-preserving encryption for numeric data. In ACM SIGMOD Conference, Paris, France, 2004. Google ScholarDigital Library
- N. Ahituv, Y. Lapid, and S. Neumann. Processing encrypted data. Communications of the ACM, 30(9):777--780, 1987. Google ScholarDigital Library
- J. Alwen, A. Shelat, and I. Visconti. Collusion-free protocols in the mediated model. In CRYPTO, pages 497--514, Santa Barbara, California, USA, 2008. Springer. Google ScholarDigital Library
- A. Arasu, S. Blanas, K. Eguro, R. Kaushik, D. Kossmann, R. Ramamurthy, and R. Venkatesan. Orthogonal security with cipherbase. In CIDR, California, USA, 2013.Google Scholar
- S. Bajaj and R. Sion. Trusteddb: A trusted hardware-based database with privacy and data confidentiality. In ACM SIGMOD Conference, California, USA, 2011. Google ScholarDigital Library
- G. R. Balkley and C. Meadows. A database encryption scheme which allows the computation of statistics using encrypted data. In IEEE S&P, Oakland, CA, USA, 1985.Google Scholar
- M. Bellare, A. Boldyreva, and A. O'Neill. Deterministic and efficiently searchable encryption. In CRYPTO, pages 535--552, California, USA, 2007. Google ScholarDigital Library
- J. Benaloh. Dense probabilistic encryption. In Selected Areas of Cryptography, pages 120--128, Ontario, Canada, 1994.Google Scholar
- J. Bethencourt, A. Sahai, and B. Waters. Ciphertext-policy attribute-based encryption. In IEEE S&P, pages 321--334. IEEE, 2007. Google ScholarDigital Library
- A. Boldyreva, N. Chenette, Y. Lee, and A. O'Neill. Order-preserving symmetric encryption. In EUROCRYPT, pages 224--241, Cologne, Germany, 2009.Google ScholarCross Ref
- A. Boldyreva, N. Chenette, Y. Lee, and A. O'Neill. Order-preserving encryption revisited: improved security analysis and alternative solutions. In CRYPTO, pages 578--595, California, USA, 2011. Google ScholarDigital Library
- D. Boneh, C. Gentry, S. Gorbunov, S. Halevi, V. Nikolaenko, G. Segev, V. Vaikuntanathan, and D. Vinayagamurthy. Fully key-homomorphic encryption, arithmetic circuit abe, and compact garbled circuits. In EUROCRYPT 2014, volume 8441 of LNCS, pages 533--556, 2014.Google ScholarCross Ref
- D. Boneh, E.-J. Goh, and K. Nissim:. Evaluating 2-dnf formulas on ciphertexts. In Theory of Cryptography, volume 3378, pages 325--341, 2005. Google ScholarDigital Library
- D. Boneh, A. Sahai, and B. Waters. Functional encryption: Definitions and challenges. In Theory of Cryptography, volume 6597, pages 253--273. Springer, 2011. Google ScholarCross Ref
- D. Boneh and B. Waters. Conjunctive, subset, and range queries on encrypted data. In Theory of Cryptography, volume 4392, pages 535--554. Springer, 2007. Google ScholarDigital Library
- C. Bösch, P. Hartel, W. Jonker, and A. Peter. A survey of provably secure searchable encryption. ACM Computing Surveys (CSUR), 47(2):18, 2015. Google ScholarDigital Library
- X. Boyen and L. Martin. Identity-based cryptography standard (ibcs) #1: Supersingular curve implementations of the bf and bb1 cryptosystems. RFC5091, December 2007.Google Scholar
- E. Boyle, S. Goldwasser, and I. Ivan. Functional signatures and pseudorandom functions. In PKC 2014, volume 8383 of LNCS, pages 501--519. Springer, 2014. Google ScholarDigital Library
- Z. Brakerski, C. Gentry, and V. Vaikuntanathan. (leveled) fully homomorphic encryption without bootstrapping. In Innovations in (Theoretical) CS, Cambridge, MA, USA, 2012.Google ScholarDigital Library
- Z. Brakerski and G. Segev. Function-private functional encryption in the private-key setting. Technical Report Report 2014/550, Cryptology ePrint Archive, 2014.Google Scholar
- Z. Brakerski and V. Vaikuntanathan. Fully homomorphic encryption from ring-lwe and security for key dependent messages. In CRYPTO, pages 505--524, California, USA, 2011. Google ScholarDigital Library
- M. Chase. Multi-authority attribute based encryption. In Theory of Cryptography, volume 4392 of Lecture Notes in CS, pages 515--534. Springer, 2007. Google ScholarDigital Library
- N. Chenette, K. Lewi, S. A. Weis, and D. J. Wu. Practical order-revealing encryption with limited leakage, 2015.Google Scholar
- CipherCloud. Cloud data protection. {retrieved: Oct, 2014}.Google Scholar
- C. Clifton, M. Kantarcioglu, J. Vaidya, X. Lin, and M. Y. Zhu. Tools for privacy preserving distributed data mining. ACM SIGKDD, 4(2):28--34, December 2002. Google ScholarDigital Library
- R. Cramer, R. Gennaro, and B. Schoenmakers. A secure and optimally efficient multiauthority election scheme. In EUROCRYPT, pages 103--118, NY, USA, 1997. Google ScholarDigital Library
- M. H. Diallo, B. Hore, E. C. Chang, S. Mehrotra, and N. Venkatasubramanian. Cloudprotect: Managing data privacy in cloud applications. In IEEE Cloud, Hawaii, USA, 2012. Google ScholarDigital Library
- W. Diffie. The first ten years of public-key cryptography. Proceedings of the IEEE, 76(5):560 -- 577, May 1988.Google ScholarCross Ref
- K. Eguro and R. Venkatesan. Fpgas for trusted cloud computing. In Field-Programmable Logic and Applications, Oslo, Norway, 2012.Google Scholar
- J. Feigenbaum. Encrypting problem instances, or, ..., can you take advantage of someone without having to trust him? In CRYPTO. Springer-Verlag, 1986. Google ScholarDigital Library
- C. Fontaine and F. Galand. A survey of homomorphic encryption for nonspecialists. EURASIP Journal on Information Security, pages 1--15, 2007.Google Scholar
- Forbes. Salesforce.com brings navajo into camp to boost cloud security. http://www.forbes.com/sites/greatspeculations/2011/08/30/salesforce-com-bringsnavajo-into-camp-to-boost-cloud-security, 2011.Google Scholar
- T. E. Gamal. A public key cryptosystem and a signature scheme based on discrete logarithms. In CRYPTO, pages 10--18, Santa Barbara, California, USA, 1984. Google ScholarDigital Library
- S. Garg, C. G. S. Halevi, M. Raykova, A. Sahai, and B. Waters. Candidate indistinguishability obfuscation and functional encryption for all circuits. In FOCS '13, pages 40--49. IEEE Computer Society, 2013. Google ScholarDigital Library
- T. Ge and S. Zdonik. Answering aggregation queries in a secure system model. In VLDB, pages 519--530, 2007. Google ScholarDigital Library
- C. Gentry. A fully homomorphic encryption scheme. PhD thesis, Stanford, 2009. Google ScholarDigital Library
- C. Gentry. Fully homomorphic encryption using ideal lattices. In ACM Symp. on the Theory of Computing, pages 169--178, Maryland, USA, 2009. Google ScholarDigital Library
- C. Gentry. Computing arbitrary functions of encrypted data. Comm. of the ACM, 53(3):97--105, 2010. Google ScholarDigital Library
- C. Gentry, S. Halevi, and N. P. Smart. Better bootstrapping in fully homomorphic encryption. In Public Key Cryptography, Darmstadt, Germany, 2012. Google ScholarDigital Library
- C. Gentry, S. Halevi, and N. P. Smart. Homomorphic evaluation of the aes circuit. In CRYPTO, pages 850--867, California, USA, 2012. Google ScholarDigital Library
- C. Gentry, A. Sahai, and B. Waters. Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based. In CRYPTO, pages 75--92, California, USA, 2013.Google ScholarCross Ref
- S. Goldwasser, S. D. Gordon, V. Goyal, A. Jain, J. Katz, F.-H. Liu, A. Sahai, E. Shi, and H.-S. Zhou. Multi-input functional encryption. In EUROCRYPT, volume 8441 of LNCS, pages 578--602. Springer, 2014.Google Scholar
- S. Goldwasser and S. Micali. Probabilistic encryption & how to play mental poker keeping secret all partial information. In ACM Symp. on Theory of Computing, pages 365--377, California, USA, 1982. Google ScholarDigital Library
- S. Goldwasser and S. Micali. Probabilistic encryption. Journal of Computer and System Sciences, 28(2):270--299, 1984.Google ScholarCross Ref
- S. Gorbunov. Cryptographic Tools for the Cloud. PhD thesis, MIT, 2015.Google Scholar
- S. Gorbunov, V. Vaikuntanathan, and H. Wee. Attribute-based encryption for circuits. In STOC '13, pages 545--554. ACM, 2013. Google ScholarDigital Library
- V. Goyal, O. Pandey, A. Sahai, and B. Waters. Attribute-based encryption for fine-grained access control of encrypted data. In 13th ACM Conference on CCS, pages 89--98. ACM, 2006. Google ScholarDigital Library
- H. Hacigümüs, B. Hore, B. Iyer, and S. Mehrotra. Search on Encrypted Data, volume 33, chapter Secure Data Management in Decentralized Systems, pages 383--425. Springer, 2007.Google Scholar
- H. Hacigümüs, B. Lyer,, and S. Mehrotra. Query optimization in encrypted database systems. In Database Systems for Advanced Applications, Beijing, China, 2005. Google ScholarDigital Library
- H. Hacigümüs, B. Lyer, C. Li,, and S. Mehrotra. Executing sql over encrypted data in the database-service-provider model. In ACM SIGMOD Conference, Wisconsin, USA, 2002. Google ScholarDigital Library
- H. Hacigümüs, B. Lyer, and S. Mehrotra. Efficient execution of aggregation queries over encrypted relational database. In Database Systems for Advanced Applications, Jeju Island, Korea, 2004.Google ScholarCross Ref
- S. Halevi. Helib: an implementation of homomorphic encryption. https://github.com/shaih/HElib. {retrieved: Oct, 2014}.Google Scholar
- S. Halevi and V. Shoup. Algorithms in helib. In CRYPTO, California, USA, 2014.Google ScholarCross Ref
- B. Hore, S. Mehrotra,, and G. Tsudik. A privacy-preserving index for range queries. In VLDB, pages 720--731, Toronto, Canada, 2004. Google ScholarDigital Library
- J. Katz, A. Sahai, and B. Waters. Predicate encryption supporting disjunctions, polynomial equations, and inner products. In EUROCRYPT, volume 4965, pages 146--162. International Association for Cryptologic Research, 2008. Google ScholarDigital Library
- F. Kerschbaum and A. Schroepfer. Optimal average-complexity ideal-security order-preserving encryption. In ACM Conference on CCS, Arizona, USA, 2014. Google ScholarDigital Library
- M. Lepinksi, S. Micali, and A. Shelat. Collusion-free protocols. In ACM Symp. on Theory of Computing, 2005. Google ScholarDigital Library
- Microsoft. Transparent data encryption. http://msdn.microsoft.com/enus/library/bb934049.aspx. {retrieved: Oct, 2014}.Google Scholar
- Microsoft. Always encrypted (database engine), February 3 2016.Google Scholar
- I. Miers, C. Garman, M. Green, and A. D. Rubin. Zerocoin: Anonymous distributed e-cash from bitcoin. In IEEE S&P, pages 397--411, San Francisco, California, USA, 2013. Google ScholarDigital Library
- D. K. Mishra and M. Chandwani. Extended protocol for secure multiparty computation using ambiguous identity. WSEAS Transaction on Computer Research, 2(2):227--233, February 2007.Google Scholar
- R. Müller, J. Teubner, and G. Alonso. Data processing on fpgas. PVLDB, 2(1):910--921, 2009. Google ScholarDigital Library
- V. Oleshchuk and V. Zadorozhny. Secure multi-party computations and privacy preservation: Results and open problems. Telektronikk, 103(2):20--26, 2007.Google Scholar
- A. O'Neill. Definitional issues in functional encryption. IACR Cryptology ePrint Archive, 556, 2010.Google Scholar
- Oracle. Transparent data encryption. http://www.oracle.com/technetwork/database/options/advanced-security/index-099011.html.Google Scholar
- R. Ostrovsky, A. Sahai, and B. Waters. Attribute-based encryption with non-monotonic access structures. In 14th ACM Conference on CCS, pages 195--203. ACM, 2007. Google ScholarDigital Library
- P. Paillier. Public-key cryptosystems based on composite degree residuosity classes. In EUROCRYPT, pages 223--238, Prague, Czech Republic, 1999. Google ScholarDigital Library
- V. Pappas, F. Krell, B. Vo, V. Kolesnikov, T. Malkin, S. G. Choi, W. George, A. Keromytis, and S. Bellovin. Blind seer: A scalable private dbms. In IEEE S&P, Oakland, CA, USA, 2014. Google ScholarDigital Library
- R. A. Popa, F. H. Li, and N. Zeldovich. An ideal-security protocol for order-preserving encoding. In IEEE S&P, Berkeley, California, USA, 2013. Google ScholarDigital Library
- R. A. Popa, C. M. S. Redfield, N. Zeldovich, and H. Balakrishnan. Cryptdb: Protecting confidentiality with encrypted query processing. In ACM Symp. on OSP, Cascais, Portugal, 2011. Google ScholarDigital Library
- K. P. N. Puttaswamy, C. Kruegel, and B. Y. Zhao. Silverline: toward data confidentiality in storage-intensive cloud applications. In ACM SOCC, Cascais, Portugal, 2011. Google ScholarDigital Library
- R. R. Ravan, N. B. Idris, and Z. Mehrabani. A survey on querying encrypted data for database as a service. In CyberC, pages 14--18, Beijing, Oct. 2013. IEEE Computer Society. Google ScholarDigital Library
- European Union Agency for Network and I. Security. Survey: An sme perspective on cloud computing. http://www.enisa.europa.eu/activities/riskmanagement/files/deliverables/cloudcomputing-smesurvey/at download/fullReport, 2009. {retrieved: Oct, 2014}.Google Scholar
- relax Google BigQuery. Encrypted bigquery client. https://code.google.com/p/encryptedbigquery-client. {retrieved: Sep, 2014}.Google Scholar
- relax North Bridge. Cloud adoption survey. http://www.northbridge.com/2013-futurecloud- computing-survey-reveals-businessdriving- cloud-adoption-everything-service-erait. {retrieved: Dec, 2014}.Google Scholar
- R. L. Rivest, L. Adleman, and M. L. Dertouzos. On Data Banks and Privacy Homomorphisms, pages 169--179. Academic Press, New York, 1982.Google Scholar
- A. Sahai and B. Waters. Fuzzy identity-based encryption. In EUROCRYPT, volume 3494, pages 457--473. Springer, 2005. Google ScholarDigital Library
- R. Sheikh, D. K. Mishra, and B. Kumar. Secure multiparty computation: From millionaires problem to anonymizer. Information Security Journal: A Global Perspective, 20(1):25--33, January 2011. Google ScholarDigital Library
- Skyhigh. Cloud security and enablement. https://www.skyhighnetworks.com/. {retrieved: Feb, 2016}.Google Scholar
- D. Song, D. Wagner, and A. Perrig. Practical techniques for searches on encrypted data. In IEEE S&P, Berkeley, USA, 2000. Google ScholarDigital Library
- SqlCipher. Database encryption. https://www.zetetic.net/sqlcipher/. {retrieved: Oct, 2014}.Google Scholar
- S. Tu, M. F. Kaashoek, S. Madden, and N. Zeldovich. Processing analytical queries over encrypted data. In VLDB, volume 6 of 5, pages 289--300, Trento, Italy, 2013. Google ScholarDigital Library
- M. v. Dijk, C. Gentry, S. Halevi, and V. Vaikuntanathan. Fully homomorphic encryption over the integers. In EUROCRYPT, Nice, France, 2010 Google ScholarDigital Library
- B. Waters. A punctured programming approach to adaptively secure functional encryption. Technical report, University of Texas at Austin, 2014.Google Scholar
- A. C. Yao. Protocols for secure computations. In 23rd Symp. on Foundations of CS, pages 160--164, Indore, India, 1982. Google ScholarDigital Library
Index Terms
- Processing Over Encrypted Data: Between Theory and Practice
Recommendations
Processing encrypted data
A severe problem in the processing of encrypted data is that very often, in order to perform arithmetic operations on the data, one has to convert the data back to its nonencrypted origin before performing the required operations. This paper addresses ...
Verifiable Computation on Outsourced Encrypted Data
Computer Security - ESORICS 2014AbstractOn one hand, homomorphic encryption allows a cloud server to perform computation on outsourced encrypted data but provides no verifiability that the computation is correct. On the other hand, homomorphic authenticator, such as homomorphic ...
Expressive search on encrypted data
ASIA CCS '13: Proceedings of the 8th ACM SIGSAC symposium on Information, computer and communications securityDifferent from the traditional public key encryption, searchable public key encryption allows a data owner to encrypt his data under a user's public key in such a way that the user can generate search token keys using her secret key and then query an ...
Comments