Paper 2022/572

Homomorphically counting elements with the same property

Ilia Iliashenko
Malika Izabachène
Axel Mertens
Hilder V. L. Pereira.
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)
PDF
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.