Date Added: Sep 2012
Consider a setting of two mutually distrustful parties Alice and Bob who want to securely evaluate some function on pre-specified inputs. The well studied notion of two-party secure computation allows them to do so in the stand-alone setting. Consider a deterministic function (e.g., 1-out-of-2 bit OT) that Alice and Bob cannot evaluate trivially and which allows only Bob to receive the output. The authors show that Alice and Bob cannot securely compute any such function in the concurrent setting even when their inputs are pre-specified. Their impossibility result also extends to all deterministic functions in which both Alice and Bob get the same output. Their results have implications in the bounded-concurrent setting as well.