Assuring BetterTimes

Subtitle: Private arithmetic formulas

Article type: Research Article

Authors: Hallgren, Per^a | Kishore, Ravi^b | Ochoa, Martín^{c; d; *} | Sabelfeld, Andrei^a

Affiliations: [a] Chalmers University of Technology, Gothenburg, Sweden | [b] International Institute of Information Technology, Hyderabad, India | [c] Singapore University of Technology and Design, Singapore | [d] Department of Applied Mathematics and Computer Science, Universidad del Rosario, Bogotá, Colombia

Correspondence: [*] Corresponding author. E-mail: [email protected].

Abstract: 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.

Keywords: Location privacy, privacy-enhancing technologies, secure multi-party computation

DOI: 10.3233/JCS-171085

Journal: Journal of Computer Security, vol. 26, no. 4, pp. 557-587, 2018