We present a privacy-assured multiplication protocol using which an arbitrary arithmetic formula with inputs from two parties over a finite field can be jointly computed on encrypted data using an additively homomorphic encryption scheme. Our protocol is secure against malicious adversaries. To motivate and illustrate applications of this technique, we demonstrate an attack on a class of known protocols showing how to compromise location privacy of honest users by manipulating messages in protocols with additively homomorphic encryption. We demonstrate how to apply the technique in order to solve different problems in geometric applications. We evaluate our approach using a prototypical implementation. The results show that the added overhead of our approach is small compared to insecure outsourced multiplication.

In a network of$n$nodes (modeled as a digraph), the goal of a perfectly secret message transmission (PSMT) protocol is to replicate sender’s message$m$at the receiver’s end without revealing any information about$m$to a computationally unbounded adversary that eavesdrops on any$t$nodes. The adversary may be mobile too that is, it may eavesdrop on a different set of$t$nodes in different rounds. We prove a necessary and sufficient condition on the synchronous network for the existence of$r$-roundPSMTprotocols, for any given$r > 0$; further, we show that round-optimality is achieved without trading-off the communication complexity; specifically, our protocols have an overall communication complexity of$O(n)$elements of a finite field to perfectly transmit one field element. Apart from optimality/scalability, two interesting implications of our results are: 1)adversarial mobility does not affect its tolerability:PSMTtolerating a static$t$-adversary is possibleif and only ifPSMTtolerating mobile$t$-adversary is possible; and 2)mobility does not affect the round optimality:the fastestPSMTprotocol tolerating a static$t$-adversary isnot fasterthan the one tolerating a mobile$t$-adversary.