PRIVACY-PRESERVING COLLABORATIVE WEB SERVICES QOS PREDICTION VIA YAO'S GARBLED CIRCUITS AND HOMOMORPHIC ENCRYPTION
Keywords:
collaborative QoS prediction, privacy-preserving, Yao's garbled circuits, ho- momorphic encryption, recommendation systemAbstract
Collaborative Web services QoS prediction has become an important tool for the genera- tion of accurate personalized QoS which is a cornerstone of most QoS-based approaches for Web services selection and composition. While a number of achievements have been attained on the study of improving the accuracy of collaborative QoS prediction, little work has been done for protecting user privacy in this process. In this paper, we pro- pose a privacy-preserving collaborative QoS prediction framework which can protect the private data of users while retaining the ability of generating accurate QoS prediction. We combine Yao's garbled circuit and additively homomorphic encryption via additively secret sharing to address non-linear computations required in the process of QoS pre- diction. We implement the proposed framework based on FasterGC, an open source implementation of Yao's garbled circuit, and conduct extensive simulations to study its performance. Simulation results, together with theoretical security and complexity analysis, show that privacy-preserving QoS prediction can be eciently achieved in our framework.
Downloads
References
M. Alrifai, D. Skoutas, and T. Risse, "Selecting Skyline Services for QoS-Based Web Service
Composition," Proc. Int'l Conf. World Wide Web (WWW'10), pp. 11-20, 2010.
M. Alrifai and T. Risse, "Combining global optimization with local selection for ecient QoS-
aware service composition," Proc. Int'l Conf. World Wide Web (WWW'09), pp. 881-890, 2009.
D. Ardagna and B. Pernici, "Adaptive Service Composition in Flexible Processes," IEEE Trans.
Software Engineering, vol. 33, no. 6, pp. 369-384, June 2007.
D. Beaver, Secure multiparty protocols and zero-knowledge proof systems tolerating a faulty
minority. Journal of Cryptology, no 4, pp. 75-122. 1991.
M. Bellare, V. Hoang, P. Rogaway, "Foundations of garbled circuits," Proc. ACM conference on
Computer and communications security (CCS'12), pp. 784-796, 2012
A. Ben-David, N. Nisan, B. Pinkas, "Fariplaymp: a system for secure multi-party computation,"
Proc. ACM conference on Computer and communications security (CCS'08), pp. 257-266, 2008
X. Chen, Z. Zheng, X. Liu, Z. Huang, and H. Sun, "Personalized QoS-Aware Web Service Recom-
mendation and Visualization," IEEE Trans. Services Computing, vol. 6, no. 1, pp. 35-47, January-
March 2013.
T. Cormen, C. Leiserson, R. Rivest and C.Stein, "Introduction to algorithms," the MIT press
J. W. Crenshaw, "Integer square roots," Embedded Systems Programming, Feb. 1998
I. Damgard, M. Geisler, and M. Krgaard, "Ecient and secure comparison for on-line auctions,"
Proc. Australasian Conf. Information Security and Privacy (ACSIP'07), pp. 416-430, 2007
C. Dwork, "Di erential privacy," Proc. Automata, Languages and Programming (ICALP'06), 2006
C. Dwork and J. Lei, "Di erential privacy and robust statistics," Proc. ACM STOC Symposium
on Theory of Computing (STOC'09), 2009
Z. Erkin, T. Veugen, T. Toft, and R.L. Lagendijk, "Generating Private Recommendations E-
ciently Using Homomorphic Encryption and Data Packing," IEEE Trans. Information Forensics
and Security, vol. 7, no. 3, pp. 1053-1066, June 2012
S. Even, O. Goldreich, and A. Lempel, "A randomized protocol for signing contracts," Commun.
ACM, vol. 28, no.6, 1985
S. Garg, S. Versteeg, R. Buyya, "A framework for ranking of cloud computing services," Future
Generation Comp. Syst. (FGCS) vol. 29, no. 4, pp 1012-1023, 2013
O. Goldrich, Foundations of Cryptography: Volume 2, Basic Applications, Cambridge university
press, 2004
D. Guinard, V. Trifa, S. Karnouskos, P. Spiess, D. Savio, "Interacting with the SOA-Based Internet
of Things: Discovery, Query, Selection, and On-Demand Provisioning of Web Services," IEEE T.
Services Computing (TSC) vol. 3, no. 3, pp. 223-235, 2010
W. Henecka, A. Sadeghi, T. Schneider et al, "Tasty: tool for automating secure two-party computa-
tions," Proc. ACM conference on Computer and communications security (CCS'10), pp. 451-462,
Y. Huang, D. Evans, J. Katz et al, "Faster secure two-party computation using garbled circuits,"
Proc. USENIX Security Symposium, 2011
Y. Ishai, J. Kilian, K. Nissim, and E. Petrank, "Extending oblivious transfers eciently," Proc.
CRYPTO'03, 2003
Y. Jiang, J. Liu, M. Tang, and X. F. Liu. An e ective web service recommendation method
based on personalized collaborative ltering. Proc. IEEE Int'l Conf. Web Services (ICWS'11), pp.
-218, 2011
D. Knuth, The Art of Computer Programming, Vol. 2, Semuninumerical Algorithms, 3rd ed.
Addison-Wesley, 1997
V. Kolesnikov and T. Schneider, "Improved garbled circuit: Free XOR gates and applications,"
Proc. Automata, Languages and Programming (ICALP'08). Springer, 2008
V. Kolesnikov, A.-R. Sadeghi, and T. Schneider, "Improved garbled circuit building blocks
and applications to auctions and computing minima," Proc. Cryptology and Network Security
(CANS'09), Springer, 2009
B. Kreuter, A. Shelat, C. Shen, "Billion-gate secure computation with malicious adversaries,"
Proc. USENIX conference on Security symposium, 2012
Y. Lindell, B. Pinkas, N. Smart, "Implementing two-party computation eciently with security
agains malicious adversaries." Proc. International conference on Security and Cryptography for
Networks (SCN'08), pp. 2-20, 2008
Y. Lindell and B. Pinkas, "A proof of Yao's protocol for two-party computation," J. Cryptology,
D. Malkhi, N. Nisan and B. Pinkas, "Fairplay-secure two-party computation systems," Proc.
USENIX conference on Security symposium, pp. 287-302. 2004
F. McSherry and I. Mironov, "Di erentially private recommender systems: Building privacy into
the Net
ix prize contenders," Proc. ACM SIGKDD international conference on Knowledge dis-
covery in data mining (KDD'09), 2009
V. Nikolaenko, U. Weinsberg, S. Ioannidis, M. Joye, D. Boneh, and N. Taft. "Privacy-preserving
ridge regression on hundreds of millions of records," Proc. IEEE Symposium on Security and
Privacy (S&P'13), 2013
V. Nikolaenko, U. Weinsberg, S. Ioannidis, M. Joye, D. Boneh, and N. Taft. "Privacy-
Preserving matrix factorization," Proc. ACM conference on Computer and communications secu-
rity (CCS'13), 2013
P. Paillier, "Public-key cryptosystems based on composite degree residuosity classes," Proc. Ad-
vances in Cryptology (EUROCRYPT' 99), pp. 223-238, 1999
B. Pinkas, T. Schneider, N. Smart, "Secure two-party computation is practical," Proc. Interna-
tional Conference on the Theory and Application of Cryptology and Information Security (ASI-
ACRYPT'09), pp. 250-267, 2009
M. Rabin, "How to exchange secrets by oblivious trarnsfer," Technical Report TR-81, Aiken
Computation Laboratory, Harvard University, 1981
L. Shao, J. Zhang, Y. Wei, J. Zhao, B. Xie, and H. Mei, "Personalized qos prediction forweb
services via collaborative ltering," Proc. IEEE Int'l Conf. Web Services (ICWS'07), pp. 439-446,
Y. Shen, J. Zhu, X. Wang, L. Cai, X. Yang, B. Zhou, "Geographic Location-Based Network-Aware
QoS Prediction for Service Composition," Proc. IEEE Int'l Conf. Web Services (ICWS'13), pp.
-74, 2013
R. Shokri, P. Pedarsani, G. Theodorakopoulos, and J. Hubaux, "Preserving privacy in collab-
orative ltering through distributed aggregation of oine pro les," Proc. ACM conference on
Recommender systems (RecSys'09), pp. 157-164, 2009
M. Tang, Y. Jiang, J. Liu, and X.Liu, "Location-Aware Collaborative Filtering for QoS-Based
Service Recommendation", Proc. IEEE Int'l Conf. Web Services (ICWS'12), pp. 202-209, 2012
A.C.-C. Yao. How to generate and exchange secrets. Proc. IEEE Symposium on Foundations of
Computer Scirence (FOCS'86), pp. 162-167, 1986
L. Yao, Q.Z. Sheng, A. Segev, J. Yu, "Recommending Web Services via Combining Collaborative
Filtering with Content-Based Features," Proc. IEEE Int'l Conf. Web Services (ICWS'13), pp.
-49, 2013
Q. Yu, Z. Zheng, and H. Wang, "Trace Norm Regularized Matrix Factorization for Service Rec-
ommendation," Proc. IEEE Int'l Conf. Web Services (ICWS'13), pp. 34-41, 2013
T. Yu, Y. Zhang, and K.-J. Lin, "Ecient algorithms for Web Services Selection with End-to-End
QoS Constraints," ACM Trans. Web, vol. 1, no. 1, pp. 1-26, 2007
L. Zeng, B. Benatallah, A. H. H. Ngu, M. Dumas, J. Kalaggnanam, and H. Chang, "QoS-Aware
Middleware for Web Services Composition," IEEE Transactions on Software Engineering, vol. 30,
no. 5, pp. 311-327, 2004
Q. Zhang, C. Ding, and C.-H. Chi. Collaborative ltering based service ranking using invocation
histories. Proc. IEEE Int'l Conf. Web Services (ICWS'11), pp. 195-202, 2011
Y. Zhang, Z. Zheng, and M.R. Lyu, "Exploring Latent Features for Memory-Based QoS Prediction
in Cloud Computing," Proc. IEEE Symposium on Reliable Distributed Systems (SRDS 2011),
Madrid, Spain, Oct.4-7, 2011
Z. Zheng, H. Ma, M.R. Lyu, I. King, "WSRec: A Collaborative Filtering Based Web Service
Recommender System," Proc. IEEE Int'l Conf. Web Services (ICWS'09), pp. 437-444, 2009
Z. Zheng, X.Wu, Y. Zhang, M.R. Lyu, and J.Wang, 'QoS Ranking Prediction for Cloud Services,"
IEEE Trans. Parallel and Distributed Systems, vol. 24, no. 6, pp. 1213-1222, June 2013
Z. Zheng, H. Ma, M.R. Lyu, and I. King, "Collaborative Web Service QoS Prediction via Neigh-
borhood Integrated Matrix Factorization," IEEE Trans. Services Computing, vol. 6, no. 3, pp.
-299, July-September 2013
