Paper Info
Title
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 security against timing attacks, as the execution of the secure algorithm on two different inputs is indistinguishable to the observer. We implement and benchmark our solution on the SHAREMIND secure computation system. Performance tests show that our privacy-preserving implementation 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.
Year
DOI
Venue
2014
10.1007/978-3-662-43826-8_8
WISTP
Keywords
Field
DocType
privacy, secure multi-party computation, genetic algorithms
Secure multi-party computation,Semantic security,Secret sharing,Computer security,Computer science,Timing attack,Theoretical computer science,Linear programming,Secure two-party computation,Genetic algorithm,Computation,Distributed computing
Conference
Volume
ISSN
Citations 
8501
0302-9743
0
PageRank 
References 
Authors
0.34
34
6
Name
Order
Citations
PageRank
Dan Bogdanov144219.11
Keita Emura231636.97
Roman Jagomägis300.34
Akira Kanaoka44511.62
Shin'ichiro Matsuo511616.05
Jan Willemson670448.01