A Secure Genetic Algorithm for the Subset Cover Problem and its Application to Privacy Protection

Abstract

We propose a method for applying genetic algorithms to confidential data. Genetic algorithms are a well-known tool for finding approximate solutions to various optimization and searching problems. More specifically, we present a secure solution for solving the subset cover problem which is formulated by a binary integer linear programming (BIP) problem (i.e. a linear programming problem, where the solution is expected to be a 0-1 vector). Our solution is based on secure multi- party computation. We give a privacy definition inspired from semantic security definitions and show how a secure computation system based on secret sharing satisfies this definition. Our solution also achieves se- curity against timing attacks, as the execution of the secure algorithm on two different inputs is indistinguishable to the observer. We imple- ment and benchmark our solution on the Sharemind secure computation system. Performance tests show that our privacy-preserving implemen- tation achieves a 99.32% precision within 6.5 seconds on a BIP problem of moderate size. As an application of our algorithm, we consider the problem of securely outsourcing risk assessment of an end user computer environment