Information-Theoretic Interactive Hashing and Oblivious Transfer to a Storage-Bounded Receiver

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\cdot 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.

I. Introduction

Interactive Hashing (IH) is a cryptographic primitive that allows a sender (Alice) to transmit a bit string to a receiver (Bob) who receives two output strings, labeled according to lexicographic order. The primitive guarantees that one of the two outputs is equal to the original input. The other string is guaranteed to be effectively random, in the sense that it is chosen beyond Alice’s control, even if she acts dishonestly. On the other hand, provided that from Bob’s point of view are equiprobable inputs for Alice, the primitive guarantees that Bob cannot guess which of the two was the original input with probability greater than 1/2. We remark that typically both outputs are also available to Alice. See Figure 1. Fig. 1.

Interactive Hashing: Alice sends string to Bob, who receives two strings , labeled according to lexicographic order. One of the two (in our example, ) is equal to the input string while the other is effectively randomly chosen. Bob cannot distinguish which of the two was the input.