Secure text processing with applications to private DNA matching

TitleSecure text processing with applications to private DNA matching
Publication TypeConference Papers
Year of Publication2010
AuthorsKatz J, Malka L
Conference NameProceedings of the 17th ACM conference on Computer and communications security
Date Published2010///
Conference LocationNew York, NY, USA
ISBN Number978-1-4503-0245-6
KeywordsCOMPUTATION, secure

Motivated by the problem of private DNA matching, we consider the design of efficient protocols for secure text processing. Here, informally, a party P1 holds a text T and a party P2 holds a pattern p and some additional information y, and P2 wants to learn {f(T,j,y)} for all locations j where p is found as a substring in T. (In particular, this generalizes the basic pattern matching problem.) We aim for protocols with full security against a malicious P2 that also preserve privacy against a malicious P1 (i.e., one-sided security). We show how to modify Yao's garbled circuit approach to obtain a protocol where the size of the garbled circuit is linear in the number of occurrences of p in T (rather than linear in $|T|$). Along the way we show a new keyword search protocol that may be of independent interest.