2010 | OriginalPaper | Buchkapitel
Computationally Secure Pattern Matching in the Presence of Malicious Adversaries
verfasst von : Carmit Hazay, Tomas Toft
Erschienen in: Advances in Cryptology - ASIACRYPT 2010
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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).