Secure Wavelet Matrix: Alphabet-Friendly Privacy-Preserving String Search for Bioinformatics
Secure Wavelet Matrix: Alphabet-Friendly Privacy-Preserving String Search for Bioinformatics
复制标题
DOI：
10.1109/tcbb.2018.2814039
复制
发表时间：
2019-09-01
影响因子：
4.5
通讯作者：
Shimizu, Kana
中科院分区：
文献类型：
--
作者：
Sudo, Hiroki;Jimbo, Masanobu;Shimizu, Kana
生物医学数据通常包括个人信息，需要能够在保护隐私的同时搜索此类敏感数据的技术。我们考虑这样一种情况，其中服务器具有文本数据库，并且用户搜索该数据库以查找子串匹配。用户想要隐藏他/她的查询，而服务器想要隐藏除了搜索结果之外的数据库。以前的方法是基于字母表大小为$\mathbf{|\Sigma|}$|Sigma|的线性时间算法，不能在生物医学文献等大字母数据库上进行搜索。提出了一种新的算法，该算法可以在$\mathbf{|\Sigma|}$|Sigma|的对数时间内搜索一个字符串。在我们的安全小波矩阵(SWM)算法中，我们使用加性同态加密来构建一种称为小波矩阵的高效数据结构。在使用字母表大小从4到1024的长度为10,000的模拟串的实验中，SWM的运行时间比先前方法快了大约两个数量级。SWM能够有效地搜索私有数据库，因此它将有助于利用敏感的生物医学信息。
Biomedical data often includes personal information, and the technology is demanded that enables the searching of such 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 $\mathbf{|\Sigma |}$|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 $\mathbf{|\Sigma |}$|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 the searching of a private database efficiently and thus it will facilitate utilizing sensitive biomedical information.