Paper 2022/572
Homomorphically counting elements with the same property
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 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-of-concept implementation in C++ and using it to evaluate a heatmap function over encrypted geographic points.
Metadata
- Available format(s)
- Category
- Applications
- Publication info
- Published elsewhere. PETS 2022
- Keywords
- Privacy-preserving Computation Homomorphic encryption FHE Ring Learning With Errors
- Contact author(s)
-
ilia iliashenko @ kuleuven be
malika izabachene @ cosmian com
axel mertens @ kuleuven be
hilder vitor @ gmail com - History
- 2022-07-18: revised
- 2022-05-16: received
- See all versions
- Short URL
- https://ia.cr/2022/572
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/572, author = {Ilia Iliashenko and Malika Izabachène and Axel Mertens and Hilder V. L. Pereira.}, title = {Homomorphically counting elements with the same property}, howpublished = {Cryptology {ePrint} Archive, Paper 2022/572}, year = {2022}, url = {https://eprint.iacr.org/2022/572} }