期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2003
卷号：2003
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Secure computation is one of the most fundamental cryptographic tasks. It is known that all functions can be computed securely in the information theoretic setting, given access to a black box for some complete function such as AND. However, without such a black box, not all functions can be securely computed. This gives rise to two types of functions, those that can be computed without a black box (``easy'') and those that cannot (``hard''). However, no further distinction among the hard functions is made. In this paper, we take a quantitative approach, associating with each function f the minimal number of calls to the black box that are required for securely computing f. This approach leads to a better understanding of the inherent complexity for securely computing a given function f. Furthermore, minimizing the number of calls to the black-box can lead to more efficient protocols when the calls to the black-box are replaced by a secure protocol. We take a first step in this study, by considering the two-party, honest-but-curious, information-theoretic case. For this setting, we provide a complete characterization for deterministic protocols. We explore the hierarchy for randomized protocols as well, comparing it to the deterministic hierarchy. We show that for every Boolean function the largest gap between randomized and deterministic protocols is at most exponential, and there are functions which exhibit such a gap.
