On Hiding Information from an Oracle

New Image

We consider the problem of computing with encrypted data. Our scenario involves two players A and B. A wishes to know the value f (x) for some x, but she lacks the power to compute it. B has the power to compute f and is willing to send f(y) to A if she sends him y, for any y. A would like to learn the value of f(x) without revealing any more than she must about x. Informally, we say that the problem f is encryptable if A, using her inferior resources, can transform the cleartext instance x into an encrypted instance y, obtain f(y) from B, and infer f(x) from f(y) in such a way that B cannot infer x from y.