Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Private Stream Search at Almost the Same Communication Cost as a Regular Search
verfasst von : Matthieu Finiasz, Kannan Ramchandran
Erschienen in: Selected Areas in Cryptography
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
Private Stream Search allows keyword-based search queries to be performed on streaming data (or on a database) without revealing any information about the keywords being searched. Using homomorphic encryption, Ostrovsky and Skeith proposed a solution to this problem in 2005. However, their solution requires the server to send an answer of size
O
(
mS
log
m
) bits when
m
documents of
S
bits match the query, while a regular (non-private) query only requires
mS
bits. Following this work, some improved schemes have been proposed with the aim of keeping the reply from the server
linear
in
mS
. In this work we propose two new
communication optimal
constructions: both allow communication linear in
mS
, but they also offer an expansion factor (compared to a non-private query) asymptotically equal to 1 when
m
and
S
increase. More precisely, our first scheme requires
m
(
S
+
O
(log
t
)) bits (where
t
is the size of the database) and our second scheme
m
(
S
+
C
) where
C
is a constant depending only on the chosen computational security level.