Databases Reference
In-Depth Information
•
Malicious Adversaries:
In this case, Alice and Bob may vary from the
protocol, and may send sophisticated inputs to one another to learn from
the information received from each other.
A key building-block for many kinds of secure function evaluations is the
1 out of 2 oblivious-transfer protocol. This protocol was proposed in [42, 93]
and involves two parties: a
sender
, and a
receiver
. The sender's input is a pair
(
x
0
,x
1
), and the receiver's input is a bit value
σ
. At the end of the
process, the receiver learns
x
σ
only, and the sender learns nothing. A number
of simple solutions can be designed for this task. In one solution [42, 49], the
receiver generates two random public keys,
K
0
and
K
1
, but the receiver knows
only the decryption key for
K
σ
. The receiver sends these keys to the sender,
who encrypts
x
0
with
K
0
,
x
1
with
K
1
, and sends the encrypted data back
to the receiver. At this point, the receiver can only decrypt
x
σ
, since this is
the only input for which they have the decryption key. We note that this is
a semi-honest solution, since the intermediate steps require an assumption of
trust. For example, it is assumed that when the receiver sends two keys to the
sender, they indeed know the decryption key to only one of them. In order to
deal with the case of malicious adversaries, one must ensure that the sender
chooses the public keys according to the protocol. An ecient method for
doing so is described in [85]. In [85], generalizations of the 1 out of 2 oblivious
transfer protocol to the 1 out
N
case and
k
out of
N
case are described.
Since the oblivious transfer protocol is used as a building block for secure
multi-party computation, it may be repeated many times over a given func-
tion evaluation. Therefore, the computational effectiveness of the approach is
important. Ecient methods for both semi-honest and malicious adversaries
are discussed in [85]. More complex problems in this domain include the com-
putation of probabilistic functions over a number of multi-party inputs [118].
Such powerful techniques can be used in order to abstract out the primitives
from a number of computationally intensive data mining problems. Many of
the above techniques have been described for the 2-party case, though generic
solutions also exist for the multiparty case. Some important solutions for the
multiparty case may be found in [22].
The oblivious transfer protocol can be used in order to compute several
data mining primitives related to vector distances in multi-dimensional space.
A classic problem which is often used as a primitive for many other prob-
lems is that of computing the scalar dot-product in a distributed environment
[54]. A fairly general set of methods in this direction are described in [36].
Many of these techniques work by sending changed or encrypted versions of
the inputs to one another in order to compute the function with the differ-
ent alternative versions followed by an oblivious transfer protocol to retrieve
the correct value of the final output. A systematic framework is described in
[36] to transform normal data mining problems to secure multi-party compu-
tation problems. The problems discussed in [36] include those of clustering,
classification, association rule mining, data summarization, and generaliza-
∈{
0
,
1
}
