Abstract:

   Research in cryptography and security has an incredible potential for
   fruitful interaction between theory and practice. The case of
   public-key cryptography may be considered an example of a successful
   transition from theory to practice, but elsewhere, there has been less
   interaction between the fields. For instance, cryptographers have
   devised procedures for performing many seemingly impossible tasks,
   using zero-knowledge proofs and protocols for secure function
   evaluation; however none of these procedures is in every-day use.
   
   This talk describes a body of research that bridges this gap, presenting
   two results in detail. The first is a protocol involving two parties,
   each one holding a private database. The aim of the protocol is to
   compute the well-known ID3 data-mining algorithm on the union of the
   databases, correctly computing the result without revealing any other
   information about the two databases. The result is unique in showing that a
   well-known complex algorithm can be implemented in the style of theorists'
   "secure function evaluation". The protocol has sub-linear overhead, and
   can be applied to databases containing millions of transactions.
   
   The second result is a Secure Human Input Protocol (SHIP), which
   enables human users to encrypt messages (e.g. passwords) in a way that
   defeats attacks by automated eavesdropping adversaries, and requires
   no computational aids for the users. The protocol makes novel use of
   several techniques that attempt to distinguish between a human user
   and a computer program. We give precise reductions from the security
   of the protocol to that of the distinguishing techniques that are used.