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.
Type de document :
Communication dans un congrès
David Naccache; Damien Sauveron. 8th IFIP International Workshop on Information Security Theory and Practice (WISTP), Jun 2014, Heraklion, Crete, Greece. Springer, Lecture Notes in Computer Science, LNCS-8501, pp.108-123, 2014, Information Security Theory and Practice. Securing the Internet of Things. 〈10.1007/978-3-662-43826-8_8〉
Liste complète des métadonnées

Littérature citée [34 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01400929
Contributeur : Hal Ifip <>
Soumis le : mardi 22 novembre 2016 - 16:23:15
Dernière modification le : mercredi 23 novembre 2016 - 08:47:43
Document(s) archivé(s) le : mardi 21 mars 2017 - 12:00:19

Fichier

978-3-662-43826-8_8_Chapter.pd...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Dan Bogdanov, Keita Emura, Roman Jagomägis, Akira Kanaoka, Shin’ichiro Matsuo, et al.. A Secure Genetic Algorithm for the Subset Cover Problem and Its Application to Privacy Protection. David Naccache; Damien Sauveron. 8th IFIP International Workshop on Information Security Theory and Practice (WISTP), Jun 2014, Heraklion, Crete, Greece. Springer, Lecture Notes in Computer Science, LNCS-8501, pp.108-123, 2014, Information Security Theory and Practice. Securing the Internet of Things. 〈10.1007/978-3-662-43826-8_8〉. 〈hal-01400929〉

Partager

Métriques

Consultations de la notice

169

Téléchargements de fichiers

17