Abstract
Dot-products form the basis of various applications ranging from
scientific computations to commercial applications in data mining and transaction
processing. Typical scientific computations utilizing sparse iterative solvers
use repeated matrix-vector products. These can be viewed as dot-products of
sparse vectors. In database applications, dot-products take the form of
counting operations. With widespread use of clustered and distributed
platforms, these operations are increasingly being performed across networked
hosts. Traditional APIs for messaging are susceptible to sniffing, and
the data being transferred between hosts is often enough to compromise the
entire computation. For example, in a domain decomposition based sparse solver,
the entire solution can often be reconstructed easily from boundary values
that are communicated on the net. In yet other applications, dot-products
may be performed across two hosts that do not want to disclose their vectors,
yet, they need to compute the dot-product. In each of these cases, there is
a need for secure and anonymous dot-product protocols. Due to the large
computational requirements of underlying applications, it is highly desirable
that secure protocols add minimal overhead to the original algorithm. Finally,
by its very nature, dot-products leak limited amounts of information -- one
of the parties can detect an entry of the other party's vector by simply probing
it with a vector with a 1 in a particular location and zeros elsewhere. Given
all of these constraints, traditional cryptographic protocols are generally
unsuitable due to their significant computational and communication overheads.
In this paper, we present an extremely efficient and sufficiently
secure protocol for computing the dot-product of two vectors using
linear algebraic techniques. Using analytical as well as experimental
results, we demonstrate superior performance in terms of computational
overhead, numerical stability, and security. We show that the overhead of
a two-party dot-product computation using MPI as the messaging API across
two high-end workstations connected via a Gigabit ethernet approaches multiple
4.69 over an un-secured dot-product. We also show that the average relative error
in dot-products across a large number of random (normalized) vectors was roughly
$4.5 \times 10^{-9}$.
