International Association
for Cryptologic Research

Scott Russell
Communication and Query Privacy: Intrusion-Resilient Secure Channels and Private Database Queries
cryptographic protocols

One part of this dissertation describes a new two-party communication primitive we call 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 discuss 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.\r\n\r\n

The second part describes an interactive binary search protocol with user and server privacy provided that improves upon an existing user-private only protocol. We utilize our search protocol to construct user- and server-private protocols for predecessor, successor, and simple range queries on one-dimensional dat[...]