| Description |
Characterization of securely computable two-party functions is one of the most fundamental problem in cryptography. For deterministic functions, a characterisation has been known since late 80's; but finding such a characterisation for {\em randomised} functions in general remains elusive since then. In this work we consider a special case, where only one party computes the output. The problem is specified by a pair $(p_{XY},p_{Z|XY})$, where $p_{XY}$ is the input distribution from which inputs $x$ and $y$ of Alice and Bob, respectively, are drawn from, and $p_{Z|XY}$ is the distribution according to which Bob produces his output $z$. Any protocol for securely computing $(p_{XY},p_{Z|XY})$ must satisfy two properties: (i) computation should be correct, and (ii) at the end of the protocol, Alice does not learn anything about Bob's input and output, and Bob does not learn anything about Alice's input.
We consider two scenarios: (i) Perfectly secure computation -- where Alice and Bob get a single pair of inputs and Bob produces the output securely, and (ii) Asymptotically secure computation -- where Alice and Bob get blocks of inputs $(x_1,x_2,\hdots,x_n)$ and $(y_1,y_2,\hdots,y_n)$, respectively, and Bob produces $(\hat{z}_1,\hat{z}_2,\hdots,\hat{z}_n)$ as his output. Asymptotic correctness means that the $L_1$-distance between the ideal output distribution and the actual output distribution goes to zero as block-length $n$ tends to infinity; and asymptotic privacy means that the information leakage goes to zero as $n$ tends to infinity. In perfect security setting we give a characterization of securely computable {\em randomized} functions and prove matching lower and upper bounds on communication complexity for such functions. We prove that the same characterization holds in asymptotic security setting as well and prove matching lower and upper bounds on communication complexity for such functions.
|