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

详细信息    查看全文

• 作者：Dan Bogdanov (17)
  Keita Emura (18)
  Roman Jagom?gis (17)
  Akira Kanaoka (19)
  Shin’ichiro Matsuo (18)
  Jan Willemson (19)
  
• 关键词：privacy ; secure multi ; party computation ; genetic algorithms
• 刊名：Lecture Notes in Computer Science
• 出版年：2014
• 出版时间：2014
• 年：2014
• 卷：8501
• 期：1
• 页码：108-123
• 参考文献：1. BLIND SEER: Bloom index search of encrypted results, http://www.cs.columbia.edu/nsl/projects/blind_seer/
  2. CryptDB, http://css.csail.mit.edu/cryptdb/
  3. Balas, E.: An additive algorithm for solving linear programs with zero-one variables. Operations Research?13(4), 517-46 (1965) CrossRef
  4. Ben-David, A., Nisan, N., Pinkas, B.: FairplayMP: A system for secure multi-party computation. In: ACM CCS 2008, pp. 257-66 (2008)
  5. Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In: STOC 1988, pp. 1-0 (1988)
  6. Bogdanov, D.: Sharemind: programmable secure computations with practical applications. PhD thesis. University of Tartu (2013)
  7. 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-26. Springer, Heidelberg (2012) CrossRef
  8. 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-06. Springer, Heidelberg (2008) CrossRef
  9. 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-18 (2012) CrossRef
  10. 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-59. Springer, Heidelberg (2012) CrossRef
  11. 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-40 (2010)
  12. Chandran, N., Goyal, V., Ostrovsky, R., Sahai, A.: Covert multi-party computation. In: FOCS 2007, pp. 238-48 (2007)
  13. 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-32. Springer, Heidelberg (2012) CrossRef
  14. Elmenreich, W., Ibounig, T., Fehérvári, I.: Robustness versus performance in sorting and tournament algorithms. Acta Polytechnica Hungarica?6(5), 7-8 (2009)
  15. Gentry, C.: Fully homomorphic encryption using ideal lattices. In: STOC 2009, pp. 169-78 (2009)
  16. Gentry, C., Halevi, S.: Implementing Gentry’s Fully-Homomorphic Encryption Scheme. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol.?6632, pp. 129-48. Springer, Heidelberg (2011) CrossRef
  17. 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-67. Springer, Heidelberg (2012) CrossRef
  18. 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-29 (1987)
  19. Goyal, V., Jain, A.: On the round complexity of covert computation. In: STOC 2010, pp. 191-00 (2010)
  20. 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-06. Springer, Heidelberg (2008) CrossRef
  21. 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-62 (2010)
  22. 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-80. Springer, Heidelberg (2011) CrossRef
  23. 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-46. Springer, Heidelberg (2012) CrossRef
  24. 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-93 (2013) CrossRef
  25. 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-77. Springer, Heidelberg (2011) CrossRef
  26. Lindell, Y., Pinkas, B.: Privacy preserving data mining. J. Cryptology?15(3), 177-06 (2002) CrossRef
  27. Malka, L.: VMCrypt: Modular software architecture for scalable secure computation. In: ACM CCS 2011, pp. 715-24 (2011)
  28. Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol.?1592, pp. 223-38. Springer, Heidelberg (1999) CrossRef
  29. 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-67. Springer, Heidelberg (2009) CrossRef
  30. Sakuma, J., Kobayashi, S.: A genetic algorithm for privacy preserving combinatorial optimization. In: GECCO 2007, pp. 1372-379 (2007)
  31. Shamir, A.: How to share a secret. Communications of the ACM?22, 612-13 (1979) CrossRef
  32. 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-0. ACM (2013)
  33. Teruya, T., Sakuma, J.: Round-efficient private stable matching from additive homomorphic encryption. In: ISC 2013 (to appear, 2014)
  34. Yao, A.C.-C.: Protocols for secure computations (extended abstract). In: FOCS 1982, pp. 160-64 (1982)
  35. 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-69. Springer, Heidelberg (2008) CrossRef
  
• 作者单位：Dan Bogdanov (17)
  Keita Emura (18)
  Roman Jagom?gis (17)
  Akira Kanaoka (19)
  Shin’ichiro Matsuo (18)
  Jan Willemson (19)
  
  17. Cybernetica, M?ealuse 2, 12618, Tallinn, Estonia
  18. National Institute of Information and Communications Technology, 4-2-1 Nukui-Kitamachi, Koganei, Tokyo, 184-8795, Japan
  19. Toho University, 2-2-1 Miyama, Funabashi, Chiba
  
• ISSN：1611-3349

文摘

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.