With the rapid increase in computing, storage and networking resources, data is not only collected and stored but also analyzed. This creates a serious privacy problem which often inhibits the use of this data. This project explores the problem of performing optimization analysis over distributed data without conflicting with privacy and security concerns. This is especially challenging due to the complexity and iterative nature of the solutions. An inherent aim is to also solve some of the fundamental problems underlying privacy-preserving analysis / secure computation and make it more accessible and applicable. Some of the innovative expected results include: (1) novel formulations of security definitions that are more relaxed than the traditional definitions yet still model the real security concerns; (2) new algorithms, computational complexity results, and tools for specific widely used optimization problems; (3) a more generalized view of privacy; (4) game theoretic interpretations and modeling of the multi-party computation; and (5) result analysis ? a quantification of privacy loss through results. The project will have tremendous broader impact via fundamental research and integrative education. Direct outcomes of the research can significantly help in widening co-operation between organizations and minimize loss through data isolation. This would result in cost savings and new income realization potentially worth billions of dollars through joint resource usage. Translation of the research to real use has the potential to revolutionize the mediator/consolidator industry. The integrative education activities will foster actual use of the technology and open up its acceptance into the real world
The rapid increase in computing, storage and networking resources has lead to ubiquitous collection and storage of data. This creates a burgeoning privacy and security problem, which often inhibits the use of collected data, resulting in significant loss through data isolation. In this project, we have addressed the problem of performing optimization analysis over distributed data without conflicting with privacy and security concerns. Optimization is a fundamental problem found in almost every aspect of real life. With resource constraints, optimization is necessary to ensure the best possible usage of scarce resources. Research in optimization methods has generated many successes; the ubiquitous collection of data opens even greater opportunities. Much of this data is constrained by privacy and security concerns, preventing the sharing and access to data needed to apply optimization techniques. Through the span of the project we have created several privacy-preserving solutions with varying tradeoffs of privacy and efficiency to perform collaborative optimization over distributed data. We have developed scalable solutions for privacy-preserving linear programming, which is the largest subclass of optimization problems. Linear Programming models are applicable to a wide variety of problems in many industries including transportation, commodities, airlines, communication, etc. There are also a variety of military applications and other economic applications. We have also developed meta-heuristic solutions such as privacy-preserving tabu search for more complex optimization problems such as graph coloring which can be used for many applications such as distributed scheduling, distributed network resource allocation, etc. Solutions have also been developed for several related problems such as privacy-preserving data analysis and data mining, data anonymization, and role engineering. As such, the solutions developed are broadly applicable to a variety of applications and areas. From the perspective of intellectual merit, our research has advanced the state of the art in methods and techniques for privacy-preserving distributed optimization, and improved the scientific understanding of secure computation. We have addressed several fundamental challenges underlying privacy-preserving collaborative computation such as developing utility metrics, modeling exterior knowledge, and using game theoretic approaches to improve the efficiency/privacy tradeoff. The results of our project also have significant broader impact by widening co-operation between organizations and preventing loss through data isolation. The use of such techniques can result in cost savings and new income realization potentially worth billions of dollars through joint resource usage. Several students have been trained through the project, and education and dissemination activities have been carried out at both the undergraduate and graduate level.
