Fair Games Against an All-Powerful Adversary.
Rafail Ostrovsky, Ramarathnam Venkatesan and Moti Yung.
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 infinitely-powerful 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 information-theoretic security to one player. We believe that the interactive-hashing is a technique of independent interest.
comment: This work was presented at DIMACS Complexity and Cryptography Workshop, October 1990, Princeton, NJ; Extended abstract in proceedings of Sequences II, June 1991, Positano, Italy, R.M. Capocelli, A. De-Santis and U. Vaccaro (Eds.), Springer-Verlag; Journal version in AMS DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol 13. (Jin-Yi Cai ed.) pp. 155-169, 1991.
Fetch PostScript file of the paper Fetch PDF file of the paper
| Back to Publications List |