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.