Secure Wavelet Matrix: Alphabet-Friendly Privacy-Preserving String Search

Abstract

MotivationPrivacy-preserving substring matching is an important task for sensitive biological/biomedical sequence database searches. It enables a user to obtain only a substring match while his/her query is concealed to a server. The previous approach for this task is based on a linear-time algorithm in terms of alphabet size |{Sigma}|. Therefore, a more efficient method is needed to deal with strings with large alphabet size such as a protein sequence, time-series data, and a clinical document.\n\nResultsWe 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 an order of magnitude faster than that of the previous method. We also tested the sWM on all sequences of one protein family in Pfam (9,826 residues in total) and clinical texts written in a natural language (77,712 letters in total). By using a laptop computer for the user and a desktop PC for the server, we found that its run time was {approx} 2.5 s (user) and {approx} 6.7 s (server) for the protein sequences and {approx} 10 s (user) and {approx} 60 s (server) for the clinical texts.\n\nAvailabilityhttps://github.com/cBioLab/sWM