Secure Wavelet Matrix: Alphabet-Friendly Privacy-Preserving String Search for Bioinformatics
Open Access
- 8 March 2018
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Computational Biology and Bioinformatics
- Vol. 16 (5) , 1675-1684
Abstract
Biomedical data often includes personal information, and the technology is demanded that enables to search such a sensitive data while protecting privacy. We consider a case in which a server has a text database and a user searches the database to find substring matches. The user wants to conceal his/her query and the server wants to conceal the database except for the search results. The previous approach for this problem is based on a linear-time algorithm in terms of alphabet size $|\Sigma|$, and it cannot search on the database of large alphabet such as biomedical documents.We present a novel algorithm that can search a string in logarithmic time of $|\Sigma|$. In our algorithm, named secure wavelet matrix (sWM), we use an additively homomorphic encryption to build an efficient data structure called a wavelet matrix.In an experiment using a simulated string of length 10,000 whose alphabet size ranges from 4 to 1024, the run time of the sWM was up to around two orders of magnitude faster than that of the previous method.sWM enables to search a private database efficiently and thus it will facilitate utilizing sensitive biomedical information.
Keywords
All Related Versions
Funding Information
- Japan-Finland Cooperative Scientific Research Program of AMED
- JST PRESTO (JPMJPR14E8)
- JST CREST (JPMJCR1688)
This publication has 26 references indexed in Scilit:
- Privacy-Preserving Wildcards Pattern Matching Using Symmetric Somewhat Homomorphic Encryption2014
- Practical Fully Simulatable Oblivious Transfer with Sublinear Communication2013
- The Wavelet Matrix2012
- Efficient and Secure Generalized Pattern Matching via Fast Fourier Transform2011
- Secure Outsourcing of DNA Searching via Finite Automata2010
- Computationally Secure Pattern Matching in the Presence of Malicious Adversaries2010
- Keyword Search and Oblivious Pseudorandom Functions2005
- Public-Key Cryptosystems Based on Composite Degree Residuosity Classes1999
- A public key cryptosystem and a signature scheme based on discrete logarithmsIEEE Transactions on Information Theory, 1985
- Probabilistic encryptionJournal of Computer and System Sciences, 1984