Impossibility of Unconditionally Secure Scalar Products

Pedersen, Thomas Brochmann and Savaş, Erkay (2008) Impossibility of Unconditionally Secure Scalar Products. (Submitted)

WarningThere is a more recent version of this item available.

PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader


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.

Item Type:Article
Subjects:Q Science > QA Mathematics > QA075 Electronic computers. Computer science
ID Code:10195
Deposited By:Erkay Savaş
Deposited On:07 Nov 2008 16:06
Last Modified:27 Nov 2009 00:11

Available Versions of this Item

Repository Staff Only: item control page