secure text processing with applications to private dna matching
Motivated by the problem of private DNA matching, we consider the design of efficient protocols for secure text processing. Here, informally, a party P 1 holds a text T and a party P 2 holds a pattern p and some additional information y, and P 2 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 P 2 that also preserve privacy against a malicious P 1 (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.
secure computation