Advertisement
Published in:
2010 | OriginalPaper | Chapter
Computationally Secure Pattern Matching in the Presence of Malicious Adversaries
Authors : Carmit Hazay, Tomas Toft
Published in: Advances in Cryptology - ASIACRYPT 2010
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We propose a dedicated protocol for the highly motivated problem of secure two-party pattern matching: Alice holds a text
t
∈ {0,1}*. of length
n
, while Bob has a pattern
p
∈ {0,1}*. of length
m
. The goal is for Bob to learn where his pattern occurs in Alice’s text. Our construction guarantees full simulation in the presence of malicious, polynomial-time adversaries (assuming that ElGamal encryption is semantically secure) and exhibits computation and communication costs of
O
(
n
+
m
) in a constant round complexity.
In addition to the above, we propose a collection of protocols for variations of the secure pattern matching problem: The pattern may contain wildcards (
O
(
nm
) communication in
O
(1) rounds). The matches may be approximated, i.e., Hamming distance less than some threshold ((
O
(
nm
) communication in
O
(1) rounds). The length,
m
, of Bob’s pattern is secret (
O
(
nm
) communication in
O
(1) rounds). The length,
n
, of Alice’s text is secret (
O
(
n
+
m
) communication in
O
(1) rounds).