Interactive hashing has featured as an essential ingredient in protocols realizing a large variety of cryptographic tasks, notably oblivious transfer in the bounded storage model. In interactive hashing, a sender transfers a bit string to a receiver such that two strings are received, the original string and a second string that appear to be chosen at random. This paper presents a self-contained, information theoretic study of interactive hashing. We start by formalizing the notion of interactive hashing as a cryptographic primitive, disentangling it from the specifics of its various implementations. To this end, we present an application-independent set of information theoretic conditions that all interactive hashing protocols must ideally satisfy. We then provide a detailed analysis of a standard implementation of interactive hashing which is shown to satisfy all the conditions of our definition. Our analysis represents a significant improvement over previous attempts in more restricted contexts. Despite its generality, it offers a considerably simpler proof of security. Moreover, it establishes a tighter upper bound on the cheating probability of a dishonest sender, who wishes to manipulate the protocol so that both output strings have some rare desirable property. In particular, we prove that if the set of desirable strings for the dishonest sender represents a fraction f of all strings, then the probability that both outputs will be from this set is no larger than 15.6805 · f. This upper bound is valid for any f and is tight up to a small constant, since a sender acting honestly would get two outputs from this set with probability very close to f. We illustrate the power of interactive hashing as a cryptographic tool by surveying protocols achieving oblivious transfer in the bounded storage model, which typically rely heavily on interactive hashing.

We present two protocols for reducing oblivious transfer (OT) to the security of trapdoor permutations and to the hardness of some coding problems, respectively. The first protocol is the most efficient known to date, while the second one is a theoretical proof-of-concept. Our constructions leverage the power of Interactive Hashing (IH). The first protocol can be viewed as a simple modification of the well-known OT construction by Even, Goldreich and Lem-pel (1985), in which a receiver must send a random domain element to a sender through IH. Alternatively, our protocol can be viewed as a simple modification of the construction by Ostrovsky, Venkatesan and Yung (1993), in which the players substitute the one-way permutation with a trapdoor permutation. We use a similar approach to derive a second OT protocol based on coding assumptions related to security of the McEliece cryptosystem. In our second construction, the receiver inputs a public key into IH while privately keeping the corresponding secret key. Two different versions of IH are used: the computationally secure one in the first protocol, and the information-theoretically secure one in the second.

The challenge for user authentication in a global file system is allowing people to grant access to specific users and groups in remote administrative domains, without assuming any kind of pre-existing administrative relationship. The traditional approach to user authentication across administrative domains is for users to prove their identities through a chain of certificates. Certificates allow for general forms of delegation, but they often require more infrastructure than is necessary to support a network file system.This paper introduces an approach without certificates. Local authentication servers pre-fetch and cache remote user and group definitions from remote authentication servers. During a file access, an authentication server can establish identities for users based just on local information. This approach is particularly well-suited to file systems, and it provides a simple and intuitive interface that is similar to those found in local access control mechanisms. An implementation of the authentication server and a file server supporting access control lists demonstrate the viability of this design in the context of the Self-certifying File System (SFS). Experiments demonstrate that the authentication server can scale to groups with tens of thousands of members.