×

DNA-inspired information concealing: a survey. (English) Zbl 1302.68111

Summary: Various research efforts would benefit from the ability to exchange and share information (traces with packet payloads, or other detailed system logs) to enable more data-driven research. Protection of the sensitive content is crucial for extensive information sharing. We present results of [the authors, “DNA-inspired information concealing”, Preprint, arXiv:0904.4449] and J. Blamey and the authors [“DNA self-concealing by repeats”, Preprint] about a technique of information concealing, based on introduction and maintenance of families of repeats. The structure of repeats in DNA constitutes an important obstacle for its reconstruction by hybridisation. A large proportion of eukaryotic genomes is composed of DNA segments that are repeated either precisely or in variant form more than once. As yet, no function has been associated with many of the repeats. In the paper by Blamey et al. [loc. cit.], the authors propose that in eukaryotes the cells have DNA as a depositary of concealed genetic information and the genome achieves the self-concealing by accumulation and maintenance of repeats. The protected information may be shared and this is useful for the development of intercellular communication and in the development of multicellular organisms. The results presented here are protected by Czech patent number 301799 and by US Patent Application number 12/670.

MSC:

68P25 Data encryption (aspects in computer science)
68W32 Algorithms on strings
92D20 Protein sequences, DNA sequences
68Q25 Analysis of algorithms and problem complexity
68M11 Internet topics
68-02 Research exposition (monographs, survey articles) pertaining to computer science

Software:

Autograph
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] R. Ramaswamy, L. Kencl, G. Iannaccone, Approximate fingerprinting to accelerate pattern matching, in: Proceedings of the ACM Internet Measurement Conference, IMC, Rio de Janeiro, Brazil, 2006.; R. Ramaswamy, L. Kencl, G. Iannaccone, Approximate fingerprinting to accelerate pattern matching, in: Proceedings of the ACM Internet Measurement Conference, IMC, Rio de Janeiro, Brazil, 2006.
[2] H.-A. Kim, B. Karp, Autograph: toward automated, distributed worm signature detection, in: Proceedings of the 13th Usenix Security Symposium, Security 2004, San Diego, CA, August 2004.; H.-A. Kim, B. Karp, Autograph: toward automated, distributed worm signature detection, in: Proceedings of the 13th Usenix Security Symposium, Security 2004, San Diego, CA, August 2004.
[3] S. Singh, C. Estan, G. Varghese, S. Savage, Automated worm fingerprinting, in: Proceedings of the ACM/USENIX Symposium on Operating System Design and Implementation, OSDI, San Francisco, CA, USA, 2004.; S. Singh, C. Estan, G. Varghese, S. Savage, Automated worm fingerprinting, in: Proceedings of the ACM/USENIX Symposium on Operating System Design and Implementation, OSDI, San Francisco, CA, USA, 2004.
[4] J. Blamey, L. Kencl, M. Loebl, DNA self-concealing by repeats (2009) (in preparation).; J. Blamey, L. Kencl, M. Loebl, DNA self-concealing by repeats (2009) (in preparation).
[5] Benenson, Y.; Adar, R.; Paz-Elizur, T., Proceedings of the National Academy of Sciences, 100, 5, 2191-2196 (2003)
[6] R. Guy-Franck, F. Paques, EMBO Reports 1, 2000, pp. 122-126.; R. Guy-Franck, F. Paques, EMBO Reports 1, 2000, pp. 122-126.
[7] Pevzner, P. A., Computational Molecular Biology: An Algorithmic Approach (2000), The MIT Press: The MIT Press Cambridge, Massachusetts, London, England · Zbl 0972.92011
[8] Arratia, R.; Bollobas, B.; Coppersmith, D.; Sorkin, G. B., Euler circuits and DNA sequencing by hybridization, Discrete Applied Mathematics, 104, 63-96 (2000) · Zbl 0997.92014
[9] Singer, M.; Berg, P., Genes and Genomes (1991), University Science Books Sausalito: University Science Books Sausalito California
[10] Mirkin, S., Expandable DNA repeats and human disease, Nature, 447, 932-940 (2007)
[11] Buard, J.; Jeffreys, A. J., Big, bad minisatellites, Nature Genetics, 5 (1997)
[12] Stead, J. D.H.; Jeffreys, A. J., Allele diversity and germline mutation at the insullin minisatellite, Human Molecular Genetics, 9, 713-723 (2000)
[13] Mirkin, S., Molecular models for repeat expansions, Chemtracts Biochemistry and Molecular Biology, 17, 639-662 (2004)
[14] Pearson, C. E.; Nichol Edamura, K.; Cleary, J. D., Repeat instability: mechanisms of dynamic mutations, Nature Reviews Genetics, 6, 729-742 (2005)
[15] Ranum, L. P.; Cooper, T. A., RNA-mediated neuromuscular disorders, Annual Review of Neuroscience, 29, 259-277 (2006)
[16] Abu-Baker, A.; Rouleau, G. A., (Wells, R. D.; Ashizawa, T., Genetic Instabilities and Neurological Diseases (2006), Elsevier: Elsevier Amsterdam), 487-513
[17] J. Xu, J. Fan, M.H. Ammar, S.B. Moon, Prefix-preserving IP address anonymization: measurement-based security evaluation and a new cryptography-based scheme, in: Proceedings of the IEEE International Conference on Network Protocols, ICNP, 2002.; J. Xu, J. Fan, M.H. Ammar, S.B. Moon, Prefix-preserving IP address anonymization: measurement-based security evaluation and a new cryptography-based scheme, in: Proceedings of the IEEE International Conference on Network Protocols, ICNP, 2002. · Zbl 1071.68527
[18] D. Maltz, J. Zhan, G. Xie, H. Zhang, G. Hjalmtysson, J. Rexford, A. Greenberg, Structure preserving anonymization of router configuration data, in: Proceedings of the ACM Internet Measurement Conference, IMC, Taormina, Italy, 2004.; D. Maltz, J. Zhan, G. Xie, H. Zhang, G. Hjalmtysson, J. Rexford, A. Greenberg, Structure preserving anonymization of router configuration data, in: Proceedings of the ACM Internet Measurement Conference, IMC, Taormina, Italy, 2004.
[19] R. Pang, V. Paxson, A high-level programming environment for packet trace anonymization and transformation, in: Proceedings of ACM SIGCOMM, 2003.; R. Pang, V. Paxson, A high-level programming environment for packet trace anonymization and transformation, in: Proceedings of ACM SIGCOMM, 2003.
[20] B. Bloom, Space/time tradeoffs in hash coding with allowable errors, in: CACM, p. 422.; B. Bloom, Space/time tradeoffs in hash coding with allowable errors, in: CACM, p. 422. · Zbl 0195.47003
[21] K. Shanmugasundaram, H. Broennimann, N. Memon, Payload attribution via hierarchical Bloom filters, in: Proceedings of the ACM Conference on Computer and Communications Security, CCS, Washington, DC, USA, October 2004.; K. Shanmugasundaram, H. Broennimann, N. Memon, Payload attribution via hierarchical Bloom filters, in: Proceedings of the ACM Conference on Computer and Communications Security, CCS, Washington, DC, USA, October 2004.
[22] Y. Li, J. Tygar, J.M. Hellerstein, Private matching, in: Proceedings of the 30th VLDB Conference, Toronto, Canada, 2004.; Y. Li, J. Tygar, J.M. Hellerstein, Private matching, in: Proceedings of the 30th VLDB Conference, Toronto, Canada, 2004.
[23] R. Agrawal, A. Evfimievski, R. Srikant, Information sharing across private databases, in: Proceedings of the ACM SIGMOD International Conference on Management of Data, San Diego, CA, USA, 2003.; R. Agrawal, A. Evfimievski, R. Srikant, Information sharing across private databases, in: Proceedings of the ACM SIGMOD International Conference on Management of Data, San Diego, CA, USA, 2003.
[24] S. Garriss, M. Kaminsky, M.J. Freedman, B. Karp, D. Mazires, H. Yu, Re: Reliable email, in: Proceedings of the Symposium on Networked Systems Design and Implementation, NSDI, San Jose, CA, USA, 2006.; S. Garriss, M. Kaminsky, M.J. Freedman, B. Karp, D. Mazires, H. Yu, Re: Reliable email, in: Proceedings of the Symposium on Networked Systems Design and Implementation, NSDI, San Jose, CA, USA, 2006.
[25] Net 2000 Ltd., Data masking whitepapers, 2005. http://www.datamasker.com/; Net 2000 Ltd., Data masking whitepapers, 2005. http://www.datamasker.com/
[26] G. Miklau, D. Suciu, A formal analysis of information disclosure in data exchange, in: Proc. of ACM SIGMOD Intl. Conf. on Management of Data, 2006.; G. Miklau, D. Suciu, A formal analysis of information disclosure in data exchange, in: Proc. of ACM SIGMOD Intl. Conf. on Management of Data, 2006. · Zbl 1115.68067
[27] R. Agrawal, R. Srikant, Privacy-preserving data mining, in: Proc. of ACM SIGMOD Intl. Conf. on Management of Data, 2000.; R. Agrawal, R. Srikant, Privacy-preserving data mining, in: Proc. of ACM SIGMOD Intl. Conf. on Management of Data, 2000.
[28] S. Agrawal, J.R. Haritsa, A framework for high-accuracy privacy-rpreserving mining, in: Proceedings of the 21st International Conference on Data Engineering ICDE, 2005.; S. Agrawal, J.R. Haritsa, A framework for high-accuracy privacy-rpreserving mining, in: Proceedings of the 21st International Conference on Data Engineering ICDE, 2005.
[29] A. Evfimievski, J. Gehrke, R. Srikant, Limiting privacy breaches in privacy preserving data mining, in: Proc. of ACM Symp. on Principles in Database Systems PODS, 2003.; A. Evfimievski, J. Gehrke, R. Srikant, Limiting privacy breaches in privacy preserving data mining, in: Proc. of ACM Symp. on Principles in Database Systems PODS, 2003.
[30] N. Mishra, M. Sandler, Privacy via pseudorandom sketches, in: Proc. of ACM Symp. on Principles in Database Systems PODS, 2006.; N. Mishra, M. Sandler, Privacy via pseudorandom sketches, in: Proc. of ACM Symp. on Principles in Database Systems PODS, 2006.
[31] V. Rastogi, D. Suciu, S. Hong, The boundary between privacy and utility in data publishing, in: Proc. of Intl. Conf. on Very Large Data Bases VLDB, 2007.; V. Rastogi, D. Suciu, S. Hong, The boundary between privacy and utility in data publishing, in: Proc. of Intl. Conf. on Very Large Data Bases VLDB, 2007.
[32] M. Hay, M. Miklau, G.D. Jensen, S. Weiss, et al., Anonymizing social networks, University of Massachusets, Amherst, Technical Report, 2007.; M. Hay, M. Miklau, G.D. Jensen, S. Weiss, et al., Anonymizing social networks, University of Massachusets, Amherst, Technical Report, 2007.
[33] Sweeney, L., \(k\)-anonymity: a model for protecting privacy, International Journal on Uncertainty, Fuzziness and Knowledge-Based Systems, 10, 5, 557-570 (2002) · Zbl 1085.68589
[34] Johnson, N. F.; Duric, Z.; Jajodia, S., Information Hiding: Steganography and Watermarking—Attacks and Countermeasures (2000), Springer
[35] Cox, I.; Miller, M.; Bloom, J.; Fridrich, J.; Kalker, T., (Digital Watermarking and Steganography. Digital Watermarking and Steganography, The Morgan Kaufmann Series in Multimedia Information and Systems (2007))
[36] Manning, C. D.; Raghavan, P.; Schütze, H., Introduction to Information Retrieval (2008), Cambridge University Press · Zbl 1160.68008
[37] Gentry, C., Computing arbitrary functions of encrypted data, Communications of the ACM, 53, 3, 97-105 (2010) · Zbl 1315.94074
[38] L. Kencl, J. Zamora, M. Loebl, Packet content anonymization by hiding words, in: Demo at IEEE INFOCOM, 2006.; L. Kencl, J. Zamora, M. Loebl, Packet content anonymization by hiding words, in: Demo at IEEE INFOCOM, 2006.
[39] Knuth, D. E., The Art of Computer Programming (1997), Addison-Wesley: Addison-Wesley Reading, Massachussets · Zbl 0895.68055
[40] M.R. Garrey, D.S. Johnson, Computers and intractability: a guide to the theory of NP-completeness.; M.R. Garrey, D.S. Johnson, Computers and intractability: a guide to the theory of NP-completeness.
[41] Kencl, L.; Loebl, M., DNA-inspired information concealing · Zbl 1302.68111
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.