|
Abstract : |
Suppose that a weak (polynomial time) device needs to interact over a clear channel with a strong (infinitely-powerful) and untrustworthy adversarial device. Assuming the existence of one-way functions, during this interaction (game) the infinitelypowerful device can encrypt and (computationally) hide information from the weak device. However, to keep the game fair, the weak player must hide information from the infinitely-powerful player in the information-theoretic sense. Clearly, encryption in this case is useless, and other means must be used. In this paper, we show that under a general complexity assumption, this task is always possible to achieve. That is, we show that the weak player can play any polynomial length partial-information game (or secure protocol) with the strong player using any one-way function; we achieve this by implementing oblivious transfer protocol in this model. We also establish related impossibility results concerning oblivious transfer. In the proof of our main result, we present an interactive-hashing technique which forces a polynomial-time player to choose two inputs in the range of a one-way function, one of which it cannot invert, while perfectly concealing which input is that one. This technique allows us to reduce the complexity assumptions and to simplify the cryptographic primitive of general secure computation protocols with informationtheoretic security to one player. We believe that the interactive-hashing is a technique of independent interest., |
