Abstract
This work treats the problem of error-resilient DNA searching via oblivious evaluation of finite automata, where a client has a DNA sequence, and a service provider has a pattern that corresponds to a genetic test. Error-resilient searching is achieved by representing the pattern as a finite automaton and evaluating it on the DNA sequence, where privacy of both the pattern and the DNA sequence must be preserved. Interactive solutions to this problem already exist, but can be a burden on the participants. Thus, we propose techniques for secure outsourcing of finite automata evaluation to computational servers, which do not learn any information. Our techniques are applicable to any type of finite automata, but the optimizations are tailored to DNA searching.
Chapter PDF
Similar content being viewed by others
Keywords
- Finite Automaton
- Homomorphic Encryption
- Oblivious Transfer
- Longe Common Subsequence
- Modular Exponentiation
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Atallah, M., Kerschbaum, F., Du, W.: Secure and private sequence comparisons. In: WPES, pp. 39–44 (2003)
Jha, S., Kruger, L., Shmatikov, V.: Towards practical privacy for genomic computation. In: IEEE Symposium on Security and Privacy, pp. 216–230 (2008)
Troncoso-Pastoriza, J., Katzenbeisser, S., Celik, M.: Privacy preserving error resilient DNA searching through oblivious automata. In: ACM CCS, pp. 519–528 (2007)
Frikken, K.: Practical private DNA string searching and matching through efficient oblivious automata evaluation. In: DBSec, pp. 81–94 (2009)
Bruekers, F., Katzenbeisser, S., Kursawe, K., Tuyls, P.: Privacy-preserving matching of DNA profiles. ePrint Cryptology Archive Report 2008/203 (2008)
Wang, R., Wang, X., Li, Z., Tang, H., Reiter, M., Dong, Z.: Privacy-preserving genomic computation through program specialization. In: ACM CCS, pp. 338–347 (2009)
Atallah, M., Li, J.: Secure outsourcing of sequence comparisons. In: PET, pp. 63–78 (2004)
Atallah, M., Li, J.: Secure outsourcing of sequence comparisons. International Journal of Information Security 4(4), 277–287 (2005)
Genetic Testing for Health, Disease & Ancestry; DNA Test – 23andMe, http://www.23andme.com
Blanton, M., Aliasgari, M.: Secure outsourcing of DNA searching via finite automata. Technical Report 2010–03, University of Notre Dame (2010)
Szajda, D., Pohl, M., Owen, J., Lawson, B.: Toward a practical data privacy scheme for a distributed implementation of the Smith-Waterman genome sequence comparison algorithm. In: NDSS (2006)
Kantarcioglu, M., Jiang, W., Liu, Y., Malin, B.: A cryptographic approach to securely share and query genomic sequences. IEEE Transactions on Information Technology in Biomedicine 12(5), 606–617 (2008)
Franklin, M., Gondree, M., Mohassel, P.: Communication-efficient private protocols for longest common subsequence. In: RSA, pp. 265–278 (2009)
Gondree, M., Mohassel, P.: Longest common subsequence as private search. In: WPES, pp. 81–90 (2009)
Naor, M., Pinkas, B.: Efficient oblivious transfer protocols. In: SODA, pp. 448–457 (2001)
Lipmaa, H.: An oblivious transfer protocol with log-squared communication. In: Zhou, J., López, J., Deng, R.H., Bao, F. (eds.) ISC 2005. LNCS, vol. 3650, pp. 314–328. Springer, Heidelberg (2005)
Gentry, C., Ramzan, Z.: Single-database private information retrieval with constant communication rate. In: ICALP, pp. 803–815 (2005)
Naor, M., Pinkas, B.: Oblivious transfer and polynomial evaluation. In: STOC (1999)
Crescenzo, G., Malkin, T., Ostrovsky, R.: Single database private information retrieval implies oblivious transfer. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 122–138. Springer, Heidelberg (2000)
Cachin, C., Micali, S., Stadler, M.: Computationally private information retrieval with polylogarithmic communication. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 402–414. Springer, Heidelberg (1999)
Kushilevitz, E., Ostrovsky, R.: Replication is not needed: Single database, computationally-private information retrieval. In: IEEE FOCS, pp. 364–373 (1997)
Melchor, C.A., Deswarte, Y.: Single-database private information retrieval schemes: Overview, performance study, and usage with statistical databases. In: Privacy in Statistical Databases, pp. 257–265 (2006)
Aguilar-Melchor, C., Gaborit, P.: A lattice-based computationally-efficient private information retrieval protocol. In: WEWORC (2007)
Damgard, I., Jurik, M.: A length-flexible threshold cryptosystem with applications. In: Australasian Conference on Information Security and Privacy (2007)
Bae, H.: Design and analysis for log-squared and log private information retrieval (2008)
Melchor, C., Crespin, B., Gaborit, P., Jolivet, V.: High-speed private information retrieval computation on GPU. In: IEEE SECURWARE (2008)
Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game. In: STOC, pp. 218–229 (1987)
Canetti, R.: Security and composition of multiparty cryptographic protocols. Journal of Cryptology 13(1), 143–202 (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Blanton, M., Aliasgari, M. (2010). Secure Outsourcing of DNA Searching via Finite Automata. In: Foresti, S., Jajodia, S. (eds) Data and Applications Security and Privacy XXIV. DBSec 2010. Lecture Notes in Computer Science, vol 6166. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-13739-6_4
Download citation
DOI: https://doi.org/10.1007/978-3-642-13739-6_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-13738-9
Online ISBN: 978-3-642-13739-6
eBook Packages: Computer ScienceComputer Science (R0)