Fully Homomorphic Encryption Scheme In Big Data

Prasanna Kumar Annapureddy,

Ankit Dadoch

Texas A&M University,

Texas A&M University,

Corpus Christi

Corpus Christi

[email protected] [email protected]

Abstract

·

Big

Data is a term given to data that is so large and complex that conventional

data processing application software’s are not enough to deal with them.

·

In

today’s world, privacy leakage related to big data is a major issue for

individuals. Usually, data protection and data security is provided through

encrypted data but at the expense of usability.

·

Fully

Homomorphic Encryption allows to perform unlimited chaining of mathematical

operations on the encrypted data making it possible for legal companies and

other institutions to use them.

·

In

this paper, we address the problem of building secure computational services

for encrypted information in cloud computing without decrypting the encrypted

data

Introduction

·

There

is an increasing need in for development of Big Data infrastructure that will

support storage and process big data in cloud computing environment.

·

Cloud

computing amongst many of its features such as reduction in cost, elasticity,

wide network access and measured service etc. offers the most crucial feature

of storage and analysing of sharing of computing resources. This is the major

reason why it is the chosen as a tool for Big Data processing and analytics.

·

Although,

along with its benefits it has some risks too

A. Cloud

Security

·

Cloud

computing is an Information Technology(IT) model. The IT components consist of

crucial components: hardware, software, networking and services.

·

Clock

computing is lacking in Structure, confidentiality, integrity and availability.

·

Therefore,

cloud computing requires protection of the cryptographic abstracted TRIAD –

confidentiality, integrity and availability.

These three are the basis of information security. The meaning of securing the clouds means that

the information that is stored should be free from attacks by an advocacy.

·

Cloud

Computing has several models namely public clouds, private clouds and hybrid

clouds and all three models require some real-time security. Transmission over

public data also requires some sort of security as the client will demand some

sort of security from the service providers.

·

Although,

computations performed on the encrypt stored data poses certain challenges as

the private key will have to be provided to the cloud providers before computation

analysis could be carried out on that data which can be another problem as the

cloud providers will have access to your data and they could also be an

adversary.

·

Therefore,

keeping in mind these challenges to the data confidentiality and user’s privacy

along with the need of application of data mining and other data analytic

algorithms to be efficiently encrypted, fully homomorphic encryption (FHE) is

used.

B. Big

Data Analytics Security

·

As

we already know, big data is defined as a collection of datasets that are so

large and complex that the processing of such data becomes very intricate using

conventional Data processing applications.

Big data analytics faces several challenges such as storage, sharing,

analysis and visualisation.

·

Big data is characterised with V’s

dimensions. These include volume,

velocity, variety and voracity. The

details of these dimensions are given below:

1.

Volume:

This term defines that Data Volume typically ranges from several TB to ZB monthly. This fits the enterprise security model as

it is pretty common for large organisations to collect tens of terabytes of

security data on monthly basis.

2.

Velocity:

This deals with real-time data analyst requirements. In cyber security,

velocity can imply to the requirement for immediate anomaly, or rapid incident

response in real-time. Real-time data analysis is crucial here to minimise

damages that are related with cyber security attack.

3.

Variety:

This term explains that multiple data type requirements and feeds that include

structured and unstructured data combined give us the Big Data. From a security point of view, Data variety

could include large files, network flows, intelligence and social

networking activity etc. So, usually enterprises will collect hundreds of

different types of data for analysing security using different algorithmic

models.

4.

Veracity:

This term implies that big data should be loyal and accurate. From the security

perspective, this means to trust confidentiality and availability of data

sources like log files and external feeds.

· The

definitions that are given above clearly define that big data needs security

with the help of cryptography.

Our Proposal

· Our

approach is concerned with developing a new model that combines the big data

analytics, cloud computing and fully homomorphic encryption to improve

security. Thus, our contribution is to merge these already existing research

entities as studied separately into some meaningful research exposition.

Public

Key Encryption

· In

today’s world, almost every individual has a portable computing device that can

access server in the cloud environments. So, the security of their data is of

utmost importance. In earlier computing

scenarios, clients were trusted but they were weak, while computationally

strong servers were not trusted due to that client lack of control they had

over their operational functionalities. The improvement over this was to simply

encrypt the pieces of data which solved almost every privacy issue perfectly.

· Data could be encrypted using symmetric key

encryption or asymmetric key encryption called public key encryption. Nonetheless, a model was derived based on the

exponentiation function called the homomorphic encryption. Further, we will discuss the public key

encryption used along with homomorphic encryption which are divided into two

categories namely partially homomorphic public key encryption and fully

homomorphic public key encryption.

Partially Homomorphic Public Key Encryption

· Encryption

allows complex mathematical operation encrypted data without the contents of

the encrypted data being revealed.

Homomorphic

encryption scheme is defined as

Quadruple-tuple

E = (Gen, Enc., Dec., Eval.) with an

extension of two group operators (+, *) over the plaintext M and the ciphertext

C, respectively.

By the

definition, this is a “homomorphism” between the plaintext M and the ciphertext

C.

If M1+M2 =

Dec (sk, C1, C2)

where, C1 = Enc (pk, M1, Eval. );

and, for arbitrary M1 and M2 E M

· A

homomorphic encryption model consists of several algorithmic parameters for

further clarification : KeyGen

Implementation Of Partially Homomorphic

Encryption Scheme

· The issue of security has hindered an open problem in cryptography,

more in the area of confidentiality and integrity security. Let us take

examples on how several schemes in conjunction with homomorphism deals with

these issues

a)

Example I : RSA Homomorphism

Consider two large prime numbers p & q such that n=pq and gcm(p,q)=1. Select a form

j(n)=(p-1)(q-1) ‘ ab=1modj(n),

implying that a=(b inv.) mod j(n).

The parameters (n,b) are public while the three

parameters p ,q and a are private. Compute the encryptions:

Enc. K (x)

= x^b mod n = y where x is plaintext and y is ciphertext.

Dec. K (y)

= y^b mod n = x

a)

The homomorphism of RSA is computed as

follows:

Consider two plaintexts x1 & x2. Then their

homomorphism is expressed as:

Enc. K

(x1) Enc. K (x2) = (x1^a) (x2^b) mod n

= (x1.x2) ^ b mod n

= Enc. K (x1*x2)

b)

Example

II : El Gamal Homomorphism

Randomly select a large odd number and a

generator a e Zp, select a &

b such that

b=a^a(mod p)

Make p, a and b public; Give a parameter r e Zp-1

also a secret random number. Then,

Enc. K

(x,r) = (a^r mod p, xb^r mod p)

The homomorphism of El Gamal Homomorphic

cryptosystem can be computed from its cryptosystem as follows:

For two arbitrarily plaintexts x1 & x2;

Enc. K

(x1,r) Enc. K (x2,r) = (a^r1

mod p, x1 b^r1 mod p)( a^r2 mod p,

x2 b^r2 mod p)

= (a^r1 a^r2 mod p, x1, b^r1

b^r2

mod p)

= (a^(r1+r2) mod p, (x1 +x2) b^r1+r2

mod p)

= Enc. K (x1+x2, r1+r2)

In

homomorphic encryption scheme, the algorithm encrypts one bit at a time.

Therefore, in order to encrypt a binary string we will have to encrypt every

bit individually.

Fully Homomorphic Encryption Scheme

·

Partial homomorphic encryption schemes had one

drawback, that they could only perform one binary operation at a time which

means they could only perform addition or multiplication computations at once.

On the other hand, fully homomorphic encryption can perform several addition

computations and one single multiplication computation on ciphertexts. Ideal

lattices and bootstrapping technique are employed to deliver this feature of

FHE.

·

The major task of FHE is to improve the cloud

computing security. This operation takes place in a certain format given below:

a)

First, the data is encrypted and sent to the

cloud computing environment;

b)

Then, the encrypted data present in the

cloud is subjected to certain computations using some functions without

converting them into plaintext;

c)

After querying the encrypted data, it is

sent back for being decrypted; and

d)

Using the private key, the plaintext is

recovered from the computational out function.

·

Propertied

Of Fully Homomorphic Encryption

I.

No limited number as to how many manipulations

that can be executed on it;

II.

The computational processes are performed on

circuit gates combinations of AND gates & XOR gates with ciphertexts as

their inputs;

III.

FHE requires an additional algorithm in the

cloud named Evaluate algorithm which takes the public key, a circuit function f

and a tuple of ciphertexts which are used as inputs;

IV.

FHE can query a search engine without

revealing what is being search;

V.

It is given by two models

Decsk (C1

+ C2) = m1+m2 and Decsk (C1*C2) = m1*m2;

VI.

Ciphertext

Compactness : This property demands that the polynomial function should not

increase in size. To put it simply, the ciphertext should remain bounded or

compact, independent of the function f;

VII.

Generally, ciphertexts contain some noise or

error in them. Employing homomorphic encryption on these ciphertexts drives the

ciphertext to render more noise. This in turn will make the decryption

infeasible. Besides, this also violates the ciphertext compactness property of

FHE.

Gentry’s Fully Homomorphic Encryption

Algorithm

·

This model of FHE consists of three steps:

I.

Somewhat

Homomorphic;

II.

Quashing;

and

III.

Bootstrapping

·

The gentry’s FHE Computational process takes

place in the following way:

·

Starts

with somewhat homomorphic encryption : Somewhat homomorphic encryption is limited to only a certain number of

additions and multiplications on ciphertexts. This limitation is a product of

the presence of noise in the ciphertext. If additional computations are applied

to the ciphertexts, the polynomial function increases in size and in turn will

render more noise and thereby resulting in infeasible decryption process as

once the noise reaches a certain level, the computational encrypted ciphertext

cannot be decrypted any further.

For instance, let noise be ‘n’ and the threshold

beyond which it causes uncertainties be ‘k’. Then, this bound is reached only

after log2 k levels of multiplication. In

SHE, the ciphertext cannot go beyond the bound as the message size gets larger

and this violates the ciphertext compactness property of FHE.

To achieve FHE, this enlarged noise issue must be

solved. Gentry’s method is used for ciphertext decryption but homomorphically

and have it sent to the cloud with the encrypted message. Such a private key

should have the capability to decrypt itself once in the cloud so as to decrypt

the encrypted message at some phases.

·

Bootstrapping

: This leads to a fully homomorphic encryption scheme. The fully

homomorphic encryption scheme goes through the following stages:

The

function which brings in a certain level of noise in the encryption scheme

that later generates compounded issues is

the centre of interest here

1.

Every operation performed on the ciphertext

results in expanding the level of inherent noise;

2.

The solution for this is to employ

bootstrapping for encryption;

3.

Every time you re-encrypt, the noise is

subsequently cut down;

4.

The operation of FHE is based on Ideal Lattices, that is ideal in number

theory which

a.

Permits new complex circuit implementation;

and

b.

Replicates the structure of ring

homomorphism.

·

The FHE includes SHE as a part of it execution

operation. This is to not allow the algorithm to converge locally. The

bootstrapping noise algorithm for the SHE is idealized like this:

a)

KEYGEN Evaluation : Output a random odd

integer p;

b)

For bit m -> {0,1}, let m’ = m mod n; where m’ is even if

m=0, odd if m=1. Select a random q.

ENCRYPTE (m,p) = C = m’ +pq

M’ is the noise associated

with the plaintext

c)

Let C’ = C mod p and C’ -> (-p/2,p/2)

Then, DECRYPT(p,c) = c’ mod 2

The noise encrypted C’ is considered to be the

noise associated with the ciphertext (that is, the shortest distance to a

multiple of p)

The homomorphism Multiplication:

Let m1,m2 -> {0,1} then,

Enc. e (m1,p)

Enc. e

(m2,p) = (m1′ + pq1)*(m2′ + pq2)

The decryption :

Dec. (c) =

(m1′ + pq1)(m1′ + pq2) mod p mod2

= m1’m2′ mod 2 = m1.m2

The compounding noise (m1′,m2′) results after a

certain number of operations after the loss of some homomorphic property.

Bootstrapping is introduces=d to stop the computational processed on the

inherent noise. This therefore allows the process to take in more inputs and

processes for a longer period and hence improves the performance.

With this contribution, the security of Big Data

has been improved significantly in the cloud computing environment.

Application Of Fully Homomorphic Encryption

Scheme In Cloud Computing

·

In the implementation, analytical performance of

the FHE cryptosystem works on the virtual platform as a cloud server. The

transmission of the encrypted data to the virtual server which is the storing

caveat of the encrypted data is handled by a VPN. This is also the platform

over which the FHE processes are computed.

fig – Database server and

client implementing homomorphic encryption

fig – Implementation of FHE in

the cloud between the server and the client

Conclusion

·

This paper has aimed at Fully Homomorphic

Encryption Schemes along with some number theory and algebra, their usefulness

in the computational application of Big Data Security & Analytics in the

cloud. The common problem with cloud computing is the privacy and the

confidentiality of the crucial data of the client along with the computation of

the data stored in the cloud computing.

·

The issue was then resolved by sending the data

encrypted to the cloud in a uniform fashion. We must explicitly make the

assertion that other mechanisms exist for secure computation.

·

In cloud, usually different data providers are

required to exchange information such as the private key. FHE schemes being

public key schemes are best suited for this scenario as many sources of data

coexist.

Future Works

·

Homomorphic Encryption will foster in a new

dimension to the cloud storage. It provides security and confidentiality to the

data without its plain text being revealed in any stage.

·

This proposed algorithm is used in Amazon Web

Services after being further simplified and can be used in online auctioning,

medical and business purposes of the many more applications it has.

·

Although, more research needs to be done in this

process for reducing the size of the ciphertext for efficient data processing

so that more computations can be processed on it before it crosses the bound

beyond which it starts posing the inherent noise issue.

·

Furthermore, there is also a need to evolve

various algorithms for searching and querying on encrypted data under FHE

scheme.

References

·

Z. Brakerski, C. Gentry, And V. Vaikuntanathan,”(Leveled) Fully

Homomorphic Encryption Without Bootstrapping,” In Itcs, 2012

·

D. Boneh, E. J In Goh, And K. Nissim, “Evaluating 2-Dnf Formulas

On Ciphertexts. In Theory Of Cryptography”; Conference, Tcc 2005, Volume 3378

of Lecture Notes in Computer Science, Pages, 325-341, Springer, 2005

·

W. Diffie, M. E Hellman, “New Directions in Cryptography, IEEE

Transactions on Information Theory, Volume IT-22, No. 6, (Online)

http://ee.standford,edu/~hellman/publications/24.pdf

·

C. Gentry; “A Fully Homomorphic Encryption Scheme”

http://crypto.standford.edu/craig.thesis.pdf

·

C. Gentry and S. Halevi, Implementing Gentry’s Fully Homomorphic

Encryption Scheme, Preliminary Report, (Online). 2009

http://reasearcher,watson.ibm.com/researcher/files/usshail/fhe-

implementation.pdf

·

C. Gentry, “Computing Arbitray Functions Data” Communication of

the ACM, V ol. 53, pp 97-105, 2010

·

S. Goldwasser and S. Micali: “Probabilistic Encryption & how

to play mental porker keeping secret all partial information”, In proceedings

of the 14th ACM symposium on the Theory of Computing (STOC ’82), New Y ork, NY

, USA, pp,21-53

·

Goldwasser, S. and S. Micali, ” Probabilistic encryption”, In

Journal of Computer and System Sciences, 1984, Vol 28, no. 2, pp270-299

·

J. Katz & L. Yehud, “Introduction to Modern Cryptography”,

Chapman& Hall/Crc Cryptography and Network Security, 2007.

·

K. McCaney, “New Encryption method with promises end-to-end cloud

security” http://gcn.com/Articles/2013/06/Encryption.end.to.end.cloud.

security.aspx?Page =1

·

J. Nittin, Saibal K. Pa and Dhananjay, K. Upadhyay;

“Implementation and Analysis of Homomorphic Encryption Schemes, International

Journal on Homomorphic Encryption

·

P. Paillier: Public-key cryptosystems based on composite degree

residuosity classes. In 18th Annual Eurocrypt Conference (EUROCRYPT’99),

Prague, Czech Republic, Volume 1592,1999

·

P.Meliand Timothy Grance, The NIST Definition of Cloud Computing,

Special Publication, 2011 800-145, Recommendation of the National Institute of Standards

and Technology. ?