 Open Access
 Total Downloads : 14
 Authors : Adilakshmy.T, Sharmila.H
 Paper ID : IJERTCONV2IS05088
 Volume & Issue : NCICCT – 2014 (Volume 2 – Issue 05)
 Published (First Online): 30072018
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Securely Outsourcing Large Scale Systems of Linear Equations Using Homomorphic Encryption
Adilakshmy.T Sharmila.H
Computer Science And Engineering Computer Science And Engineering SCET,SGI SCET,SGI
Villupuram,India Villupuram,India
diviyabarati@gmail.com sharmisekar1992@gmail.com
Abstract Harnessing the cloud for securely Outsourcing linear equations propose a very efficient cheating detection mechanism. In this paper, we formulate the problem in the computation outsourcing model for securely solving largescale systems of LE via iterative methods, and provide the secure mechanism design which fulfills input/output privacy, cheating resilience, and efficiency. Our mechanism brings computational savings as it only incurs local computation burden for the customer within each algorithm iteration and demands no unrealistic IO cost, while solving large scale LE locally usually in terms of both time and memory requirements. We explore the algebraic property of matrix vector multiplication to design a batch result verification mechanism, which allows customers to verify all answers computed by cloud from previous iterations in one batch, and further ensures both the efficiency advantage and the robustness of the design. Fully homomorphic encryption (FHE) scheme, a general result of secure computation outsourcing has been shown viable in theory, where the computation is represented by an encrypted combinational Boolean circuit that allows to be evaluated with encrypted private inputs.
Index Terms Computation outsourcing, Iterative method, Computational savings, Homomorphic encryption, Cheating detection.

INTRODUCTION
In cloud computing, customers can enjoy the literally unlimited computing resources in the cloud through the convenient yet flexible payperuse manners . Despite the tremendous benefits, the fact that customers and cloud are not necessarily in the same trusted domain brings many security concerns and challenges toward this promising computation outsourcing model. First, customers data that are processed and generated during the computation in cloud are often sensitive in nature, such as business financial records, proprietary research data, and personally identifiable health information, etc. While applying ordinary encryption techniques to these sensitive information before outsourcing could be one way to combat the security concern, it also makes the task of computation over encrypted data in general a very difficult problem. Second, since the operational details inside the cloud are not transparent enough to customers, no guarantee is provided on the quality of the computed results from the cloud. ., to protect the sensitive input and output data and to validate the computation result integrity, it would be hard to expect customers to turn over control of their computing needs from local machines to cloud solely based on its economic savings. Focusing on the engineering and scientific computing problems, this paper investigates secure outsourcing for widely applicable largescale systems of linear equations (LE), which are among the most popular
algorithmic and computational tools in various engineering disciplines that analyze and optimize realworld systems. By interior point methods, system optimization problems can be converted to a system of nonlinear equations, which is then solved as a sequence of systems of linear equations. The analysis from existing approaches and the computational practicality motivates us to design secure mechanism of outsourcing LE via a completely different approach iterative method, where the solution is extracted via finding successive approximations to the solution until the required accuracy is obtained. Compared to direct method, iterative method only demands relatively simpler matrixvector operations with O(n2 ) computational cost, which is much easier to implement in practice and widely adopted for largescale LE. To the best of our knowledge, no existing work has ever successfully tackled secure protocols for iterative methods on solving largescale systems of LE in the computation outsourcing model, and we give the first study in this paper. Specifically, our mechanism utilizes the additive homomorphic encryption scheme to securely harness the cloud for finding successive approximations to the solution in a privacypreserving and cheatingresilient manner.

SYSTEM ARCHITECTURE
We consider a computation outsourcing architecture involving cloud customer and cloud server illustrated in above Figure. The customer has a largescale LE problem Ax =b, denoted as = (, ), to be solved. However, due to the lack of computing resources, he cannot carry out such expensive computation locally. Thus, the customer resorts to cloud server for solving the LE problem. Cloud customer would initialize a randomized key generation algorithm and prepare
the LE problem into some encrypted form_K via key K. Transformation and encryption operations will be needed when necessary. Then the cloud customer would use the encrypted form_K of LE to start the computation outsourcing process. In case of using iterative methods, the protocol ends when the solution within the required accuracy if found. Finally the cloud customer would verify the encrypted result produced from cloud server, using randomized secret key K. A correct output x to the problem is produced by decrypting the encrypted output. When the fails the customer outputs indicating the cloud server was cheating.
Fig. 1.Architecture of Secure Outsourcing Linear Equations In Cloud Computing
A. Data Flow Diagram
ENCRYPTION DATA
DECRYPTION FILE
FILE DOWNLOAD
IMAGE UPLOAD
IMAGE DOWNLOAD
USER DATABASE
computing resources, the cannot carry out such expensive computation locally. Thus, the cuNsCtoICmCeTr' 1r4eCsoonrftesretnoce cPlroocuededings
server for solving the LE problem. Cloud customer would initialize a randomized key generation algorithm and prepare the LE problem into some encrypted form_K via key K. Transformation and encryption operations will be needed when necessary. Then the cloud customer would use the encrypted form_K of LE to start the computation outsourcing process. In case of using iterative methods, the protocol ends when the solution within the required accuracy if found. Finally the cloud customer would verify the encrypted result produced from cloud server, using randomized secret key K. A correct output x to the problem is produced by decrypting the encrypted output. When the fails the customer outputs indicating the cloud server was cheating. Customer is going to upload and download image, file etc.

THE PROPOSED SCHEME
We propose a very efficient cheating detection mechanism to effectively verify in one batch of all the computation results by the cloud server from previous algorithm iterations with high probability. We formulate the problem in the computation outsourcing model for securely solving largescale systems of LE via iterative methods, and provide the secure mechanism design which fulfills input/output privacy, cheating resilience, and efficiency. Our mechanism brings computational savings as it only incurs O(n) local computation burden for the customer within each algorithm iteration and demands no unrealistic IO cost, while solving large scale LE locally usually demands more than O(n2) computation cost in terms of both time and memory requirements. We explore the algebrac property of matrix vector multiplication to design a batch result verification mechanism, which allows customers to verify all answers computed by cloud from previous iterations in one batch, and further ensures both the efficiency advantage and the robustness of the design. Fully homomorphic encryption (FHE) scheme, a general result of secure computation outsourcing has been shown viable in theory, where the computation is represented by an encrypted combinational Boolean circuit that allows to be evaluated with encrypted private inputs.
Fig. 2.Data Flow Diagram For Securely Outsourcing Linear Equations
In the data flow diagram, The customer has a largescale LE problem s to be solved. However, due to the lack of

TECHNIQUES

PseudoRandom Key Generator
PRKG is a program written for, and used in, probability and statistics applications when large quantities of random digits are needed. Most of these programs produce endless strings of singledigit numbers, usually in base 10, known as the decimal system. When large samples of pseudorandom numbers are taken, each of the 10 digits in the set
{0,1,2,3,4,5,6,7,8,9} occurs with equal frequency, even though they are not evenly distributed in the sequence. Many algorithm s have been developed in an attempt to produce truly random sequences of numbers, endless strings of digits in which it is theoretically impossible to predict the next digit in the sequence based on the digits up to a given point. But the very existence of the algorithm, no matter how sophisticated, means that the next digit can be predicted! This has given rise to the term pseudorandom for such machinegenerated strings of digits. They are equivalent to randomnumber sequences for most
applications, but they are not truly random according to the rigorous definition. The digits in the decimal expansions of irrational number s such as pi (the ratio of a circle's circumference to its diameter in a Euclidean plane), e (the natural logarithm base), or the square roots of numbers that are not perfect squares (such as 2 1/2 or 10 1/2 ) are believed by some mathematicians to be truly random. But computers can be programmed to expand such numbers to thousands, millions, billions, or trillions of decimal places; sequences can be selected that begin with digits far to the right of the decimal (radix) point, or that use every second, third, fourth, or n th digit. However, again, the existence of an algorithm to determine the digits in such numbers is used by some theoreticians to argue that even these singledigit number sequences are pseudorandom, and not truly random. The question then becomes, is the algorithm accurate (that is, random) to infinity, or not? — And because no one can answer such a question definitively because it is impossible to travel to infinity and find out, the matter becomes philosophical.

Iterative method
In many engineering computing and industrial applications, iterative method has been widely used in practice for solving largescale LE and sometimes is the mandatory choice over direct method due to its ease of implementation and relatively less computational power consumption, including the memory and storage IO requirement. We now review some basics on the general form of stationary iterative methods for solving LE problems. A system of linear equations is written as
Ax =b; (1)
Where x is the n * 1 vector of unknowns, A is an n * n (nonsingular) coefficient matrix, and b is an n *1 righthand side vector (so called constant terms). Most iterative methods involve passing from one iteration to the next by modifying a few components of some approximate vector solution at a time until the required accuracy is obtained. Without loss of generality, we focus on Jacobi iteration here and throughout the paper presentation for its simplicity. Though extensions to other stationary iterative methods can be possible, we dont study them in the current work. We begin with the decomposition: A =D+ R, where D is the diagonal component and R is the remaining matrix. Then, the (1) can be written as Ax = (D + R) x = b, and finally reorganized as: x =D_1. R. x + D_1. b. According to the Jacobi method, we can use an iterative technique to solve the left hand side of this expression for x (k+1), using previous value for x (k) on the right hand side. If we denote iteration matrix T = D_1. R and c = D_1. b, the above iterative equations can be represented as
X(k+1)=T.x(k)+c. (2)
It is the case for a large body of LE problems derived from many realworld applications.

Homomorphic Encryption
Our construction utilizes a semantically secure encryption scheme with additive homomorphic property. Given two Integers x1 and x2, we have Enc(x1 + x2) = Enc (x1)* Enc(x2), and also Enc(x1 _ x2) = Enc(x1) x2. In our
implementation we adopt the Paillier cryptosystem. For a vector x = (x1, x2. . . Xn) T Â£ (ZN) nN, CwIeCCuTs'e1E4 nCco(nxfe)retnocedPernoocteeedings
the coordinatewise encryption of x: Enc(x) = (Enc(x1), Enc(x2) . . . Enc (xn)) T. For some n * n matrix T, where each of the component T[i, j] in T is from ZN , we denote the componentwise encryption of T as Enc(T), and we have Enc(T)[i, j]= Enc(T[i, j]).


RESULTS
Fig.3 HOME PAGE
Fig.4 USER LOGIN PAGE
Fig.5 USER REGISTRATION
outsourcing. The design is built upon the assumption of two
no colluding servers and thus
NvCuIlCnCerTa' b1l4eCotnoferecnocleluPdroicnegedings
Fig.6 IMAGE SEARCH
Fig.7 FILE SEARCH

RELATED WORK
Recently, a general result of secure computation outsourcing has been shown viable in theory [18], which is based on Yaos garbled circuits and Gentrys fully homomorphic encryption (FHE) scheme. However, applying this general mechanism to our daily computations would be far from practical, due to the extremely high complexity of FHE operation and the pessimistic circuit sizes that can hardly be handled in practice. Instead of outsourcing general functions, in the security community, Atallahetal. Explore a list of customized solutions for securely outsourcing specific computations. In, they give the first investigation of secure outsourcing of numerical and scientific computation, including LE. Though a set of problem dependent disguising techniques are proposed, they explicitly allow private information leakage. Besides, the important case of result verification is not considered. In, Atallah and Bejanmin give a protocol design for secure matrix multiplication
attacks. Later on in, Atallah and Frikken give an improved protocol for secure outsourcing matrix multiplications based on secret sharing, which outperforms their previous work in terms of single server assumption and computation efficiency. But the drawback is that due to secret sharing technique, all scalar operations in original matrix multiplication are expanded to polynomials, introducing significant communication overhead. Considering the case of the result verification, the communication overhead must be further doubled, due to the introducing of additional precomputed random noise matrices. In short, these solutions, although elegant, are still not efficient enough for immediate practical uses on largescale problems, which we aim to address for the secure LE outsourcing in this paper. Wang et al. Give the first study of secure outsourcing of linear programming in cloud computing. Their solution is based on problem transformation, and has the advantage of bringing customer savings without introducing substantial overhead on cloud. However, those techniques involve cubictime computational burden matrixmatrix operations, which may not be handled by the weak customer in our assumption. Very recently, Blanton et al. explored secure outsourcing allpair distance calculations of largescale biometric data. Their focus is on result verification, which leverages certain structures of the distance computations and the framewor of adding fake items and random sampling.

CONCLUSIONS
In this paper, we investigated the problem of securely outsourcing largescale LE in cloud computing. Different from previous study, the computation outsourcing frame work is based on iterative methods. In particular, the design requires a onetime amortizable setup phase with O(n2) cost, and then each following iterative algorithm execution only incurs O(n) local computational cost with the benefits of easytoimplement and less memory requirement in practice. We also investigated the algebraic property of the matrix vector multiplication and developed an efficient and effective cheating detection scheme for robust result verification. Thorough security analysis and extensive experiments on the real cloud platform demonstrate the validity and practicality of the proposed mechanism.

REFERENCES

C. Wang, K. Ren, J. Wang, and K. Mahendra Raje Urs,Harnessing the Cloud for Securely Solving LargeScale Systems of Linear equations, Proc. 31st Intl Conf. Distributed Computing Systems (ICDCS), pp. 549558, 2011.

K. Forsman, W. Gropp, L. Kettunen, D. Levine, and J. Salonen,Solution of Dense Systems of Linear Equations Arising from Integralequation Formulations, IEEE Antennas and Propagation Magazine, vol. 37, no. 6, pp. 96100, Dec. 1995.

A. Edelman, Large Dense Numerical Linear Algebra in 1993: The Parallel Computing Influence, Intl J. High Performance Computing Applications, vol. 7, no. 2, pp. 113128, 1993.

V. Prakash, S. Kwon, and R. Mittra, An Efficient Solution of a Dense System of Linear Equations Arising in the MethodofMoments Formulation, Microwave and Optical Technology Letters,vol. 33, no. 3, pp. 196200, 2002.

B. Carpentieri, Sparse Preconditioners for Dense Linear Systems from Electromagnetic Applications, PhD dissertation, CERFACS, Toulouse, France, 2002.

R. Cramer and I. Damgard, Secure Distributed Linear Algebra in a Constant Number of Rounds, CRYPTO: Proc. Ann. Intl Cryptology Conf. Advances in Cryptology, 2001.

C. Wang, N. Cao, J. Li, K. Ren, and W. Lou, Secure Ranked Keyword Search over Encrypted Cloud Data, Proc. IEEE 30th Intl Conf. Distributed Computing Systems (ICDCS), pp. 253262, 2010.

S. Yu, C. Wang, K. Ren, and W. Lou, Achieving Secure, Scalable,and FineGrained Access Control in Cloud Computing, Proc. IEEE INFOCOM, pp. 534542, 2010.

C. Wang, K. Ren, S. Yu, and K. Mahendra Raje Urns, Achieving Usable and PrivacyAssured Similarity Search Over Outsourced Cloud Data, Proc. IEEE INFOCOM, pp. 451459, 2012.

T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, Introduction to Algorithms, second ed. MIT press, 2008.

D. Benjamin and M.J. Atallah, Private and CheatingFree Outsourcing of Algebraic Computations, Proc. Sixth Conf. Privacy, Security, and Trust (PST), pp. 240245, 2008.

M. Atallah and K. Frikken, Securely Outsourcing Linear Algebra Computations, Proc. Fifth ACM Symp. Information, Computer and Comm. Security (ASIACCS), pp. 4859, 2010.

G. Dahlquist and A. Bjorck, Numerical Methods. Dover Publications, 2003.

M. Bellare, J. Garay, and T. Rabin, Fast Batch Verification for Modular Exponentiation and Digital Signatures, Eurocrypt: Proc. Intl Conf. the Theory and Application of Cryptographic Techniques, pp. 236250, 1998.

J. Camenisch, S. Hohenberger, and M. Pedersen, Batch Verification of Short Signatures, EUROCRYPT: Proc. 26th Ann. Intl Conf. Advances in Cryptology, pp. 243263, 2007.
ISSN: 22780181
NCICCT' 14 Conference Proceedings