International Journal of Computer Science Trends and Technology (IJCST) Volume 5 Issue 2, Mar Apr 2017

RESEARCH ARTICLE OPEN ACCESS

Significant Approaches to Computation on Encrypted Data

Irene Getzi S
Department of MCA
Jyoti Nivas College
Bangalore - India

ABSTRACT
Cloud computing bring about a major shift in computing. The control over data and operations from the client organization is
now shifted to their cloud providers. The basic tasks like storage, retrieval and maintenance of data become the responsibility of
the cloud service provider and not the user. As more and more security breaches happening all over the world in different forms
it is necessary to protect the data from the adversaries. The most difficult adversary to protect against in a public cloud is the
cloud provider itself. It controls everything: the data center, the network, the operating system the hardware and the users. Thus
it becomes rampant to store the data in the encrypted format that provides confidentiality and privacy. However as soon as data
is encrypted it becomes seemingly impossible to perform computations on the data without decrypting it. The question of
computing on encrypted data (COED) has instigates a number of fascinating techniques as well as deep open problems. It
remains a driving force behind much of the most exciting research in cryptography today. This paper presents some of the
underlying technologies and overview of the work done in this regard.
Keywords :- Computations on encrypted data, COED, functional encryption, symmetric searchable encryption, secure searches,
homomorphic encryption

I. INTRODUCTION A problem with the traditional data retrieval or computational

system is that, when a query is given on the encrypted data, it
We live in the era of information explosion and have lets the server decrypt the data, runs the query on the server
witnessed the trend of leveraging cloud-based services for side, and sends only the results back to the user. This allows
large scale content storage, processing, and distribution. the server to learn the data being queried or computed and
"Data-as-a-Service" (DaaS) applications are on arise and hence makes encryption less useful. The security mechanism
various business systems are trying to evolve and benefit from adapted should not leak any information on the access or the
cloud services. Though the benefits of cloud computing is search to the server. In short, the system should allow the user
clear, the cloud based systems poses an added level of risk to perform complicated processing of data without being able
because the essential services are now outsourced to a third to see it.
party. Thus it is necessary to develop a proper security
mechanism for cloud implementations to reap the benefits it Computation on Encrypted Data (COED) seeks to develop
offers. As the cloud server itself cannot be trusted, we need a methods that allow computing with encrypted data without
secured technology that protects our data and applications first decrypting it, making it more difficult for adversaries to
without relying on or revealing information to the untrusted get to know the information. These technologies are becoming
server. increasingly well developed, and some have found
commercial application. In this paper, we outline some of
One possible approach to enforce protection to the data these technologies that support COED; these are technologies
without relying on cloud servers could be to encrypt data which support Encrypted Search such as Searchable
before outsourcing to the untrusted server and disclose the Symmetric Encryption
corresponding decryption keys only to authorized users. This
reduces security and privacy risks by hiding all information
about the plaintext data. Encryption makes it impossible for II. BACKGROUND STUDY
both insiders and outsiders to access the data without the keys COED complements the cryptographic protocols that protect
but at the same time makes traditional data utilization services data in transit and at storage by offering protection during
such as searching, retrieving and performing computations on computation. COED technologies offer end-to-end protection
the data a difficult task. to sensitive information by allowing data to stay encrypted at
all times even when performing computation.
Data sets are becoming very large nowadays that it becomes
difficult to keep a local copy of data in the client location to The most basic form of computation on encrypted data is to
perform analysis. Often, it is also the case that the data cannot perform a search on it as Search is the primary way to access
be aggregated at a single repository due to mutual privacy the stored data. The problem of encrypted search is now of
concerns.

ISSN: 2347-8578 www.ijcstjournal.org Page 321

 International Journal of Computer Science Trends and Technology (IJCST) Volume 5 Issue 2, Mar Apr 2017
interest to many sub-fields in computer science as well as for
many privacy preserving applications related to business, Though deterministic encryption scheme offers a faster
health-care and to governments. solution, it has the limitation that it always encrypts the same
message to the same ciphertext. Also the server can learn if
The problem of searching on encrypted data was first the client is repeating a search a not. Another issue occurs
considered explicitly by Song, Wagner and Perrig in [1]. when the scheme uses public-key; the data is encrypted by
Various searchable encryption schemes were proposed that client's public key that is available to the server. The server
uses technologies like property-preserving encryption [6], can then mount a dictionary attack on the encrypted database.
Functional encryption [7], symmetric searchable encryption
[2, 4], and homomorphic encryption [9, 10]. Order-preserving encryption is, apparently, a method of
encrypting data so that it's possible to make efficient
Secured searches are a well-studied concept and it offers a inequality comparisons on the encrypted items without
very rich set of search queries on encrypted data such as decrypting them. Such a solution can be used when the data
boolean queries, multi-key word search queries, and range has high min-entropy, which is a way of saying that the data
queries. Ongoing researches are happening on searching looks random to the server.
through very large scale datasets and multicloud
environments. B. Functional Encryption
For many cloud services applications, there is often a need
In order to reap the full benefits offered by cloud, secured to specify a decryption policy in the ciphertext and only
searching alone may not be sufficient. Data mining or individuals who satisfy the policy can be allowed to decrypt.
analytics application may require basic to complex i.e. we may want to only give access to a function/part of the
computations to be performed on the encrypted data. plaintext, depending on the authorization rules of a user. A
Homomorphic encryption, secure multiparty computation and functional encryption system, with a decryption key allows a
Oblivious RAM can offer significant results in this regard. user to learn a function of the encrypted data. i.e. in a
functional encryption system for functionality F, an authority
holding a master secret key can generate a key that enables the
III. SIGNIFICANT COED TECHNOLOGIES computation of the function on encrypted data.
WITH CONTROLLED LEAKEGE
The notion of FE was first described by Sahai and Waters in a
talk [17] and Later Boneh et al.[7] formalized its construction
There are a number of ways to compute on encrypted data and is based Identity Based Encryption (IBE) where data gets
each one is suitable for a specialized setting. The different encrypted using receivers identification such as passwords
tradeoffs considered are functionality, security, and efficiency. and the receiver can search on the ciphertext using secret key
While homomorphic encryption and Oblivious RAM can offer generated with his ID.
better security without leakage it cannot provide a practical
solution. When fully homomorphic or ORAM based schemes Various other properties were considered and give rise what is
cannot provide a practical solution, we can take advantage of called Attribute-Based Encryption (ABE). ABE can be
controlled leakage constructions. This section provides an regarded as a generalization of IBE. It decomposes the user
overview on some of the competing technologies used for identity as a set of attributes, and enables every user to have
computation on encrypted data with controlled leakage. its unique attributes set. The encryptor can pick an attributes
set and generate an access control policy associated this
attributes set, then he can use encrypt data with this policy. A
A. Property-Preserving Encryption decryptor whose attributes set satisfy the policy have the
permission to decrypt the ciphertext. Its flexible access control
Property-preserving encryption (PPE) is a specialized policy and multi-user support property turned out to be
encryption scheme that can be used in secure outsourced extremely suitable for cloud architecture.
storage that intentionally leaks certain properties of the
underlying message. PPE-based solutions can achieve fast The schemes based on functional encryption offered better
sub-linear time server-side encrypted search. But they do have security and access control mechanism but are slower than the
some limitations such as it leaks quite a bit of information to PPE-based approach. The encrypted database by itself does
the server about the data collection [6]. not reveal much useful information to the server since
keywords are encrypted using a randomized (identity-based)
There are different types of PPE schemes that each leak encryption scheme. But the problem with this approach is that
different properties. The two main examples are deterministic as with any public-key encrypted search solution, the server
encryption (DE), which preserves the equality property, and has both the ability to create the index file with the users
order preserving encryption (OPE), which preserves order public key and to search over them.
comparison.

ISSN: 2347-8578 www.ijcstjournal.org Page 322

 International Journal of Computer Science Trends and Technology (IJCST) Volume 5 Issue 2, Mar Apr 2017
Hence symmetric key setting was introduced that may be well ORAM-based solution can offer optimal level of security
suitable for this setting because only client can generate guarantee without any leakage. Originally proposed by
encrypted index and search tokens. Goldreich and Ostrovsky [3], ORAM is a cryptographic
construction that allows a client to read and write to memory
C. Symmetric Searchable Encryption without the memory device knowing which locations are
being accessed. Particularly, the sequence of physical
The Symmetric searchable encryption scheme (SSE) addresses accessed is independent of the actual data that the
employs a prebuilt search index encrypted by the clients user is accessing. To achieve this, existing ORAM
secret key that is sent to the outsourced server along with the constructions continuously re-encrypt and reshuffle data
encrypted documents. The scheme lets users with appropriate blocks on the storage server.
tokens securely search over the encrypted data through
keywords without decrypting it. Thus a client can access the encrypted data residing on an
untrusted storage server, while completely hiding the access
The symmetric searchable scheme proposed by Song in [1] patterns to storage. Unfortunately, this approach requires
uses Steam cipher method for encryption and supports many rounds of interaction and has a high overhead that
sequential search method that may allow attackers to get the makes ORAM inefficient and unacceptable especially for
information of keywords using a statistical analysis on the large scale data outsourcing applications.
searching result.
B. Homomorphic Encryption
The works that followed in this area proposed index-based
search schemes and focused on how to build an efficient and Homomorphic encryption (HE) is a cryptographic
secure index for the data files. Different index structures are construction that allows computations to be carried out
proposed to extend the functionality of SSE that supports on encrypted data, such that the generated encrypted result,
search queries on matrix data, labeled data, neighbor and when decrypted, matches the result of operations performed
adjacency queries on graph data multi-keyword boolean on the clear text. It allows mathematical operations to be
search queries. performed on encrypted without compromising the encryption.
In 2009, Craig Gentry introduced the first Fully
Subsequently, the inverted index approaches were proposed in Homomorphic Encryption (FHE) scheme that was based on
[2, 4] that reduced the search time to sub-linear time. While lattice-based cryptosystem. However, Gentry's scheme proved
the inverted index approach yields the efficient search time, it unfeasible in practice due to a massive overhead in both
is not well-suited to handle dynamic collections. The above- computation and memory cost.
mentioned schemes mainly used only static indexes that make
it difficult for the user to dynamically add or update to the A quite lot of work is being carried out to increase the
existing index or document collection. That requires the index efficiency of the scheme. The homomorphic properties mainly
file to be rebuilt. focus on additions and multiplications because, in theory, any
operation can be brought down to a binary circuit at its lower
The notion of dynamic updates was introduced by Kamara et level.
al. in the [2], which allows dynamic addition and deletion of
index entries. The Dynamic SSE schemes require additional The existing public-key systems, such as ElGamal [12] and
data structures such as search tables and arrays and thus Pallier [6], support only one homomorphic operation. A
making their construction very complex and difficult to doubly-homomorphic system proposed in [15] can be applied
implement. only to compute few boolean operations as the ciphertext size
doubled at every step. As a result, one could only perform few
The major limitation with the SSE schemes is that it leaks boolean operations before the ciphertext size became
certain information to the underlying server such as the access unmanageable. Recently constructions based on elliptic curves
and search patterns. In fact, by observing enough search are gaining momentum and seems to produce better results.
results the server could use some sophisticated statistical
attack to infer something about the client's queries and data.
This limitation can be overcome with the Oblivious RAM or C. Secure Multiparty Computation
homomorphic technologies.
Computation on encrypted data using HE schemes slows
IV. SIGNIFICANT COED TECHNOLOGIES down by nearly 10 orders of magnitude, making it infeasible.
WITHOUT LEAKEGE A related research area is secure multiparty computation
(SMC), in which multiple entities can jointly perform
A. Oblivious RAM (ORAM) computations while maintaining the privacy of each entitys
data. SMC protocols incur significant overhead, but
ORAM-based solution can offer optimal level of security comparatively less than HE schemes.

ISSN: 2347-8578 www.ijcstjournal.org Page 323

 International Journal of Computer Science Trends and Technology (IJCST) Volume 5 Issue 2, Mar Apr 2017

Secure Multiparty Computation (SMC) allows multiple parties

to perform computation on their private data to evaluate some
function, without revealing their private data. Only the result
of the computation will be available to all the parties. This
privacy-preserving technique can be used when multiple cloud
providers or multiple cloud users jointly compute some
function of their private data inputs.

Fully homomorphic encryption (FHE) enables secure

computation over the encrypted data of a single party. This
can be extended to multiple parties using multiparty
computation. Recently various schemes [10, 13, 14] are
proposed that combine the functionalities of homomorphic
encryption and multiparty computation to offer efficient [5] R. Curtmola, J. Garay, S. Kamara, and R. Ostrovsky.
solutions with less interaction and communication overhead. Searchable symmetric encryption: Improved definitions
and efficient constructions, In Proceedings of the 2006
ACM Conference on Computer and Communications
V. CONCLUSIONS Security, CCS06, pages 7988, 2006.
With the rise of cloud computing and storage, there is rise in [6] E. Stefanov and E. Shi. Oblivistore: High performance
the concerns about the security issues of outsourced data. As a
oblivious cloud storage. In Proceedings of the 2013
result, several constructions have been proposed in recent
years to provide with the ability to perform searches and IEEE Symposium on Security and Privacy, SP13, pages
computation on the encrypted data that would greatly reduce 253267, 2013.
the risk of data breaches and insider attacks. Some of the [7] M. Abdalla, M. Bellare, D. Catalano, M. Kiltz, T. Kohno,
schemes like Functional and property preserving encryption T. Lange, J. Malone-Lee, G. Neven, P. Paillier, H. Shi,
schemes The most well-known of these COED methods, Fully Searchable encryption revisited: Consistency properties,
Homomorphic Encryption, can in theory offer a perfect relation to anonymous IBE, and extensions, in:
solution, but is extremely inefficient for most real-world
Advances in Cryptology, CRYPTO 2005, Springer,
situations. Other solutions include Oblivious RAM and
multiparty computation and special forms of identity-based Berlin, Heidelberg, 2005, pp. 205222.
encryption, but these are still pretty expensive. [8] D. Boneh , Amit Sahai, and Brent Waters, Functional
The ultimate challenge when it comes to COED is to enable Encryption: Definitions and Challenges, Theory of
secure computing on huge data sets with controlled leakage. Cryptography Conference, TCC 2011: pp 253-273
[9] Joppe W. Bos, Kristin Lauter, , Michael Naehrig, Private
predictive analysis on encrypted medical data, Journal of
REFERENCES Biomedical Informatics, Volume 50, August 2014, Pages
[1] S. M. Metev and V. P. Veiko, Laser Assisted 234243
Microtechnology, 2nd ed., R. M. Osgood, Jr., Ed. Berlin, [10] Manish M. Potey C.A. Dhote. Deepak H. Sharma,
Germany: Springer-Verlag, 1998. Homomorphic Encryption for Security of Cloud Data,
[2] D. X. Song, D. Wagner, and A. Perrig. Practical Procedia Computer Science Volume 79, 2016, Pages
techniques for searching on encrypted data. In IEEE 175-181.
Symposium on Security and Privacy, SP00, pages 44 [11] Adriana Lopez-Alt, Eran Tromer, Vinod Vaikuntanathan,
55, 2000. On-the-Fly Multiparty Computation on the Cloud via
[3] S. Kamara, C. Papamanthou, and T. Roeder, Dynamic Multikey Fully Homomorphic Encryption, Proceeding
searchable symmetric encryption. In Proceedings of the STOC '12 Proceedings of the forty-fourth annual ACM
2012 ACM Conference on Computer and symposium on Theory of computing Pages 1219-1234
Communications Security, CCS12, pages 965976, [12] Ivan Damgard, Yuval Ishai, Mikkel Krigaard, Perfectly
2012. Secure Multiparty Computation and the Computational
[4] O. Goldreich and R. Ostrovsky. Software protection and Overhead of Cryptography, Proceeding
simulation on oblivious RAMs. J. ACM, 43(3):431473, EUROCRYPT'10 Proceedings of the 29th Annual
1996. international conference on Theory and Applications of
Cryptographic Techniques, Pages 445-465.

ISSN: 2347-8578 www.ijcstjournal.org Page 324

 International Journal of Computer Science Trends and Technology (IJCST) Volume 5 Issue 2, Mar Apr 2017
[13] ElGamal, T, A public key cryptosystem and a signature
scheme based on discrete logarithms. IEEE Transactions
on Information Theory 31(4), 469472 (1985)
[14] R. L. Lagendijk, Zekeriya Erkin, and Mauro Barni,
Encrypted Signal Processing for Privacy Protection,
Conveying the utility of homomorphic encryption and
multiparty computation, IEEE Signal Processing
Magazine, 2013
[15] David Pointcheval Thomas Johansson , Multiparty
Computation with Low Communication, Computation
and Interaction via Threshold FHE, Conference
proceedings, EUROCRYPT 2012
[16] Sander, T., Young, A., Yung, M, Non-interactive Crypto
Computing for NC1. In: Proceedings of the 40th
Symposium on Foundations of Computer Science
(FOCS), New York, NY, USA, October 1999, pp. 554
567. IEEE Computer Society Press, Los Alamitos (1999)
[17] Pallier, P, Public-key cryptosystems based on composite
degree residuosity classes. In: Stern, J. (ed.)
EUROCRYPT 1999. LNCS, vol. 1592, pp. 223238.
Springer, Heidelberg (1999)
[18] Brent Waters, Functional Encryption: Beyond Public
Key Cryptography, Identity based encryption workshop
2008.
[19] D. Boneh, E. Kushilevitz, R. Ostrovsky, W.E. Skeith III,
Public key encryption that allows PIR queries, in:
Advances in Cryptology, CRYPTO 2007, Springer,
Berlin, Heidelberg, 2007, pp. 5067.

ISSN: 2347-8578 www.ijcstjournal.org Page 325