Entry Bethencourt:2009:NTP from tissec.bib

Last update: Sun Oct 15 02:58:48 MDT 2017                Valid HTML 3.2!

Index sections

Top | Symbols | Numbers | Math | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

BibTeX entry

@Article{Bethencourt:2009:NTP,
  author =       "John Bethencourt and Dawn Song and Brent Waters",
  title =        "New Techniques for Private Stream Searching",
  journal =      j-TISSEC,
  volume =       "12",
  number =       "3",
  pages =        "16:1--16:??",
  month =        jan,
  year =         "2009",
  CODEN =        "ATISBQ",
  DOI =          "https://doi.org/10.1145/1455526.1455529",
  ISSN =         "1094-9224 (print), 1557-7406 (electronic)",
  ISSN-L =       "1094-9224",
  bibdate =      "Mon Feb 2 18:03:37 MST 2009",
  bibsource =    "http://portal.acm.org/;
                 http://www.math.utah.edu/pub/tex/bib/tissec.bib",
  abstract =     "A system for private stream searching, introduced by
                 Ostrovsky and Skeith, allows a client to provide an
                 untrusted server with an encrypted search query. The
                 server uses the query on a stream of documents and
                 returns the matching documents to the client while
                 learning nothing about the nature of the query. We
                 present a new scheme for conducting private keyword
                 search on streaming data which requires $O(m)$ server
                 to client communication complexity to return the
                 content of the matching documents, where $m$ is an
                 upper bound on the size of the documents. The required
                 storage on the server conducting the search is also
                 $O(m)$. The previous best scheme for private stream
                 searching was shown to have $O(m \log m)$ communication
                 and storage complexity. Our solution employs a novel
                 construction in which the user reconstructs the
                 matching files by solving a system of linear equations.
                 This allows the matching documents to be stored in a
                 compact buffer rather than relying on redundancies to
                 avoid collisions in the storage buffer as in previous
                 work. This technique requires a small amount of
                 metadata to be returned in addition to the documents;
                 for this the original scheme of Ostrovsky and Skeith
                 may be employed with $O(m \log m)$ communication and
                 storage complexity. We also present an alternative
                 method for returning the necessary metadata based on a
                 unique encrypted Bloom filter construction. This method
                 requires $O(m \log(t / m))$ communication and storage
                 complexity, where $t$ is the number of documents in the
                 stream. In this article we describe our scheme, prove
                 it secure, analyze its asymptotic performance, and
                 describe a number of extensions. We also provide an
                 experimental analysis of its scalability in practice.
                 Specifically, we consider its performance in the
                 demanding scenario of providing a privacy preserving
                 version of the Google News Alerts service.",
  acknowledgement = ack-nhfb,
  articleno =    "16",
  fjournal =     "ACM Transactions on Information and System Security",
  journal-URL =  "http://portal.acm.org/browse_dl.cfm?idx=J789",
  keywords =     "Bloom filter; private information retrieval; private
                 stream searching; public key program obfuscation",
}

Related entries