Homomorphically counting elements with the same property
Authors: Ilia Iliashenko (Ciphermode Labs), Malika Izabachène (Cosmian), Axel Mertens (imec-COSIC - KU Leuven), Hilder V. L. Pereira (imec-COSIC - KU Leuven)
Volume: 2022
Issue: 4
Pages: 670–683
DOI: https://doi.org/10.56553/popets-2022-0127
Abstract: We propose homomorphic algorithms for privacy-preserving applications where we are given an encrypted dataset and we want to compute the number of elements that share a common property. We consider a two party scenario between a client and a server, where the storage and computation is outsourced to the server. We present two new efficient methods to solve this problem by homomorphically evaluating a selection function encoding the desired property, and counting the number of elements which evaluates to the same value. Our first method programs the homomorphic computation in the style of the the functional bootstrapping of TFHE and can be instantiated with essentially any homomorphic encryption scheme that operates on polynomials, like FV or BGV. Our second method relies on new homomorphic operations and ciphertext formats, and it is more suitable for applications where the number of possible inputs is much larger than the number of possible values for the property. We illustrate the feasibility of our methods by presenting a publicly available proof-ofconcept implementation in C++ and using it to evaluate a heatmap function over encrypted geographic points.
Keywords: Privacy-preserving Computation, Homomorphic encryption, Ring Learning With Errors
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 license.
