Completeness Theorems With Constructive Proofs for Finite Deterministic 2-Party Functions (full Version)

Date Added: Apr 2011
Format: PDF

In this paper the authors present simple but comprehensive combinatorial criteria for completeness of finite deterministic 2-party functions with respect to information-theoretic security. They give a general protocol construction for efficient and statistically secure reduction of oblivious transfer to any finite deterministic 2-party function that fulfills the criteria. For the resulting protocols they prove universal composability. The results are tight in the sense that the criteria still are necessary for any finite deterministic 2-party function to allow for implementation of oblivious transfer with statistical privacy and correctness.