Communication and query privacy: Intrusion-Resilient Secure Channels and private database queries

This dissertation consists of two parts. The first part considers the problem of two-party communication in the presence of a passive eavesdropper. We describe a new communication primitive called an Intrusion-Resilient Secure Channel (IRC) that offers improved confidentiality over traditional secure channels against passive but mobile, highly adaptive adversaries. IRCs limit the loss of confidentiality resulting from the exposure of parties' secret keys by utilizing key-evolution and proactive security techniques similar to those employed in intrusion-resilient signature schemes. We show how to construct an IRC using existing chosen-ciphertext-secure public-key cryptosystems in a black-box manner. We also show how to use IRCs to improve two-party protocol security. As a concrete example, we prove an IRC-augmented version of the Itkis-Reyzin intrusion-resilient signature scheme secure against highly adaptive adversaries capable of exposing even expired secrets.; The second part of this dissertation considers the privacy of a user's queries to a server-hosted database. User privacy means the server learns nothing about the user's query or its result. Server privacy means the user learns nothing about the server's database beyond the correct query answer. We describe an interactive binary search protocol with both user and server privacy that improves upon an existing user-private only protocol. We use our search protocol to construct user- and server-private protocols for predecessor, successor, and simple range queries on one-dimensional data. We also describe a user- and server-private protocol for multi-way search, a generalization of binary search, and how to modify the other protocols to utilize it. All of these protocols are secure in the standard model without setup assumptions against semi-honest parties who correctly follow the protocol but attempt to break its privacy. To facilitate the efficient retrieval of range query results, we also provide a communication-optimized user- and server-private protocol for retrieving a contiguous range of elements of known size by position. This protocol generalizes existing notions of block oblivious transfer and is secure against semi-honest servers and malicious users who deviate arbitrarily from the protocol.