Impossibility of unconditionally secure scalar products

Pedersen, Thomas Brochmann and Savaş, Erkay (2009) Impossibility of unconditionally secure scalar products. Data and Knowledge Engineering, 68 (10). pp. 1059-1070. ISSN 0169-023X

This is the latest version of this item.

PDF (This is a RoMEO green publisher -- author can archive pre-print (ie pre-refereeing) and post-print (ie final draft post-refereeing) ; author cannot archive publisher's version/PDF) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: http://dx.doi.org/10.1016/j.datak.2009.04.006


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 inevitably 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 or the difficulty of discrete logarithms, both efficient and secure scalar products do exist. We proposed two new protocols for secure scalar products and compare their performance with existing secure scalar products.

Item Type:Article
Uncontrolled Keywords:Security and privacy; Data mining; Scalar products
Subjects:Q Science > QA Mathematics > QA075 Electronic computers. Computer science
ID Code:12981
Deposited By:Erkay Savaş
Deposited On:27 Nov 2009 00:11
Last Modified:24 Jul 2019 09:48

Available Versions of this Item

Repository Staff Only: item control page