@conference {15138, title = {Secure text processing with applications to private DNA matching}, booktitle = {Proceedings of the 17th ACM conference on Computer and communications security}, series = {CCS {\textquoteright}10}, year = {2010}, month = {2010///}, pages = {485 - 492}, publisher = {ACM}, organization = {ACM}, address = {New York, NY, USA}, abstract = {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{\textquoteright}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.}, keywords = {COMPUTATION, secure}, isbn = {978-1-4503-0245-6}, doi = {10.1145/1866307.1866361}, url = {http://doi.acm.org/10.1145/1866307.1866361}, author = {Katz, Jonathan and Malka,Lior} }