Secure Product Bvs Indore

A Protocol for Computing Product while Preserving Privacy of Inputs Rashid Sheikh1, Manoj Joshi1, Durgesh Kumar Mishra2 1

MRSC, Indore, M.P., INDIA Acropolis Institute of Technology and Research, Indore, M.P., INDIA [email protected], [email protected], [email protected] +919826024087, +919826092030, +919826047547 2

Abstract - In this paper, we propose a protocol which allows individual parties to compute the product of their data inputs without disclosing individual data inputs to other parties. Our work is motivated by k-secure sum protocol and extended k-secure sum protocol. The proposed protocol is based on factoring the individual data blocks into a fixed number of factors. One of the parties will be unanimously selected as protocol initiator. This party will start the protocol and at the end announce the result. Our protocol provides increased computation and communication complexities to malicious parties making the hacking activity more difficult. Keywords - Computation complexity, privacy, Secure Multiparty Computation (SMC) 1. Introduction Many practical real life applications require the confidentiality of individual data inputs during evaluation of some function of those inputs. Each input supplying party wants to keep its data secret. On the other hand knowing the value of common function is in their mutual interest. This branch of computer science is called Secure Multiparty Computation (SMC). This has become more relevant field owing to tremendous amount of online transactions taking place over the internet. Initially the field started with two-party computation and then extended to multiparty computation [1, 4, 5]. The best and the simplest example of SMC is the secure sum protocol which allows parties to compute the sum of their individual data without revealing any data to other parties [13]. Motivated by this protocol in this paper we propose a simple protocol to compute the product individual data inputs keeping the data secret. In our protocol the parties are arranged in a ring. One of the parties is selected as a protocol initiator which starts the computation. Each party in our protocol factors the data block into a fixed number of factors .The protocol initiator passes first factor of its data block to next party. The party receiving this factor multiplies the received factor with its first factor and passes the partial product to the next party in the ring. The procedure is repeated until last factor of the data block arrives. Finally the product is announced by the protocol initiator. Since each party sends only partial product of factors, no party is able to know the individual data block of any other party. Thus the privacy of individual data is maintained. If each party follows the protocol honestly, each will get correct product. We have analyzed the case when any two adjacent parties maliciously cooperate to know the data of a middle party. In previous protocols adjacent parties need to perform only one computation to know the secret data of middle party. In our protocol, since only factors can be attacked in one computation, computational complexity is as large as the number of factors. Analysis shows that the probability of party becoming victim decreases as we increase the number of factors. The probability of a party becoming victim also decreases as we increase the number of parties. 2. Literature Survey This concept was first introduced by A.C.Yao[1] in 1982 where he defined and provided solution to “Two millionaires Problem”. In this problem two millionaires want to know who is richer without disclosing their individual wealth to each other. After that many researcher like Goldreich, Lindell, Wigderson et al. extended the idea to more practical problems[2,4,5,10]. Well researched problems include privacy-preserving data mining[2,7], privacy-preserving statistical analysis [12], privacy-preserving cooperative scientific computation [8] , privacy-preserving geometric analysis [11], privacy-preserving database query, privacypreserving Private Information Retrieval [ 6, 9] etc. Depending on these general problems many specific real life problems are discovered and studied. Among these are privacy-preserving social network analysis, privacy-preserving criminal investigation, privacy-preserving load balancing in a distributed system, and

many more to mention. Recently Mishra and Chandwani introduced the concept of anonymity with SMC [14].An excellent review of SMC research and a new framework for problem discovery is given in [3]. The solution to SMC problem focuses two needs; Privacy of individual data and the accuracy of the result. The best example of SMC is the Secure Sum Protocol as given by Clifton et al. in 2002. They used a random number which is selected by a party which starts the protocol for computing the sum of individual data. This party is called the protocol initiator. This party starts the protocol by adding the random number to its own data block. It passes the partial sum to the next party in the ring. The next party skimpily adds its data block to the received partial sum and then passes the sum to the next party. This process is repeated until all the data blocks are added and the sum is received by the protocol initiator. Since the protocol initiator only knows the random number, it will subtract the random number from the received sum and announce the result. The protocol works very well when all the parties are honest. But when two adjacent parties maliciously cooperate to get the data of a middle party the can do it with one computation. Thus the computational complexity to hackers is very low. The probability of party becoming victim is higher. Recently we proposed more secure protocols for computing the sum; k-secure sum protocol and extended k-secure sum protocol [15]. In k-secure sum protocol we break each party’s data into k segments without using any random number. We proved that this protocol is k times secure than the secure sum protocol of Clifton et al. We further extended this protocol by using a random number with each data segment. The security of the algorithm was further improved. This protocol was called extended k-Secure Sum Protocol. 3. Formal Description of k-Secure Product Protocol 1. Assume P0 , P1, P2 ,…, Pn-1 are n parties involved in cooperative k-secure sum computation. 2. Assume k is an integer which represents number of factors in each data block. 3. Let D0 , D1, D2,…, Dn-1 are data blocks belonging to P0 , P1, P2 ,…, Pn-1 respectively. 4. Break Di into factors Di0 , Di1, ,…, Di(k-1) such that Di = ∏ Di,j where j = 0 to k-1. 5. Assume rc =k and Sij = 0, /* Sij is partial product */ 6. while rc!=0 begin for j = 0 to k-1 for i = 0 to n-1 Pi sends Sij = Di,j * Sij to P(i+1)mod n rc = rc – 1 end 7. P0 announces Si,j 8. End of algorithm 4. Analysis When Two Neighbor Parties Turn Malicious When two parties adjacent to a third party become malicious the middle party will become victim because these parties communicate with each other to know factor value of the middle party. In Clifton’s Secure Sum protocol [13] corrupt parties need to perform one computation to know private data of middle party. In our proposed protocol these parties perform one computation to know one factor only. To know all factors of a data block of a party the malicious parties will have to perform k such computations. Thus, the computation complexity to break one party’s data is k times as compared to secure sum algorithm [13]. This k is number of factors in which each data block is broken. That is the reason why our protocol is named as k-Secure Product Protocol. The probabilistic analysis shows that as number of parties increases the probability of a node becoming victim decreases. Let n be number of parties. In Secure Sum Protocol [13] the probability of one party becoming victim by any two neighbors is given by: P1 = n / nC2 P1=2/n-1

where, n ≥ 3

In our k-Secure Product Protocol using k factors of a data block the probability is given by-

(1)

P1k = (2/n-1)k (2) Note that since 2/n-1 is less than 1, raising the power k causes probability to decrease. Thus, the probability analysis of the k-Secure Product Protocol indicates that our protocol is more secure than Secure Sum Protocol given by Clifton et al. 5. Conclusion and Future Scope Our k-Secure Product Algorithm is used to get the product of private data belonging to all parties providing lower probability of data leakage. The probability analysis shows that this is an appreciable improvement over previous protocol. It provides excellent security when number of segments is sufficiently large. If all parties work honestly the protocol provide correct result maintaining the privacy of individual data. The k-Secure Product Protocol improves complexity k times as compared to previous protocols. Further efforts can be made to make the protocol more secure. One way is that each party keeps one factor with it and k-1 factors are distributed to other parties. After this distribution, the factors kept by a party will not belong to the data block of a single party. The k-Secure Product Algorithm may now be applied. References [1] A.C.Yao, “protocol for secure computations,” in proceedings of the 23rd annual IEEE symposium on foundation of computer science, pages 160-164, Nov.1982. [2]. Y. Lindell, “secure multiparty computation for privacy preserving data mining,” IBM, T.J. Watson Research Center, USA, http: // u.cs.biu.ac.il/-lindell/ research-statements / mpc- ppdm.htm/2001. [3] W. Du and M.J. Atallah, “Secure Multiparty Computation Problems and Their Applications: A Review and Open Problems,” In proceedings of new security paradigm workshop, Cloudcroft, New Maxico, USA, page 11-20, Sep. 11-13 2001. [4] O. Goldreich, S. Micali and A. Wigderson, “How to play any mental game.” In proceedings of the 19th annual ACM Symposium on Theory of Computation, pages 218-229, May 1987. [5] O. Goldreich, “Multiparty Computation (Working Draft),” Available from http: //www.wisdom.weizmann.ac.il/ home / oded / public html / foc.html, 1998. [6] B.Chor and N.Gilbao. “Computationally Private Information Retrieval (Extended Abstract),” In proceedings of 29th annual ACM Symposium on Theory of Computing, El Paso, TX USA, May 4-6 1997. [7] R. Agrawal and R. Srikant. “Privacy-Preserving Data Mining,” In proceedings of the 2000 ACM SIGMOD on management of data, Dallas, TX USA, pages 439-450, May 15-18 2000. [8] W. Du and M.J. Atallah. “Privacy-Preserving Cooperative Scientific Computations,” In 14th IEEE Computer Security Foundations Workshop, Nova Scotia, Canada, pages 273-282, Jun. 11-13 2001. [9] W. Du and M.J. Atallah, “Protocols for Secure Remote Database Access with Approximate Matching,” In 7th ACM Conference on Computer and Communications Security (ACMCCS 2000), The first workshop on security and privacy in e-commerce, Athens, Greece, Nov. 1-4 2000. [10] J. Biskup and U. Flegel. “On Pseudonymization Of Audit Data For Intrusion Detection,” In Workshop on Design Issues in Anonymity and observability, pages 161-180, Jul. 2000. [11] M. J. Atallah and W. Du. “Secure Multiparty Computational Geometry,” In proceedings of Seventh International Workshop on Algorithms and Data Structures(WADS2001). Providence, Rhode Island, USA, Pages 165-179, Aug. 8-10 2001. [12] W. Du and M.J.Atallah, “Privacy-Preserving Statistical Analysis,” In proceedings of the 17th Annual Computer Security Applications Conference, New Orleans, Louisiana, USA, pages 102-110, Dec. 10-14 2001. [13] C. Clifton, M. Kantarcioglu, J.Vaidya, X. Lin, and M. Y. Zhu, “Tools for Privacy-Preserving Distributed Data Mining,”J. SIGKDD Explorations, Newsletter,vol.4, no.2, ACM Press, pages 28-34, Dec. 2002. [14] D. K. Mishra, M. Chandwani, “Extended Protocol for Secure Multiparty Computation using Ambiguous Identity”. WSEAS Transaction on Computer Research, Vol 2, issue 2, Feb 2007. [15] R. Sheikh, B. Kumar and D. K. Mishra, “Privacy Preserving k-Secure Sum Protocol,” Accepted in International Journal of Computer Science and Information Security, Nov 2009.