Impossibility of Unconditionally Secure Scalar Products
Pedersen, Thomas Brochmann and Savaş, Erkay (2008) Impossibility of Unconditionally Secure Scalar Products. (Submitted)
The ability to perform scalar products of two vectors, each known to a different party, is a central problem in privacy preserving data mining and other multi party computation problems. Ongoing search for both efficient and secure scalar product protocols has revealed that this task is not easy. In this paper we show that, indeed, scalar products can never be made secure in the information theoretical sense. We show that any attempt to make unconditionally secure scalar products will always allow one of the parties to learn the other parties input vector with high probability. On the other hand, we show that under various assumptions, such as the existence of a trusted third party, both efficient and secure scalar products do exist.
Available Versions of this Item
Repository Staff Only: item control page