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.
Chapter PDF
Similar content being viewed by others
References
BLIND SEER: Bloom index search of encrypted results, http://www.cs.columbia.edu/nsl/projects/blind_seer/
CryptDB, http://css.csail.mit.edu/cryptdb/
Balas, E.: An additive algorithm for solving linear programs with zero-one variables. Operations Research 13(4), 517–546 (1965)
Ben-David, A., Nisan, N., Pinkas, B.: FairplayMP: A system for secure multi-party computation. In: ACM CCS 2008, pp. 257–266 (2008)
Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In: STOC 1988, pp. 1–10 (1988)
Bogdanov, D.: Sharemind: programmable secure computations with practical applications. PhD thesis. University of Tartu (2013)
Bogdanov, D., Jagomägis, R., Laur, S.: A Universal Toolkit for Cryptographically Secure Privacy-Preserving Data Mining. In: Chau, M., Wang, G.A., Yue, W.T., Chen, H. (eds.) PAISI 2012. LNCS, vol. 7299, pp. 112–126. Springer, Heidelberg (2012)
Bogdanov, D., Laur, S., Willemson, J.: Sharemind: A Framework for Fast Privacy-Preserving Computations. In: Jajodia, S., Lopez, J. (eds.) ESORICS 2008. LNCS, vol. 5283, pp. 192–206. Springer, Heidelberg (2008)
Bogdanov, D., Niitsoo, M., Toft, T., Willemson, J.: High-performance secure multi-party computation for data mining applications. International Journal of Information Security 11(6), 403–418 (2012)
Bohli, J.-M., Li, W., Seedorf, J.: Assisting server for secure multi-party computation. In: Askoxylakis, I., Pöhls, H.C., Posegga, J. (eds.) WISTP 2012. LNCS, vol. 7322, pp. 144–159. Springer, Heidelberg (2012)
Burkhart, M., Strasser, M., Many, D., Dimitropoulos, X.A.: SEPIA: Privacy-preserving aggregation of multi-domain network events and statistics. In: USENIX 2010, pp. 223–240 (2010)
Chandran, N., Goyal, V., Ostrovsky, R., Sahai, A.: Covert multi-party computation. In: FOCS 2007, pp. 238–248 (2007)
Choi, S.G., Hwang, K.-W., Katz, J., Malkin, T., Rubenstein, D.: Secure multi-party computation of boolean circuits with applications to privacy in online marketplaces. In: Dunkelman, O. (ed.) CT-RSA 2012. LNCS, vol. 7178, pp. 416–432. Springer, Heidelberg (2012)
Elmenreich, W., Ibounig, T., Fehérvári, I.: Robustness versus performance in sorting and tournament algorithms. Acta Polytechnica Hungarica 6(5), 7–18 (2009)
Gentry, C.: Fully homomorphic encryption using ideal lattices. In: STOC 2009, pp. 169–178 (2009)
Gentry, C., Halevi, S.: Implementing Gentry’s Fully-Homomorphic Encryption Scheme. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 129–148. Springer, Heidelberg (2011)
Gentry, C., Halevi, S., Smart, N.P.: Homomorphic evaluation of the AES circuit. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 850–867. Springer, Heidelberg (2012)
Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or a completeness theorem for protocols with honest majority. In: STOC 1987, pp. 218–229 (1987)
Goyal, V., Jain, A.: On the round complexity of covert computation. In: STOC 2010, pp. 191–200 (2010)
Goyal, V., Mohassel, P., Smith, A.: Efficient two party and multi party computation against covert adversaries. In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 289–306. Springer, Heidelberg (2008)
Henecka, W., Kögl, S., Sadeghi, A.-R., Schneider, T., Wehrenberg, I.: TASTY: Tool for automating secure two-party computations. In: ACM CCS 2010, pp. 451–462 (2010)
Hirt, M., Lucas, C., Maurer, U., Raub, D.: Graceful degradation in multi-party computation (extended abstract). In: Fehr, S. (ed.) ICITS 2011. LNCS, vol. 6673, pp. 163–180. Springer, Heidelberg (2011)
Hirt, M., Lucas, C., Maurer, U., Raub, D.: Passive corruption in statistical multi-party computation - (extended abstract). In: Smith, A. (ed.) ICITS 2012. LNCS, vol. 7412, pp. 129–146. Springer, Heidelberg (2012)
Kamm, L., Bogdanov, D., Laur, S., Vilo, J.: A new way to protect privacy in large-scale genome-wide association studies. Bioinformatics 29(7), 886–893 (2013)
Laur, S., Willemson, J., Zhang, B.: Round-Efficient Oblivious Database Manipulation. In: Lai, X., Zhou, J., Li, H. (eds.) ISC 2011. LNCS, vol. 7001, pp. 262–277. Springer, Heidelberg (2011)
Lindell, Y., Pinkas, B.: Privacy preserving data mining. J. Cryptology 15(3), 177–206 (2002)
Malka, L.: VMCrypt: Modular software architecture for scalable secure computation. In: ACM CCS 2011, pp. 715–724 (2011)
Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999)
Pinkas, B., Schneider, T., Smart, N.P., Williams, S.C.: Secure two-party computation is practical. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 250–267. Springer, Heidelberg (2009)
Sakuma, J., Kobayashi, S.: A genetic algorithm for privacy preserving combinatorial optimization. In: GECCO 2007, pp. 1372–1379 (2007)
Shamir, A.: How to share a secret. Communications of the ACM 22, 612–613 (1979)
Takahashi, T., Emura, K., Kanaoka, A., Matsuo, S., Minowa, T.: Risk visualization and alerting system: Architecture and proof-of-concept implementation. In: SESP 2013, pp. 3–10. ACM (2013)
Teruya, T., Sakuma, J.: Round-efficient private stable matching from additive homomorphic encryption. In: ISC 2013 (to appear, 2014)
Yao, A.C.-C.: Protocols for secure computations (extended abstract). In: FOCS 1982, pp. 160–164 (1982)
Ye, Q., Wang, H., Pieprzyk, J., Zhang, X.-M.: Efficient disjointness tests for private datasets. In: Mu, Y., Susilo, W., Seberry, J. (eds.) ACISP 2008. LNCS, vol. 5107, pp. 155–169. Springer, Heidelberg (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 IFIP International Federation for Information Processing
About this paper
Cite this paper
Bogdanov, D., Emura, K., Jagomägis, R., Kanaoka, A., Matsuo, S., Willemson, J. (2014). A Secure Genetic Algorithm for the Subset Cover Problem and Its Application to Privacy Protection. In: Naccache, D., Sauveron, D. (eds) Information Security Theory and Practice. Securing the Internet of Things. WISTP 2014. Lecture Notes in Computer Science, vol 8501. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-43826-8_8
Download citation
DOI: https://doi.org/10.1007/978-3-662-43826-8_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-43825-1
Online ISBN: 978-3-662-43826-8
eBook Packages: Computer ScienceComputer Science (R0)