- Author:
- Wenliang Du,
- Major Professors:
- Mikhail J. Atallah,
- Eugene H. Spafford
Alice has a private input x (of any data type, such as a number, a matrix or a data set). Bob has another private input y . Alice and Bob want to cooperatively conduct a specific computation on x and y without disclosing to the other person any information about her or his private input except for what could be derived from the results. This problem is a Secure Two-party Computation (STC) problem, which has been extensively studied in the past. Several generic solutions have been proposed to solve the general STC problem; however the generic solutions are often too inefficient to be practical. Therefore, in this dissertation, we study several specific STC problems with the goal of finding more efficient solutions than the generic ones.
We introduce a number of specific STC problems in the domains of scientific computation, statistical analysis, computational geometry and database query. Most of the problems have not been studied before in the literature.
To solve these problems: (1) We investigate how data perturbation could be used to hide data. Data perturbation hides a datum by adding to it a random number. We show that this technique is effective in preserving privacy. (2) We explore how domain specific knowledge can improve the efficiency of the solutions that we develop over the generic solutions that do not consider domain specific knowledge. We show that such knowledge is important in both hiding data and achieving higher efficiency. (3) We also introduce a number of common building blocks that are useful in solving secure two-party computation problems in various computation domains.
Cited By
- Wang Y and Li Y (2015). An efficient and tunable matrix-disguising method toward privacy-preserving computation, Security and Communication Networks, 8:17, (3099-3110), Online publication date: 25-Nov-2015.
- Qin J, Duan H, Zhao H and Hu J (2014). A new Lagrange solution to the privacy-preserving general geometric intersection problem, Journal of Network and Computer Applications, 46:C, (94-99), Online publication date: 1-Nov-2014.
- Hong Y, Vaidya J, Lu H and Wang L Collaboratively Solving the Traveling Salesman Problem with Limited Disclosure Proceedings of the 28th Annual IFIP WG 11.3 Working Conference on Data and Applications Security and Privacy XXVIII - Volume 8566, (179-194)
- Laud P and Pankova A On the (Im)possibility of privately outsourcing linear programming Proceedings of the 2013 ACM workshop on Cloud computing security workshop, (55-64)
- Pan X and Meng X (2013). Preserving location privacy without exact locations in mobile services, Frontiers of Computer Science: Selected Publications from Chinese Universities, 7:3, (317-340), Online publication date: 1-Jun-2013.
- Hong Y, Vaidya J and Lu H Efficient distributed linear programming with limited disclosure Proceedings of the 25th annual IFIP WG 11.3 conference on Data and applications security and privacy, (170-185)
- Mohammed N, Fung B, Hung P and Lee C (2010). Centralized and Distributed Anonymization for High-Dimensional Healthcare Data, ACM Transactions on Knowledge Discovery from Data (TKDD), 4:4, (1-33), Online publication date: 1-Oct-2010.
- Bednarz A, Bean N and Roughan M Hiccups on the road to privacy-preserving linear programming Proceedings of the 8th ACM workshop on Privacy in the electronic society, (117-120)
- Wang I, Shen C, Zhan J, Hsu T, Liau C and Wang D (2009). Toward empirical aspects of secure scalar product, IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 39:4, (440-447), Online publication date: 1-Jul-2009.
- Vaidya J Privacy-preserving linear programming Proceedings of the 2009 ACM symposium on Applied Computing, (2002-2007)
- Yao D, Frikken K, Atallah M and Tamassia R (2008). Private Information, ACM Transactions on Information and System Security (TISSEC), 12:1, (1-27), Online publication date: 1-Oct-2008.
- Machanavajjhala A, Kifer D, Gehrke J and Venkitasubramaniam M (2007). L-diversity, ACM Transactions on Knowledge Discovery from Data, 1:1, (3-es), Online publication date: 1-Mar-2007.
- Kiltz E, Leander G and Malone-Lee J Secure computation of the mean and related statistics Proceedings of the Second international conference on Theory of Cryptography, (283-302)
- Sehgal S and Pal A Finding pareto-optimal set of distributed vectors with minimum disclosure Proceedings of the 6th international conference on Distributed Computing, (144-149)
- Luo W and Li X A study of secure multi-party elementary function computation protocols Proceedings of the 3rd international conference on Information security, (5-12)
- Atallah M, Bykova M, Li J, Frikken K and Topkara M Private collaborative forecasting and benchmarking Proceedings of the 2004 ACM workshop on Privacy in the electronic society, (103-114)
- Frikken K and Atallah M Privacy preserving route planning Proceedings of the 2004 ACM workshop on Privacy in the electronic society, (8-15)
- Du W and Zhan Z Building decision tree classifier on private data Proceedings of the IEEE international conference on Privacy, security and data mining - Volume 14, (1-8)
- Du W and Zhan Z A practical approach to solve Secure Multi-party Computation problems Proceedings of the 2002 workshop on New security paradigms, (127-135)
Recommendations
Efficient Fair Secure Two-Party Computation
APSCC '12: Proceedings of the 2012 IEEE Asia-Pacific Services Computing Conference)Yao first introduced a constant-round protocol for secure two-party computation (2PC) withstanding semi-honest adversaries by using a tool called """"garbled circuit"""". Later, many protocols based on garbled circuit approach have been presented, most ...
Complete fairness in secure two-party computation
STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computingIn the setting of secure two-party computation, two mutually distrusting parties wish to compute some function of their inputs while preserving, to the extent possible, various security properties such as privacy, correctness, and more. One desirable ...
An efficient fair UC-secure protocol for two-party computation
With the development of modern Internet and mobile networks, there is an increasing need for collaborative privacy-preserving applications. Secure multi-party computation SMPC gives a general solution to these applications and has become a hot topic. ...