Constant-Round Oblivious Transfer in the Bounded Storage Model

摘要

Our techniques utilize explicit constructions from the theory of derandomization. In particular, we achieve the constant round complexity of our oblivious transfer protocol by constructing a novel four-message protocol for Interactive Hashing, in place of the well-known protocol by Naor et al. (known as the NOVY protocol) which involves many rounds of interaction. Our four-message interactive hashing protocol is constructed by use of t-wise independent permutations and may be of independent interest. For achieving constant-round complexity we also construct a new subset encoding scheme that is dense; namely, guarantees that almost every string in the image of the encoding function has a preimage. Other tools we employ include randomness extractors and averaging samplers.