Kernel Density Estimation on Homomorphically Encrypted Data

I propose a method for univariate Kernel Density Estimation (KDE), for bounded support probability density functions, on Homomorphically Encrypted (HE) data. The estimator, called HE-KDE, facilitates outsourcing nonparametric density estimation to a semi-honest cloud without exposing the non-encrypted data. HE-KDE locally approximates a kernel function with a polynomial. In contrast to kernels typically used for non-encrypted KDE, the polynomial can be natively evaluated on ring-homomorphically encrypted data.

The density estimator is non-negative, and its integral is bounded by one. However, it is defective as it need not integrate to one. There is a trade-off between minimising the Mean Integrated Square Error (MISE) of the estimator and maximising encryption security. A polynomial balancing these two goals is designed. Asymptotically, it ensures that the MISE converges to zero, and provides encryption security.

Applications on simulated data are presented, using Homomorphic Encryption for Arithmetic of Approximate Numbers (HEAAN, Cheon et al. (2017)).